Existence of EFX Allocations

The classic problem in fair division involves dividing a set of goods among a set of people in a fair way. A key question is what it means for an allocation of goods to be fair. One such notion is that of envy-freeness.

Suppose we have a set $N = \{1, \ldots, n\}$ of $n$ agents and a set $M = \{g_1, \ldots, g_m\}$ of $m$ goods. Every agent $i$ has a preference function $v_i$, where $v_i(g_j)$ represents how much agent $i$ values good $g_j$. An allocation is a partition of $M$ into $n$ sets $(X_1, \ldots, X_n)$, where $X_i \subseteq M$ is the set of goods given to agent $i$. The allocation $(X_1, \ldots, X_n)$ is envy-free if, for every $i$ and $j$,

$$\sum_{g \in X_i} v_i(g) \geq \sum_{g \in X_j} v_i(g).$$

That is, for every $i$, agent $i$ values their set of goods $X_i$ at least as much as any other agent’s set of goods $X_j$, so no one is envious of anyone else.

It is known that envy-free allocations do not always exist. For instance, if there are two agents and one object, and both agents want the object, there is no way to specify an envy-free allocation.

A modification of the notion of envy-freeness is called envy-freeness up to any good (EFX). Here, the guarantee is that for every $i$ and $j$, and for every $g^* \in X_j$,

$$\sum_{g \in X_i} v_i(g) \geq \sum_{g \in X_j \setminus g^*} v_i(g).$$

That is, for every $i$, agent $i$ does not envy anyone else if we remove any one of their goods.

Read more about EFX allocations here, where Ariel Procaccia says that, in his view, EFX “is the successor of envy-free cake cutting as fair division’s biggest problem.”

Chaudhury, Garg, and Mehlhorn proved that EFX allocations always exist for three agents with additive valuations (which means that the value of a set of goods is equal to the sum of the values of each good, as we implicitly assume above). This problem asks whether EFX allocations always exist.

In particular, this problem asks for a counterexample: an instance of at least four agents, goods, and preferences for which there is no EFX allocation.

A recent paper from June 2026 showed that, in the additive case, there is an example with $n$ agents for every $n \geq 4$ such that no EFX allocation exists when allocating chores instead of goods. (The difference is that agents want to value their allocation of chores less than others’.) This gives some evidence that such counterexamples might exist for EFX allocations of goods, too.

The main risk with this problem is that no such counterexample exists: maybe there is always an EFX allocation. Another risk is that the instance is too large to be computationally verified.