efx_three_small_goods_obstruction_no_nat
No coarse allocation of the explicit eleven-good instance both weakly preserves the current utility thresholds and satisfies every natural-number EFX inequality.
Statement
theorem efx_three_small_goods_obstruction_no_nat (p : Fin 7 → Fin 4) :
¬ efx_three_small_goods_obstruction_feasible_nat p- 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 5
- efx_three_small_goods_obstruction_feasible_natThe exact natural-number condition that a coarse eleven-good allocation both weakly preserves all four current utility thresholds and…
- efx_three_small_goods_obstruction_no_zero_natEvery coarse allocation whose first old pair is given to agent 0 fails the conjunction of current utility preservation and the exact…
- efx_three_small_goods_obstruction_no_one_natEvery coarse allocation whose first old pair is given to agent 1 fails the conjunction of current utility preservation and the exact…
- efx_three_small_goods_obstruction_no_two_natEvery coarse allocation whose first old pair is given to agent 2 fails the conjunction of current utility preservation and the exact…
- efx_three_small_goods_obstruction_no_three_natEvery coarse allocation whose first old pair is given to agent 3 fails the conjunction of current utility preservation and the exact…
- Used by 1
- 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…
The proof, explained
The theorem asserts that no coarse allocation p : Fin 7 → Fin 4 of the 11 goods is feasible under both the minimum utility thresholds and the natural-number EFX inequalities. The proof represents the function p as an explicit 7-tuple of assignments (a, b, c, d, e, f, g) and performs a case analysis on the agent a ∈ {0, 1, 2, 3} who receives the first block of goods. Each of the four cases is then discharged by an existing obstruction lemma that rules out all possible completions (b, c, d, e, f, g).
The assignment function p is pointwise equal to the explicit vector of its seven values, ![p 0, p 1, p 2, p 3, p 4, p 5, p 6].
By functional extensionality (funext), two functions on Fin 7 coincide if they agree on all inputs. The proof checks each of the seven elements 0, ..., 6 of Fin 7 by exhausting them (fin_cases) and verifying equality definitionally (rfl).
have hp : p = ![p 0,p 1,p 2,p 3,p 4,p 5,p 6] := by funext i fin_cases i <;> rfl
It suffices to show that no 7-tuple (a, b, c, d, e, f, g) ∈ (Fin 4)⁷ is feasible.
Rewriting p as an explicit vector using hp puts the goal into vector form. Generalizing the seven evaluations p 0, ..., p 6 to independent variables a, b, c, d, e, f, g replaces the specific function p with an arbitrary 7-tuple of agent assignments.
rw [hp] generalize p 0 = a, p 1 = b, p 2 = c, p 3 = d, p 4 = e, p 5 = f, p 6 = g
No coarse allocation is feasible, concluding the proof.
A case split on a ∈ Fin 4 separates into the four possibilities for which agent receives the first block of goods: a = 0, 1, 2, or 3. Each case is closed by invoking a pre-proved obstruction lemma (efx_three_small_goods_obstruction_no_zero_nat, efx_three_small_goods_obstruction_no_one_nat, efx_three_small_goods_obstruction_no_two_nat, and efx_three_small_goods_obstruction_no_three_nat) that certifies no completion (b, c, d, e, f, g) can satisfy both the utility thresholds and the EFX inequalities.
uses
efx_three_small_goods_obstruction_no_zero_nat,efx_three_small_goods_obstruction_no_one_nat,efx_three_small_goods_obstruction_no_two_nat,efx_three_small_goods_obstruction_no_three_natfin_cases a · exact efx_three_small_goods_obstruction_no_zero_nat b c d e f g · exact efx_three_small_goods_obstruction_no_one_nat b c d e f g · exact efx_three_small_goods_obstruction_no_two_nat b c d e f g · exact efx_three_small_goods_obstruction_no_three_nat b c d e f g
efx_three_small_goods_obstruction_no_zero_nat- For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 0 results in an allocation that fails either the threshold or the EFX conditions.
efx_three_small_goods_obstruction_no_one_nat- For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 1 results in an allocation that fails either the threshold or the EFX conditions.
efx_three_small_goods_obstruction_no_two_nat- For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 2 results in an allocation that fails either the threshold or the EFX conditions.
efx_three_small_goods_obstruction_no_three_nat- For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 3 results in an allocation that fails either the threshold or the EFX conditions.
- Representing the function p : Fin 7 → Fin 4 as an explicit vector ![p 0, ..., p 6] via funext and fin_cases is a formal detail needed because the underlying obstruction lemmas are stated on explicit vectors rather than arbitrary functions.
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_nat (p : Fin 7 → Fin 4) : ¬ efx_three_small_goods_obstruction_feasible_nat p := by have hp : p = ![p 0,p 1,p 2,p 3,p 4,p 5,p 6] := by funext i fin_cases i <;> rfl rw [hp] generalize p 0 = a, p 1 = b, p 2 = c, p 3 = d, p 4 = e, p 5 = f, p 6 = g fin_cases a · exact efx_three_small_goods_obstruction_no_zero_nat b c d e f g · exact efx_three_small_goods_obstruction_no_one_nat b c d e f g · exact efx_three_small_goods_obstruction_no_two_nat b c d e f g · exact efx_three_small_goods_obstruction_no_three_nat b c d e f g