efx_three_small_goods_obstruction_no_current_ir
In the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than her current utility threshold.
Statement
theorem efx_three_small_goods_obstruction_no_current_ir (p : Fin 7 → Fin 4) (hEF : is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ)) (efx_three_small_goods_obstruction_coarse p)) : ∃ i : Fin 4, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ)) (bundle_of (efx_three_small_goods_obstruction_coarse p) i) < (efx_three_small_goods_obstruction_threshold i : ℝ)
- Source
- Route obstruction for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Experiments 11265, 11268, and 11269. The last independently exhausts all 16384 full coarse assignments and all 1152 old-permutation two-bonus states; a row scaling removes a welfare-maximizer tie. General Pareto-monotone EFX completion barriers are already known in arXiv:2002.05119v3 Section 5. This explicit three-universally-small-goods example constrains maximum-sum two-bonus completion, not EFX existence or the original-diagonal three-bonus conjecture, and carries no research-level novelty claim.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- efx_three_small_goods_obstruction_valuesThe explicit positive four-agent eleven-good natural-valued matrix from experiment 11269, with four old adjacent pairs among goods 0…
- efx_three_small_goods_obstruction_coarseAn allocation of the eleven goods obtained by assigning each of the four old adjacent pairs intact to arbitrary agents p(0),...,p(3), and…
- efx_three_small_goods_obstruction_thresholdThe four current utility thresholds (883,1992,800,800), attained by the starting EFX allocation of the first ten goods in the explicit…
- efx_three_small_goods_obstruction_no_natNo coarse allocation of the explicit eleven-good instance both weakly preserves the current utility thresholds and satisfies every…
- is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
- additive_valuation_bundle_sum_iteAn additive value of an allocated bundle equals the sum over all goods of the item value when that good has the specified owner, and zero…
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 1
- efx_three_small_goods_completion_loss_or_splitIn the explicit eleven-good instance cast to real values, every complete EFX allocation which keeps each of the four old adjacent pairs…
The proof, explained
The proof proceeds by contradiction. Assuming no agent falls strictly below her threshold means that every agent achieves at least her threshold utility. Combined with the assumption that the allocation is EFX, both conditions of feasibility over the natural numbers are satisfied once cast from the real numbers. This contradicts the known obstruction theorem `efx_three_small_goods_obstruction_no_nat`, which establishes that no coarse assignment can be feasible.
To obtain a contradiction, it suffices to show that the coarse assignment p is feasible over the natural numbers.
We argue by contradiction, assuming that no agent receives strictly less than her threshold. Pushing the negation reveals that every agent's bundle valuation is at least her threshold. Invoking the obstruction result `efx_three_small_goods_obstruction_no_nat` establishes that no coarse assignment can be feasible over the natural numbers; thus, proving `efx_three_small_goods_obstruction_feasible_nat p` will produce `False` and complete the contradiction.
uses
efx_three_small_goods_obstruction_no_natclassical by_contra h push Not at h apply efx_three_small_goods_obstruction_no_nat p
Every agent i receives total utility at least her threshold efx_three_small_goods_obstruction_threshold i.
We split the feasibility conjunction into its two goals using `constructor`. For any agent i, the contradiction hypothesis gives that her real bundle valuation is at least her threshold. We rewrite the bundle valuation into an indicator sum over all eleven goods via `additive_valuation_bundle_sum_ite`. We then verify (`hcast`) that summing the real-cast values equals the real cast of the sum in ℕ (`push_cast`, `rfl`). Finally, `exact_mod_cast` casts the inequality from ℝ back to ℕ, proving that agent i receives at least her threshold value.
uses
additive_valuation_bundle_sum_iteconstructor · intro i have hi := h i rw [additive_valuation_bundle_sum_ite] at hi have hcast : (∑ g, if efx_three_small_goods_obstruction_coarse p g = i then (efx_three_small_goods_obstruction_values i g : ℝ) else 0) = ((∑ g, if efx_three_small_goods_obstruction_coarse p g = i then efx_three_small_goods_obstruction_values i g else 0 : ℕ) : ℝ) := by push_cast rfl rw [hcast] at hi exact_mod_cast hi
The allocation satisfies the natural-number EFX condition: for all distinct agents i ≠ j and every good g assigned to j, agent i's valuation of j's bundle is at most her valuation of her own bundle plus her valuation of g.
Given distinct agents i ≠ j and a good g assigned to j (so g belongs to j's bundle), we use `is_efx_goods_nat_cast_iff` to convert the real EFX hypothesis `hEF` into the equivalent condition over ℕ. Applying this condition to i, j, and g, and converting the bundle sums to indicator sums over all goods via `Finset.sum_filter`, discharges the second feasibility goal.
uses
is_efx_goods_nat_cast_iff,Finset.sum_filter· intro i j hij g hg have hh := (is_efx_goods_nat_cast_iff efx_three_small_goods_obstruction_values (efx_three_small_goods_obstruction_coarse p)).mp hEF have hm : g ∈ bundle_of (efx_three_small_goods_obstruction_coarse p) j := by simpa [bundle_of] using hg have := hh i j hij g hm simpa only [bundle_of, Finset.sum_filter] using this
efx_three_small_goods_obstruction_no_nat- For any coarse assignment p, the feasibility condition efx_three_small_goods_obstruction_feasible_nat p does not hold.
additive_valuation_bundle_sum_ite- The additive valuation of an agent's assigned bundle equals the sum over all goods of their valuation if the good is assigned to that agent and 0 otherwise.
is_efx_goods_nat_cast_iff- An allocation is EFX with respect to natural-number valuations cast to ℝ if and only if for all distinct agents i ≠ j and any good g in j's bundle, agent i's total value for j's bundle is at most her value for her own bundle plus her value for g, computed in ℕ.
Finset.sum_filter- The sum of a function over elements of a finite set satisfying a predicate equals the sum over the whole set where elements not satisfying the predicate evaluate to 0.
- The valuation functions and thresholds are defined over the natural numbers, but the theorem statement and EFX condition are cast to the real numbers. In Lean, transitioning between ℕ and ℝ requires explicit casts (`push_cast`, `exact_mod_cast`) and characterization lemmas (`is_efx_goods_nat_cast_iff`), whereas on paper this embedding is treated as transparent.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Function Finsettheorem efx_three_small_goods_obstruction_no_current_ir (p : Fin 7 → Fin 4) (hEF : is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ)) (efx_three_small_goods_obstruction_coarse p)) : ∃ i : Fin 4, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ)) (bundle_of (efx_three_small_goods_obstruction_coarse p) i) < (efx_three_small_goods_obstruction_threshold i : ℝ) := by classical by_contra h push Not at h apply efx_three_small_goods_obstruction_no_nat p constructor · intro i have hi := h i rw [additive_valuation_bundle_sum_ite] at hi have hcast : (∑ g, if efx_three_small_goods_obstruction_coarse p g = i then (efx_three_small_goods_obstruction_values i g : ℝ) else 0) = ((∑ g, if efx_three_small_goods_obstruction_coarse p g = i then efx_three_small_goods_obstruction_values i g else 0 : ℕ) : ℝ) := by push_cast rfl rw [hcast] at hi exact_mod_cast hi · intro i j hij g hg have hh := (is_efx_goods_nat_cast_iff efx_three_small_goods_obstruction_values (efx_three_small_goods_obstruction_coarse p)).mp hEF have hm : g ∈ bundle_of (efx_three_small_goods_obstruction_coarse p) j := by simpa [bundle_of] using hg have := hh i j hij g hm simpa only [bundle_of, Finset.sum_filter] using this