Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Authors

  • Paul W. Goldberg University of Oxford
  • Alexandros Hollender University of Oxford
  • Warut Suksompong University of Oxford

DOI:

https://doi.org/10.1609/aaai.v34i02.5570

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 strengthening those from prior work.

Downloads

Published

2020-04-03

How to Cite

Goldberg, P. W., Hollender, A., & Suksompong, W. (2020). Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1990-1997. https://doi.org/10.1609/aaai.v34i02.5570

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms