Pareto Inefficiency of EFX

Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub TarnawskiarXiv 2026 · arXiv

In the world of fair division—think heirs splitting an estate or teams drafting players—two ideals often clash: Fairness (nobody should feel cheated) and Efficiency (we shouldn't leave value on the table). This paper settles a long-standing question about whether these two goals can always coexist when we use one of the most popular definitions of fairness.

TL;DR

The authors prove that two gold-standard properties of resource allocation—Envy-Freeness up to any good (EFX) and Pareto Optimality (PO)—are fundamentally incompatible. They provide the first counterexample where every agent values every item positively, yet no allocation can satisfy both properties simultaneously.

What Problem Does This Paper Address?

When dividing indivisible items (like cars or jewelry), perfect envy-freeness is often impossible. If there's only one diamond, whoever doesn't get it will be envious. To solve this, researchers use EFX: Agent A doesn't envy Agent B as long as we can remove any single item from B's bundle to settle the score. It’s widely considered the "closest analogue" to true envy-freeness for discrete goods.

Meanwhile, Pareto Optimality (PO) is the baseline for efficiency: an allocation is PO if you can't make one person happier without making someone else worse off.

Previous work showed that EFX and PO might conflict if some agents value certain goods at zero. However, many researchers hoped that if every item had at least some positive value to everyone, a "fair and efficient" outcome would always exist. This paper proves that hope was misplaced.

Methods

Finding a counterexample in fair division is like finding a needle in a haystack of possibilities. To do this, the authors employed a modern "agentic harness"—a collaborative AI setup using models like Claude Opus 5.5 and GPT-6 Astra to search through potential valuation profiles.

Once the AI identified a promising 4-agent, 8-good instance, the authors used the mathematical properties of the dihedral group of order 8 (the symmetries of a square) to simplify the proof. By mapping agents to the corners of a square and goods to its edges and diagonals, they reduced a massive search space of 65,536 possible allocations into just a few canonical cases that could be analyzed by hand.

The square representation of agents and goods used to simplify the proof through symmetry.

Datasets

The paper does not use traditional large-scale datasets. Instead, it introduces two precisely engineered valuation matrices that serve as "impossibility proofs":

  • The 4-agent, 8-good instance: The primary counterexample for exact EFX.
  • The 4-agent, 9-good parameterized instance: Used to prove the result for approximate EFX.

Key Insights and Ideas

  • The Singleton Trap: The core "aha moment" is that EFX is incredibly restrictive. To prevent envy, it often forces high-value "large" goods to be allocated as singletons (one item per person).
  • Forced Waste: Because EFX forces these large goods to be held alone, it creates a situation where agents are "starved" of smaller goods they might actually prefer.
  • The Pareto Trade: The authors show that in any EFX allocation for their specific instance, there is always a "carefully choreographed trade" available. For example, an agent holding a large good would gladly trade it for a specific combination of medium and small goods, leaving everyone better off. However, that trade always breaks the EFX condition.
An example of a trade where Agent 2 gains utility, but the resulting allocation (B) is no longer EFX.

Key Results

  • Theorem 1: There exists an instance with 4 agents and 8 goods where no allocation is both EFX and Pareto optimal, even with strictly positive valuations.
  • Theorem 2: The conflict isn't just for perfect EFX. For any approximation factor $\alpha > 2/3$, there are instances where no $\alpha$-EFX allocation is Pareto optimal.
  • Complexity: The search space for the 4-agent/8-good example is $4^8 = 65,536$ allocations. While small enough for a computer to verify, the specific values required to trigger the conflict are subtle, explaining why this remained an open problem for years.
The specific valuation table for the 4-agent, 8-good counterexample.

Limitations and Future Work

  • The Alpha Gap: The authors ruled out compatibility for $\alpha > 2/3$, but it remains unknown if a Pareto optimal $\alpha$-EFX allocation always exists for smaller constants (like $\alpha = 1/2$).
  • Average Case vs. Worst Case: These counterexamples are "pathological"—they are carefully constructed to fail. A major open question is whether EFX and PO are compatible "almost always" in real-world or random scenarios.
  • The "Enigmatic" Question: This paper focuses on the efficiency of EFX, but the most famous open problem in the field—whether an EFX allocation always exists for 4+ agents (regardless of efficiency)—remains unsolved.

Summary updated

Abstract

We consider the problem of allocating indivisible goods to agents with additive valuations, under two classic notions of fairness and efficiency: envy-freeness up to any good (EFX) and Pareto optimality. While some of the earliest work on EFX showed that Pareto optimal EFX allocations may not exist if agents can have zero value for some goods, it has remained open whether the same is true when all values are positive. We present a simple instance in which every good has positive value to every agent, but no Pareto optimal EFX allocation exists. We then generalize to a family of instances showing that Pareto optimal $α$-EFX allocations may not exist for any $α> 2/3$.
BibTeX
@misc{mahabadi2026pareto,
  author = {Sepideh Mahabadi and Prasanna Ramakrishnan and Jakub Tarnawski},
  title = {{Pareto Inefficiency of EFX}},
  year = {2026},
  eprint = {2610.29201},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.29201},
}
Figure