efx_three_small_goods_obstruction_no_three_nat
Every coarse allocation whose first old pair is given to agent 3 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_three_nat : ∀ b c d e f g : Fin 4,
¬ efx_three_small_goods_obstruction_feasible_nat ![3,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_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…
- 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 is proved by exhaustive finite computation. After unfolding the definitions of feasibility, coarse allocations, utility thresholds, and valuation vectors, the claim reduces to checking that none of the $4^6 = 4096$ possible assignments of the remaining items satisfies the conjunction of threshold and EFX inequalities. The Lean kernel evaluates the decidable goal (`decide +kernel`) and verifies that every assignment fails.
The feasibility condition for an allocation assigning the first pair of goods to agent 3 is expanded into explicit arithmetic inequalities on the remaining parameters.
Unfolding the definitions of feasibility (`efx_three_small_goods_obstruction_feasible_nat`), coarse allocation (`efx_three_small_goods_obstruction_coarse`), threshold values (`efx_three_small_goods_obstruction_threshold`), and valuations (`efx_three_small_goods_obstruction_values`) expresses the goal as an explicit conjunction of linear inequalities on natural numbers over the 11 goods and 4 agents, parameterized by the remaining choices $b, c, d, e, f, g \in \{0, 1, 2, 3\}$.
unfold efx_three_small_goods_obstruction_feasible_nat efx_three_small_goods_obstruction_coarse efx_three_small_goods_obstruction_threshold efx_three_small_goods_obstruction_valuesNo assignment of the remaining items satisfies both the utility thresholds and the EFX inequalities. automation
The goal is a universally quantified statement over the finite domain $(\text{Fin } 4)^6$, consisting of $4^6 = 4096$ possible allocations. Because all sums and comparisons are decidable arithmetic operations on natural numbers, the proposition is decidable. The `decide +kernel` tactic triggers kernel evaluation to check all 4096 combinations exhaustively, confirming that feasibility fails in every case.
decide +kernel
- The proof relies entirely on exhaustive computational verification by the Lean kernel (`decide +kernel`), which evaluates all $4^6 = 4096$ possible allocations of the remaining items.
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_three_nat : ∀ b c d e f g : Fin 4, ¬ efx_three_small_goods_obstruction_feasible_nat ![3,b,c,d,e,f,g] := by unfold efx_three_small_goods_obstruction_feasible_nat efx_three_small_goods_obstruction_coarse efx_three_small_goods_obstruction_threshold efx_three_small_goods_obstruction_values decide +kernel