Cake Division with Minimal Cuts: Envy-Free Procedures for 3 Person, 4 Persons, and Beyond
The minimal number of parallel cuts required to divide a cake into n pieces is n-1. A new 3-person procedure, requiring 2 parallel cuts, is given that produces an envy- free division, whereby each person thinks he or she receives at least a tied- for- largest piece. An extension of this procedure leads to a 4-person division, us ing 3 parallel cuts, that makes at most one player envious. Finally, a 4-person envy-free procedure is given, but it requires up to 5 parallel cuts, and some pieces may be disconnected. All these procedures improve on extant procedures by using fewer moving knives, making fewer people envious, or using fewer cuts. While the 4-person, 5-cut procedure is complex, endowing people with more information about others' preferences, or allowing them to do things beyond stopping moving knives, may yield simpler procedures for making envy- free divisions with minimal cuts, which are known always to exist
|Date of creation:||2001|
|Contact details of provider:|| Postal: C.V. Starr Center, Department of Economics, New York University, 19 W. 4th Street, 6th Floor, New York, NY 10012|
Phone: (212) 998-8936
Fax: (212) 995-3932
Web page: http://econ.as.nyu.edu/object/econ.cvstarr.html
More information through EDIRC
|Order Information:|| Postal: C.V. Starr Center, Department of Economics, New York University, 19 W. 4th Street, 6th Floor, New York, NY 10012|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Francis Su, "undated". "Rental Harmony: Sperner's Lemma in Fair Division," Claremont Colleges Working Papers 1999-10, Claremont Colleges.
- Steven J. Brams & D. Marc Kilgour, 2001. "Competitive Fair Division," Journal of Political Economy, University of Chicago Press, vol. 109(2), pages 418-443, April.
- Elisha Peterson & Francis Su, 2000. "Four-Person Envy-Free Chore Division," Claremont Colleges Working Papers 2000-48, Claremont Colleges.
- Brams,Steven J. & Taylor,Alan D., 1996. "Fair Division," Cambridge Books, Cambridge University Press, number 9780521556446.