Contiguous cake cutting: hardness results and approximation algorithms

DOI10.1613/JAIR.1.12222MaRDI QIDQ5130002zbMATH OpenOpenAlexFDO

Authors Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

Publication date 3 November 2020

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.05416

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Agent technology and artificial intelligence (68T42) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

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.

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Contiguous cake cutting: hardness results and approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5130002)