The complexity of cake cutting with unequal shares
- An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. <br /> In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known protocols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highlyAn unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share. <br /> In this article, we investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands, which delivers a proportional solution in fewer queries than all known protocols. By giving a matching lower bound, we then show that our protocol is asymptotically the fastest possible. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.…
| Author details: | Agnes CsehORCiDGND, Tamas FleinerGND |
|---|---|
| DOI: | https://doi.org/10.1145/3380742 |
| ISSN: | 1549-6325 |
| ISSN: | 1549-6333 |
| Title of parent work (English): | ACM transactions on algorithms : TALG |
| Publisher: | Association for Computing Machinery |
| Place of publishing: | New York |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2020/06/06 |
| Publication year: | 2020 |
| Release date: | 2023/11/13 |
| Tag: | Cake cutting; fair division; proportional division; unequal shares |
| Volume: | 16 |
| Issue: | 3 |
| Article number: | 29 |
| Number of pages: | 21 |
| Funding institution: | Cooperation of Excellences Grant [KEP-6/2019]; Hungarian Academy of; Sciences under its Momentum Programme [LP2016-3/2019]; Hungarian Academy; of Sciences under its Janos Bolyai Research Fellowship; OTKAOrszagos; Tudomanyos Kutatasi Alapprogramok (OTKA) [K128611] |
| Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
| Peer review: | Referiert |
