How to Cut a Cake Almost Fairly
Please always quote using this 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.
Author: | Sven Krumke, Maarten Lipmann, Willem de Paepe, Diana Poensgen, Jörg Rambau, Leen Stougie, Gerhard Woeginger |
---|---|
Document Type: | ZIB-Report |
Tag: | Fair division; cake cutting |
MSC-Classification: | 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 | |
Date of first Publication: | 2002/05/07 |
Series (Serial Number): | ZIB-Report (02-23) |
ZIB-Reportnumber: | 02-23 |
Published in: | Appeared in: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 263-264 |