Paper proves EFX fair division fails for 4+ agents even with simple chores
A new impossibility result shows no envy-free chore allocation exists for tri-valued costs with 4+ agents.
A new paper by Wentao He and Biaoshuai Tao (arXiv: 2606.08872) tackles the fair division of indivisible chores under additive cost functions, resolving a key open problem for the EFX (envy-free up to any item) criterion. The authors prove that for tri-valued additive cost functions (each chore has one of three possible costs), and for any number of agents n ≥ 4, there exists an instance where no EFX allocation exists. Their counterexample is surprisingly minimal: only three types of chores and two types of agents are needed. This tightens the known boundaries—EFX was previously known to exist for identical agents or two chore types, but the result shows that three types is enough to break existence.
The paper also explores bi-valued instances (only two distinct chore costs). Here, the authors show that for n ≥ 4, there exists an instance where every EFX allocation is not Pareto-optimal, marking the first such demonstration with strictly positive costs. Earlier examples relied on zero-cost chores to violate Pareto-optimality. The number n=4 is tight: for n≤3, EFX is compatible with Pareto-optimality. Finally, the authors provide a positive result: an EFX allocation is guaranteed to exist for n=4 under bi-valued costs, balancing the negative findings.
- For n≥4 agents with tri-valued costs, a counterexample using 3 chore types and 2 agent types shows EFX may not exist.
- First example of EFX-Pareto incompatibility with all positive costs, shown for bi-valued instances with n≥4.
- EFX existence is guaranteed for 4 agents with bi-valued cost functions.
Why It Matters
Settles a foundational limit in fair division theory, with implications for chore allocation algorithms in multi-agent systems.