Source-linked AI summary
Counterexamples to EFX for Submodular and Subadditive Valuations
Simon Mackenzie, Mashbat Suzuki
TL;DR
The paper addresses whether EFX must exist for structured valuation classes and whether failures can be made transparent and human-verifiable. It constructs symmetric three-agent, eight-good counterexamples for weighted coverage and monotone subadditive valuations. The constructions rule out exact EFX in the former class and α-EFX for every α ∈(2^-1/6, 1] in the latter, while leaving explicit open directions for stronger bounds and other submodular classes.
Problem
Whether EFX allocations always exist for familiar, structured valuation classes remains an open question, especially beyond known positive regimes.
Method
The paper constructs symmetric three-agent, eight-good instances whose agents share one valuation template up to relabeling, including a weighted coverage valuation certified through coverage indicators.
Results
The constructions admit no EFX allocation for monotone weighted coverage valuations and no α-EFX allocation for monotone subadditive valuations for any α ∈(2^-1/6, 1].
Takeaways & Limitations
EFX can fail even when agents differ only in how goods are labeled, showing that strong relabeling symmetry still permits these counterexamples.
Takeaways & Limitations
For monotone subadditive valuations, the construction leaves a gap between the known 1/2-EFX guarantee and the ruled-out range above 2^-1/6.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether EFX can fail in structured valuation classes and provides transparent counterexamples. It constructs three-agent, eight-good instances showing exact EFX failure for weighted coverage valuations and approximate EFX failure for monotone subadditive valuations.
- Motivation: EFX is a central relaxation of envy-freeness for indivisible goods, but its universal existence remains unresolved.EFX requires that removing any one good from an envied bundle eliminates the envy.
- Motivation: A prior monotone counterexample used SAT-based search and hundreds of table entries, making its structure difficult to verify by hand.The paper seeks more familiar, structured, and human-verifiable counterexamples.
- Results: Three agents and eight goods suffice for a weighted coverage instance with no EFX allocation, so EFX can fail for monotone submodular valuations.Weighted coverage valuations are a subclass of submodular valuations.
- Results: No allocation is α-EFX for any α ∈(2^-1/6, 1] in a three-agent, eight-good instance with monotone subadditive valuations.The bound 2^-1/6 is approximately 0.891 and places the optimal guarantee between 1/2 and 2^-1/6.
- Construction: Both constructions use agents whose valuations share one template and differ only through cyclic relabeling of the goods.Goods are grouped into types, and agents do not distinguish goods of the same type.
- Context: The examples match the prior construction’s three-agent, eight-good size while offering a more structured symmetry.Related positive results include EFX existence for identical valuations and a three-agent MMS-feasible regime, which these counterexamples do not satisfy.
2 A Cyclic Ordinal Obstruction to EFX
The paper builds a symmetric three-agent, eight-good ordinal instance whose monotone preferences admit no EFX allocation. Cyclic relabelling reduces the proof to a few bundle-size patterns, each ruled out by strong envy.
- Ordinal formulation: The construction uses monotone weak preferences represented by rank functions, with EFX requiring each bundle to rank at least as highly as every one-good deletion from another bundle.Indifference classes receive equal ranks, and larger bundles never receive lower ranks.
- Cyclic construction: The instance has three agents and eight goods, and agents 1 and 2 obtain their preferences from agent 0 by cyclically relabelling goods.Thus, all agents share the same preference structure up to relabelling.
- Base weak order: The base order assigns ranks to singletons and pairs, gives exceptional triples rank 7, and extends larger bundles using internal ranks.The first six goods form types A, B, and C, while x and y are additional goods.
- Monotonicity: The rank functions are monotone, so the ordinal construction satisfies the required monotonicity condition for every agent.Monotonicity for the relabelled agents follows from monotonicity of the base rank function.
- Combinatorial reduction: Cyclic symmetry lets the proof restrict attention to representative bundle-size patterns after ruling out allocations containing a bundle of size at most one.With eight goods and three agents, the remaining patterns are (2, 2, 4) and (2, 3, 3).
- Non-existence proof: Both remaining patterns fail EFX: in every case, some agent strongly envies another after deleting a suitable good.The proof establishes this separately for patterns (2, 2, 4) and (2, 3, 3), completing the non-existence result.
3 Weak Preferences to Submodular and Subadditive Valuations
The paper transfers an ordinal non-existence obstruction to explicit monotone subadditive and weighted-coverage valuations. The constructions preserve strict bundle comparisons, establishing both an approximate-EFX barrier and exact EFX non-existence.
- Transfer from ordinal preferences: A cardinal profile preserving the strict part of an ordinal preference profile with no EFX allocation also has no EFX allocation.The transfer uses any allocation that violates ordinal EFX and converts the surviving strict comparison into a cardinal envy comparison.
- Subadditive realization: The valuation profile is normalised, monotone, and subadditive.The construction assigns zero to the empty set and uses λ<1 to obtain monotonicity; bounded values establish subadditivity.
- Subadditive realization: For every α ∈(2^-1/6, 1], the constructed subadditive profile admits no α-EFX allocation.A one-rank gap yields vi(S)<αvi(T) whenever α exceeds λ=2^-1/6, contradicting α-EFX.
- Weighted-coverage realization: The weighted-coverage realization depends only on the five represented types, reducing consistency verification to 32 type supports.The exhaustive support table is a finite certificate that coverage values strictly preserve the rank order.
- Weighted-coverage realization: The weighted-coverage profile is normalised, monotone, and submodular, and it admits no EFX allocation.The other agents’ valuations are cyclic relabellings, while strict-order preservation transfers ordinal EFX non-existence.
4 Discussion and Open Directions
The discussion emphasizes structured, symmetric constructions as a human-verifiable route to EFX counterexamples. It identifies approximation gaps and broader valuation classes, agent counts, and symmetry assumptions as open directions.
- Construction strategy: Typed goods and cyclic symmetry reduce the non-existence proof to a small case analysis over bundle types.The proof uses ordinal rankings before realizing them with cardinal valuations.
- Construction strategy: Ordinal profiles with no EFX allocation can be sought first and then realized, or slightly modified, within a target valuation class.The paper demonstrates this strategy for monotone subadditive and weighted-coverage valuations.
- Symmetry: Agents identical up to relabeling still yield no-EFX instances for both subadditive and weighted-coverage valuations.All agents share one valuation template and differ only by permutations of the goods.
- Open directions: For subadditive valuations, the known 1/2-EFX guarantee remains separated from the construction’s exclusion of every α∈(2^-1/6, 1].Closing this gap may require more goods or agents, a different obstruction, or cardinal information beyond ordinal rank gaps.
- Open directions: Future work includes testing other structured submodular classes and seeking genuinely four-agent obstructions.Gross substitutes, OXS, and four-way interactions are identified as possible directions.