AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_obstruction_maximality

theoremverified

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

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).

  1. 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.

    lines 8–11

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

    line 12

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