Recognition: unknown
Counterexamples to EFX for Submodular and Subadditive Valuations
Pith reviewed 2026-05-08 04:11 UTC · model grok-4.3
The pith
Counterexamples show that EFX allocations fail to exist for symmetric submodular valuations over three agents and eight goods.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors exhibit a three-agent eight-good instance with monotone subadditive valuations in which no allocation satisfies alpha-EFX for any alpha larger than one over the sixth root of two, approximately 0.89. They give a closely related instance with submodular valuations for which no EFX allocation exists at all. The symmetry of the valuations, identical up to permutation of the goods, produces simple combinatorial obstructions that block every possible allocation.
What carries the argument
Symmetric monotone subadditive and submodular valuation functions on eight goods for three agents, whose structure forces every allocation to violate the EFX or alpha-EFX condition upon exhaustive enumeration.
If this is right
- EFX allocations are not guaranteed to exist for submodular valuations even when the instance has only three agents.
- For monotone subadditive valuations the strongest approximation factor achievable in this instance is at most approximately 0.89.
- Symmetry of valuations across agents is insufficient to guarantee an EFX allocation.
- The small size and symmetry of the instances make the obstructions to EFX human-verifiable by direct checking.
Where Pith is reading between the lines
- The construction suggests that search for EFX allocations in submodular settings may need to rely on different techniques or weaker fairness notions than those sufficient for additive valuations.
- Similar symmetric obstructions could be used to derive non-existence results for other fairness criteria in fair division.
- The bound of roughly 0.89 may motivate investigation into the exact worst-case approximation ratio for EFX under subadditive valuations.
Load-bearing premise
The constructed valuation functions are correctly monotone subadditive or submodular and the complete list of allocations has been checked to violate the stated EFX property.
What would settle it
Discovery of any allocation of the eight goods to the three agents in the given instance that satisfies EFX for the submodular valuations or alpha-EFX with alpha greater than 0.89 for the subadditive valuations.
read the original abstract
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 $\alpha$-EFX for any $\alpha > \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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs a symmetric three-agent eight-good instance with monotone subadditive valuations such that no allocation satisfies α-EFX for any α > 1/2^{1/6} ≈ 0.89, and a closely related three-agent eight-good instance with submodular (weighted coverage) valuations admitting no EFX allocation at all. Symmetry across agents up to good relabeling is used to obtain compact, combinatorially verifiable obstructions via exhaustive enumeration of allocations.
Significance. If the constructions are correct, the work supplies the first explicit counterexamples showing EFX can fail for submodular valuations and a concrete approximation threshold for subadditive valuations. The symmetric design is a clear strength: it keeps the instance small, reduces the enumeration burden, and yields human-checkable combinatorial arguments rather than opaque computer search. This advances the boundary between existence and non-existence results in fair division beyond additive valuations.
major comments (1)
- The central claims rest on the explicit monotone subadditive (resp. submodular) valuation tables and the assertion that exhaustive enumeration finds no qualifying allocation. The manuscript must present the full valuation functions (value of every subset for each agent) in a table or appendix, together with a clear account of how symmetry reduces the cases that need checking, so that the subadditivity/submodularity and the non-existence statements can be independently verified.
Simulated Author's Rebuttal
We thank the referee for the positive assessment of our constructions and for the constructive suggestion to enhance verifiability. We address the single major comment below.
read point-by-point responses
-
Referee: The central claims rest on the explicit monotone subadditive (resp. submodular) valuation tables and the assertion that exhaustive enumeration finds no qualifying allocation. The manuscript must present the full valuation functions (value of every subset for each agent) in a table or appendix, together with a clear account of how symmetry reduces the cases that need checking, so that the subadditivity/submodularity and the non-existence statements can be independently verified.
Authors: We agree that full explicit tables and a detailed symmetry-reduction argument will make the claims independently verifiable. In the revised manuscript we will add a dedicated appendix that lists the value of every subset for each of the three agents. We will also expand the main text (and appendix) with a precise combinatorial account of how the symmetry—agents’ valuations being identical up to good relabeling—partitions allocations into a small number of equivalence classes. This reduces the cases that must be checked to a handful of representative allocations whose EFX violations can be verified by direct (hand) computation, confirming both the subadditivity/submodularity properties and the non-existence of α-EFX allocations above the stated threshold. revision: yes
Circularity Check
No significant circularity: explicit counterexample construction
full rationale
The paper's central contribution is an explicit construction of symmetric monotone subadditive (and separately submodular) valuation functions on three agents and eight goods, followed by exhaustive enumeration showing that no allocation meets the stated EFX or α-EFX threshold. This is a direct, self-contained counterexample against external definitions of EFX; no step reduces a claimed prediction or theorem to a fitted parameter, self-definition, or self-citation chain. The symmetry is invoked only for compactness and human verifiability of the combinatorial obstructions, not as a load-bearing assumption that presupposes the result. The argument is independent of prior author work and does not rename known patterns or smuggle ansatzes.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Valuations are monotone and subadditive (or submodular) as standardly defined in the fair division literature.
Reference graph
Works this paper leans on
-
[1]
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=
Compatibility of fairness and nash welfare under subadditive valuations , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=
2026
-
[2]
Communications of the ACM , publisher =
Technical perspective: An answer to fair division's most enigmatic question , author =. Communications of the ACM , publisher =
-
[3]
Econometrica , volume = 16, number = 1, pages =
The Problem of Fair Division , author =. Econometrica , volume = 16, number = 1, pages =
-
[4]
and Kurokawa, D
Caragiannis, I. and Kurokawa, D. and Moulin, H. and Procaccia, A. and Shah, N. and Wang, J. , year = 2016, booktitle =. The Unreasonable Fairness of Maximum
2016
-
[5]
2026 , eprint =
Hannaneh Akrami and Alexander Mayorov and Kurt Mehlhorn and Shreyas Srinivas and Christoph Weidenbach , title =. 2026 , eprint =
2026
-
[6]
2022 , eprint =
Hannaneh Akrami and Noga Alon and Bhaskar Ray Chaudhury and Jugal Garg and Kurt Mehlhorn and Ruta Mehta , title =. 2022 , eprint =
2022
-
[7]
Proceedings of the Thirty-Fifth
Moshe Babaioff and Tomer Ezra and Uriel Feige , title =. Proceedings of the Thirty-Fifth. 2021 , doi =
2021
-
[8]
2023 , eprint =
Xiaolin Bu and Jiaxin Song and Ziqi Yu , title =. 2023 , eprint =
2023
-
[9]
The Unreasonable Fairness of Maximum
Ioannis Caragiannis and David Kurokawa and Herv. The Unreasonable Fairness of Maximum. ACM Transactions on Economics and Computation , volume =. 2019 , doi =
2019
-
[10]
Journal of the ACM , volume =
Bhaskar Ray Chaudhury and Jugal Garg and Kurt Mehlhorn , title =. Journal of the ACM , volume =. 2024 , doi =
2024
-
[11]
Proceedings of the Thirty-Fifth
Bhaskar Ray Chaudhury and Jugal Garg and Ruta Mehta , title =. Proceedings of the Thirty-Fifth. 2021 , doi =
2021
-
[12]
Near Fairness in Matroids , booktitle =
Laurent Gourv. Near Fairness in Matroids , booktitle =. 2014 , doi =
2014
-
[13]
SIAM Journal on Discrete Mathematics , volume =
Benjamin Plaut and Tim Roughgarden , title =. SIAM Journal on Discrete Mathematics , volume =. 2020 , doi =
2020
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.