How to Cut a Cake Almost Fairly
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-6905
- In the cake cutting problem, $n\ge2$ players want to cut a cake into $n$ pieces so that every player gets a ``fair'' share of the cake by his own measure. We describe a protocol with $n-1$~cuts in which each player can enforce to get a share of at least~$1/(2n-2)$. Moreover we show that no protocol with $n-1$~cuts can guarantee a better fraction.
Verfasserangaben: | Sven Krumke, Maarten Lipmann, Willem de Paepe, Diana Poensgen, Jörg Rambau, Leen Stougie, Gerhard Woeginger |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Fair division; cake cutting |
MSC-Klassifikation: | 91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Axx Game theory / 91A06 n-person games, n > 2 |
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Axx Game theory / 91A10 Noncooperative games | |
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Axx Game theory / 91A80 Applications of game theory | |
Datum der Erstveröffentlichung: | 07.05.2002 |
Schriftenreihe (Bandnummer): | ZIB-Report (02-23) |
ZIB-Reportnummer: | 02-23 |
Verlagspublikation: | Appeared in: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 263-264 |