AFTD Auto-Formalizing Theoretical Domains

efx_allsource_three_pair_no_self

theoremverified

The original envy-free state has no self champion for the charity good.

Statement

theorem efx_allsource_three_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 : 10 < ∑ g ∈ T, efx_allsource_three_pair_values i g) :
  ∃ (j : Fin 4) (g : Fin 9), g ∈ T ∧ 10 <
    ∑ h ∈ T.erase g, efx_allsource_three_pair_values j h
Source
Four-agent envy-free one-charity three-split barrier for OP-7; SMT experiment 11699 and independent enumeration 11701. Both are evidence, not Lean proofs.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

In this 4-agent, 9-good fair-division setting, each agent $i$ is initially associated with goods $2i$ and $2i+1$ (having baseline value 10) plus a charity good 8. The theorem establishes that whenever an agent $i$ values a subbundle $T \\subseteq \\{8, 2i, 2i+1\\}$ at strictly more than 10, some good $g \\in T$ can be removed such that some agent $j$ still values $T \\setminus \\{g\\}$ at strictly more than 10. The proof generalizes the statement and delegates the exhaustive verification of all finitely many cases directly to the Lean kernel via computational reflection.

  1. The goal is generalized to a closed universal statement over all agents $i \\in \\mathrm{Fin}\\,4$ and candidate subsets $T \\subseteq \\{8, 2i, 2i+1\\}$.

    Reverting $i$ and $T$ moves the parameters and their governing hypotheses back into the target, transforming the goal into a self-contained universal sentence.

    line 6

      revert i T
  2. For every agent $i$ and every subset $T \\subseteq \\{8, 2i, 2i+1\\}$ with valuation strictly exceeding 10, there exists an agent $j$ and a good $g \\in T$ such that $j$'s valuation of $T \\setminus \\{g\\}$ also strictly exceeds 10. automation

    Because the agent set $\\mathrm{Fin}\\,4$, the good set $\\mathrm{Fin}\\,9$, and the subsets of a 3-element set are finite, the universal quantification is a bounded combinatorial problem. The `decide +kernel` tactic evaluates the decidable predicate by exhaustive computation in the Lean kernel, closing the goal.

    line 7

      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

theorem efx_allsource_three_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 : 10 < ∑ g ∈ T, efx_allsource_three_pair_values i g) :  ∃ (j : Fin 4) (g : Fin 9), g ∈ T ∧ 10 <    ∑ h ∈ T.erase g, efx_allsource_three_pair_values j h := by  revert i T  decide +kernel
See it in the graphDiscuss this resultChallenge it