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

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.