# EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence

arXiv: https://arxiv.org/abs/2606.08872 · HTML: https://mlsanity.com/paper/2606.08872/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2026.

## Built on by (most cited first, 1 of 1)

- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

We consider the fair division problem of indivisible chores and resolve the long-standing open problem for the existence of EFX (envy-free up to any item) allocations with additive cost functions. We show that, even for tri-valued additive cost functions, for every n≥ 4, there exists an instance with n agents where no EFX allocation exists. Our counterexample only uses three types of chores and two types of agents. The numbers of types for chores and agents are both tight: an EFX allocation is known to exist for one type of agents (i.e., with identical cost functions) or two types of chores. We then consider bi-valued instances. We show that, for every n≥ 4, there exists an instance with n agents where every EFX allocation is not Pareto-optimal. This is also the first example showing the incompatibility of EFX and Pareto-optimality when the costs of items are positive: existing examples showing the incompatibility of EFX and Pareto-optimal exploit items with 0 costs. Our result shows such an example exists even for bi-valued instances. The number of agents n is also tight: for n≤ 3, it is known that EFX is compatible with Pareto-optimality. Finally, we also show that an EFX allocation is guaranteed to exist for n=4.