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:
- 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.
- 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.
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