How to cut a cake almost fairly

S.O. Krumke; M. Lipmann; W. de Paepe; D. Poensgen; J. Rambau; L. Stougie; Gerhard Woeginger

How to cut a cake almost fairly

S.O. Krumke, M. Lipmann, W. de Paepe, D. Poensgen, J. Rambau, L. Stougie, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002)
Place of Publication	New York, USA
Publisher	ACM Press
Pages	263-264
ISBN (Print)	0-89871-513-X
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 https://archive.siam.org/meetings/da02/

Conference

Conference	13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002
Abbreviated title	SODA 2002
Country	United States
City	San Francisco
Period	6/01/02 → 8/01/02
Internet address	https://archive.siam.org/meetings/da02/

Keywords

METIS-208657

Access to Document

https://dl.acm.org/citation.cfm?id=545415

Cite this

@inproceedings{2634aa5d3a2142769bb18f4f7c69736a,

title = "How to cut a cake almost fairly",

abstract = "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.",

keywords = "METIS-208657",

author = "S.O. Krumke and M. Lipmann and {de Paepe}, W. and D. Poensgen and J. Rambau and L. Stougie and Gerhard Woeginger",

year = "2002",

language = "English",

isbn = "0-89871-513-X",

pages = "263--264",

booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002)",

publisher = "ACM Press",

note = "13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002, SODA 2002 ; Conference date: 06-01-2002 Through 08-01-2002",

url = "https://archive.siam.org/meetings/da02/",

}

Krumke, SO, 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). ACM Press, New York, USA, pp. 263-264, 13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002, San Francisco, United States, 6/01/02. <https://dl.acm.org/citation.cfm?id=545415>

How to cut a cake almost fairly. / Krumke, S.O.; Lipmann, M.; de Paepe, W.; Poensgen, D.; Rambau, J.; Stougie, L.; Woeginger, Gerhard.

Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002). New York, USA : ACM Press, 2002. p. 263-264.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - How to cut a cake almost fairly

AU - Krumke, S.O.

AU - Lipmann, M.

AU - de Paepe, W.

AU - Poensgen, D.

AU - Rambau, J.

AU - Stougie, L.

AU - Woeginger, Gerhard

N1 - Conference code: 13

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - METIS-208657

M3 - Conference contribution

SN - 0-89871-513-X

SP - 263

EP - 264

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002)

PB - ACM Press

CY - New York, USA

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algortihms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -