AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_obstruction_no_three_nat

theoremverified

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
Used by 1

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.

  1. 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\}$.

    lines 5–8

      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
  2. No 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.

    line 9

      decide +kernel

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

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
See it in the graphDiscuss this resultChallenge it