AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_obstruction_no_nat

theoremverified

No coarse allocation of the explicit eleven-good instance both weakly preserves the current utility thresholds and satisfies every natural-number EFX inequality.

Statement

theorem efx_three_small_goods_obstruction_no_nat (p : Fin 7 → Fin 4) :
    ¬ efx_three_small_goods_obstruction_feasible_nat p
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 no coarse allocation p : Fin 7 → Fin 4 of the 11 goods is feasible under both the minimum utility thresholds and the natural-number EFX inequalities. The proof represents the function p as an explicit 7-tuple of assignments (a, b, c, d, e, f, g) and performs a case analysis on the agent a ∈ {0, 1, 2, 3} who receives the first block of goods. Each of the four cases is then discharged by an existing obstruction lemma that rules out all possible completions (b, c, d, e, f, g).

  1. The assignment function p is pointwise equal to the explicit vector of its seven values, ![p 0, p 1, p 2, p 3, p 4, p 5, p 6].

    By functional extensionality (funext), two functions on Fin 7 coincide if they agree on all inputs. The proof checks each of the seven elements 0, ..., 6 of Fin 7 by exhausting them (fin_cases) and verifying equality definitionally (rfl).

    lines 5–7

      have hp : p = ![p 0,p 1,p 2,p 3,p 4,p 5,p 6] := by
        funext i
        fin_cases i <;> rfl
  2. It suffices to show that no 7-tuple (a, b, c, d, e, f, g) ∈ (Fin 4)⁷ is feasible.

    Rewriting p as an explicit vector using hp puts the goal into vector form. Generalizing the seven evaluations p 0, ..., p 6 to independent variables a, b, c, d, e, f, g replaces the specific function p with an arbitrary 7-tuple of agent assignments.

    lines 8–9

      rw [hp]
      generalize p 0 = a, p 1 = b, p 2 = c, p 3 = d, p 4 = e, p 5 = f, p 6 = g
  3. No coarse allocation is feasible, concluding the proof.

    A case split on a ∈ Fin 4 separates into the four possibilities for which agent receives the first block of goods: a = 0, 1, 2, or 3. Each case is closed by invoking a pre-proved obstruction lemma (efx_three_small_goods_obstruction_no_zero_nat, efx_three_small_goods_obstruction_no_one_nat, efx_three_small_goods_obstruction_no_two_nat, and efx_three_small_goods_obstruction_no_three_nat) that certifies no completion (b, c, d, e, f, g) can satisfy both the utility thresholds and the EFX inequalities.

    lines 10–14

    uses efx_three_small_goods_obstruction_no_zero_nat, efx_three_small_goods_obstruction_no_one_nat, efx_three_small_goods_obstruction_no_two_nat, efx_three_small_goods_obstruction_no_three_nat

      fin_cases a
      · exact efx_three_small_goods_obstruction_no_zero_nat b c d e f g
      · exact efx_three_small_goods_obstruction_no_one_nat b c d e f g
      · exact efx_three_small_goods_obstruction_no_two_nat b c d e f g
      · exact efx_three_small_goods_obstruction_no_three_nat b c d e f g
efx_three_small_goods_obstruction_no_zero_nat
For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 0 results in an allocation that fails either the threshold or the EFX conditions.
efx_three_small_goods_obstruction_no_one_nat
For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 1 results in an allocation that fails either the threshold or the EFX conditions.
efx_three_small_goods_obstruction_no_two_nat
For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 2 results in an allocation that fails either the threshold or the EFX conditions.
efx_three_small_goods_obstruction_no_three_nat
For every choice of agent assignments b, c, d, e, f, g ∈ Fin 4 to the remaining six blocks, assigning the first block to agent 3 results in an allocation that fails either the threshold or the EFX conditions.

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_nat (p : Fin 7 → Fin 4) :    ¬ efx_three_small_goods_obstruction_feasible_nat p := by  have hp : p = ![p 0,p 1,p 2,p 3,p 4,p 5,p 6] := by    funext i    fin_cases i <;> rfl  rw [hp]  generalize p 0 = a, p 1 = b, p 2 = c, p 3 = d, p 4 = e, p 5 = f, p 6 = g  fin_cases a  · exact efx_three_small_goods_obstruction_no_zero_nat b c d e f g  · exact efx_three_small_goods_obstruction_no_one_nat b c d e f g  · exact efx_three_small_goods_obstruction_no_two_nat b c d e f g  · exact efx_three_small_goods_obstruction_no_three_nat b c d e f g
See it in the graphDiscuss this resultChallenge it