AFTD Auto-Formalizing Theoretical Domains

team_thm4_part2_exists

def

Theorem 4 (2) of arXiv:2605.21234 under its most generous (existential) reading: some maximum-weight matching M* satisfies the bound.

Statement

open Finset in
def team_thm4_part2_exists (ε : ℕ → ℝ) (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 4
  • team_weightA line-up of team 1 against the fixed line-up of team 2 is a perfect matching, i.e. a permutation π of the n positions (player i of team 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…
  • team_isMaxWeightπ is a maximum-weight perfect matching.
  • team_isOptimalπ is an optimal line-up (maximises the winning probability).
Used by 1
  • 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…

Lean source view module on GitHub

open Finset in
/-- Theorem 4 (2) of arXiv:2605.21234 under its most generous (existential) reading: some maximum-weight matching `M*` satisfies the bound. -/
def team_thm4_part2_exists (ε : ℕ → ℝ) (N : ℕ) : Prop :=
  ∀ n ≥ N, ∀ P : Fin n → Fin n → ℝ, (∀ i j, 0 ≤ P i j ∧ P i j ≤ 1) →
    ∀ O : Equiv.Perm (Fin n), team_isOptimal P O →
      ∃ Mstar : Equiv.Perm (Fin n), team_isMaxWeight P Mstar ∧
        ((n : ℝ) / 2 - Real.sqrt n * Real.log n ≤ team_weight P Mstar →
          team_weight P Mstar ≤ (n : ℝ) / 2 + Real.sqrt n * Real.log n →
          team_winProb P O ≤ team_winProb P Mstar
            + (4 + ε n) / ((n : ℝ) + 1) * ∑ i, (P i (Mstar i) - 1 / 2) ^ 2)
See it in the graphDiscuss this resultChallenge it