Brams, Steven J. and Jones, Michael A. and Klamler, Christian (2010): Divideandconquer: A proportional, minimalenvy cakecutting algorithm. Forthcoming in: SIAM Review (2011)

PDF
MPRA_paper_22704.pdf Download (209Kb)  Preview 
Abstract
We analyze a class of proportional cakecutting algorithms that use a minimal number of cuts (n1 if there are n players) to divide a cake that the players value along one dimension. While these algorithms may not produce an envyfree or efficient allocationas these terms are used in the fairdivision literatureone, divideandconquer (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 cakevalued along a linethat 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:  Divideandconquer: A proportional, minimalenvy cakecutting algorithm 
Language:  English 
Keywords:  mechanism design; fair division; divisible good; cakecutting; divideandchoose 
Subjects:  D  Microeconomics > D6  Welfare Economics > D63  Equity, Justice, Inequality, and Other Normative Criteria and Measurement D  Microeconomics > D7  Analysis of Collective DecisionMaking > D74  Conflict; Conflict Resolution; Alliances C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory 
Item ID:  22704 
Depositing User:  Steven J. Brams 
Date Deposited:  17. May 2010 13:38 
Last Modified:  13. Feb 2013 11:39 
References:  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: EnvyFree Procedures for 3 Persons, 4 Persons, and Beyond." Math. Social Sciences 48 (2004): 251269. 3. J. B. Barbanel and S. J. Brams, "TwoPerson PieCutting: 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): 496514. 5. S. J. Brams, M. A. Jones, and C. Klamler, "Better Ways to Cut a Cake." Notices of the AMS 53 (2006): 13141321. 6. S J. Brams, M. A. Jones, and C. Klamler, "Proportional PieCutting." Int. J. of Game Theory 26 (2008): 353367. 7. S. J. Brams and A. D. Taylor, Fair Division: From CakeCutting to Dispute Resolution, Cambridge University Press, 1996. 8. S. J. Brams, A D. Taylor, and W. S. Zwicker, "Old and New MovingKnife Schemes." Math. Intell. 17 (1995): 3035. 9. C. Busch, M. MagdonIsmail, and M. S. Krishamoorthy, "Hardness Results for CakeCutting." Bulletin of the European Association for Theoretical Computer Science 86 (2005): 85106. 10. L. E. Dubins and E. H. Spanier, "How to Cut a Cake Fairly." Amer. Math. Monthly 84 (1961): 117. 11. S. Even and A. Paz, "A Note on Cake Cutting." Discrete Appl. Math. 7 (1984): 285296. 12. D. Gale, "Mathematical Entertainments." Math. Intellig. 15 (1993): 4852. 13. Online Encyclopedia of Integer Sequences, hppt://www.research.att.com/~njas/sequences/ 14. J. Robertson and W. Webb, CakeCutting Algorithms: Be Fair If You Can, A K Peters, 1998. 15. H. Shishido and D.Z. Zeng, "MarkChooseCut Algorithms for Fair and Strongly Fair Division. Group Decision and Negotiation 8 (1999): 125137. 16. W. Stromuist, "How to Cut a Cake Fairly." Amer. Math. Monthly 87 (1980): 640644. 17. F. E. Su, "Rental Harmony: Sperner's Lemma in Fair Division." Amer. Math. Monthly 106 (1999): 922934. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/22704 