Two-person cake-cutting: the optimal number of cuts

Barbanel, Julius B. and Brams, Steven J. (2011): Two-person cake-cutting: the optimal number of cuts.

Abstract

A cake is a metaphor for a heterogeneous, divisible good. When two players divide such a good, there is always a perfect division—one that is efficient (Pareto-optimal), envy-free, and equitable—which can be effected with a finite number of cuts under certain mild conditions; this is not always the case when there are more than two players (Brams, Jones, and Klamler, 2011b). We not only establish the existence of such a division but also provide an algorithm for determining where and how many cuts must be made, relating it to an algorithm, “Adjusted Winner” (Brams and Taylor, 1996, 1999), that yields a perfect division of multiple homogenous goods.

• Item Type: MPRA Paper
• Language: English
• Keywords: Cake-cutting; fair division; envy-freeness; adjusted winner; heterogeneous good
• Subjects: 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; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games

References

1. Barbanel, Julius B. (2000). “On the structure of Pareto optimal cake partitions.” Journal of Mathematical Economics 33: 401–424.

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

3. 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.

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

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 (2011a). “Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm.” SIAM Review 53, no. 2 (June): 291-307.

11. Brams, Steven J., Michael A. Jones, and Christian Klamler (2011b). “N-Player Cake-Cutting: There May Be No Perfect Division.” Preprint, Department of Politics, New York University.

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

13. Brams, Steven J., and Alan D. Taylor (1999). The Win-Win Solution: Guaranteeing Fair Shares to Everybody. New York: W. W. Norton.

14. 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.

15. 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.

16. 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.

17. 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.

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

19. Weller, D. (1985). “Fair division of a measurable space.” Journal of Mathematical Economics 14: 5-17.