efx_three_small_goods_obstruction_no_zero_nat
Every coarse allocation whose first old pair is given to agent 0 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_zero_nat : ∀ b c d e f g : Fin 4,
¬ efx_three_small_goods_obstruction_feasible_nat ![0,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 establishes that in the explicit eleven-good instance, no coarse allocation that assigns the first pair of goods to agent 0 can simultaneously preserve current utility thresholds and satisfy the EFX inequalities. After unfolding the definitions of feasibility, thresholds, coarse bundling, and valuation matrix, the assertion reduces to a finite universal check over $4^6 = 4096$ candidate allocations. The Lean kernel verifies this statement exhaustively by direct computational evaluation via `decide +kernel`.
The feasibility predicate is expanded into an explicit finite combinatorial condition on the allocation vector $(0, b, c, d, e, f, g)$.
The proof unfolds the definitions of `efx_three_small_goods_obstruction_feasible_nat`, `efx_three_small_goods_obstruction_coarse`, `efx_three_small_goods_obstruction_threshold`, and `efx_three_small_goods_obstruction_values`. This translates the abstract feasibility condition into explicit sums of values from the fixed $4 \times 11$ valuation matrix and comparisons against the threshold vector $(883, 1992, 800, 800)$, together with the EFX envy inequalities for each pair of distinct agents.
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_valuesNone of the $4^6 = 4096$ possible allocations satisfy the feasibility requirements. automation
Because the six variables $b, c, d, e, f, g$ range over the finite set of four agents $\{0, 1, 2, 3\}$, the universal quantification ranges over a finite domain of $4^6 = 4096$ candidate allocations. All arithmetic sums and inequalities over natural numbers are decidable, making the entire proposition a closed decidable sentence. The `decide +kernel` tactic delegates this exhaustive case check to the Lean kernel's reduction engine, which verifies by direct computation that every candidate allocation fails either a threshold inequality or an EFX condition.
decide +kernel
- The proof relies entirely on exhaustive finite verification via kernel evaluation (`decide +kernel`), which checks all $4^6 = 4096$ candidate allocations without producing human-readable intermediate steps.
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_zero_nat : ∀ b c d e f g : Fin 4, ¬ efx_three_small_goods_obstruction_feasible_nat ![0,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