Envy-freeness up to any item

Envy-freeness up to any item (EFX) is a fairness notion in fair item allocation. It is a relaxation of envy-free item allocation. Determining whether EFX allocations always exist is widely regarded as the central open problem in the theory of fair item allocation.¹

In the classical fair division problem, a set of indivisible items must be allocated among a group of agents, each with their own preferences over subsets of items. An allocation assigns every item to exactly one agent. A valuation function describes how agent i values any bundle of items. Valuations are typically assumed to be monotone (adding items never decreases value) and often additive (the value of a bundle equals the sum of the values of its items).

An allocation is envy-free (EF) if no agent prefers another agent's bundle to their own. Envy-free allocations do not always exist when items are indivisible — for instance, a single valuable item cannot be shared between two agents without creating envy. This motivates the study of relaxations of fairness notions.

A standard relaxation is envy-freeness up to one good (EF1), introduced by Budish:² an allocation is EF1 if any envy agent i has toward agent j can be eliminated by hypothetically removing some single item from j's bundle. EF1 allocations always exist and can be computed in polynomial time (see envy-free item allocation).

Envy-freeness up to any good (EFX) is a strictly stronger notion than EF1. It was introduced in 2016 by Caragiannis, Kurokawa, Moulin, Proaccia, Shah and Wang³⁴ in their study of maximum Nash welfare allocations. An allocation is EFX if for every pair of agents i and j, and for every item g in j's bundle that agent i values positively, removing g from j's bundle would eliminate i's envy.

In contrast to EF1, which requires only the existence of some item whose removal eliminates envy, EFX requires that removing any positively valued item from the envied bundle would suffice. The good is not actually removed — this is a thought experiment used to define the fairness condition.

Caragiannis et al. described EFX as "arguably the best fairness analog of envy-freeness for indivisible items."⁴ The question of whether EFX allocations always exist was immediately recognized as a fundamental open problem, and has been called "fair division's most enigmatic question."¹

The first general existence result for EFX was established by Plaut and Roughgarden in 2018.⁵⁶ They showed that an EFX allocation always exists for two agents with arbitrary monotone valuations, via a simple adaptation of the classical cut-and-choose protocol. Agent 1 splits all items into two bundles so as to maximize her minimum value across the two bundles — that is, she finds the partition that makes the worse bundle as valuable as possible from her own perspective. Agent 2 then picks whichever bundle she prefers, and agent 1 receives the other.

The key observation is that this optimal split guarantees both bundles are EFX-feasible for agent 1: if removing any single item from either bundle left that bundle strictly more valuable than the other, agent 1 could have moved that item across beforehand and obtained a better-balanced partition — contradicting optimality. Since this holds for both bundles, agent 1 is EFX-satisfied no matter which bundle agent 2 takes. Agent 2, having chosen her favorite bundle, does not envy agent 1 at all, and is therefore EFX-satisfied trivially.

In contrast to EF1, which requires a number of queries logarithmic in the number of items, computing an EFX allocation may require a linear number of queries even when there are two agents with identical additive valuations.⁷ For two agents with general monotone valuations, computing an EFX allocation may require an exponential number of queries.⁵⁶

Another difference between EF1 and EFX is that the number of EFX allocations can be as few as 2 (for two agents and any number of items), while the number of EF1 allocations is always exponential in the number of items.⁸

The existence of EFX allocations for three or more agents with non-identical valuations was a major open problem, noted by Plaut and Roughgarden as "highly non-trivial even for three players with different additive valuations."⁶

A breakthrough⁹¹⁰¹¹ was established at 2020 by Chaudhury, Garg, and Mehlhorn,¹²¹³ who proved that an EFX allocation always exists for three agents with additive valuations. The core difficulty compared to the two-agent case is that any transfer of goods between two agents' bundles inevitably affects the third agent's envy relationships as well — a change that fixes one agent's envy may create or worsen another's. The proof maintains a partial EFX allocation in which some goods may be left temporarily unallocated, and resolves envy by a combination of transfers along envy cycles and carefully controlled augmentations from the unallocated pool, tracked by a lexicographic potential function that strictly increases at each step and guarantees termination. The argument makes heavy use of the additive structure of the valuations and does not extend to four or more agents.

