License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-12278
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1227/
Go to the corresponding Portal


Brams, Steven J. ; Jones, Michael A. ; Klamler, Christian

Better Ways to Cut a Cake - Revisited

pdf-format:
Document 1.pdf (212 KB)


Abstract

Procedures to divide a cake among n people with n-1 cuts (the minimum number) are analyzed and compared. For 2 persons, cut-and-choose, while envy-free and efficient, limits the cutter to exactly 50% if he or she is ignorant of the chooser's preferences, whereas the chooser can generally obtain more. By comparison, a new 2-person surplus procedure (SP'), which induces the players to be truthful in order to maximize their minimum allocations, leads to a proportionally equitable division of the surplus - the part that remains after each player receives 50% - by giving each person a certain proportion of the surplus as he or she values it. For n geq 3 persons, a new equitable procedure (EP) yields a maximally equitable division of a cake. This division gives all players the highest common value that they can achieve and induces truthfulness, but it may not be envy-free. The applicability of SP' and EP to the fair division of a heterogeneous, divisible good, like land, is briefly discussed.

BibTeX - Entry

@InProceedings{brams_et_al:DSP:2007:1227,
  author =	{Steven J. Brams and Michael A. Jones and Christian Klamler},
  title =	{Better Ways to Cut a Cake - Revisited},
  booktitle =	{Fair Division},
  year =	{2007},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  number =	{07261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1227},
  annote =	{Keywords: Fair division, cake-cutting, envy-freeness, strategy-proofness}
}

Keywords: Fair division, cake-cutting, envy-freeness, strategy-proofness
Seminar: 07261 - Fair Division
Issue Date: 2007
Date of publication: 26.11.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI