team_winProb
def
Winning 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 independent matches.
Statement
noncomputable def team_winProb {n : ℕ} (P : Fin n → Fin n → ℝ) (π : Equiv.Perm (Fin n)) : ℝ
- 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_tailPoisson-binomial upper tail: team_tail [q₁, …, qₙ] t is the probability that at least t of n independent events with success probabilities…
- Used by 11
- 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_id_winProb2In the strengthened instance the identity line-up (all edges 1/2) wins with probability exactly 1/2.
- 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_id_winProbThe identity line-up wins with probability exactly 1/2.
- 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_isOptimalπ is an optimal line-up (maximises the winning probability).
- 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_rot_winProbThe rotation line-up wins with probability 9/16.
- team_thm4_part2_existsTheorem 4 (2) of arXiv:2605.21234 under its most generous (existential) reading: some maximum-weight matching M* satisfies the bound.
- 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
/-- Winning 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` independent matches. -/ noncomputable def team_winProb {n : ℕ} (P : Fin n → Fin n → ℝ) (π : Equiv.Perm (Fin n)) : ℝ := team_tail (List.ofFn (fun i => P i (π i))) (n / 2 + 1)