The result was subsequently extended and simplified by Akrami, Alon, Chaudhury, Garg, Mehlhorn, and Mehta,¹⁴¹⁵ who showed it holds even when two of the three agents have arbitrary monotone valuations and only one is required to be additive.

Both algorithms run in pseudo-polynomial time (polynomial in the number of items and the highest utility an agent assigns to an item). Whether a polynomial-time algorithm exists remains an open question.¹⁰

Since exact EFX allocations are not known to always exist for general instances, a substantial body of work has focused on approximations, relaxations, and restricted settings.

For a parameter α ∈ [0,1], an allocation is α-EFX if for every pair of agents i and j and every positively valued item g in j's bundle, agent i's value for their own bundle is at least α times their value for j's bundle after removing g. Thus 1-EFX coincides with exact EFX, and larger α corresponds to a stronger guarantee.

A 1/2-approximate EFX allocation (that also satisfies a different approximate-fairness notion called Maximin Aware) can be found in polynomial time.¹⁶

The best known approximation for general additive valuations is (φ − 1) ≈ 0.618-EFX, where φ = (1+√5)/2 is the golden ratio, achieved via a variant of the envy-graph procedure in polynomial time. Their algorithm also guarantees EF1 and an 2/(φ+2) approximation to group maximin share.¹⁷¹⁸

Improving beyond the (φ − 1) factor remains an important open problem. Under additional ordinal assumptions — specifically, when agents agree on which n items are the most valuable — a 2/3-EFX allocation was shown to exist.¹⁹

A natural relaxation allows some goods to remain unallocated, donated to a "charity". Obviously, donating all items yields an envy-free allocation, which is trivially EFX. The challenge is to attain EFX together with some welfare guarantees.

Caragiannis, Gravin and Huang proved that, when all agents have additive valuations, there exists a partial EFX allocation that achieves at least half of the maximum Nash welfare.²⁰

This was strengthened to show that a partial EFX allocation with at most n−1 unallocated goods always exists for any number of agents with general monotone valuations (for additive valuations, this allocation also attains at least half of the maximum Nash welfare).²¹²²

Subsequently, it was shown that four agents always admit an EFX allocation with at most one unallocated good, and n ≥ 5 agents with at most n−2 unallocated goods.²³

An elegant connection between approximate EFX allocations and a combinatorial graph-theoretic problem called the rainbow cycle number was introduced.²⁴²⁵ For a given integer d, the rainbow cycle number R(d) is the largest k such that there exists a k-partite directed graph satisfying: (1) every part has at most d vertices; (2) for every pair of parts i and j, each vertex in i has an incoming edge from some vertex in j; and (3) the graph contains no rainbow cycle — that is, no directed cycle that visits each part at most once. It was shown that bounding the rainbow cycle number polynomially in d yields approximate EFX allocations with sublinearly many unallocated goods. The initial bound gave (1−ε)-EFX existence with O((n/ε)^4/5) unallocated goods, for any ε>0.²⁴²⁵ A subsequent near-linear bound on the rainbow cycle number tightened this to Õ((n/ε)^1/2) unallocated goods.²⁶²⁷

It remains open whether an EFX allocation exists with a sub-linear number of unallocated goods.¹⁰

For any positive integer k, EFkX is a weakening of EFX allowing removal of up to any k items.

EF2X allocations are known to exist for n=4 agents with additive valuations.²⁸ For restricted additive valuations — where each agent values every good at either 0 or a good-specific amount — EF2X allocations were shown to always exist.²⁹

It remains open whether there is any constant k such that EFkX allocations exist for all n and all additive valuations.

EFX allocations are also known to exist in several restricted valuation settings. When each agent's value for every item takes one of at most two possible values, the maximum Nash welfare allocation is always EFX, and an explicit polynomial-time algorithm was given.³⁰³¹

When all agents share one of two possible additive valuation functions, EFX was shown to always exist;³² this was extended to two monotone valuations,³³ and to three distinct additive valuation functions.³⁴

EFX is also known to exist for lexicographic preferences and for graph-structured allocation settings.³⁵