Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
✍ Scribed by Julius B. Barbanel; Steven J. Brams
- Publisher
- Elsevier Science
- Year
- 2004
- Tongue
- English
- Weight
- 263 KB
- Volume
- 48
- Category
- Article
- ISSN
- 0165-4896
No coin nor oath required. For personal study only.
✦ Synopsis
The minimal number of parallel cuts required to divide a cake into n pieces is n À 1. A new 3person procedure, requiring two 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, using three parallel cuts, which makes at most one person envious. Finally, a 4-person envy-free procedure is given, but it requires up to five 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.