efx_three_small_goods_obstruction_no_two_nat
Every coarse allocation whose first old pair is given to agent 2 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_two_nat : ∀ b c d e f g : Fin 4,
¬ efx_three_small_goods_obstruction_feasible_nat ![2,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 4
- 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_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…
- 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…
- 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 establishes that no coarse allocation in the explicit eleven-good instance can be feasible if the first pair of goods is assigned to agent 2. Assuming feasibility for contradiction, the proof extracts each agent's utility threshold requirement and rewrites the allocated bundles using a sum decomposition lemma that groups the eleven goods into four pairs and three single items. Auxiliary lemmas upper-bound the maximum utility any agent can obtain from the three single items by 200, 400, 200, and 200, respectively. Finally, an exhaustive case analysis across all 64 possible assignments of the remaining three pairs of goods demonstrates via linear arithmetic that the threshold inequalities can never be simultaneously met.
The total utility sum for agent $i$ decomposes into the sum of values of the four pairs of goods and the three single goods assigned to $i$. automation
Expanding the definition of the coarse allocation and the sum over $\operatorname{Fin} 11$ using `Fin.sum_univ_succ`, the proof splits by cases over whether $p(k) = i$ for each $k \in \{0, \dots, 6\}$. In each of the 128 branches, simplification and linear arithmetic (`omega`) verify that the sum of the eleven items matches the seven grouped terms.
uses
Fin.sum_univ_succsimp only [efx_three_small_goods_obstruction_coarse, Fin.sum_univ_succ] by_cases h0 : p 0 = i <;> by_cases h1 : p 1 = i <;> by_cases h2 : p 2 = i <;> by_cases h3 : p 3 = i <;> by_cases h4 : p 4 = i <;> by_cases h5 : p 5 = i <;> by_cases h6 : p 6 = i <;> simp_all <;> omega
The utility contribution of the three single goods to agent 0 is at most 200. automation
For agent 0, goods 8, 9, and 10 have values 83, 115, and 2. Since $83 + 115 + 2 = 200$, the sum of values of goods assigned to agent 0 is at most 200, verified by case analysis on whether $e=0, f=0, g=0$ (`split_ifs`) and linear arithmetic (`omega`).
private lemma efx_three_small_goods_obstruction_no_two_nat_bound0 (e f g : Fin 4) : (if e = 0 then 83 else 0) + (if f = 0 then 115 else 0) + (if g = 0 then 2 else 0) ≤ 200 := by split_ifs <;> omega
The utility contribution of the three single goods to agent 1 is at most 400. automation
For agent 1, goods 8, 9, and 10 have values 4, 392, and 4, whose sum is $4 + 392 + 4 = 400 \le 400$. The bound holds for all recipient choices $e, f, g$, verified by `split_ifs` and `omega`.
private lemma efx_three_small_goods_obstruction_no_two_nat_bound1 (e f g : Fin 4) : (if e = 1 then 4 else 0) + (if f = 1 then 392 else 0) + (if g = 1 then 4 else 0) ≤ 400 := by split_ifs <;> omega
The utility contribution of the three single goods to agent 2 is at most 200. automation
For agent 2, goods 8, 9, and 10 have values 34, 2, and 164, whose sum is $34 + 2 + 164 = 200 \le 200$. The bound holds for all recipient choices $e, f, g$, verified by `split_ifs` and `omega`.
private lemma efx_three_small_goods_obstruction_no_two_nat_bound2 (e f g : Fin 4) : (if e = 2 then 34 else 0) + (if f = 2 then 2 else 0) + (if g = 2 then 164 else 0) ≤ 200 := by split_ifs <;> omega
The utility contribution of the three single goods to agent 3 is at most 200. automation
For agent 3, goods 8, 9, and 10 have values 2, 83, and 115, whose sum is $2 + 83 + 115 = 200 \le 200$. The bound holds for all recipient choices $e, f, g$, verified by `split_ifs` and `omega`.
private lemma efx_three_small_goods_obstruction_no_two_nat_bound3 (e f g : Fin 4) : (if e = 3 then 2 else 0) + (if f = 3 then 83 else 0) + (if g = 3 then 115 else 0) ≤ 200 := by split_ifs <;> omega
Assuming feasibility, each agent $0, 1, 2, 3$ must receive total utility at least their threshold.
We introduce the allocation variables $b, c, d, e, f, g$ and the feasibility hypothesis `hf`. Specializing the threshold condition of feasibility (`hf.1`) at agents 0, 1, 2, and 3 yields four utility lower bounds $h_0, h_1, h_2, h_3$.
intro b c d e f g hf have h0 := hf.1 0 have h1 := hf.1 1 have h2 := hf.1 2 have h3 := hf.1 3
The threshold inequalities for agents 0, 1, 2, 3 are rewritten in terms of the specific valuations, with agent 2 receiving the first pair.
We rewrite the utility sums in $h_0, h_1, h_2, h_3$ using `efx_three_small_goods_obstruction_no_two_nat_sum_id`. We then evaluate the values and thresholds: agent 2 receives the first pair (value $284 + 284 = 568$), while agents 0, 1, and 3 receive 0 from that pair; their thresholds are 883, 1992, 800, and 800 respectively.
uses
efx_three_small_goods_obstruction_no_two_nat_sum_idrw [efx_three_small_goods_obstruction_no_two_nat_sum_id] at h0 h1 h2 h3 simp [efx_three_small_goods_obstruction_values, efx_three_small_goods_obstruction_threshold] at h0 h1 h2 h3
The single-good utility bounds are established for each agent under the given allocation.
We instantiate the four auxiliary lemmas `efx_three_small_goods_obstruction_no_two_nat_bound0` through `bound3` with the single-good recipients $e, f, g$, obtaining upper bounds $hb_0, hb_1, hb_2, hb_3$ on the utility each agent can obtain from items 8, 9, and 10.
uses
efx_three_small_goods_obstruction_no_two_nat_bound0,efx_three_small_goods_obstruction_no_two_nat_bound1,efx_three_small_goods_obstruction_no_two_nat_bound2,efx_three_small_goods_obstruction_no_two_nat_bound3have hb0 := efx_three_small_goods_obstruction_no_two_nat_bound0 e f g have hb1 := efx_three_small_goods_obstruction_no_two_nat_bound1 e f g have hb2 := efx_three_small_goods_obstruction_no_two_nat_bound2 e f g have hb3 := efx_three_small_goods_obstruction_no_two_nat_bound3 e f g
No assignment of the remaining three pairs of goods can satisfy all four threshold inequalities, deriving a contradiction. automation
We perform an exhaustive case split using `fin_cases` across all $4^3 = 64$ possible assignments of the pairs $b, c, d \in \{0, 1, 2, 3\}$. In every case, simplifying the threshold hypotheses and invoking `omega` with the single-good bounds shows that the required utilities cannot be simultaneously satisfied, reaching a contradiction in all branches.
fin_cases b <;> fin_cases c <;> fin_cases d <;> simp at h0 h1 h2 h3 <;> omega
Fin.sum_univ_succ- A finite sum over $\operatorname{Fin}(n+1)$ can be split into the first term at 0 plus the sum of the remaining terms.
efx_three_small_goods_obstruction_no_two_nat_sum_id- Under coarse allocation $p$, the total utility agent $i$ receives from all eleven goods equals the sum of values of the four pairs (if assigned to $i$) plus the values of the three single goods (if assigned to $i$).
efx_three_small_goods_obstruction_no_two_nat_bound0- The total utility agent 0 can receive from the three single goods is at most 200, regardless of the assignment $e, f, g$.
efx_three_small_goods_obstruction_no_two_nat_bound1- The total utility agent 1 can receive from the three single goods is at most 400, regardless of the assignment $e, f, g$.
efx_three_small_goods_obstruction_no_two_nat_bound2- The total utility agent 2 can receive from the three single goods is at most 200, regardless of the assignment $e, f, g$.
efx_three_small_goods_obstruction_no_two_nat_bound3- The total utility agent 3 can receive from the three single goods is at most 200, regardless of the assignment $e, f, g$.
- Feasibility (`efx_three_small_goods_obstruction_feasible_nat`) is defined as the conjunction of threshold satisfaction (utility preservation) and pairwise EFX inequalities, but the proof relies solely on threshold satisfaction (`hf.1`); the EFX inequalities are not used.
- The sum identity lemma in lines 12–15 splits the sum over eleven items into seven terms by performing a brute-force case split over all 128 combinations of whether each item is assigned to agent $i$.
- The exhaustive contradiction in lines 46–47 splits into $4^3 = 64$ subgoals via `fin_cases`, each of which is closed by the automated linear arithmetic solver `omega`.
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.
Lean’s trace was cut to the first 400 of 569 tactics.
open Function Finsetprivate lemma efx_three_small_goods_obstruction_no_two_nat_sum_id (p : Fin 7 → Fin 4) (i : Fin 4) : (∑ h : Fin 11, if efx_three_small_goods_obstruction_coarse p h = i then efx_three_small_goods_obstruction_values i h else 0) = (if p 0 = i then efx_three_small_goods_obstruction_values i 0 + efx_three_small_goods_obstruction_values i 1 else 0) + (if p 1 = i then efx_three_small_goods_obstruction_values i 2 + efx_three_small_goods_obstruction_values i 3 else 0) + (if p 2 = i then efx_three_small_goods_obstruction_values i 4 + efx_three_small_goods_obstruction_values i 5 else 0) + (if p 3 = i then efx_three_small_goods_obstruction_values i 6 + efx_three_small_goods_obstruction_values i 7 else 0) + (if p 4 = i then efx_three_small_goods_obstruction_values i 8 else 0) + (if p 5 = i then efx_three_small_goods_obstruction_values i 9 else 0) + (if p 6 = i then efx_three_small_goods_obstruction_values i 10 else 0) := by simp only [efx_three_small_goods_obstruction_coarse, Fin.sum_univ_succ] by_cases h0 : p 0 = i <;> by_cases h1 : p 1 = i <;> by_cases h2 : p 2 = i <;> by_cases h3 : p 3 = i <;> by_cases h4 : p 4 = i <;> by_cases h5 : p 5 = i <;> by_cases h6 : p 6 = i <;> simp_all <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound0 (e f g : Fin 4) : (if e = 0 then 83 else 0) + (if f = 0 then 115 else 0) + (if g = 0 then 2 else 0) ≤ 200 := by split_ifs <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound1 (e f g : Fin 4) : (if e = 1 then 4 else 0) + (if f = 1 then 392 else 0) + (if g = 1 then 4 else 0) ≤ 400 := by split_ifs <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound2 (e f g : Fin 4) : (if e = 2 then 34 else 0) + (if f = 2 then 2 else 0) + (if g = 2 then 164 else 0) ≤ 200 := by split_ifs <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound3 (e f g : Fin 4) : (if e = 3 then 2 else 0) + (if f = 3 then 83 else 0) + (if g = 3 then 115 else 0) ≤ 200 := by split_ifs <;> omegatheorem efx_three_small_goods_obstruction_no_two_nat : ∀ b c d e f g : Fin 4, ¬ efx_three_small_goods_obstruction_feasible_nat ![2,b,c,d,e,f,g] := by intro b c d e f g hf have h0 := hf.1 0 have h1 := hf.1 1 have h2 := hf.1 2 have h3 := hf.1 3 rw [efx_three_small_goods_obstruction_no_two_nat_sum_id] at h0 h1 h2 h3 simp [efx_three_small_goods_obstruction_values, efx_three_small_goods_obstruction_threshold] at h0 h1 h2 h3 have hb0 := efx_three_small_goods_obstruction_no_two_nat_bound0 e f g have hb1 := efx_three_small_goods_obstruction_no_two_nat_bound1 e f g have hb2 := efx_three_small_goods_obstruction_no_two_nat_bound2 e f g have hb3 := efx_three_small_goods_obstruction_no_two_nat_bound3 e f g fin_cases b <;> fin_cases c <;> fin_cases d <;> simp at h0 h1 h2 h3 <;> omega