A near equitable 2-person cake cutting algorithm

Abstract

Let the cake be represented by the unit interval of reals, with two players having possibly different valuations. We propose a finite algorithm that produces contiguous pieces for both players such that their values differ by at most ϵ, where ϵ > 0 is a given small number. Players are not required to reveal their complete value functions, they only have to announce the bisection points of a sequence of intervals. If both utility functions are everywhere positive then the algorithm converges to the unique equitable point.

Keywords:

• cake cutting
• algorithm
• approximation

AMS Subject Classifications::

• 91B32
• 91A06

Acknowledgements

The authors thank Jana Hajduková who initiated this research and Lev Bukovský for valuable discussions. This work was supported by the VEGA grants 1/0035/09, 1/0325/10 and the APVV grant SK-HU-003-08.