Abstract
This paper addresses a long-standing open question in fair division: the existence of envy-free up to one item (EF1) allocations for a "discrete cake"—a sequence of indivisible items. While previous mathematical proofs were limited to four agents, this work provides a universal existence proof for any number of agents. By combining combinatorial topology with a novel asymmetric rounding algorithm, the author demonstrates that a contiguous EF1 division always exists for agents with monotone valuations.
Introduction
In the classic cake-cutting problem, the goal is to divide a heterogeneous resource among multiple participants with different preferences. While the continuous version (dividing a literal cake) is well-studied, the discrete version is often more applicable to real-world scenarios, such as dividing plots of land along a road or scheduling meeting slots. In these cases, items are indivisible and must be assigned in contiguous "bundles."
The challenge lies in achieving fairness. Perfect envy-freeness is often impossible with indivisible items; thus, researchers aim for EF1 (Envy-Free up to One item). An allocation is EF1 if any envy an agent feels toward another would disappear if a single item were removed from the envied agent's bundle. Previous research established the existence of EF1 for up to four agents, but the mathematical framework failed for larger groups due to complex symmetry conflicts.
Methodology
The paper overcomes these hurdles using a blend of combinatorial topology and a specialized rounding technique.
Sperner’s Lemma and the Simplex
The author represents the space of all possible contiguous partitions as points on a high-dimensional triangle, known as a simplex. By "coloring" the vertices of this simplex based on which bundle an agent prefers at a specific cut-point, the author applies Sperner’s Lemma. This topological tool guarantees the existence of a "fully-colored" sub-simplex where different agents prefer different bundles, indicating a potential fair division point.
Left-Right Asymmetric Rounding
The core innovation is the Left-Right Asymmetric Rounding algorithm. Theoretical cuts often fall in the middle of an item, requiring a method to map them to discrete boundaries. Previous symmetric approaches caused the proof to fail for $n > 4$. Igarashi introduces an asymmetric "pessimistic/optimistic" approach: agents are pessimistic about the leftmost item of a bundle but optimistic about the rightmost. This asymmetry breaks the ties that previously hindered the proof.
Key Insights and Results
- Universal Existence: The paper proves that a connected EF1 division always exists for $n$ agents with monotone valuations, regardless of the size of $n$.
- The Power of Asymmetry: The mathematical difficulty in earlier proofs stemmed from treating the start and end of a bundle identically. Prioritizing "left" agents over "right" agents during rounding ensures that no agent’s estimate of their bundle deviates too far from reality.
- EF1_outer: The proof actually establishes a stronger fairness property called $EF1_{outer}$, which requires that the remaining bundle remains connected even after removing the envy-clearing item.
- Traceable Graphs: The results extend beyond simple lines to any traceable graph—networks where a single Hamiltonian path visits every node.
Limitations and Future Directions
While the paper provides a landmark existence proof, finding these divisions remains computationally difficult. Locating a Sperner-labeled simplex is generally PPAD-complete, meaning an efficient polynomial-time algorithm is still missing. Additionally, while the proof holds for monotone preferences (where more is always better), future work is needed to determine if these results apply to "mixed" items, such as chores that carry negative value.
Summary updated