Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul W. Goldberg, Alexandros Hollender, Warut Suksompong

Introduction

The "cake cutting" problem is a fundamental metaphor in fair division theory, representing the challenge of partitioning a heterogeneous, divisible resource—such as land, advertising space, or time—among multiple agents with diverse preferences. A division is considered envy-free (EF) if no agent prefers another's piece over their own.

While mathematical proofs, most notably by Stromquist in 1980, guarantee that a contiguous envy-free allocation (where each agent receives a single, solid block) always exists, finding it is computationally daunting. In 2008, research demonstrated that no finite algorithm can compute an exact contiguous EF allocation for three or more agents. This paper bridges the gap between mathematical existence and computational reality by introducing the first efficient approximation algorithms and identifying the specific constraints that make the problem NP-hard.

The Complexity of Contiguity

In many real-world scenarios, receiving a "union of crumbs" is impractical; contiguity is a requirement. However, the requirement for contiguous pieces significantly complicates the search for fairness. The authors investigate three primary dimensions of this problem:

  1. Approximation: Can we efficiently find an allocation that is almost envy-free?
  2. Constraints: Does the problem become harder if we impose simple requirements, such as a specific ordering of agents?
  3. Discretization: How do these continuous principles apply to the division of indivisible items lined up on a shelf?

Algorithmic Approaches and the 1/3 Barrier

The paper employs a mix of algorithmic design and computational complexity theory to navigate these challenges. For general preferences, the authors design a greedy-style "moving-knife" algorithm that achieves 1/3-envy-freeness in polynomial time. This means that any envy an agent feels toward another is capped at one-third of their total valuation of the cake.

For a more specific class of "uniform single-interval" valuations—where agents only value a specific window of the resource—the authors provide an algorithm that achieves a 1/4-envy-free allocation. These results represent a significant step forward, providing the first polynomial-time guarantees for a problem previously considered computationally intractable.

The Fragility of Existence

One of the paper's most striking insights is the "fragility" of the existence of EF allocations. While an unconstrained EF allocation is guaranteed to exist, the authors prove that adding even minor real-world constraints makes the problem NP-hard to even decide if a solution exists. Using reductions from 3-SAT with elaborate "Clause-Gadgets" and "Variable-Gadgets," they show that the following problems are NP-hard:

  • Finding an EF allocation where a specific agent is assigned the leftmost piece.
  • Finding an EF allocation with a fixed, pre-determined ordering of agents.
  • Finding an EF allocation where a cut must occur at a specific, fixed position.

This jump from "always possible" to "NP-hard to decide" highlights the extreme sensitivity of fair division to external constraints.

Discrete vs. Continuous Fairness

The study also extends into the discrete realm, where agents must divide indivisible items arranged in a line. The authors prove that even with binary valuations (where an agent either wants an item or they don't), finding a contiguous allocation that is envy-free, proportional, or equitable remains NP-hard. This strengthens previous complexity results that relied on more complex, additive valuation functions.

Conclusion and Future Directions

This research clarifies the computational landscape of contiguous cake cutting. It establishes that while exact envy-freeness is elusive, meaningful approximations are reachable in polynomial time. However, the paper also serves as a cautionary tale for mechanism designers: adding even the simplest constraints to a fair division problem can render it computationally impossible to solve.

Future work remains to bridge the "approximation gap." While 1/3-envy-freeness is a milestone, it is currently unknown if a Fully Polynomial-Time Approximation Scheme (FPTAS) exists—an algorithm that could achieve an arbitrarily small level of envy ($\epsilon$) in polynomial time. Additionally, the tension between fairness (envy-freeness) and efficiency (maximizing total social welfare) remains a fertile ground for further investigation.

Summary updated

BibTeX
@article{goldberg2020contiguous,
  author = {Paul W. Goldberg and Alexandros Hollender and Warut Suksompong},
  title = {{Contiguous Cake Cutting: Hardness Results and Approximation Algorithms}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=lmnaiwxxDE7},
}
Figure