Cutting a pie is not a piece of cake

Barbanel, Julius B. and Brams, Steven J. and Stromquist, Walter (2008): Cutting a pie is not a piece of cake. Forthcoming in: American Mathematical Monthly , Vol. 116, No. June/July 2009

Abstract

Is there a division among n players of a cake using n-1 parallel vertical cuts, or of a pie using n radial cuts, that is envy-free (each player thinks he or she receives a largest piece and so does not envy another player) and undominated (there is no other allocation as good for all players and better for at least one)? David Gale first asked this question for pies. We provide complete answers for both cakes and pies. The answers depend on the number of players (two versus three or more players) and whether the players' preferences satisfy certain continuity assumptions. We also give some simple algorithms for cutting a pie when there are two or more players, but these algorithms do not guarantee all the properties one might desire in a division, which makes pie-cutting harder than cake-cutting. We suggest possible applications and conclude with two open questions.

• Item Type: MPRA Paper
• Language: English
• Keywords: Fair division; cake-cutting; pie-cutting; divisible good; envy-freeness; allocative efficiency
• Subjects: D - Microeconomics > D7 - Analysis of Collective Decision-Making; D - Microeconomics > D6 - Welfare Economics; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory

References

1. J. Barbanel, The Geometry of Efficient Fair Division, Cambridge University Press, Cambridge, 2005.

2. J. Barbanel and S. Brams, Cake division with minimal cuts: Envy-free procedures for 3 persons, 4 persons, and beyond, Math. Social Sci. 48 (2004) 251-270.

3. S. Brams, M. Jones, and C. Klamler, Better ways to cut a cake, Notices Amer. Math. Soc. 35 (2006) 1314-1321.

4. ____, Proportional pie-cutting, Internat. J. of Game Theory 36 (2008) 353-367.

5. S. Brams and A. Taylor, Fair Division: From Cake-Cutting to Dispute Resolution, Cambridge University Press, New York, 1996.

6. S. Brams, A. Taylor, and W. Zwicker, Old and new moving-knife schemes, Math. Intelligencer 17 (1995) 30-35.

7. ___, A moving-knife solution to the four-person envy-free cake division problem, Proc. Amer. Math. Soc. 125 (1997) 547-554.

8. D. Gale, Mathematical entertainments, Math. Intelligencer 15 (1993) 48-52.

9. M. Jones, Equitable, envy-free, and efficient cake cutting for two people and its application to divisible goods, Math. Mag. 75 (2002) 275-283.

10. J. Robertson and W. Webb, Cake-Cutting Algorithms: Be Fair If You Can, A K Peters, Natick, MA, 1998.

11. W. Stromquist, How to cut a cake fairly, this MONTHLY 87 (1980) 640-644.

12. ____, A pie that can't be cut fairly, in Dagstuhl Seminar Proceedings 07261, Seminar on Fair Division, June 2007, available at http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=1219.

13. F. E. Su, Rental harmony: Sperner’s lemma in fair division, this MONTHLY 106 (1999) 922-934.

14. W. Thomson, Children crying at birthday parties. Why?, Econom. Theory 31 (2007) 501-521.