Counterexamples to EFX for Submodular and Subadditive Valuations
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913098998218752 |
|---|---|
| author | Mackenzie, Simon Suzuki, Mashbat |
| author_facet | Mackenzie, Simon Suzuki, Mashbat |
| contents | The existence of EFX allocations is a fundamental question in fair division. In this paper, we construct a three-agent, eight-good instance with monotone subadditive valuations such that no allocation satisfies $α$-EFX for any $α> \frac{1}{\sqrt[6]{2}} \approx 0.89$. We also provide a closely related three-agent, eight-good instance with submodular (in fact weighted coverage) valuations for which no EFX allocation exists.
A key feature of our construction is its symmetry: the agents' valuations are identical up to a relabeling of the goods. Thus, EFX can fail even when agents differ only in how the goods are labeled. This symmetry makes the counterexamples compact and human-verifiable, yielding simple combinatorial obstructions to the existence of EFX. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06451 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Counterexamples to EFX for Submodular and Subadditive Valuations Mackenzie, Simon Suzuki, Mashbat Computer Science and Game Theory Theoretical Economics The existence of EFX allocations is a fundamental question in fair division. In this paper, we construct a three-agent, eight-good instance with monotone subadditive valuations such that no allocation satisfies $α$-EFX for any $α> \frac{1}{\sqrt[6]{2}} \approx 0.89$. We also provide a closely related three-agent, eight-good instance with submodular (in fact weighted coverage) valuations for which no EFX allocation exists. A key feature of our construction is its symmetry: the agents' valuations are identical up to a relabeling of the goods. Thus, EFX can fail even when agents differ only in how the goods are labeled. This symmetry makes the counterexamples compact and human-verifiable, yielding simple combinatorial obstructions to the existence of EFX. |
| title | Counterexamples to EFX for Submodular and Subadditive Valuations |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2605.06451 |