efx_three_small_goods_obstruction_no_one_nat
Every coarse allocation whose first old pair is given to agent 1 fails the conjunction of current utility preservation and the exact natural-number EFX inequalities in the explicit eleven-good instance.
Statement
theorem efx_three_small_goods_obstruction_no_one_nat : ∀ b c d e f g : Fin 4,
¬ efx_three_small_goods_obstruction_feasible_nat ![1,b,c,d,e,f,g]- 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_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_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_thresholdThe four current utility thresholds (883,1992,800,800), attained by the starting EFX allocation of the first ten goods in the explicit…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- 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…
The proof, explained
The theorem asserts that in the 11-good, 4-agent instance, no coarse allocation that assigns the first pair of goods to agent 1 can be feasible. Feasibility requires in particular that every agent receives at least their threshold utility. By splitting into 16 cases according to which agents receive the second and third pairs of goods, each subcase reduces to checking that no choice of assignments for the remaining four items can satisfy the threshold requirements; each of these 16 subcases is verified by finite exhaustive computation.
Each of the 16 combinations of (b, c) fails the utility threshold condition automation
The 16 helper lemmas exhaustively verify by finite computation (via `decide`) that for each fixed pair (b, c) with b, c in Fin 4 and all possible remaining assignments d, e, f, g, at least one agent does not meet their required utility threshold.
private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decide
Assume a feasible coarse allocation exists with the first old pair assigned to agent 1, and extract its threshold feasibility condition
We assume for contradiction that there is a feasible allocation with the first pair assigned to agent 1, and extract the first conjunct h1 stating that every agent meets their utility threshold.
intro b c d e f g h have h1 := h.1
Exhausting over all 16 choices of (b, c) leads to a contradiction in every case
We perform case analysis on b and c in Fin 4, resulting in 16 cases. In each case, applying the corresponding helper lemma with d, e, f, g and h1 produces a contradiction.
uses
efx_three_small_goods_obstruction_no_one_nat_chunk_0_0,efx_three_small_goods_obstruction_no_one_nat_chunk_0_1,efx_three_small_goods_obstruction_no_one_nat_chunk_0_2,efx_three_small_goods_obstruction_no_one_nat_chunk_0_3,efx_three_small_goods_obstruction_no_one_nat_chunk_1_0,efx_three_small_goods_obstruction_no_one_nat_chunk_1_1,efx_three_small_goods_obstruction_no_one_nat_chunk_1_2,efx_three_small_goods_obstruction_no_one_nat_chunk_1_3,efx_three_small_goods_obstruction_no_one_nat_chunk_2_0,efx_three_small_goods_obstruction_no_one_nat_chunk_2_1,efx_three_small_goods_obstruction_no_one_nat_chunk_2_2,efx_three_small_goods_obstruction_no_one_nat_chunk_2_3,efx_three_small_goods_obstruction_no_one_nat_chunk_3_0,efx_three_small_goods_obstruction_no_one_nat_chunk_3_1,efx_three_small_goods_obstruction_no_one_nat_chunk_3_2,efx_three_small_goods_obstruction_no_one_nat_chunk_3_3fin_cases b <;> fin_cases c · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 d e f g h1
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 Finsetprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (0:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (1:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (2:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 : ∀ d e f g : Fin 4, ¬ (∀ (i : Fin 4), efx_three_small_goods_obstruction_threshold i ≤ ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (3:Fin 4), d, e, f, g] h = i then efx_three_small_goods_obstruction_values i h else 0) := by decidetheorem efx_three_small_goods_obstruction_no_one_nat : ∀ b c d e f g : Fin 4, ¬ efx_three_small_goods_obstruction_feasible_nat ![1,b,c,d,e,f,g] := by intro b c d e f g h have h1 := h.1 fin_cases b <;> fin_cases c · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 d e f g h1 · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 d e f g h1