Contiguous Cake Cutting: Hardness Results and Approximation Algorithms

Paul Goldberg, Alexandros Hollender, Warut Suksompong

Abstract

The problem of fair division, often metaphorically referred to as "cake cutting," involves partitioning a heterogeneous resource among multiple agents with distinct preferences. While the existence of contiguous envy-free allocations is mathematically guaranteed, finding them algorithmically is known to be impossible in finite time for three or more agents. This paper addresses this gap by presenting polynomial-time algorithms for approximate envy-freeness and establishing NP-hardness results for the problem when subjected to common practical constraints, such as fixed agent ordering.

Introduction

Cake cutting is a fundamental problem in social choice and economics, where a divisible resource (the "cake") must be divided among $n$ agents. A division is envy-free if no agent prefers another's piece over their own. In many real-world scenarios, such as land division or time-slot allocation, contiguity is a critical requirement: each agent must receive a single connected interval.

Although Stromquist (1980) proved that contiguous envy-free allocations always exist, he later demonstrated that no finite algorithm can find such an allocation for $n \ge 3$ agents in the standard Robertson-Webb query model. This work explores the computational boundaries of this problem by investigating approximation guarantees and the impact of additional constraints on complexity.

Approximation Algorithms

The authors propose two primary approximation algorithms to bridge the gap between theoretical existence and algorithmic feasibility:

  1. General Valuations: For arbitrary valuation functions, the paper introduces a polynomial-time algorithm that guarantees 1/3-envy-freeness. This means no agent envies another by more than one-third of their total value for the entire cake. The algorithm utilizes a moving-knife approach, cutting and assigning pieces as soon as they reach the 1/3 threshold for any agent.
  2. Restricted Valuations: For "uniform single-interval" valuations—where agents only value a specific sub-interval of the cake uniformly—the authors provide an improved 1/4-envy-free algorithm. This approach leverages the specific structure of these preferences to achieve a tighter fairness bound.

Hardness of Fair Division

To understand why finding a perfect envy-free allocation is difficult, the authors analyze the problem through the lens of computational complexity. They prove that while existence is guaranteed in the unconstrained case, adding simple constraints makes the search problem NP-hard.

The hardness proofs rely on reductions from the 3-SAT problem. The authors construct specific "gadgets" to represent variables and clauses within the cake-cutting framework.

Figure 1: Variable gadget used in the NP-hardness reduction to ensure consistency between literal assignments.
Figure 2: Clause gadget representing logical constraints in the 3-SAT reduction.

Key findings include:

  • Fixed Ordering: Finding an envy-free allocation where the order of agents is pre-specified (e.g., Agent 1 must be to the left of Agent 2) is NP-hard.
  • Fixed Cut Positions: Requiring even a single cut to occur at a specific location renders the search for an envy-free allocation NP-hard.
  • Discrete Settings: The paper extends these results to indivisible items arranged on a line, showing that finding contiguous blocks that satisfy fairness criteria like proportionality or envy-freeness is NP-hard, even with simple binary valuations.

Conclusion

This research highlights a significant trade-off between fairness and computational efficiency in resource allocation. While perfect contiguous envy-freeness is elusive, the 1/3-envy-free algorithm provides a practical, efficient alternative for general settings. The hardness results emphasize that seemingly minor operational constraints can fundamentally change the complexity of fair division. Future research may focus on whether the 1/3 and 1/4 bounds are tight or if polynomial-time algorithms can achieve even smaller envy levels.

Summary updated

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.
BibTeX
@article{goldberg2020contiguous,
  author = {Paul 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