efx_intact_obstruction_no_coarse
No assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to reals.
Statement
theorem efx_intact_obstruction_no_coarse (p : Fin 5 → Fin 4) : ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) (efx_intact_obstruction_coarse p)
- Source
- Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Explicit route obstruction found in experiment 10980; it does not refute EFX existence and carries no research-level advance claim.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- efx_intact_obstruction_valuesThe explicit strictly positive four-agent seven-good valuation matrix used to test completion by keeping old bundles intact: rows…
- efx_intact_obstruction_coarseAssign the four old bundles {5}, {0,1}, {2,3}, {4} and the new singleton {6} to arbitrary agents p(0),...,p(4), respectively; mergers and…
- efx_intact_obstruction_no_coarse_natEvery assignment of the four intact old bundles and the new singleton in the explicit seven-good instance violates an EFX inequality,…
- 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.
- Used by 1
- efx_intact_obstruction_requires_splitEvery EFX allocation of the explicit seven-good positive instance separates goods 0 and 1 or separates goods 2 and 3; hence it splits an…
The proof, explained
The proof proceeds by contradiction. Assuming the coarse assignment is EFX with item values cast to the real numbers, it uses `is_efx_goods_nat_cast_iff` to translate this into the equivalent discrete EFX condition over natural numbers. It then applies `efx_intact_obstruction_no_coarse_nat`, an established impossibility result showing that no coarse assignment can satisfy this condition when written as sums with indicator functions. Finally, it verifies that the discrete EFX hypothesis implies this indicator-sum formulation by rewriting the bundle sums with `Finset.sum_filter`.
Assuming the coarse assignment is EFX over the real numbers, it satisfies the discrete EFX inequality for natural-number valuations.
We proceed by contradiction and assume that the coarse assignment `efx_intact_obstruction_coarse p` is EFX with values cast to ℝ (`intro h`). The lemma `is_efx_goods_nat_cast_iff` states that this real-valued EFX condition is equivalent to the natural-number EFX inequality: for all distinct agents i ≠ j and each item g in j's bundle, the sum of i's values for items in j's bundle is at most i's value for its own bundle plus the value of g. Applying the forward direction (`mp`) yields this discrete inequality as hypothesis `hh`.
uses
is_efx_goods_nat_cast_iffintro h have hh := (is_efx_goods_nat_cast_iff efx_intact_obstruction_values (efx_intact_obstruction_coarse p)).mp h
It suffices to show that the coarse assignment satisfies the EFX condition expressed as conditional sums over all items.
The lemma `efx_intact_obstruction_no_coarse_nat` asserts that no coarse assignment p can satisfy the integer EFX inequalities when bundle sums are expressed as conditional sums over all seven goods. Applying this lemma reduces our goal of deriving a contradiction (`False`) to verifying this conditional-sum inequality.
uses
efx_intact_obstruction_no_coarse_natapply efx_intact_obstruction_no_coarse_nat pThe coarse assignment satisfies the conditional-sum EFX inequality, completing the contradiction.
Fix distinct agents i and j and an item g assigned to j (`efx_intact_obstruction_coarse p g = j`). By definition of `bundle_of`, g belongs to agent j's bundle. Instantiating the discrete EFX hypothesis `hh` with these arguments gives the inequality between bundle sums. Finally, `Finset.sum_filter` rewrites the bundle sums into sums over all seven goods using indicator conditions (`if efx_intact_obstruction_coarse p h = ... then ... else 0`), which matches the target goal and closes the proof.
uses
Finset.sum_filterintro i j hij g hg have hg' : g ∈ bundle_of (efx_intact_obstruction_coarse p) j := by simpa [bundle_of] using hg have h' := hh i j hij g hg' simpa only [bundle_of, Finset.sum_filter] using h'
is_efx_goods_nat_cast_iff- An allocation of indivisible goods with natural-number valuations is EFX when item values are cast to real numbers if and only if for all distinct agents i ≠ j and each item g in j's bundle, agent i's valuation of j's bundle is at most i's valuation of its own bundle plus i's valuation of g.
efx_intact_obstruction_no_coarse_nat- No coarse assignment p of the five item bundles to the four agents satisfies the natural-number EFX inequalities expressed via indicator-filtered sums over all seven goods.
Finset.sum_filter- Summing a function over elements of a finite set that satisfy a predicate equals summing over the entire set with an if-then-else term that evaluates to the function value when the predicate holds and zero otherwise.
- The lemma `efx_intact_obstruction_no_coarse_nat` encapsulates the core combinatorial obstruction, established separately by exhaustive analysis over all mappings p : Fin 5 → Fin 4; this theorem lifts that result from natural numbers to real-valued valuations.
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_intact_obstruction_no_coarse (p : Fin 5 → Fin 4) : ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) (efx_intact_obstruction_coarse p) := by intro h have hh := (is_efx_goods_nat_cast_iff efx_intact_obstruction_values (efx_intact_obstruction_coarse p)).mp h apply efx_intact_obstruction_no_coarse_nat p intro i j hij g hg have hg' : g ∈ bundle_of (efx_intact_obstruction_coarse p) j := by simpa [bundle_of] using hg have h' := hh i j hij g hg' simpa only [bundle_of, Finset.sum_filter] using h'