Barbanel, Julius B. and Brams, Steven J. (2011): Two-person cake-cutting: the optimal number of cuts.
Download (606kB) | Preview
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|
|Original Title:||Two-person cake-cutting: the optimal number of cuts|
|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
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
|Depositing User:||Steven J. Brams|
|Date Deposited:||22. Oct 2011 15:48|
|Last Modified:||16. Feb 2013 05:19|
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.