AFTD Auto-Formalizing Theoretical Domains

team_isOptimal

def

π is an optimal line-up (maximises the winning probability).

Statement

def team_isOptimal {n : ℕ} (P : Fin n → Fin n → ℝ) (π : Equiv.Perm (Fin n)) : Prop
Defined in
The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2); formalized by the operator (Claude), 2026-10-05
Verified
05 Oct 2026
Axioms
none listed
Built on 1
  • team_winProbWinning probability of a line-up in the Team Order problem of arXiv:2605.21234: team 1 wins if it wins at least ⌊n/2⌋ + 1 of the n…
Used by 6
  • team_thm4_part2Theorem 4 (2) of arXiv:2605.21234, with the o(1) term made explicit as a function ε: for all large n, every instance, every maximum-weight…
  • team_gapQuantitative form: on the instance of size 2m+3, the optimal line-up beats the all-1/2 maximum-weight matching by at least 1/16, while the…
  • team_thm4_part2_exists_falseEven the existential reading of Theorem 4 (2) of arXiv:2605.21234 is false, for every function ε in place of o(1): on the (2m+3)-player…
  • team_gap_uniqueQuantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all…
  • team_thm4_part2_falseTheorem 4 (2) of arXiv:2605.21234 is false, whatever function is used for its o(1) term: for every m, on the (2m+3)-player instance the…
  • team_thm4_part2_existsTheorem 4 (2) of arXiv:2605.21234 under its most generous (existential) reading: some maximum-weight matching M* satisfies the bound.

Lean source view module on GitHub

/-- `π` is an optimal line-up (maximises the winning probability). -/
def team_isOptimal {n : ℕ} (P : Fin n → Fin n → ℝ) (π : Equiv.Perm (Fin n)) : Prop :=
  ∀ σ : Equiv.Perm (Fin n), team_winProb P σ ≤ team_winProb P π
See it in the graphDiscuss this resultChallenge it