efx_three_small_goods_obstruction_maximality
For every choice of omitted bonus t and every coarse allocation q keeping the four old pairs intact, if the two-bonus restriction satisfies EFX and weakly preserves all original old-only utilities, its total own utility is at most 4475. If equality holds, its four own utilities equal the current threshold vector (883,1992,800,800).
Statement
theorem efx_three_small_goods_obstruction_maximality : ∀ (t : Fin 3) (q : Fin 6 → Fin 4),
efx_three_small_goods_obstruction_partial_feasible t q →
(∑ i : Fin 4, efx_three_small_goods_obstruction_partial_own t q i) ≤ 4475 ∧
((∑ i : Fin 4, efx_three_small_goods_obstruction_partial_own t q i) = 4475 →
∀ i, efx_three_small_goods_obstruction_partial_own t q i = efx_three_small_goods_obstruction_threshold i)- 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 7
- 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_partial_ownThe exact natural-number own utility of agent i in the two-bonus restriction indexed t under the coarse allocation q.
- efx_three_small_goods_obstruction_partial_feasibleA two-bonus coarse allocation is feasible when it weakly preserves every original old-only utility and satisfies all exact natural-number…
- efx_three_small_goods_obstruction_partial_coarseAssign the first eight old goods in four intact adjacent pairs to agents q(0),...,q(3), and the two retained bonuses to q(4),q(5). Mergers…
- 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_original_thresholdThe four original old-only utilities (800,1600,800,800), attained by assigning the first eight goods in adjacent pairs to the four agents…
- efx_three_small_goods_obstruction_partial_valuesThe ten-good restriction of the explicit eleven-good matrix obtained by retaining all eight old goods and omitting bonus good 8+t, with…
The proof, explained
The theorem is established by finite exhaustive computation. By expanding the definitions of partial feasibility, utility sums, and thresholds, the statement is transformed into a closed, decidable proposition over a finite search space of 3 choices for the omitted bonus good and 4⁶ = 4096 coarse allocations. Lean's kernel then evaluates all 12,288 cases directly, verifying that the total utility is at most 4475 and that equality forces the utility vector to be exactly (883, 1992, 800, 800).
The goal is reduced to an explicit, decidable proposition over finite domains and concrete numerical matrices.
Unfolding the definitions of partial feasibility, own utilities, coarse allocations, partial values, and thresholds expresses the statement purely in terms of finite universal quantifiers, finite sums, and concrete payoff matrices.
unfold efx_three_small_goods_obstruction_partial_feasible efx_three_small_goods_obstruction_partial_own efx_three_small_goods_obstruction_partial_coarse efx_three_small_goods_obstruction_partial_values efx_three_small_goods_obstruction_threshold efx_three_small_goods_obstruction_original_threshold efx_three_small_goods_obstruction_valuesFor every choice of omitted item t and every coarse allocation q, if the allocation is feasible, the total utility is at most 4475, with equality only at the threshold vector (883, 1992, 800, 800). automation
With all definitions expanded, the proposition has no free variables and ranges over a finite domain: 3 choices for t and 4⁶ = 4096 coarse allocations q, giving 12,288 cases in total. The `decide +kernel` tactic instructs the Lean kernel to evaluate the decidability instance by exhaustive computation, verifying the inequality and equality condition for every case.
decide +kernel
- The proof relies on kernel computation (`decide +kernel`) to exhaustively check all 3 × 4⁶ = 12,288 possible combinations of omitted bonus items and coarse allocations.
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_maximality : ∀ (t : Fin 3) (q : Fin 6 → Fin 4), efx_three_small_goods_obstruction_partial_feasible t q → (∑ i : Fin 4, efx_three_small_goods_obstruction_partial_own t q i) ≤ 4475 ∧ ((∑ i : Fin 4, efx_three_small_goods_obstruction_partial_own t q i) = 4475 → ∀ i, efx_three_small_goods_obstruction_partial_own t q i = efx_three_small_goods_obstruction_threshold i) := by unfold efx_three_small_goods_obstruction_partial_feasible efx_three_small_goods_obstruction_partial_own efx_three_small_goods_obstruction_partial_coarse efx_three_small_goods_obstruction_partial_values efx_three_small_goods_obstruction_threshold efx_three_small_goods_obstruction_original_threshold efx_three_small_goods_obstruction_values decide +kernel