Divide-and-conquer: A proportional, minimal-envy cake-cutting algorithm

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)

Abstract

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
• Language: English
• 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 ; Revolutions; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory

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