Math Conjectures

Complete EFX allocation for additive goods

OPENMajorConjectureProposed 2016 · Full conjecture

Canonical statement

For every finite agent set NN, finite set MM of indivisible goods, and nonnegative additive valuations vi(S)=∑g∈Svi(g)v_i(S)=\sum_{g\in S}v_i(g), there is a partition (Xi)i∈N(X_i)_{i\in N} of MM such that, for all i,j∈Ni,j\in N and every g∈Xjg\in X_j,
vi(Xi)≥vi(Xj∖{g}). v_i(X_i)\ge v_i(X_j\setminus\{g\}).
View source LaTeX
For every finite agent set \(N\), finite set \(M\) of indivisible goods, and nonnegative additive valuations \(v_i(S)=\sum_{g\in S}v_i(g)\), there is a partition \((X_i)_{i\in N}\) of \(M\) such that, for all \(i,j\in N\) and every \(g\in X_j\),
\[
v_i(X_i)\ge v_i(X_j\setminus\{g\}).
\]
GAME-002:[CaragiannisEtAl2019MNW][ChaudhuryEtAl2021Charity][ChaudhuryGargMehlhorn2024Three][AfshinmehrEtAl2026Multigraph]
Game theory and mathematical economicsTheoretical computer science

Notes

The conjecture concerns the fair division of indivisible goods. An allocation is envy-free up to any good (EFX) if no agent envies another agent's bundle once any single good is removed from it: formally, vi(Xi)≥vi(Xj∖{g})v_i(X_i)\ge v_i(X_j\setminus\{g\}) for all agents i,ji,j and every good g∈Xjg\in X_j. Posed in 2016 by Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang [CaragiannisEtAl2019MNW], the conjecture asserts that for additive valuations a complete EFX allocation — one distributing every good — always exists.

Existence is known for at most three additive agents, the three-agent case being a theorem of Chaudhury, Garg and Mehlhorn [ChaudhuryGargMehlhorn2024Three]. If a few goods may be left unallocated, almost envy-free allocations exist for any number of agents [ChaudhuryEtAl2021Charity], and complete EFX allocations exist for several structured valuation classes, most recently on multigraphs [AfshinmehrEtAl2026Multigraph].

For four or more agents with arbitrary additive valuations, the general theorems currently available either donate some goods to charity or weaken the EFX guarantee by a factor, and whether a complete exact EFX allocation always exists remains open.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.