3 Persons, 2 Cuts: A Maximin Envy-Free and a Maximally Equitable Cake-Cutting Algorithm

Brams, Steven and Landweber, Peter (2018): 3 Persons, 2 Cuts: A Maximin Envy-Free and a Maximally Equitable Cake-Cutting Algorithm.

Abstract

We describe a 3-person, 2-cut envy-free cake-cutting algorithm, inspired by a continuous moving-knife procedure, that does not require that the players continuously move knifes across the cake. By having the players submit their value functions over the cake to a referee—rather than move knives according to these functions—the referee can ensure that the division is not only envy-free but also maximin. In addition, the referee can use the value functions to find a maximally equitable division, whereby the players receive equally valued shares that are maximal, but this allocation may not be envy-free.

• Item Type: MPRA Paper
• Language: English
• Keywords: Fair division; cake-cutting; envy-freeness; equitability
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; I - Health, Education, and Welfare > I3 - Welfare, Well-Being, and Poverty > I31 - General Welfare, Well-Being

References

Amanatidis, Georgios, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, and Etftychia Vakaliou (2018). “An Improved Envy-Free Cake Cutting Protocol for Four Agents.” Preprint. http://www.cs.cmu.edu/~cpsomas/envy_free.pdf

Aziz, Haris, and Simon Mackenzie (2017). “A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents.” Preprint. https://arxiv.org/abs/1604.03655

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

Barbanel, Julius B., and Steven J. Brams (2004). “Cake Division with Minimal Cuts: Envy-Free Procedures for 3 Persons, 4 Persons, and Beyond.” Mathematical Social Sciences 48, no. 3 (November): 251-259.

Brams, Steven J., Michael A. Jones, and Christian Klamler (2006). “Better Ways to Cut a Cake.” Notices of the AMS 35, no. 11 (December): 1314-1321.

Brams, Steven J., D. Marc Kilgour, and Christian Klamler (2017). “Maximin Envy-Free Division of Indivisible Items,” Group Decision and Negotiation 26, no. 1 (January): 115-131.

Brams, Steven J., and Alan D. Taylor (1995). “An Envy-Free Cake Division Protocol.” American Mathematical Monthly 102, no. 1 (January): 9-18.

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

Brams, Steven J., Alan D. Taylor, and William S. Zwicker (1997). “A Moving-Knife Solution to the Four-Person Envy-Free Cake Division Problem.” Proceedings of the American Mathematical Society 125, no. 2 (February): 547-554.

Dehghani, Sina, Alireza Farhadi, MohammadTaghi HajiAghayi, and Hadi Yami (2018). “Envy-Free Chore Division for an Arbitrary Number of Agents.” Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. http://epubs.siam.org/doi/abs/10.1137/1.9781611975031.164

Gal Ya’akov (Kobi), Moshe Mash, Ariel D. Procaccia, and Yair Zick (2018), “Which is the Fairest (Rent Division) of Them All?” Journal of the ACM (forthcoming).

Gale, David (1993). “Mathematical Entertainments.” Mathematical Intelligencer 15, no. 1 (Winter): 48-52.

Ianovski, Egor (2012). “Cake Cutting Mechanisms.” Preprint. https://arxiv.org/pdf/1203.0100.pdf

Kurokawa, David, Ariel D. Procacia, and Junxing Wang (2018). “Fair Enough: Guaranteeing Approximate Maximin Shares.” Journal of the ACM 65, no. 2: 8:1-8:27.

Neyman, Jerzy (1946). “Un Théorèm d’Existence.” C. R. Academie de Science Paris 222: 843-845.

Stromquist, Walter (1980). “How to Cut a Cake Fairly.” American Mathematical Monthly 18, no. 8 (October): 640-644.

Stromquist, Walter (2008). “Envy-Free Cake Divisions Cannot Be Found by Finite Protocols.” Electronic Journal of Combinatorics 15, #R11. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r11/pdf

Su, Francis Edward (1999). “Rental Harmony: Sperner’s Lemma in Fair Division.” American Mathematical Monthly 106, no. 10 (December): 430-442.

Wolfram Equation Solver (2018). https://www.wolframalpha.com/examples/EquationSolving.html