Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

DOI10.1613/JAIR.1.12222zbMath1490.68242arXiv1911.05416OpenAlexW3106128496MaRDI QIDQ5130002

Alexandros Hollender, Paul W. Goldberg, 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

Mathematics Subject Classification ID

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

Related Items (7)

Truthful fair division without free disposal ⋮ Fair multi-cake cutting ⋮ On existence of truthful fair cake cutting mechanisms ⋮ How to Cut a Cake Fairly: A Generalization to Groups ⋮ Mind the gap: cake cutting with separation ⋮ Two's company, three's a crowd: consensus-halving for a constant number of agents ⋮ Fair Cake Division Under Monotone Likelihood Ratios

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate well-supported Nash equilibria below two-thirds
• Fair and efficient cake division with connected pieces
• Envy-free cake divisions cannot be found by finite protocols
• Expand the shares together: envy-free mechanisms with a small number of cuts
• On the computability of equitable divisions
• On the existence of equitable cake divisions
• Rental Harmony: Sperner's Lemma in Fair Division
• On the Complexity of Nash Equilibria and Other Fixed Points
• How to Cut A Cake Fairly
• How to Cut a Cake Fairly
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• An Envy-Free Cake Division Protocol
• Algorithmic Solutions for Envy-Free Cake Cutting
• Waste Makes Haste
• Almost Envy-Freeness with General Valuations
• Cake Cutting Algorithms
• Consensus halving is PPA-complete
• A discrete and bounded envy-free cake cutting protocol for four agents
• Fairly allocating contiguous blocks of indivisible items
• Cake cutting really is not a piece of cake
• Envy-free division of discrete cakes

This page was built for publication: Contiguous Cake Cutting: Hardness Results and Approximation Algorithms