Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

Abstract

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting.
BibTeX
@article{goldberg2020contiguous,
  author = {Paul W. Goldberg and Alexandros Hollender and Warut Suksompong},
  title = {{Contiguous Cake Cutting: Hardness Results and Approximation Algorithms}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=lmnaiwxxDE7},
}

Loading related content...

Figure