efx_three_small_goods_completion_loss_or_split
In the explicit eleven-good instance cast to real values, every complete EFX allocation which keeps each of the four old adjacent pairs intact has some agent whose utility is strictly less than her starting ten-good EFX utility threshold. Thus a completion preserving all current utilities must split an old pair.
Statement
theorem efx_three_small_goods_completion_loss_or_split (σ : Fin 11 → Fin 4) (hEF : is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ)) σ) (hstay : σ 0 = σ 1 ∧ σ 2 = σ 3 ∧ σ 4 = σ 5 ∧ σ 6 = σ 7) : ∃ i : Fin 4, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ)) (bundle_of σ 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 7
- 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_current_irIn the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than…
- 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.
The proof, explained
The proof reduces the claim to the obstruction theorem `efx_three_small_goods_obstruction_no_current_ir`, which rules out coarse EFX allocations that preserve all utility thresholds. Because the allocation σ keeps the four adjacent pairs of goods intact, it is functionally identical to a coarse allocation p of 7 items (the four pairs plus the three individual goods). After verifying this identity by exhaustive casework on all eleven goods, applying the obstruction theorem concludes that some agent must fall strictly below their starting utility threshold.
Decompose the pair-preservation hypothesis and define the coarse 7-item allocation p.
The hypothesis `hstay` decomposes into four equalities: σ(0) = σ(1), σ(2) = σ(3), σ(4) = σ(5), and σ(6) = σ(7), which assert that each of the four adjacent pairs of goods is assigned to the same agent. We then define a coarse allocation p on 7 items that assigns each of the four intact pairs (via representative goods 0, 2, 4, 6) and the three remaining individual goods (8, 9, 10) to their respective recipients under σ.
rcases hstay with ⟨h0,h1,h2,h3⟩ let p : Fin 7 → Fin 4 := ![σ 0,σ 2,σ 4,σ 6,σ 8,σ 9,σ 10]
The allocation σ coincides with the coarse allocation induced by p.
By function extensionality, it suffices to show σ(g) = efx_three_small_goods_obstruction_coarse(p)(g) for every good g in {0, ..., 10}. An exhaustive case analysis over all eleven goods confirms this: for each pair {0, 1}, {2, 3}, {4, 5}, and {6, 7}, both goods receive the same agent by the pair-preservation hypotheses, and the remaining goods 8, 9, 10 match the definition of p directly.
have heq : σ = efx_three_small_goods_obstruction_coarse p := by funext g fin_cases g <;> simp [p, efx_three_small_goods_obstruction_coarse, h0, h1, h2, h3]
Some agent receives utility strictly below their threshold.
Rewriting σ with the coarse allocation efx_three_small_goods_obstruction_coarse(p) in both the EFX hypothesis and the goal turns the statement into the obstruction theorem `efx_three_small_goods_obstruction_no_current_ir`, which directly concludes that some agent's utility falls strictly below their starting EFX threshold.
uses
efx_three_small_goods_obstruction_no_current_irrw [heq] at hEF ⊢ exact efx_three_small_goods_obstruction_no_current_ir p hEF
efx_three_small_goods_obstruction_no_current_ir- For any coarse allocation of 7 items among 4 agents, if the induced 11-good allocation is EFX with respect to the obstruction valuations, then at least one agent receives an additive utility strictly less than their starting threshold.
- The identity between the 11-good allocation σ and the coarse allocation is verified by finite case exhaustion over all eleven goods using `fin_cases` and `simp`.
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_completion_loss_or_split (σ : Fin 11 → Fin 4) (hEF : is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ)) σ) (hstay : σ 0 = σ 1 ∧ σ 2 = σ 3 ∧ σ 4 = σ 5 ∧ σ 6 = σ 7) : ∃ i : Fin 4, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ)) (bundle_of σ i) < (efx_three_small_goods_obstruction_threshold i : ℝ) := by rcases hstay with ⟨h0,h1,h2,h3⟩ let p : Fin 7 → Fin 4 := ![σ 0,σ 2,σ 4,σ 6,σ 8,σ 9,σ 10] have heq : σ = efx_three_small_goods_obstruction_coarse p := by funext g fin_cases g <;> simp [p, efx_three_small_goods_obstruction_coarse, h0, h1, h2, h3] rw [heq] at hEF ⊢ exact efx_three_small_goods_obstruction_no_current_ir p hEF