×

Proportional pie-cutting. (English) Zbl 1151.91011

Authors’ abstract: D. Gale [Math. Intell. 15, 48–52 (1993)] was perhaps the first to suggest that there is a difference between cake and pie cutting. A cake can be viewed as a rectangle valued along its horizontal axis, and a pie as a disk valued along its circumference. We will use vertical, parallel cuts to divide a cake into pieces, and radial cuts from the center to divide a pie into wedge-shaped pieces. We restrict our attention to allocations that use the minimal number of cuts necessary to divide cakes or pies. In extending the definition of envy-freeness to unequal entitlements, we provide a counterexample to show that a cake cannot necessarily be divided into a proportional allocation of ratio \(p :1- p\) between two players where one player receives \(p\) of the cake according to her measure and the other receives \(1 - p\) of the cake according to his measure. In contrast, for pie, we prove that an efficient, envy-free, proportional allocation exists for two players. The former can be explained in terms of the Universal Chord Theorem, whereas the latter is proved by another result on chords. We provide procedures that induce two risk-averse players to reveal their preferences truthfully to achieve proportional allocations. We demonstrate that, in general, proportional, envy-free, and efficient allocations that use a minimal number of cuts may fail to exist for more than two players.

MSC:

91A05 2-person games
Full Text: DOI

References:

[1] Barbanel JB (2005). The geometry of efficient fair division. Cambridge University Press, New York · Zbl 1071.91001
[2] Barbanel JB and Brams SJ (2004). Cake division with minimal cuts: envy-free procedures for three persons, four persons and beyond. Math Soc Sci 48: 251–269 · Zbl 1080.91017 · doi:10.1016/j.mathsocsci.2004.03.006
[3] Barbanel JB, Brams SJ, Stromquist W (2007) Cutting a pie is not a piece of cake. Preprint · Zbl 1229.91172
[4] Boas RP (1960). A primer of real functions. Mathematical Association of America, Washington, DC · Zbl 0089.03401
[5] Brams SJ and Taylor AD (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press, New York · Zbl 0991.91019
[6] Brams SJ, Jones MA and Klamler C (2006). Better ways to cut a cake. Notices Am Math Soc 53: 1314–1321 · Zbl 1142.91025
[7] Gale D (1993). Mathematical entertainments. Math Intell 15: 48–52 · Zbl 0781.01011 · doi:10.1007/BF03025257
[8] Jones MA (2002). Equitable, envy-free and efficient cake cutting for two people and its application to divisible goods. Math Mag 75: 275–283 · Zbl 1079.90592 · doi:10.2307/3219163
[9] Levy P (1934). Sur une generalisation du Théorème de Rolle. CR Acad Sci Paris 198: 424–425 · Zbl 0008.21806
[10] Robertson J and Webb W (1998). Cake-cutting algorithms: be fair if you can. AK Peters, Natick · Zbl 0939.91001
[11] Stromquist W (1980). How to cut a cake fairly. Am Math Mon 88: 640–644 · Zbl 0441.90002 · doi:10.2307/2320951
[12] Thomson W (2007). Children crying at birthday parties. Why?. Econ Theory 31: 501–521 · Zbl 1114.91034 · doi:10.1007/s00199-006-0109-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.