A Note on EFX Inapproximability for Chores
This work provides the first explicit constant-factor lower bounds on EFX approximation for chores under complement-free cost functions, addressing a gap in fair division theory.
The authors prove that for indivisible chores with subadditive cost functions, no α-EFX allocation exists for α < 2^{1/3} ≈ 1.26, and for submodular costs, no α-EFX allocation exists for α < 20/19, establishing constant-factor inapproximability results that narrow the gap with the known upper bound of 2.
We study the approximability of EFX allocations for indivisible chores under complement-free cost functions. The non-existence of exact EFX allocations for general monotone functions for chores is known from \cite{CS24}, and a result of \cite{akrami2026} transfers such comparison-based non-existence results to monotone submodular, and hence subadditive, functions. We strengthen this picture by giving explicit constant-factor inapproximability results for submodular and subadditive functions. Our main construction is a three-agent, six-chore instance with monotone subadditive cost functions for which no $α$-EFX allocation exists for any $1\le α<2^{1/3}\approx 1.26$, thus narrowing the gap with the known upper bound of $2$. The construction is obtained by refining the original counterexample of \cite{CS24} and using the approach of \cite{mackenzie2026}. We also give a weighted-coverage realization of the ordinal profile, yielding an instance in which no $α$-EFX allocation exists for any $1\le α<20/19$ under submodular costs. Thus, even within well-studied complement-free classes, EFX for chores admits nontrivial constant lower bounds on approximability.