The EFX Existence Problem for Indivisible Items

305 concepts183 papers1 proposal

When dividing resources among multiple people, the gold standard of fairness is envy-freeness: an allocation where no agent prefers anyone else's bundle over their own. If the resource is divisible—like a cake or a plot of land—perfect envy-freeness is mathematically guaranteed to exist.

But when the resources are indivisible—such as houses, cars, or specific tasks—perfect envy-freeness is often impossible. If two siblings are dividing a single diamond, one will inevitably get the diamond, and the other will inevitably experience envy.

To handle the messy reality of indivisible items, computer scientists and economists relax the definition of fairness. While the most common relaxations are easy to guarantee, a slightly stricter variant has become the "holy grail" of fair division theory. Its universal existence remains one of the most significant open problems in the field.

From EF1 to EFX: Closing the Loophole

To accommodate indivisibility, researchers introduced Envy-Freeness up to One item (EF1). Under EF1, Agent A might envy Agent B, but that envy must vanish if we hypothetically remove at least one item from Agent B’s bundle. EF1 allocations are highly scalable and always exist; they can be found using a simple round-robin draft.

However, EF1 contains a glaring loophole. Imagine Agent B receives a priceless painting and a cheap plastic pen, while Agent A receives nothing. Agent A deeply envies Agent B. If we hypothetically remove the cheap pen, Agent A still envies Agent B's painting. But if we remove the painting, the envy vanishes entirely. Because there exists a single item (the painting) whose removal eliminates the envy, this allocation technically satisfies EF1.

To close this loophole, researchers proposed a stricter standard: Envy-Freeness up to Any item (EFX). Under EFX, envy must vanish upon the removal of any single item from the envied agent's bundle. In our painting-and-pen example, removing the pen leaves the painting, meaning Agent A would still envy Agent B. Thus, the allocation fails EFX.

Fairness Notion Rule for Eliminating Envy Intuitive Meaning
EF1 Envy must vanish after removing some item. "They only got one major thing more than me."
EFX Envy must vanish after removing any item. "Even if I ignore their least valuable item, I don't envy them."

EFX represents a much more robust and satisfying standard of discrete fairness. The catch? We do not know if an EFX allocation is always guaranteed to exist.

The Boundary of Knowledge

The EFX Existence Problem asks a deceptively simple question: For any set of agents with arbitrary preferences over a set of indivisible items, does a complete EFX allocation always exist?

The answer depends heavily on whether we are allocating goods (items people want) or chores (tasks people want to avoid).

The Case for Goods

For goods, the problem is surprisingly stubborn. In Almost Envy-Freeness with General Valuations, the authors proved that EFX allocations are guaranteed to exist when all agents share identical preferences. However, when three or more agents have distinct, additive preferences, a universal existence proof remains elusive.

As emphasized by Georgios Amanatidis et al. in Maximum Nash Welfare and Other Stories About EFX, proving existence for more than three agents with general valuations is a massive theoretical hurdle. The combinatorial complexity of ensuring that every single pair of agents satisfies the "up to any item" condition simultaneously breaks down standard continuous mathematical tools.

The Case for Chores

When allocating chores, the landscape is even more treacherous. In Unified Fair Allocation of Goods and Chores via Copies, Yotam Gafni et al. established a formal duality framework between goods and chores, yet a general existence proof for arbitrary chore preferences remains missing.

In fact, for chores, the universal guarantee completely breaks down under complex preferences. In On the Pursuit of EFX for Chores: Non-existence and Approximations, the authors settled a long-standing question by constructing a counterexample with three agents and six chores, proving that for general monotone cost functions, EFX allocations can actually fail to exist. Whether they always exist for chores under purely additive cost functions is still an open question.

Why the Existence Proof Matters

The lack of a definitive existence proof creates a domino effect in algorithmic game theory. When designing mechanisms for society, we often want to balance fairness with economic efficiency (social welfare).

In The Price of Fairness for Indivisible Goods, Xiaohui Bei et al. analyzed the "price of fairness"—the total welfare a society must sacrifice to ensure an allocation is fair. Because we can guarantee the existence of EF1 allocations, we can calculate exactly how much efficiency we lose by enforcing them. But because we cannot guarantee that an EFX allocation even exists, we cannot derive general bounds on the efficiency loss associated with this stricter standard.

Bypassing the Problem with Charity

To make progress despite the existence bottleneck, researchers have turned to a clever compromise: charity. If it is impossible to find an EFX allocation that distributes all items, can we find one if we are allowed to leave a few items unallocated?

Ioannis Caragiannis et al. pioneered this approach in Envy-freeness up to any item with high Nash welfare: The virtue of donating items. They proved that for any instance with additive valuations, one can always find an EFX allocation of the remaining items by donating a small subset of items to charity, while still preserving at least half of the maximum possible Nash welfare.

This strategy was later refined using advanced graph theory. In Improving EFX Guarantees through Rainbow Cycle Number, Bhaskar Ray Chaudhury et al. mapped the relationships between agents and bundles to a directed graph. They showed that envies form cycles, and by resolving these cycles, one can achieve EFX by withholding only a sublinear number of goods.

Building on this graph-theoretic framework, Shayan Chashm Jahan in Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap introduced the "rainbow path degree" invariant. This mathematical breakthrough proved that the number of items that must be discarded to guarantee EFX can be minimized to a tiny fraction: at most $O(\sqrt{n \log n})$ goods.

[Agent A] ---> Envies ---> [Agent B]
   ^                          |
   |                          v
[Agent C] <--- Envies <--- [Agent B's Bundle]

   *Envy Cycle Identified* -> Discard an item to break the cycle -> EFX Maintained

By forcing researchers to explore what happens when items are left on the table, the EFX existence problem has driven deep, unexpected insights into graph theory, welfare optimization, and the fundamental boundaries of human envy.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 196 papers
  2. Version 1 · 2026-10-04 · 340 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_efx_existence_problem_7770ce32,
  title = {EFX existence problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efx-existence-problem/rdr_7770ce3214424db0a8c32e03e3b05581},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_efx_existence_problem_7770ce32_v2,
  title = {EFX existence problem},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efx-existence-problem/rdr_7770ce3214424db0a8c32e03e3b05581/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake