Abstract
This paper presents a significant breakthrough in the fair division of indivisible goods. It proves that for four agents with additive preferences, there always exists an allocation that is Envy-Free up to any item (EFX) while leaving at most one item unallocated. The authors introduce a novel graph-theoretic tool, "generalized champion edges," to navigate the combinatorial complexity of the problem. This work provides the first existence result for EFX with four agents and establishes a general bound for $n$ agents, showing that an EFX allocation leaving at most $n-2$ items unallocated always exists.
Introduction
The challenge of dividing indivisible goods—such as heirlooms, land parcels, or tasks—fairly among multiple participants is a cornerstone of computational social choice. The ideal standard is Envy-Freeness (EF), where no agent prefers another's bundle to their own. However, EF is often unattainable with indivisible items. Consequently, researchers focus on Envy-Free up to any item (EFX): an allocation where no agent envies another after the removal of any single item from the other's bundle. While EFX is a robust fairness criterion, proving its existence for more than three agents has remained an open mystery until now.
Methodology: Generalized Champion Edges
The authors employ a graph-theoretic framework where agents are represented as vertices and directed edges represent relationships such as envy or "championship." A standard champion edge indicates that an agent is the most envious of a bundle when an unallocated item is added to it.
The core innovation of this paper is the generalized champion edge ($i \xrightarrow{H | S} j$). This edge type represents a flexible reallocation move: giving agent $i$ agent $j$’s current bundle plus a set of items $H$, while freeing up a subset of items $S$ for reallocation. By identifying cycles within a graph composed of these edges, the authors can iteratively reshuffle items to increase the "potential" of the allocation while preserving the EFX property.
Key Insights and Results
The paper's primary contribution is the 4-Agent Milestone: every instance with four agents and additive valuations admits an EFX allocation leaving at most one item unallocated. This suggests that the primary obstacle to a "full" EFX allocation (where all items are distributed) is often a single troublesome item.
Key findings include:
- General $n$-Agent Bound: For any number of agents $n$, an EFX allocation exists leaving at most $n-2$ items unallocated.
- Nice Cancelable Valuations: The results extend beyond additive valuations to a broader class termed "nice cancelable," which includes unit-demand, budget-additive, and multiplicative valuations.
- Algorithmic Progress: The new framework simplifies previous proofs for the three-agent case, providing a more unified approach to the field.
Conclusion and Future Work
While this work brings the field closer to a complete solution, the "at most one" unallocated item remains a limitation. Proving the existence of a full EFX allocation for four agents without any unallocated items is the next logical step. Furthermore, while "nice cancelable" valuations cover many common scenarios, the existence of EFX for general monotonic valuations remains one of the most significant open problems in fair division theory.
Summary updated