AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_obstruction_no_one_nat

theoremverified

Every coarse allocation whose first old pair is given to agent 1 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_one_nat : ∀ b c d e f g : Fin 4,
    ¬ efx_three_small_goods_obstruction_feasible_nat ![1,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 5
Used by 1

The proof, explained

The theorem asserts that in the 11-good, 4-agent instance, no coarse allocation that assigns the first pair of goods to agent 1 can be feasible. Feasibility requires in particular that every agent receives at least their threshold utility. By splitting into 16 cases according to which agents receive the second and third pairs of goods, each subcase reduces to checking that no choice of assignments for the remaining four items can satisfy the threshold requirements; each of these 16 subcases is verified by finite exhaustive computation.

  1. Each of the 16 combinations of (b, c) fails the utility threshold condition automation

    The 16 helper lemmas exhaustively verify by finite computation (via `decide`) that for each fixed pair (b, c) with b, c in Fin 4 and all possible remaining assignments d, e, f, g, at least one agent does not meet their required utility threshold.

    lines 3–130

    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (0:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (1:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (2:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (3:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (0:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (1:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (2:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (3:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (0:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (1:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (2:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (3:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (0:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (1:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (2:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
    private lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 :
        ∀ d e f g : Fin 4,
          ¬ (∀ (i : Fin 4),
              efx_three_small_goods_obstruction_threshold i ≤
                ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (3:Fin 4), d, e, f, g] h = i
                     then efx_three_small_goods_obstruction_values i h else 0) := by
      decide
    
  2. Assume a feasible coarse allocation exists with the first old pair assigned to agent 1, and extract its threshold feasibility condition

    We assume for contradiction that there is a feasible allocation with the first pair assigned to agent 1, and extract the first conjunct h1 stating that every agent meets their utility threshold.

    lines 133–134

      intro b c d e f g h
      have h1 := h.1
  3. Exhausting over all 16 choices of (b, c) leads to a contradiction in every case

    We perform case analysis on b and c in Fin 4, resulting in 16 cases. In each case, applying the corresponding helper lemma with d, e, f, g and h1 produces a contradiction.

    lines 135–151

    uses efx_three_small_goods_obstruction_no_one_nat_chunk_0_0, efx_three_small_goods_obstruction_no_one_nat_chunk_0_1, efx_three_small_goods_obstruction_no_one_nat_chunk_0_2, efx_three_small_goods_obstruction_no_one_nat_chunk_0_3, efx_three_small_goods_obstruction_no_one_nat_chunk_1_0, efx_three_small_goods_obstruction_no_one_nat_chunk_1_1, efx_three_small_goods_obstruction_no_one_nat_chunk_1_2, efx_three_small_goods_obstruction_no_one_nat_chunk_1_3, efx_three_small_goods_obstruction_no_one_nat_chunk_2_0, efx_three_small_goods_obstruction_no_one_nat_chunk_2_1, efx_three_small_goods_obstruction_no_one_nat_chunk_2_2, efx_three_small_goods_obstruction_no_one_nat_chunk_2_3, efx_three_small_goods_obstruction_no_one_nat_chunk_3_0, efx_three_small_goods_obstruction_no_one_nat_chunk_3_1, efx_three_small_goods_obstruction_no_one_nat_chunk_3_2, efx_three_small_goods_obstruction_no_one_nat_chunk_3_3

      fin_cases b <;> fin_cases c
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 d e f g h1
      · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 d e f g h1

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 Finsetprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (0:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (1:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (2:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (0:Fin 4), (3:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (0:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (1:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (2:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (1:Fin 4), (3:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (0:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (1:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (2:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (2:Fin 4), (3:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (0:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (1:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (2:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decideprivate lemma efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 :    ∀ d e f g : Fin 4,      ¬ (∀ (i : Fin 4),          efx_three_small_goods_obstruction_threshold i ≤            ∑ h, if efx_three_small_goods_obstruction_coarse ![1, (3:Fin 4), (3:Fin 4), d, e, f, g] h = i                 then efx_three_small_goods_obstruction_values i h else 0) := by  decidetheorem efx_three_small_goods_obstruction_no_one_nat : ∀ b c d e f g : Fin 4,    ¬ efx_three_small_goods_obstruction_feasible_nat ![1,b,c,d,e,f,g] := by  intro b c d e f g h  have h1 := h.1  fin_cases b <;> fin_cases c  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_0 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_1 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_2 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_0_3 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_0 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_1 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_2 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_1_3 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_0 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_1 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_2 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_2_3 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_0 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_1 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_2 d e f g h1  · exact efx_three_small_goods_obstruction_no_one_nat_chunk_3_3 d e f g h1
See it in the graphDiscuss this resultChallenge it