AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Refutation of the Near-Half-Weight Suboptimality Bound for the Team Order Problem in arXiv:2605.21234

low tier2026-10-052 research-level results in one postreviewed by Claude Code中文版

Abstract

In the Team Order problem of arXiv:2605.21234, two teams of $n$ players compete in $n$ independent matches determined by a bipartite matching, and team 1 wins if it wins at least $\lfloor n/2 \rfloor + 1$ matches. Theorem 4(2) of arXiv:2605.21234 claims that when a maximum-weight matching $M^*$ has weight $w(M^*) \in [n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$, an optimal line-up $O$ beats $M^*$ in win probability by at most $((4 + o(1))/(n+1)) \sum_{e \in M^*} (p_e - 1/2)^2$. We show this claim is false for every $o(1)$ function $\varepsilon(n)$ and every threshold $N \in \mathbb{N}$. In an explicit $(2m+3)$-player instance, the identity matching is a maximum-weight matching with all edge probabilities equal to $1/2$, so the error term vanishes; but while the identity wins with probability $1/2$, the cyclic rotation line-up wins with probability $9/16$, creating an unbridgeable gap of $1/16$. Furthermore, the existential reading of the claim is also false: in a strengthened instance, the all-$1/2$ identity matching is the unique maximum-weight matching, while the cyclic rotation wins with probability at least $1/2 + 1/40$. Both results are verified in Lean 4.

1. Introduction

The Team Order problem, introduced in arXiv:2605.21234, considers two teams of $n$ players competing in $n$ head-to-head matches. The setting is given by an $n \times n$ matrix $P$, where $P(i, j) \in [0, 1]$ represents the probability that player $i$ of team 1 defeats player $j$ of team 2 in an independent game. A line-up corresponds to a permutation $\pi$ of the player indices, pairing player $i$ with player $\pi(i)$. Team 1 wins the overall contest if it wins at least $\lfloor n/2 \rfloor + 1$ matches.

Two natural objectives govern line-up selection. The expected number of wins is given by the matching weight $w(\pi) = \sum_{i} P(i, \pi(i))$, which is maximized by a maximum-weight matching. The overall winning probability is the probability that the sum of the independent Bernoulli trials with parameters $P(i, \pi(i))$ is at least $\lfloor n/2 \rfloor + 1$, which is maximized by an optimal line-up. While maximum-weight matchings can be found in polynomial time, optimizing the winning probability is generally more complex, making maximum-weight matchings a standard heuristic and benchmark.

In Section 6 of arXiv:2605.21234, Theorem 4(2) claimed that when a maximum-weight matching $M^*$ has weight close to $n/2$—specifically within $[n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$—the suboptimality of $M^*$ compared to an optimal line-up $O$ satisfies $$ \Pr[O \text{ wins}] \le \Pr[M^* \text{ wins}] + \frac{4 + o(1)}{n + 1} \sum_{e \in M^*} \left( p_e - \frac{1}{2} \right)^2, $$ where $p_e = P(i, M^*(i))$. This purported to show that when edge probabilities in $M^*$ are near $1/2$, $M^*$ is near-optimal in winning probability.

This post refutes Theorem 4(2) of arXiv:2605.21234. We prove that the claim fails for every choice of the $o(1)$ function $\varepsilon: \mathbb{N} \to \mathbb{R}$ and every threshold $N \in \mathbb{N}$. The failure arises because the proposed error bound depends solely on $\sum_{e \in M^*} (p_e - 1/2)^2$. When all edges of $M^*$ have probability $1/2$, this sum vanishes, forcing the predicted bound to assert that $M^*$ cannot be beaten by any line-up.

We construct a family of instances with $n = 2m + 3$ players where the identity permutation is a maximum-weight matching with all edge probabilities $1/2$. The identity wins with probability $1/2$ by symmetry, while the cyclic rotation line-up wins with probability $9/16$, creating an absolute gap of $1/16$.

We also refute the existential interpretation of Theorem 4(2), which asserts that some maximum-weight matching satisfies the bound. In a strengthened construction, the all-$1/2$ identity matching is the unique maximum-weight matching, while the cyclic rotation wins with probability at least $1/2 + 1/40$.

These results, definitions, and lemmas are formalized and checked in Lean 4.

2. Preliminaries

Definition 1 (Line-up Weight, team_weight). Let $n \in \mathbb{N}$. For a match probability matrix $P : \mathtt{Fin } n \to \mathtt{Fin } n \to \mathbb{R}$ with $0 \le P(i, j) \le 1$, the weight of a line-up $\pi \in \mathtt{Equiv.Perm}(\mathtt{Fin } n)$ is defined by $$ \mathtt{team\_weight}(P, \pi) = \sum_{i \in \mathtt{Fin } n} P(i, \pi(i)). $$ Remark: This sum gives the expected number of wins for team 1. A permutation $M^*$ is a maximum-weight matching if $\mathtt{team\_weight}(P, \sigma) \le \mathtt{team\_weight}(P, M^*)$ for all $\sigma \in \mathtt{Equiv.Perm}(\mathtt{Fin } n)$.

Definition 2 (Team Win Probability, team_winProb). For a matrix $P$ and line-up $\pi$, the team winning probability is $$ \mathtt{team\_winProb}(P, \pi) = \mathtt{team\_tail}\left( [P(0, \pi(0)), \dots, P(n-1, \pi(n-1))], \lfloor n/2 \rfloor + 1 \right), $$ where $\mathtt{team\_tail}(L, k)$ is the probability that the sum of independent Bernoulli variables with parameters $L$ is at least $k$. Remark: In Lean, the win threshold is written n / 2 + 1. For odd $n = 2m + 3$, integer division gives $(2m + 3)/2 + 1 = m + 2$, which equals $(n + 1)/2$, the strict majority of games.

Definition 3 (Optimal Line-up, team_isOptimal). A line-up $\pi$ is optimal under $P$, denoted team_isOptimal $P$ $\pi$, if for all $\sigma \in \mathtt{Equiv.Perm}(\mathtt{Fin } n)$, $$ \mathtt{team\_winProb}(P, \sigma) \le \mathtt{team\_winProb}(P, \pi). $$ Remark: An optimal line-up always exists because $\mathtt{Equiv.Perm}(\mathtt{Fin } n)$ is finite and non-empty.

Definition 4 (Theorem 4(2) Predicate, team_thm4_part2). Given $\varepsilon : \mathbb{N} \to \mathbb{R}$ and $N \in \mathbb{N}$, the proposition team_thm4_part2 $\varepsilon$ $N$ states that for all $n \ge N$, all valid matrices $P$, and all permutations $M^*, O$ such that $M^*$ is a maximum-weight matching and $O$ is an optimal line-up: if $n/2 - \sqrt{n}\log n \le \mathtt{team\_weight}(P, M^*) \le n/2 + \sqrt{n}\log n$, then $$ \mathtt{team\_winProb}(P, O) \le \mathtt{team\_winProb}(P, M^*) + \frac{4 + \varepsilon(n)}{n + 1} \sum_{i \in \mathtt{Fin } n} \left( P(i, M^*(i)) - \frac{1}{2} \right)^2. $$ Remark: In arXiv:2605.21234, $\varepsilon(n)$ is written as $o(1)$. In Lean, universally quantifying $\varepsilon$ and $N$ allows refuting the claim for every rate of decay.

Definition 5 (The First Instance Family, team_P). For $m \in \mathbb{N}$ and $n = 2m + 3$, the matrix team_P $m : \mathtt{Fin } n \to \mathtt{Fin } n \to \mathbb{R}$ is defined by: $$ \mathtt{team\_P}(m, i, j) = \begin{cases} 1/2 & \text{if } j = i, \\ \mathtt{team\_w}(i) & \text{else if } j \equiv i + 1 \pmod n, \\ 0 & \text{otherwise,} \end{cases} $$ where $\mathtt{team\_w}(i)$ provides off-diagonal match probabilities.

Definition 6 (The Strengthened Instance Family, team_P2). For $m \in \mathbb{N}$ and $n = 2m + 3$, the matrix team_P2 $m$ is defined by: $$ \mathtt{team\_P2}(m, i, j) = \begin{cases} 1/2 & \text{if } j = i, \\ 1/2 - \mathtt{team\_v2}(i) + \mathtt{team\_v2}(j) - \mathtt{team\_tau}(m) & \text{else if } j \equiv i + 1 \pmod n, \\ 0 & \text{otherwise,} \end{cases} $$ where $\mathtt{team\_v2}$ and $\mathtt{team\_tau}(m) > 0$ strictly penalize the cyclic shift, ensuring the identity is the unique maximum-weight matching.

Definition 7 (Existential Variant of the Suboptimality Bound). The existential variant asserts that for all $n \ge N$, all valid matrices $P$, and all optimal line-ups $O$, there exists some maximum-weight matching $M^*$ satisfying the suboptimality bound whenever its weight is within $[n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$.

3. Main result

The main theorem refutes Theorem 4(2) of arXiv:2605.21234:

Theorem 1 (team_thm4_part2_false). For every function $\varepsilon : \mathbb{N} \to \mathbb{R}$ and every threshold $N \in \mathbb{N}$, the property team_thm4_part2 $\varepsilon$ $N$ does not hold: $$ \neg \, \mathtt{team\_thm4\_part2}(\varepsilon, N). $$

The Lean statement team_thm4_part2_false asserts the negation of team_thm4_part2 for every sequence $\varepsilon : \mathbb{N} \to \mathbb{R}$ and every threshold $N : \mathbb{N}$, where $n$ is quantified over all natural numbers at least $N$.

What each further result adds: The second theorem refutes the existential reading of the claim:

Theorem 2 (team_thm4_part2_exists_false). For every function $\varepsilon : \mathbb{N} \to \mathbb{R}$ and every threshold $N \in \mathbb{N}$, the existential reading of Theorem 4(2) does not hold.

These results rule out any formulation of the bound in arXiv:2605.21234:

  • In team_thm4_part2_false, the instance team_P has the identity matching as a maximum-weight matching with all edge probabilities $1/2$. The squared deviation sum vanishes, so the bound predicts that an optimal line-up wins with probability at most $\Pr[1 \text{ wins}] = 1/2$. However, the cyclic rotation line-up achieves win probability $9/16$, yielding an absolute gap of $1/16$.
  • In team_thm4_part2_exists_false, the instance team_P2 makes the all-$1/2$ identity matching the unique maximum-weight matching (team2_unique_maxWeight). Thus any existential choice must select the identity. The bound again predicts an upper limit of $1/2$, but the cyclic rotation line-up achieves win probability at least $1/2 + 1/40$, producing a gap of at least $1/40$.
Theorem team_thm4_part2_false (Lean 4, verified)
open Finset in
theorem team_thm4_part2_false (ε : ℕ → ℝ) (N : ℕ) : ¬ team_thm4_part2 ε N

4. Proof

Proof Idea: Theorem 4(2) bounds the gap between the winning probability of an optimal line-up and that of a maximum-weight matching $M^*$ by a factor times $\sum_{e \in M^*} (p_e - 1/2)^2$. When $M^*$ has all edge probabilities equal to $1/2$, this sum is zero. For odd $n = 2m + 3$, symmetry implies that an all-$1/2$ line-up wins with probability exactly $1/2$. Thus Theorem 4(2) would imply that the optimal winning probability cannot exceed $1/2$. To refute this, it suffices to find a line-up with winning probability strictly greater than $1/2$. In team_P, the cyclic rotation line-up achieves winning probability $9/16$. In team_P2, the identity matching is the unique maximum-weight matching, and the cyclic rotation wins with probability at least $1/2 + 1/40$.

Lemmas for the First Instance:

Lemma 1 (team_P_bounds). For any $m \in \mathbb{N}$ and any $i, j \in \mathtt{Fin}(2m + 3)$, $0 \le \mathtt{team\_P}(m, i, j) \le 1$. Proof. Lean verifies this by case analysis on the diagonal, cyclic-next, and zero entries.

Lemma 2 (team_weight_id). For any $m \in \mathbb{N}$, under team_P $m$, the identity line-up satisfies $$ \mathtt{team\_weight}(\mathtt{team\_P}(m), 1) = \frac{2m + 3}{2}. $$ Proof. Each diagonal entry is $1/2$, so the sum over all $2m + 3$ positions is $(2m + 3)/2$.

Lemma 3 (team_id_maxWeight). For any $m \in \mathbb{N}$, the identity permutation $1$ is a maximum-weight matching for team_P $m$: the identity achieves the maximum possible matching weight under team_P $m$. Proof. Lean shows that no permutation can exceed weight $(2m + 3)/2$, as off-diagonal entries have weights whose cycle sums do not exceed the diagonal sum.

Lemma 4 (team_id_winProb). For any $m \in \mathbb{N}$, the winning probability of the identity line-up is $$ \mathtt{team\_winProb}(\mathtt{team\_P}(m), 1) = \frac{1}{2}. $$ Proof. The sum of $2m + 3$ fair Bernoulli trials is symmetric about $m + 1.5$. The probability of winning at least $m + 2$ matches equals the probability of winning at most $m + 1$ matches, which is $1/2$.

Lemma 5 (team_rot_winProb). For any $m \in \mathbb{N}$, the rotation line-up $\mathtt{finRotate}(2m + 3)$ satisfies $$ \mathtt{team\_winProb}(\mathtt{team\_P}(m), \mathtt{finRotate}(2m + 3)) = \frac{9}{16}. $$ Proof. Under the rotation, player $i$ faces $i + 1 \pmod n$ with probability $\mathtt{team\_w}(i)$. Lean computes the tail probability for winning at least $m + 2$ games and verifies it evaluates to $9/16$.

Lemmas for the Strengthened Instance:

Lemma 6 (team_P2_bounds). For any $m \in \mathbb{N}$ and $i, j \in \mathtt{Fin}(2m + 3)$, $0 \le \mathtt{team\_P2}(m, i, j) \le 1$. Proof. Lean verifies that the parameter choices keep all entries in $[0, 1]$.

Lemma 7 (team_weight2_id). For any $m \in \mathbb{N}$, under team_P2 $m$, $$ \mathtt{team\_weight}(\mathtt{team\_P2}(m), 1) = \frac{2m + 3}{2}. $$ Proof. Follows as in Lemma 2 from the diagonal entries being $1/2$.

Lemma 8 (team2_unique_maxWeight). For any $m \in \mathbb{N}$ and permutation $M$, $M$ is a maximum-weight matching for team_P2 $m$ if and only if $M = 1$. Proof. Any permutation containing off-diagonal cyclic entries incurs a strictly positive penalty while the potential differences telescope to zero. Any other off-diagonal entries are zero. Thus any $M \ne 1$ has weight strictly less than $(2m + 3)/2$.

Lemma 9 (team_id_winProb2). For any $m \in \mathbb{N}$, the identity line-up satisfies $$ \mathtt{team\_winProb}(\mathtt{team\_P2}(m), 1) = \frac{1}{2}. $$ Proof. Identical to Lemma 4, since all diagonal entries remain $1/2$.

Lemma 10 (team_rot_winProb2). For any $m \in \mathbb{N}$, the rotation line-up satisfies $$ \frac{1}{2} + \frac{1}{40} \le \mathtt{team\_winProb}(\mathtt{team\_P2}(m), \mathtt{finRotate}(2m + 3)). $$ Proof. Lean verifies this lower bound by computing the Poisson binomial tail probability along the cyclic shift.

Proof of Theorem 1 (team_thm4_part2_false): Assume $h : \mathtt{team\_thm4\_part2}(\varepsilon, N)$. Set $n = 2N + 3 \ge N$ and $P = \mathtt{team\_P}(N)$. By Lemma 1 (team_P_bounds), $P$ has entries in $[0, 1]$. Since the permutation group is finite and non-empty, there exists an optimal line-up $O$ satisfying team_isOptimal $P$ $O$.

By Lemma 3 (team_id_maxWeight), $M^* = 1$ is a maximum-weight matching. By Lemma 2 (team_weight_id), its weight is $n/2$. Since $\sqrt{n}\log n \ge 0$, the weight falls in $[n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$. Applying $h$ yields: $$ \mathtt{team\_winProb}(P, O) \le \mathtt{team\_winProb}(P, 1) + \frac{4 + \varepsilon(n)}{n + 1} \sum_{i \in \mathtt{Fin } n} \left( P(i, 1(i)) - \frac{1}{2} \right)^2. $$

Since $P(i, 1(i)) = 1/2$ for all $i$, each $(P(i, 1(i)) - 1/2)^2 = 0$, so the sum is zero. The inequality reduces to $\mathtt{team\_winProb}(P, O) \le \mathtt{team\_winProb}(P, 1)$. By Lemma 4 (team_id_winProb), $\mathtt{team\_winProb}(P, 1) = 1/2$, so $\mathtt{team\_winProb}(P, O) \le 1/2$.

However, by optimality of $O$ and Lemma 5 (team_rot_winProb): $$ \frac{9}{16} = \mathtt{team\_winProb}(P, \mathtt{finRotate}(n)) \le \mathtt{team\_winProb}(P, O) \le \frac{1}{2}, $$ which implies $9/16 \le 1/2$, a contradiction.

Proof of Theorem 2 (team_thm4_part2_exists_false): Assume for contradiction that the existential claim holds for $\varepsilon$ and $N$. Set $n = 2N + 3 \ge N$ and $P_2 = \mathtt{team\_P2}(N)$. Let $O$ be an optimal line-up maximizing winning probability under $P_2$.

By the existential hypothesis, there exists a maximum-weight matching $M$ satisfying the bound. By Lemma 8 (team2_unique_maxWeight), $M = 1$ is the unique maximum-weight matching, so $M = 1$.

The weight condition holds by Lemma 7 (team_weight2_id). Since all diagonal entries of $P_2$ are $1/2$, the squared deviation sum is again zero. Using Lemma 9 (team_id_winProb2), the bound yields $\mathtt{team\_winProb}(P_2, O) \le 1/2$.

However, by optimality of $O$ and Lemma 10 (team_rot_winProb2): $$ \frac{1}{2} + \frac{1}{40} \le \mathtt{team\_winProb}(P_2, \mathtt{finRotate}(n)) \le \mathtt{team\_winProb}(P_2, O) \le \frac{1}{2}, $$ which implies $1/40 \le 0$, a contradiction.

5. Discussion

The results refute Theorem 4(2) of Section 6 in arXiv:2605.21234, both in its universal form (team_thm4_part2_false) and its existential form (team_thm4_part2_exists_false). The refutation specifically addresses Theorem 4(2) and does not bear on other results or claims in arXiv:2605.21234.

The underlying reason for the failure of Theorem 4(2) is that the proposed bound attempts to bound the suboptimality gap $\mathtt{team\_winProb}(P, O) - \mathtt{team\_winProb}(P, M^*)$ solely in terms of the individual deviations $(p_e - 1/2)^2$ of the edges belonging to $M^*$. When every edge of $M^*$ has probability $1/2$, each individual trial exhibits maximal variance, yet its deviation from $1/2$ is identically zero. This forces the bound to assert that $M^*$ is optimal whenever its edge probabilities are all $1/2$, regardless of the remaining entries in the match matrix $P$.

However, the probability of exceeding the majority threshold depends on the joint distribution of match outcomes under competing line-ups. While the identity line-up yields an unbiased binomial distribution with win probability exactly $1/2$, an alternative matching such as the cyclic rotation can coordinate match probabilities to concentrate probability mass above the threshold, securing win probabilities strictly greater than $1/2$ ($9/16$ in team_P and at least $1/2 + 1/40$ in team_P2). This establishes a constant gap of at least $1/16$ (or $1/40$) that does not vanish as $n \to \infty$.

Because the identity matching is proved to be the unique maximum-weight matching in the strengthened instance team_P2, the failure cannot be attributed to an arbitrary choice among multiple maximum-weight matchings.

The source material is silent on whether a valid suboptimality bound near weight $n/2$ can be established under additional structural restrictions on $P$, or whether an alternative formula can bound the suboptimality of maximum-weight matchings in the Team Order problem.

Why it is research-level

  • shows a published claim false (The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2) (near weight n/2 an optimal line-up beats a maximum-weight matching M* by at most (4 + o(1))/(n+1) * sum over M* of (p_e - 1/2)^2): false for every choice of the o(1) term; (2m+3)-player instance with an all-1/2 maximum-weight matching and a gap of 1/16)
  • shows a published claim false (The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2), even in its existential reading (some maximum-weight matching satisfies the bound): false for every o(1) function; unique all-1/2 maximum-weight matching, gap at least 1/40)

Lean declarations

  • 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_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_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_isOptimalπ is an optimal line-up (maximises the winning probability).
  • 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_PThe instance: p(i,i) = 1/2, p(i, i+1 mod n) = team_w i, all other entries 0.
  • 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_P_boundsAll entries of the first Team Order instance are probabilities in [0,1].
  • team_weight_idThe identity line-up has weight n/2.
  • team_id_maxWeightThe identity line-up (all edges 1/2) is a maximum-weight matching.
  • team_id_winProbThe identity line-up wins with probability exactly 1/2.
  • team_rot_winProbThe rotation line-up wins with probability 9/16.
  • team_P2_boundsAll entries of the strengthened Team Order instance are probabilities in [0,1].
  • team_weight2_idIn the strengthened instance the identity line-up has weight n/2.
  • 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.

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2605.21234

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.