AFTD Auto-Formalizing Theoretical Domains

efx_allsource_pair_no_self

theoremverified

The envy-free partial allocation has no self champions for the unallocated good.

Statement

theorem efx_allsource_pair_no_self (i : Fin 4) (T : Finset (Fin 9))
  (hT : T ⊆ insert 8 ({![0,2,4,6] i, ![1,3,5,7] i} : Finset (Fin 9)))
  (hprefer : efx_allsource_pair_baseline i < ∑ g ∈ T, efx_allsource_pair_values i g) :
  ∃ (j : Fin 4) (g : Fin 9), g ∈ T ∧ efx_allsource_pair_baseline j <
    ∑ h ∈ T.erase g, efx_allsource_pair_values j h
Source
Three-valued all-source no-self two-split EFX obstruction for OP-7; experiments 11638–11642.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem states that in a specific fair division instance with 4 agents and 9 goods, whenever an agent i strictly prefers a bundle T ⊆ {8, 2i, 2i+1} to their baseline, some agent j strictly prefers T \ {g} to their baseline for some item g ∈ T. Because there are only 4 agents and each candidate bundle is a subset of a 3-element set of goods, the problem reduces to checking at most 32 cases. Reverting the parameters yields a closed sentence over finite domains, which Lean's `decide` tactic verifies by exhaustive computation.

  1. Every candidate pair of agent i and bundle T is verified to admit a champion agent j and good g. automation

    The assertion is purely finite: the agent i belongs to the 4-element set `Fin 4`, and T ranges over the power set of the 3-element set `{8, ![0,2,4,6] i, ![1,3,5,7] i}`, for a total of at most 4 × 2³ = 32 possible configurations. Reverting i and T presents the statement as a closed, universally quantified proposition over finite types, which Lean's `decide` tactic verifies by exhaustive computation.

    lines 6–7

      revert i T
      decide

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

theorem efx_allsource_pair_no_self (i : Fin 4) (T : Finset (Fin 9))  (hT : T ⊆ insert 8 ({![0,2,4,6] i, ![1,3,5,7] i} : Finset (Fin 9)))  (hprefer : efx_allsource_pair_baseline i < ∑ g ∈ T, efx_allsource_pair_values i g) :  ∃ (j : Fin 4) (g : Fin 9), g ∈ T ∧ efx_allsource_pair_baseline j <    ∑ h ∈ T.erase g, efx_allsource_pair_values j h := by  revert i T  decide
See it in the graphDiscuss this resultChallenge it