Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination

Georgios Amanatidis, Evangelos Markakis, Apostolos Ntokos

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:

  1. 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.
  2. 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.
  3. 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$.

Comparison of approximation factors for various fairness criteria across different algorithms.

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

Abstract

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a $(ϕ-1)$-approximation of envy-freeness up to any good (EFX) and a $\frac{2}{ϕ+2}$-approximation of groupwise maximin share fairness (GMMS), where $ϕ$ is the golden ratio ($ϕ\approx 1.618$). The best known approximation factor for either one of these fairness notions prior to this work was $1/2$. Moreover, the returned allocation achieves envy-freeness up to one good (EF1) and a $2/3$-approximation of pairwise maximin share fairness (PMMS). While EFX is our primary focus, we also exhibit how to fine-tune our algorithm and improve the guarantees for GMMS or PMMS. Finally, we show that GMMS -- and thus PMMS and EFX -- allocations always exist when the number of goods does not exceed the number of agents by more than two.
BibTeX
@inproceedings{amanatidis2020multiple,
  author = {Georgios Amanatidis and Evangelos Markakis and Apostolos Ntokos},
  title = {{Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5545},
}
Figure