A Note on EFX Inapproximability for Chores

Abstract

We study the approximability of envy-free up to any item (EFX) allocations for indivisible chores under complement-free cost functions. Our main result is an instance with $255$ agents and $764$ chores with binary XOS cost functions, in which no $\alpha$-EFX allocation exists for any $1\le \alpha <2$. The construction is based on a combinatorial expansion property of binary labels, obtained using Sidon sets and Reed--Solomon codes. We formalize the main result in Lean 4. We also study the special case of three agents. We construct a six-chore instance with monotone subadditive cost functions for which no $\alpha$-EFX allocation exists for any $1\le \alpha <2^{1/3}$, and a six-chore instance with monotone submodular cost functions for which no $\alpha$-EFX allocation exists for any $1\le \alpha <20/19$. These constructions are obtained by refining the original counterexample of \cite{CS24}.

arXiv comment13 pages. Added the binary XOS lower bound and Lean 4 formalization; revised exposition and references