Contiguous cake cutting: hardness results and approximation algorithms

DOI10.1613/JAIR.1.12222zbMATH Open1490.68242arXiv1911.05416OpenAlexW3106128496MaRDI QIDQ5130002FDOQ5130002

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)

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.

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

Recommendations

• Fair and efficient cake division with connected pieces
• Algorithmic solutions for envy-free cake cutting
• Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal
• Fair multi-cake cutting
• Cutting a Cake Fairly for Groups Revisited

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Rental Harmony: Sperner's Lemma in Fair Division
• On the Complexity of Nash Equilibria and Other Fixed Points
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• How to Cut A Cake Fairly
• Title not available (Why is that?)
• Cake cutting algorithms
• How to Cut a Cake Fairly
• Almost envy-freeness with general valuations
• An Envy-Free Cake Division Protocol
• On the existence of equitable cake divisions
• Envy-free cake divisions cannot be found by finite protocols
• Algorithmic solutions for envy-free cake cutting
• Almost envy-free allocations with connected bundles
• A discrete and bounded envy-free cake cutting protocol for four agents
• Fair and efficient cake division with connected pieces
• Expand the shares together: envy-free mechanisms with a small number of cuts
• On the computability of equitable divisions
• Envy-free division of discrete cakes
• Consensus halving is PPA-complete
• Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal
• Cake cutting really is not a piece of cake

Cited In (12)

• Truthful fair division without free disposal
• Fair multi-cake cutting
• Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
• On existence of truthful fair cake cutting mechanisms
• Approximate envy-freeness in graphical cake cutting
• How to cut a cake fairly: a generalization to groups
• A Note on a Cake Cutting Algorithm of Banach and Knaster
• Fair Cake Division Under Monotone Likelihood Ratios
• Fair and efficient cake division with connected pieces
• Dividing a graphical cake
• Mind the gap: cake cutting with separation
• Two's company, three's a crowd: consensus-halving for a constant number of agents

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)