Abstract
This paper presents a novel polynomial-time algorithm, Draft-and-Eliminate, designed to achieve "universal fairness" in the division of indivisible goods. By integrating a golden-ratio-based drafting process with envy-cycle elimination, the authors break the long-standing 1/2-approximation barrier for two critical fairness notions: Envy-Freeness up to any good (EFX) and Groupwise Maximin Share (GMMS). The algorithm simultaneously guarantees an approximation factor of approximately 0.618 for EFX and 0.553 for GMMS, while maintaining exact EF1 and a 2/3-approximation for PMMS.
Introduction
Fair division explores how to allocate resources among agents with heterogeneous preferences such that the resulting distribution is perceived as equitable. When resources are indivisible—such as real estate or specific assignments—perfect Envy-Freeness (where no agent prefers another's bundle) is often mathematically impossible.
To address this, researchers utilize several relaxation criteria:
- EF1 (Envy-Free up to one good): An agent does not envy another after the removal of at most one item from the other's bundle.
- EFX (Envy-Free up to any good): An agent does not envy another after the removal of any item from the other's bundle. This is a significantly stronger and harder-to-satisfy condition than EF1.
- MMS/PMMS/GMMS (Maximin Share variants): These criteria guarantee agents a value based on hypothetical partitions they would make themselves.
Prior to this work, the best polynomial-time algorithms for EFX and GMMS were capped at a 1/2-approximation. Most existing methods also struggled to satisfy multiple criteria simultaneously. This paper introduces a unified approach to surpass these limits.
Methodology: The Draft-and-Eliminate Algorithm
The core contribution is Algorithm 3 (Draft-and-Eliminate), which operates in three distinct phases:
- Golden Ratio Preprocessing: The algorithm establishes an agent ordering using the golden ratio ($\phi \approx 1.618$) as a critical threshold. If an agent's envy for a previously selected item exceeds this factor, the priority order is dynamically adjusted.
- Two-Round Balanced Drafting: Agents select items in two rounds. The first follows the priority order, while the second uses a reverse order for a specific subset. This balanced approach prevents early-mover advantages from creating insurmountable envy.
- Envy-Cycle Elimination: The final allocation is refined using a directed graph where nodes represent agents and edges represent envy. By rotating bundles along identified cycles, the algorithm eliminates envy while preserving the EF1 property.
The innovation lies in the synergy between the drafting phase—"priming" the allocation—and the cycle elimination phase, which together ensure the stronger EFX and GMMS guarantees.
Key Results
The Draft-and-Eliminate algorithm and its variants provide the first polynomial-time improvements over the 0.5 barrier for EFX and GMMS. Specifically, the algorithm achieves an EFX approximation of $\phi - 1 \approx 0.618$ and a GMMS approximation of $2/(\phi + 2) \approx 0.553$.
As shown in the table above, the proposed methods consistently outperform previous benchmarks. Notably, the algorithm also maintains exact EF1 (1.0) and improves the PMMS guarantee to 0.667. Furthermore, the authors demonstrate that for small cases where the number of goods $m \le n+2$, an exact GMMS (and EFX) allocation is always efficiently computable.
Discussion and Future Work
The use of the golden ratio $\phi$ serves as a pivotal balancing point between drafting advantages and envy constraints. While this work marks a significant step forward, several avenues remain:
- Valuation Complexity: The current results assume additive valuations. Extending these "universal" guarantees to submodular or general monotone functions is a key area for future research.
- The EFX Existence Problem: The fundamental question of whether an exact EFX allocation always exists for general $n$ and $m$ remains open.
- Tightness of Bounds: Future work may determine if the 0.618 and 0.553 factors are the theoretical limits for polynomial-time algorithms or if further improvements are possible.
Summary updated