Contiguous Cake Cutting: Hardness Results and Approximation Algorithms
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.
Cite
Text
Goldberg et al. "Contiguous Cake Cutting: Hardness Results and Approximation Algorithms." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I02.5570Markdown
[Goldberg et al. "Contiguous Cake Cutting: Hardness Results and Approximation Algorithms." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/goldberg2020aaai-contiguous/) doi:10.1609/AAAI.V34I02.5570BibTeX
@inproceedings{goldberg2020aaai-contiguous,
title = {{Contiguous Cake Cutting: Hardness Results and Approximation Algorithms}},
author = {Goldberg, Paul W. and Hollender, Alexandros and Suksompong, Warut},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {1990-1997},
doi = {10.1609/AAAI.V34I02.5570},
url = {https://mlanthology.org/aaai/2020/goldberg2020aaai-contiguous/}
}