In the cake cutting problem, n ≥ 2 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) of the cake. Moreover we show that no protocol with n - 1 cuts can guarantee a better fraction.
|Title of host publication||Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002)|
|Place of Publication||New York, USA|
|Publication status||Published - 2002|
|Event||13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002 - Radisson Miyako Hotel, San Francisco, United States|
Duration: 6 Jan 2002 → 8 Jan 2002
Conference number: 13
|Conference||13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002|
|Abbreviated title||SODA 2002|
|Period||6/01/02 → 8/01/02|
Krumke, S. O., Lipmann, M., de Paepe, W., Poensgen, D., Rambau, J., Stougie, L., & Woeginger, G. (2002). How to cut a cake almost fairly. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002) (pp. 263-264). New York, USA: ACM Press.