A Note on EFX Inapproximability for Chores
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918514791546880 |
|---|---|
| author | Christoforidis, Vasilis |
| author_facet | Christoforidis, Vasilis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21448 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Note on EFX Inapproximability for Chores Christoforidis, Vasilis Computer Science and Game Theory 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. |
| title | A Note on EFX Inapproximability for Chores |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2605.21448 |