Theorem 1.1 — three agents with weighted-coverage valuations over eight goods admit no EFX allocation
ProvedEFXCounterex.Submodular.theorem_1_1counterexampleefxfair-divisionp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-coverage
There is a valuation profile for three agents and eight goods in which every is a weighted-coverage valuation (finitely many features, nonnegative weights, a bundle worth the total weight of the features its goods cover) and no allocation (pairwise disjoint bundles covering all eight goods) is EFX for . The paper proves it as the proof of Theorem 1.3 (p. 15) at , : Theorem 3.4, then the strictification of §3.2.2, then Lemma 3.7 (Lemma 3.5 is not needed).
Differences from the source:
- encoding: an allocation is a tuple of pairwise disjoint bundles whose union is M (empty bundles allowed, no unallocated goods) → X : Fin n → Finset (Fin m) with IsAllocation X := LittleCharity.EFX.IsPartialAllocation X ∧ LittleCharity.EFX.pool X = ∅; reason: pairwise disjoint plus empty pool (no unallocated good) is exactly 'union is M'
- encoding: "a fair division instance with three agents and eight goods in which all agents have weighted coverage valuations" → w : Fin 3 → Finset (Fin 8) → ℝ with IsWeightedCoverage (w i) for every i (features Fin k); reason: weighted-coverage values are nonnegative sums, so ℝ-valued is the same; any finite feature set is some Fin k
Preamble
import Mathlib import Definitions.Def_LittleCharity_EFX_Setting import Definitions.Def_EFXCounterex_Submodular_Setting
Formal statement
namespace EFXCounterex.Submodular
/-- Theorem 1.1 (p. 2). There is a fair-division instance with three agents and eight goods in
which every agent has a weighted-coverage valuation and no (complete) allocation is EFX. -/
theorem theorem_1_1 :
∃ w : Fin 3 → Finset (Fin 8) → ℝ,
(∀ i, IsWeightedCoverage (w i)) ∧
∀ X : Fin 3 → Finset (Fin 8), IsAllocation X → ¬ LittleCharity.EFX.IsEFX w X := by sorry
end EFXCounterex.Submodular
Source
Akrami, Mackenzie, Mayorov, Mehlhorn, Srinivas, Suzuki, Weidenbach 2026, Counterexamples to EFX for Submodular and Subadditive Valuations, arXiv:2605.06451 (supplied manuscript, sha256 700243a1…), Theorem 1.1, p. 2 (proof: proof of Theorem 1.3, p. 15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.