Envy-Freeness up to Any Item for Indivisible Goods

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2340 papers455 conceptsfrozen 2026-10-04

Fair division is simple when resources are infinitely divisible, like a cake or a plot of land. But when we divide indivisible items—like cars, houses, or specific tasks—perfect fairness is often mathematically impossible. If two people want the same diamond, one will inevitably be envious of the other.

To handle this, researchers have developed "relaxations" of fairness. The most prominent is Envy-Freeness up to one item (EF1), which says that Alice doesn't envy Bob if she can remove one item from Bob's bundle to make things even. While EF1 is well-understood and always exists, the field is currently chasing a much more elusive and robust standard: Envy-Freeness up to Any item (EFX).

The EFX Holy Grail

The intuition behind EFX is a stricter version of the "one item" rule. In EF1, Alice's envy must vanish if she removes the most valuable item from Bob's bundle. In EFX, Alice's envy must vanish if she removes any item from Bob's bundle—even the one she values the least.

As Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos describe in Multiple Birds with One Stone, EFX is considered the "holy grail" of fair division. Despite its intuitive appeal, proving that an EFX allocation always exists for more than three agents remains one of the most significant open problems in the field.

Currently, we know EFX exists for specific cases:

  • Small groups: It is proven for up to three agents.
  • Limited preferences: Pratik Ghosal and colleagues showed in (Almost Full) EFX for Three (and More) Types of Agents that if agents share only a few distinct valuation types, EFX allocations (or near-EFX allocations with very few discarded goods) are guaranteed.
  • Restricted Valuations: Under "leveled valuations," where quantity matters more than quality, George Christodoulou and Vasilis Christoforidis proved in Fair and Truthful Allocations Under Leveled Valuations that exact EFX is always achievable.

The Price of Being Fair

If we insist on fairness, how much total "happiness" (social welfare) do we lose? This is known as the Price of Fairness.

In Settling the Price of Fairness for Indivisible Goods, Nisarg Shah and Umang Bhaskar established that for $n$ agents, the efficiency loss for EF1 is exactly $\Theta(\sqrt{n})$. This means as the number of participants grows, the gap between a "fair" outcome and a "maximum happiness" outcome widens predictably.

However, because we still don't know if EFX always exists for large groups, the Price of Fairness for EFX remains a theoretical mystery. Xiaohui Bei and Warut Suksompong note in The Price of Fairness for Indivisible Goods that without a guaranteed existence theorem, we cannot derive general bounds on how much efficiency we must sacrifice for this stricter standard.

From Goods to Chores

Fairness isn't just about sharing toys; it's also about sharing housework. Dividing "chores" (items with negative utility) is mathematically distinct from dividing "goods."

Yotam Gafni, Xin Huang, and Ron Lavi attempted to bridge this gap in Unified Fair Allocation of Goods and Chores via Copies, showing that chores can be modeled as "goods with multiple copies." Despite this bridge, EFX for chores is even harder to guarantee. Shengwei Zhou and Xiaowei Wu provided the first approximation algorithms for EFX chores in Approximately EFX Allocations for Indivisible Chores, but the exact existence for three or more agents remains unsolved.

Group Fairness and Externalities

The research is also moving beyond individual envy to Groupwise Maximin Share (GMMS). As Arpita Biswas and Y. Narahari argue in Groupwise Maximin Fair Allocation of Indivisible Goods, fairness should hold for any subgroup of agents. If a group of friends splits a set of items, no smaller clique within that group should feel they were collectively shortchanged.

Finally, new frontiers involve externalities—where Alice cares not just about her bundle, but about whether Bob or Charlie got the item she hates. Eduard Eiben and Argyrios Deligkas showed in The Complexity of Fair Division of Indivisible Items with Externalities that these social dynamics make finding fair allocations significantly harder, often pushing the problem into NP-completeness even for small groups.

Why It Works: The Intuition of Removal

The power of the EFX/EF1 framework lies in its simplicity. By defining fairness through the removal of items, we bypass the need for complex interpersonal utility comparisons. We don't need to know exactly how much Alice values a diamond compared to Bob; we only need to know that if we take the diamond away, Alice no longer feels Bob's bundle is better than hers. This "item-based" relaxation provides a concrete algorithmic path toward equitable distribution in a world where things cannot be perfectly split.

Papers in this version

Showing 60 of 340 papers.

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 1, frozen text):

@misc{lacuna_envy_freeness_up_to_any_item_for_indivis_7770ce32_v1,
  title = {Envy-Freeness up to Any Item for Indivisible Goods},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/envy-freeness-up-to-any-item-for-indivisible-goods/rdr_7770ce3214424db0a8c32e03e3b05581/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}