efx_intact_obstruction_requires_split
Every EFX allocation of the explicit seven-good positive instance separates goods 0 and 1 or separates goods 2 and 3; hence it splits an old bundle of the stated six-good EFX allocation.
Statement
theorem efx_intact_obstruction_requires_split (σ : Fin 7 → Fin 4) (h01 : σ 0 = σ 1) (h23 : σ 2 = σ 3) : ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) σ
- 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 4
- 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_coarseNo assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to…
- 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…
The proof, explained
To show that any EFX allocation must separate either goods 0 and 1 or goods 2 and 3, the proof shows that any allocation σ keeping both pairs intact is equal to a coarse allocation efx_intact_obstruction_coarse p for a 5-item assignment p. It verifies this equality by case exhaustion on the seven goods using the two assumptions, then appeals to the obstruction theorem efx_intact_obstruction_no_coarse, which proves that no coarse allocation can be EFX on this instance.
The allocation σ is identical to the coarse allocation efx_intact_obstruction_coarse p defined by p = ![σ 5, σ 0, σ 2, σ 4, σ 6].
Because σ assigns goods 0 and 1 to the same agent (h01) and goods 2 and 3 to the same agent (h23), it leaves those two pairs intact and effectively assigns five items: good 5, the pair {0, 1}, the pair {2, 3}, good 4, and good 6. Defining p : Fin 5 → Fin 4 to record the recipient of each item, we apply function extensionality and split into seven cases for g ∈ Fin 7. In each case, simplifying using the definitions of p and efx_intact_obstruction_coarse together with the hypotheses h01 and h23 confirms that σ g = efx_intact_obstruction_coarse p g.
let p : Fin 5 → Fin 4 := ![σ 5, σ 0, σ 2, σ 4, σ 6] have heq : σ = efx_intact_obstruction_coarse p := by funext g fin_cases g <;> simp [efx_intact_obstruction_coarse, p, h01, h23]
The allocation σ is not an EFX allocation.
Rewriting σ as efx_intact_obstruction_coarse p transforms the goal into showing that this coarse allocation is not EFX. The theorem efx_intact_obstruction_no_coarse asserts that no coarse allocation of this form can be EFX on the given seven-good instance, closing the proof.
uses
efx_intact_obstruction_no_coarserw [heq] exact efx_intact_obstruction_no_coarse p
efx_intact_obstruction_no_coarse- For any assignment p of five bundles to four agents, the coarse allocation efx_intact_obstruction_coarse p is not an EFX allocation for the seven-good instance.
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_requires_split (σ : Fin 7 → Fin 4) (h01 : σ 0 = σ 1) (h23 : σ 2 = σ 3) : ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) σ := by let p : Fin 5 → Fin 4 := ![σ 5, σ 0, σ 2, σ 4, σ 6] have heq : σ = efx_intact_obstruction_coarse p := by funext g fin_cases g <;> simp [efx_intact_obstruction_coarse, p, h01, h23] rw [heq] exact efx_intact_obstruction_no_coarse p