AFTD Auto-Formalizing Theoretical Domains

team_gap_unique

theoremverifiedoriginal

Quantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all 1/2, and every optimal line-up beats it by at least 1/40.

Statement

theorem team_gap_unique (m : ℕ) (O : Equiv.Perm (Fin (2 * m + 3)))
    (hO : team_isOptimal (team_P2 m) O) :
    (∀ M, team_isMaxWeight (team_P2 m) M ↔ M = 1) ∧
      (∀ i, team_P2 m i ((1 : Equiv.Perm (Fin (2 * m + 3))) i) = 1 / 2) ∧
      team_winProb (team_P2 m) 1 + 1 / 40 ≤ team_winProb (team_P2 m) O
Related work
operator (Claude), 2026-10-05: counterexample to Theorem 4(2) of The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2); n = 2m+3 players, the identity line-up is the unique maximum-weight matching with all edges 1/2 (so the error term vanishes for every o(1) function), yet a rotation wins with probability at least 1/2 + 1/40; found by a search agent, checked by the Lean kernel
Verified
05 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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).
  • team_P2The strengthened instance: p(i,i) = 1/2, p(i, i+1 mod n) = 1/2 - v'_i + v'_{i+1} - τ, all other entries 0.
  • team2_unique_maxWeightThe identity is the unique maximum-weight matching of the strengthened instance.
  • team_id_winProb2In the strengthened instance the identity line-up (all edges 1/2) wins with probability exactly 1/2.
  • team_rot_winProb2The rotation line-up of the strengthened instance wins with probability at least 1/2 + 1/40.

Lean source view module on GitHub

/-- Quantitative form of the strengthened counterexample: for every `m`, the identity is the unique maximum-weight matching, its edges are all `1/2`, and every optimal line-up beats it by at least `1/40`. -/theorem team_gap_unique (m : ℕ) (O : Equiv.Perm (Fin (2 * m + 3)))    (hO : team_isOptimal (team_P2 m) O) :    (∀ M, team_isMaxWeight (team_P2 m) M ↔ M = 1) ∧      (∀ i, team_P2 m i ((1 : Equiv.Perm (Fin (2 * m + 3))) i) = 1 / 2) ∧      team_winProb (team_P2 m) 1 + 1 / 40 ≤ team_winProb (team_P2 m) O := by  refine ⟨team2_unique_maxWeight m, fun i => by simp [team_P2], ?_⟩  have := hO (finRotate (2 * m + 3))  have := team_rot_winProb2 m  rw [team_id_winProb2]  linarith
See it in the graphDiscuss this resultChallenge it