Brams, Steven J. and Jones, Michael A. and Klamler, Christian (2010): Divide-and-conquer: A proportional, minimal-envy cake-cutting algorithm. Forthcoming in: SIAM Review (2011)
Download (214kB) | Preview
We analyze a class of proportional cake-cutting algorithms that use a minimal number of cuts (n-1 if there are n players) to divide a cake that the players value along one dimension. While these algorithms may not produce an envy-free or efficient allocation--as these terms are used in the fair-division literature--one, divide-and-conquer (D&C), minimizes the maximum number of players that any single player can envy. It works by asking n ≥ 2 players successively to place marks on a cake--valued along a line--that divide it into equal halves (when n is even) or nearly equal halves (when n is odd), then halves of these halves, and so on. Among other properties, D&C ensures players of at least 1/n shares, as they each value the cake, if and only if they are truthful. However, D&C may not allow players to obtain proportional, connected pieces if they have unequal entitlements. Possible applications of D&C to land division are briefly discussed.
|Item Type:||MPRA Paper|
|Original Title:||Divide-and-conquer: A proportional, minimal-envy cake-cutting algorithm|
|Keywords:||mechanism design; fair division; divisible good; cake-cutting; divide-and-choose|
|Subjects:||D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
D - Microeconomics > D7 - Analysis of Collective Decision-Making > D74 - Conflict; Conflict Resolution; Alliances
C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory
|Depositing User:||Steven J. Brams|
|Date Deposited:||17. May 2010 13:38|
|Last Modified:||13. Feb 2013 11:39|
1. J. B. Barbanel, The Geometry of Efficient Fair Division, Cambridge University Press, 2005.
2. J. B. Barbanel and S. J. Brams,"Cake Division with Minimal Cuts: Envy-Free Procedures for 3 Persons, 4 Persons, and Beyond." Math. Social Sciences 48 (2004): 251-269.
3. J. B. Barbanel and S. J. Brams, "Two-Person Pie-Cutting: The Fairest Cuts." College Math. J. (to appear 2011).
4. J. B. Barbanel, S. J. Brams, and W. Stromquist, "Cutting a Pie Is Not a Piece of Cake." Amer. Math. Monthly 116 (2009): 496-514.
5. S. J. Brams, M. A. Jones, and C. Klamler, "Better Ways to Cut a Cake." Notices of the AMS 53 (2006): 1314-1321.
6. S J. Brams, M. A. Jones, and C. Klamler, "Proportional Pie-Cutting." Int. J. of Game Theory 26 (2008): 353-367.
7. S. J. Brams and A. D. Taylor, Fair Division: From Cake-Cutting to Dispute Resolution, Cambridge University Press, 1996.
8. S. J. Brams, A D. Taylor, and W. S. Zwicker, "Old and New Moving-Knife Schemes." Math. Intell. 17 (1995): 30-35.
9. C. Busch, M. Magdon-Ismail, and M. S. Krishamoorthy, "Hardness Results for Cake-Cutting." Bulletin of the European Association for Theoretical Computer Science 86 (2005): 85-106.
10. L. E. Dubins and E. H. Spanier, "How to Cut a Cake Fairly." Amer. Math. Monthly 84 (1961): 1-17.
11. S. Even and A. Paz, "A Note on Cake Cutting." Discrete Appl. Math. 7 (1984): 285-296.
12. D. Gale, "Mathematical Entertainments." Math. Intellig. 15 (1993): 48-52.
13. Online Encyclopedia of Integer Sequences, hppt://www.research.att.com/~njas/sequences/
14. J. Robertson and W. Webb, Cake-Cutting Algorithms: Be Fair If You Can, A K Peters, 1998.
15. H. Shishido and D.-Z. Zeng, "Mark-Choose-Cut Algorithms for Fair and Strongly Fair Division. Group Decision and Negotiation 8 (1999): 125-137.
16. W. Stromuist, "How to Cut a Cake Fairly." Amer. Math. Monthly 87 (1980): 640-644.
17. F. E. Su, "Rental Harmony: Sperner's Lemma in Fair Division." Amer. Math. Monthly 106 (1999): 922-934.