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|
|Date of revision:|
|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|
References listed on IDEAS
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.:
- Brams, S.J. & Kilgour, D.M., 1999.
"Competitive Fair Division,"
99-05, C.V. Starr Center for Applied Economics, New York University.
- Elisha Peterson & Francis Su, 2000. "Four-Person Envy-Free Chore Division," Claremont Colleges Working Papers 2000-48, Claremont Colleges.
- Francis Su, . "Rental Harmony: Sperner's Lemma in Fair Division," Claremont Colleges Working Papers 1999-10, Claremont Colleges.
- Brams,Steven J. & Taylor,Alan D., 1996. "Fair Division," Cambridge Books, Cambridge University Press, number 9780521556446, November.
When requesting a correction, please mention this item's handle: RePEc:cvs:starer:01-07. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Anne Stubing)
If references are entirely missing, you can add them using this form.