N-Person cake-cutting: there may be no perfect division

Brams, Steven J. and Jones, Michael A. and Klamler, Christian (2011): N-Person cake-cutting: there may be no perfect division.

Abstract

A cake is a metaphor for a heterogeneous, divisible good, such as land. A perfect division of cake is efficient (also called Pareto-optimal), envy-free, and equitable. We give an example of a cake in which it is impossible to divide it among three players such that these three properties are satisfied, however many cuts are made. It turns out that two of the three properties can be satisfied by a 3-cut and a 4-cut division, which raises the question of whether the 3-cut division, which is not efficient, or the 4-cut division, which is not envy-free, is more desirable (a 2-cut division can at best satisfy either envy-freeness or equitability but not both). We prove that no perfect division exists for an extension of the example for three or more players.

• Item Type: MPRA Paper
• Language: English
• Keywords: Cake-cutting; fair division; efficiency; envy-freeness; equitability; heterogeneous good
• Subjects: D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement; D - Microeconomics > D3 - Distribution > D30 - General; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D74 - Conflict ; Conflict Resolution ; Alliances ; Revolutions; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games

References

1. Barbanel, Julius B. (2005). The Geometry of Efficient Fair Division. New York: Cambridge University Press.

2. Barbanel, Julius B., and Steven J. Brams (2004). “Cake Division with Minimal Cuts: Envy-Free Procedures for 3 Person, 4 Persons, and Beyond.” Mathematical Social Sciences 48, no. 4 (November): 251-269.

3. Barbanel, Julius B., and Steven J. Brams (2011a). “Two-Person Pie-Cutting: The Fairest Cuts.” College Mathematics Journal 42, no. 1 (January): 25-32.

4. Barbanel, Julius B., and Steven J. Brams (2011b). Two-persone Cake-cutting: The Optimal Number of Cuts. Preprint, Department of Politics, New York University.

5. Barbanel, Julius B., Steven J. Brams, and Walter Stromquist (2009). “Cutting a Pie Is Not a Piece of Cake.” American Mathematical Monthly 116, no. 6 (June-July): 496-514.

6. Brams, Steven J. (2006). “Fair Division.” In Barry R. Weingast and Donald Wittman (eds.), Handbook of Political Economy. Oxford, UK: Oxford University Press, pp. 425-437.

7. Brams, Steven J. (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press.

8. Brams, Steven J., Michael A. Jones, and Christian Klamler (2006). “Better Ways to Cut a Cake.” Notices of the AMS 53, no. 11 (December): 1314-1321.

9. Brams, Steven J., Michael A. Jones, and Christian Klamler (2008). “Proportional Pie-Cutting.” International Journal of Game Theory 36, nos. 3-4 (March): 353-367.

10. Brams, Steven J., Michael A. Jones, and Christian Klamler (2011). “Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm.” SIAM Review 53, no. 2 (June): 291-307.

11. Brams, Steven J., and Alan D. Taylor (1996). Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge, UK: Cambridge University Press.

12. Caragiannis, Ioannis, John K. Lai, and Ariel D. Procaccia (2011). “Towards More Expressive Cake Cutting.” Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 127-132.

13. Cohler, Yuga, John K. Lai, David C. Parkes, and Ariel D. Procaccia (2011). “Optimal Envy-Free Cake Cutting.” Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 626-631.

14. Gale, David (1993). "Mathematical Entertainments." Mathematical Intelligencer 15, no. 1 (Winter): 48-52.

15. Jones, Michael A. (2002). “Equitable, Envy-Free, and Efficient Cake Cutting for Two People and Its Application to Divisible Goods.” Mathematics Magazine 75, no. 4 (October): 275-283.

16. Klamler, Christian (2010). “Fair Division.” In D. Marc Kilgour and Colin Eden (eds.), Handbook of Group Decision and Negotiation. Heidelberg, Germany: Springer, pp. 183-202.

17. Robertson, Jack, and William Webb (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, MA: A K Peters.