对 arXiv:2605.21234 中团队排阵问题近半权重次优性界的反驳
low tier2026-10-05本文含 2 个研究级成果审阅: Claude CodeEnglish
摘要
在 arXiv:2605.21234 的团队排阵问题中,两支各有 $n$ 名选手的队伍在由二分匹配决定的 $n$ 场独立比赛中进行对抗,若队伍 1 赢得至少 $\lfloor n/2 \rfloor + 1$ 场比赛,则队伍 1 获胜。arXiv:2605.21234 的定理 4(2) 声称,当最大权匹配 $M^*$ 的权重满足 $w(M^*) \in [n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$ 时,最优排阵 $O$ 在获胜概率上超出 $M^*$ 至多 $((4 + o(1))/(n+1)) \sum_{e \in M^*} (p_e - 1/2)^2$。我们证明了该断言对于每个 $o(1)$ 函数 $\varepsilon(n)$ 和每个阈值 $N \in \mathbb{N}$ 均不成立。在一个显式的 $(2m+3)$ 名选手的实例中,恒等匹配是一个所有边概率均等于 $1/2$ 的最大权匹配,因此误差项消失;然而恒等匹配获胜的概率为 $1/2$,而循环轮换排阵获胜的概率为 $9/16$,从而产生了 $1/16$ 的不可逾越的差距。此外,该断言的存在性解读亦不成立:在一个强化实例中,全 $1/2$ 的恒等匹配是唯一的最大权匹配,而循环轮换排阵的获胜概率至少为 $1/2 + 1/40$。两项结果均在 Lean 4 中得到验证。
1. 引言
arXiv:2605.21234 中引入的团队排阵问题考虑两支各有 $n$ 名选手的队伍在 $n$ 场单挑比赛中展开对抗。这一设定由一个 $n \times n$ 矩阵 $P$ 给出,其中 $P(i, j) \in [0, 1]$ 表示队伍 1 的选手 $i$ 在一场独立比赛中击败队伍 2 的选手 $j$ 的概率。一种排阵对应于选手索引的一个置换 $\pi$,将选手 $i$ 与选手 $\pi(i)$ 进行配对。若队伍 1 赢得至少 $\lfloor n/2 \rfloor + 1$ 场比赛,则队伍 1 赢得整场比赛。
两项自然的目标主导着排阵的选择。胜场数的期望值由匹配权重 $w(\pi) = \sum_{i} P(i, \pi(i))$ 给出,它由最大权匹配达到最大。整体获胜概率是参数为 $P(i, \pi(i))$ 的独立伯努利试验之和至少为 $\lfloor n/2 \rfloor + 1$ 的概率,它由最优排阵达到最大。虽然最大权匹配可以在多项式时间内求得,但优化获胜概率通常更为复杂,这使得最大权匹配成为一种标准的启发式方法和基准。
在 arXiv:2605.21234 的第 6 节中,定理 4(2) 声称,当最大权匹配 $M^*$ 的权重接近 $n/2$——具体而言在 $[n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$ 之内时——$M^*$ 相对于最优排阵 $O$ 的次优性满足 $$ \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, $$ 其中 $p_e = P(i, M^*(i))$。该结论据称表明,当 $M^*$ 中的边概率接近 $1/2$ 时,$M^*$ 在获胜概率上接近最优。
本文反驳了 arXiv:2605.21234 的定理 4(2)。我们证明了对于 $o(1)$ 函数 $\varepsilon: \mathbb{N} \to \mathbb{R}$ 的任意选取以及任意阈值 $N \in \mathbb{N}$,该断言均不成立。该断言之所以失败,是因为所提出的误差界仅依赖于 $\sum_{e \in M^*} (p_e - 1/2)^2$。当 $M^*$ 的所有边概率均为 $1/2$ 时,该和式消失为零,从而迫使所预测的上界断言 $M^*$ 不可能被任何排阵所击败。
我们构造了一族具有 $n = 2m + 3$ 名选手的实例,其中恒等置换是一个所有边概率均为 $1/2$ 的最大权匹配。由对称性,恒等置换获胜的概率为 $1/2$,而循环轮换排阵获胜的概率为 $9/16$,从而产生了一个 $1/16$ 的绝对差距。
我们还反驳了定理 4(2) 的存在性解释,该解释断言存在某个最大权匹配满足该上界。在一项强化构造中,全 $1/2$ 的恒等匹配是唯一的最大权匹配,而循环轮换排阵的获胜概率至少为 $1/2 + 1/40$。
这些结果、定义与引理均在 Lean 4 中形式化并经过验证。
2. 预备知识
定义 1(排阵权重,team_weight)。 设 $n \in \mathbb{N}$。对于满足 $0 \le P(i, j) \le 1$ 的比赛概率矩阵 $P : \mathtt{Fin } n \to \mathtt{Fin } n \to \mathbb{R}$,排阵 $\pi \in \mathtt{Equiv.Perm}(\mathtt{Fin } n)$ 的权重定义为 $$ \mathtt{team\_weight}(P, \pi) = \sum_{i \in \mathtt{Fin } n} P(i, \pi(i)). $$ 注:该和式给出了队伍 1 的获胜期望场数。若对所有 $\sigma \in \mathtt{Equiv.Perm}(\mathtt{Fin } n)$ 均有 $\mathtt{team\_weight}(P, \sigma) \le \mathtt{team\_weight}(P, M^*)$,则置换 $M^*$ 是一个最大权匹配。
定义 2(队伍获胜概率,team_winProb)。 对于矩阵 $P$ 和排阵 $\pi$,队伍获胜概率为 $$ \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), $$ 其中 $\mathtt{team\_tail}(L, k)$ 是参数为 $L$ 的独立伯努利变量之和至少为 $k$ 的概率。 注:在 Lean 中,获胜阈值写作 n / 2 + 1。对于奇数 $n = 2m + 3$,整数除法给出 $(2m + 3)/2 + 1 = m + 2$,它等于 $(n + 1)/2$,即对局的严格多数。
定义 3(最优排阵,team_isOptimal)。 排阵 $\pi$ 在 $P$ 下称为最优的(记作 team_isOptimal $P$ $\pi$),如果对所有 $\sigma \in \mathtt{Equiv.Perm}(\mathtt{Fin } n)$, $$ \mathtt{team\_winProb}(P, \sigma) \le \mathtt{team\_winProb}(P, \pi). $$ 注:由于 $\mathtt{Equiv.Perm}(\mathtt{Fin } n)$ 有限且非空,因此最优排阵始终存在。
定义 4(定理 4(2) 谓词,team_thm4_part2)。 给定 $\varepsilon : \mathbb{N} \to \mathbb{R}$ 和 $N \in \mathbb{N}$,命题 team_thm4_part2 $\varepsilon$ $N$ 断言:对于所有 $n \ge N$、所有合法矩阵 $P$,以及所有使得 $M^*$ 是最大权匹配且 $O$ 是最优排阵的置换 $M^*, O$: 若 $n/2 - \sqrt{n}\log n \le \mathtt{team\_weight}(P, M^*) \le n/2 + \sqrt{n}\log n$,则 $$ \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. $$ 注:在 arXiv:2605.21234 中,$\varepsilon(n)$ 写作 $o(1)$。在 Lean 中,对 $\varepsilon$ 和 $N$ 进行全称量化使得能够针对任意衰减速率反驳该断言。
定义 5(第一族实例,team_P)。 对于 $m \in \mathbb{N}$ 及 $n = 2m + 3$,矩阵 team_P $m : \mathtt{Fin } n \to \mathtt{Fin } n \to \mathbb{R}$ 定义为: $$ \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} $$ 其中 $\mathtt{team\_w}(i)$ 给出非对角比赛概率。
定义 6(强化实例族,team_P2)。 对于 $m \in \mathbb{N}$ 及 $n = 2m + 3$,矩阵 team_P2 $m$ 定义为: $$ \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} $$ 其中 $\mathtt{team\_v2}$ 与 $\mathtt{team\_tau}(m) > 0$ 严格惩罚循环移位,确保恒等匹配是唯一的最大权匹配。
定义 7(次优性界的存在性变体)。 存在性变体断言:对于所有 $n \ge N$、所有合法矩阵 $P$ 以及所有最优排阵 $O$,只要某个最大权匹配 $M^*$ 的权重落在 $[n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$ 之内,就存在该最大权匹配 $M^*$ 满足次优性界。
3. 主要结果
主定理反驳了 arXiv:2605.21234 的定理 4(2):
定理 1(team_thm4_part2_false)。 对于每个函数 $\varepsilon : \mathbb{N} \to \mathbb{R}$ 和每个阈值 $N \in \mathbb{N}$,性质 team_thm4_part2 $\varepsilon$ $N$ 均不成立: $$ \neg \, \mathtt{team\_thm4\_part2}(\varepsilon, N). $$
Lean 语句 team_thm4_part2_false 断言了对每个序列 $\varepsilon : \mathbb{N} \to \mathbb{R}$ 和每个阈值 $N : \mathbb{N}$,team_thm4_part2 的否定均成立,其中 $n$ 在所有不小于 $N$ 的自然数上量化。
各后续结果所增添的内容: 第二个定理反驳了该断言的存在性解读:
定理 2(team_thm4_part2_exists_false)。 对于每个函数 $\varepsilon : \mathbb{N} \to \mathbb{R}$ 和每个阈值 $N \in \mathbb{N}$,定理 4(2) 的存在性解读均不成立。
这些结果排除了 arXiv:2605.21234 中该上界的任何表述形式:
- 在
team_thm4_part2_false中,实例team_P将恒等匹配作为所有边概率均为 $1/2$ 的最大权匹配。平方偏差和消失为零,因此该界预测最优排阵获胜的概率至多为 $\Pr[1 \text{ wins}] = 1/2$。然而,循环轮换排阵达到的获胜概率为 $9/16$,产生了 $1/16$ 的绝对差距。 - 在
team_thm4_part2_exists_false中,实例team_P2使得全 $1/2$ 的恒等匹配成为唯一的最大权匹配(team2_unique_maxWeight)。因此任何存在性选择都必须选取恒等匹配。该界再次预测了 $1/2$ 的上限,但循环轮换排阵达到的获胜概率至少为 $1/2 + 1/40$,产生了至少 $1/40$ 的差距。
open Finset in theorem team_thm4_part2_false (ε : ℕ → ℝ) (N : ℕ) : ¬ team_thm4_part2 ε N
4. 证明
证明思路: 定理 4(2) 将最优排阵与最大权匹配 $M^*$ 之间的获胜概率差距界定为一个因子乘以 $\sum_{e \in M^*} (p_e - 1/2)^2$。当 $M^*$ 的所有边概率均等于 $1/2$ 时,该和式为零。对于奇数 $n = 2m + 3$,由对称性可知全 $1/2$ 的排阵获胜概率恰好为 $1/2$。因此定理 4(2) 将意味着最优获胜概率不能超过 $1/2$。为了反驳这一点,只需找到一个获胜概率严格大于 $1/2$ 的排阵。在 team_P 中,循环轮换排阵达到的获胜概率为 $9/16$。在 team_P2 中,恒等匹配是唯一的最大权匹配,且循环轮换排阵获胜的概率至少为 $1/2 + 1/40$。
第一族实例的引理:
引理 1(team_P_bounds)。 对任意 $m \in \mathbb{N}$ 及任意 $i, j \in \mathtt{Fin}(2m + 3)$,有 $0 \le \mathtt{team\_P}(m, i, j) \le 1$。 证明。Lean 通过对对角元、循环下一项元和零元进行分情况讨论验证了此引理。
引理 2(team_weight_id)。 对任意 $m \in \mathbb{N}$,在 team_P $m$ 下,恒等排阵满足 $$ \mathtt{team\_weight}(\mathtt{team\_P}(m), 1) = \frac{2m + 3}{2}. $$ 证明。每个对角元均为 $1/2$,因此对所有 $2m + 3$ 个位置求和即为 $(2m + 3)/2$。
引理 3(team_id_maxWeight)。 对任意 $m \in \mathbb{N}$,恒等置换 $1$ 是 team_P $m$ 的最大权匹配: 在 team_P $m$ 下,恒等置换达到了最大可能的匹配权重。 证明。Lean 表明没有置换的权重可以超过 $(2m + 3)/2$, 因为非对角元的权重的环和不超过对角和。
引理 4(team_id_winProb)。 对任意 $m \in \mathbb{N}$,恒等排阵的获胜概率为 $$ \mathtt{team\_winProb}(\mathtt{team\_P}(m), 1) = \frac{1}{2}. $$ 证明。$2m + 3$ 个公平伯努利试验之和关于 $m + 1.5$ 对称。赢得至少 $m + 2$ 场比赛的概率等于赢得至多 $m + 1$ 场比赛的概率,该概率为 $1/2$。
引理 5(team_rot_winProb)。 对任意 $m \in \mathbb{N}$,轮换排阵 $\mathtt{finRotate}(2m + 3)$ 满足 $$ \mathtt{team\_winProb}(\mathtt{team\_P}(m), \mathtt{finRotate}(2m + 3)) = \frac{9}{16}. $$ 证明。在轮换下,选手 $i$ 以概率 $\mathtt{team\_w}(i)$ 面对 $i + 1 \pmod n$。Lean 计算了赢得至少 $m + 2$ 局的尾部概率,并验证其求值结果为 $9/16$。
强化实例的引理:
引理 6(team_P2_bounds)。 对任意 $m \in \mathbb{N}$ 及 $i, j \in \mathtt{Fin}(2m + 3)$,有 $0 \le \mathtt{team\_P2}(m, i, j) \le 1$。 证明。Lean 验证了参数选取保证所有元素均落在 $[0, 1]$ 内。
引理 7(team_weight2_id)。 对任意 $m \in \mathbb{N}$,在 team_P2 $m$ 下, $$ \mathtt{team\_weight}(\mathtt{team\_P2}(m), 1) = \frac{2m + 3}{2}. $$ 证明。与引理 2 类似,由对角元均为 $1/2$ 直接得出。
引理 8(team2_unique_maxWeight)。 对任意 $m \in \mathbb{N}$ 及置换 $M$,$M$ 是 team_P2 $m$ 的最大权匹配当且仅当 $M = 1$。 证明。任何包含非对角循环元素的置换都会招致严格正的惩罚,而势能差发生裂项相消为零。其余所有非对角元素均为零。因此任何 $M \ne 1$ 的权重均严格小于 $(2m + 3)/2$。
引理 9(team_id_winProb2)。 对任意 $m \in \mathbb{N}$,恒等排阵满足 $$ \mathtt{team\_winProb}(\mathtt{team\_P2}(m), 1) = \frac{1}{2}. $$ 证明。与引理 4 完全相同,因为所有对角元仍为 $1/2$。
引理 10(team_rot_winProb2)。 对任意 $m \in \mathbb{N}$,轮换排阵满足 $$ \frac{1}{2} + \frac{1}{40} \le \mathtt{team\_winProb}(\mathtt{team\_P2}(m), \mathtt{finRotate}(2m + 3)). $$ 证明。Lean 通过计算沿循环移位的泊松二项尾部概率验证了该下界。
定理 1 的证明(team_thm4_part2_false): 假设 $h : \mathtt{team\_thm4\_part2}(\varepsilon, N)$。令 $n = 2N + 3 \ge N$ 且 $P = \mathtt{team\_P}(N)$。由引理 1(team_P_bounds),$P$ 的元素均在 $[0, 1]$ 内。由于置换群有限且非空,存在满足 team_isOptimal $P$ $O$ 的最优排阵 $O$。
由引理 3(team_id_maxWeight),$M^* = 1$ 是一个最大权匹配。由引理 2(team_weight_id),其权重为 $n/2$。由于 $\sqrt{n}\log n \ge 0$,该权重落在 $[n/2 - \sqrt{n}\log n, n/2 + \sqrt{n}\log n]$ 内。应用 $h$ 可得: $$ \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. $$
因为对所有 $i$ 均有 $P(i, 1(i)) = 1/2$,所以每个 $(P(i, 1(i)) - 1/2)^2 = 0$,故该和式为零。该不等式化简为 $\mathtt{team\_winProb}(P, O) \le \mathtt{team\_winProb}(P, 1)$。由引理 4(team_id_winProb),$\mathtt{team\_winProb}(P, 1) = 1/2$,因此 $\mathtt{team\_winProb}(P, O) \le 1/2$。
然而,由 $O$ 的最优性以及引理 5(team_rot_winProb): $$ \frac{9}{16} = \mathtt{team\_winProb}(P, \mathtt{finRotate}(n)) \le \mathtt{team\_winProb}(P, O) \le \frac{1}{2}, $$ 这意味着 $9/16 \le 1/2$,产生矛盾。
定理 2 的证明(team_thm4_part2_exists_false): 反设存在性断言对 $\varepsilon$ 和 $N$ 成立。令 $n = 2N + 3 \ge N$ 且 $P_2 = \mathtt{team\_P2}(N)$。设 $O$ 为在 $P_2$ 下最大化获胜概率的最优排阵。
由存在性假设,存在满足该上界的最大权匹配 $M$。由引理 8(team2_unique_maxWeight),$M = 1$ 是唯一的最大权匹配,因此 $M = 1$。
权重条件由引理 7(team_weight2_id)成立。由于 $P_2$ 的所有对角元均为 $1/2$,平方偏差和再次为零。由引理 9(team_id_winProb2),该上界给出 $\mathtt{team\_winProb}(P_2, O) \le 1/2$。
然而,由 $O$ 的最优性以及引理 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}, $$ 这意味着 $1/40 \le 0$,产生矛盾。
5. 讨论
这些结果在全称形式(team_thm4_part2_false)和存在形式(team_thm4_part2_exists_false)上均反驳了 arXiv:2605.21234 第 6 节中的定理 4(2)。该反驳专门针对定理 4(2),不涉及 arXiv:2605.21234 中的其他结果或断言。
定理 4(2) 失效的根本原因在于,所提出的界试图仅通过属于 $M^*$ 的边的个别偏差 $(p_e - 1/2)^2$ 来界定次优性差距 $\mathtt{team\_winProb}(P, O) - \mathtt{team\_winProb}(P, M^*)$。当 $M^*$ 的每条边的概率均为 $1/2$ 时,每个单独的试验都表现出最大方差,但其与 $1/2$ 的偏差恒等于零。这迫使该界断言:只要 $M^*$ 的边概率全为 $1/2$,$M^*$ 就是最优的,而完全不论比赛矩阵 $P$ 中的其余元素如何。
然而,超过多数阈值的概率取决于竞争排阵下比赛结果的联合分布。虽然恒等排阵产生获胜概率恰好为 $1/2$ 的无偏二项分布,但诸如循环轮换等替代匹配可以协调比赛概率,使概率质量集中在阈值之上,从而获得严格大于 $1/2$ 的获胜概率(在 team_P 中为 $9/16$,在 team_P2 中至少为 $1/2 + 1/40$)。这确立了至少 $1/16$(或 $1/40$)的常数差距,该差距在 $n \to \infty$ 时并不消失。
由于在强化实例 team_P2 中已证明恒等匹配是唯一的最大权匹配,因此该失效不能归咎于在多个最大权匹配之间的任意选取。
原文材料未提及在对 $P$ 施加额外结构限制的条件下,能否在权重接近 $n/2$ 处建立有效的次优性界,也未提及是否有替代公式能够界定团队排阵问题中最大权匹配的次优性。
为什么是研究级成果
- 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 声明
- 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.
参考文献
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。