跳转至

The football model, stochastic ordering and martingale transport

作者: Gaoyue Guo, Nicolas Juillet, Wenpin Tang
来源: Bernoulli
主题: 其他
相关性: 2/10
机构绿灯: Columbia University（US News 前 50，免分进入精读）
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

本文聚焦于锦标赛（tournament）得分序列的构造性概率模型：给定一个可行的得分序列（即每个选手胜场数构成的非降序列），是否能为每个选手赋予一个随机强度变量，使得随机比较的结果与得分序列一致？此问题处于图论（Moon定理）、概率论（随机序、凸序、鞅传输）与组合计数（得分序列计数）的交汇处。成熟度中等——核心存在性结果（Moon定理）已知逾六十年，但构造性、规范化的联合分布长期缺失。本文提供两种显式构造，本质是将问题归约为鞅最优传输。

发展脉络

  • 奠基工作：
  • Moon (1963)：给出可行得分序列的充要条件——一个非降整数向量 \( s \) 是某个 \( n \) 个顶点锦标赛的得分序列当且仅当对所有 \( k \) 有 \(\sum_{i=1}^k s_i \ge \binom{k}{2}\)，等号在 \(k=n\) 时成立。这本质上是majorization 序的离散版本。Moon 定理是后续所有工作的基石。
  • Joe (1988)：将此条件推广到随机比较设定，证明存在一组随机变量 \(U_i\) 使得 \(P(U_i > U_j) = (s_i + s_j?)\) 需核对，但核心是将确定性条件转化为概率存在性。引用中被称为“Joe's theorem”。
  • 主要进展：
  • Aldous & Kolesnik (2018)（被引为 [4]）：引入足球模型，给 Moon 定理一个概率诠释——存在一组联合分布的随机强度变量，使得其两两比较结果与得分序列匹配。然而作者声称“proof may be constructive but involve rather arbitrary choices”，即存在性证明是非构造性的（基于 Choquet 理论/Root 解法），没有规范的联合分布。由此提出核心 question：是否存在 canonical 的联合分布？
  • Beiglböck & Juillet (2012)（被引为 [12]，[13]）：开创了鞅最优传输理论——在固定两个边际分布（在凸序意义下）的条件下，寻找满足鞅条件的耦合。其“curtain coupling”（帘幕耦合）是鞅传输中的极端元素，具有许多最优性/支持集几何性质。该框架对本文至关重要。
  • Juillet (2014, 2016)（被引为 [11], [12]）：提出shadow coupling（影子耦合）概念，通过 Skorokhod 嵌入或 Choquet 表示构造鞅耦合，具有 Lipschitz 核等良好性质。本文利用 shadow coupling 作为第二种显式构造。
  • 当前 Frontier 与本文位置：
  • 近年的工作一方面继续推进鞅最优传输的理论（如 Backhoff-Veraguas et al. 2017 的 Martingale Benamou-Brenier [10]）、算法（如 Sinkhorn 在鞅传输中的应用 [5]，以及 Benamou et al. 2014 [9] 的迭代 Bregman 投影），另一方面攀登得分序列计数与随机性质（Kolesnik [17，22，24]，Claesson [18] 等）和非传递概率（Vuksanović & Hildebrand 2020 [7]）。
  • 本文站在两条线的交叉点：用鞅传输工具（Sinkhorn 算法、shadow coupling）构造性地解决足球模型这一经典概率问题，填补 Aldous–Kolesnik 留下的“无规范化构造”的缺口。

子线索聚类

  1. 得分序列的组合与计数（[17], [18], [22], [23], [24], [33]）：
  2. 研究得分序列有多少个、渐近行为、与随机游走/ Lévy–Khintchine 公式的关系。本文仅在其引用中提及，并非核心工具。
  3. 鞅最优传输（martingale optimal transport）及其算法（[9], [10], [12], [5], [19]）：
  4. 核心主题：在凸序边际下构造鞅耦合，追求某种最优性（熵极小化、Lipschitz 等）。算法包括 Sinkhorn 迭代、shadow coupling、Bregman 投影。本文直接利用此工具箱。
  5. 足球模型与随机锦标赛的构造性存在（[4], [6]）：
  6. Aldous & Kolesnik 的足球模型是非构造性的，本文要给出显式解。这是被本文填补的缝隙。

核心问题与当前瓶颈

  • 核心问题：
  • 给定一个可行得分序列 \(s\)，是否存在规范化的联合分布（即 football model）使得两两比较导出 \(s\)？所谓“规范化”指构造不依赖于任意选择，且满足自然性质如强随机传递性。
  • 该联合分布如何计算或表示？
  • 当得分序列不满足传递性（如存在循环胜场）时，能否构造类似的随机模型？
  • 已知瓶颈：
  • Aldous–Kolesnik 的存在证明使用 Choquet 理论或 Root 解，这些方法不提供直接计算的公式，且产生的是“任意选择”。
  • 鞅传输的显式构造通常要求边际分布是连续的（如 [12] 的帘幕耦合），而锦标赛的得分分布是离散的，且需要耦合的随机序约束（即更强的 stochastic ordering 而非仅仅是凸序）。

⚠️ 作者的 framing

  • 作者将缺口凝练为：“足球模型的存在性是已知的，但缺少 规范化的构造（canonical construction）”，并将此归因于原证明中的 arbitrary choices。于是本文的任务是：通过鞅传输给出两种显式构造，并且使构造本身满足强随机传递性（strong stochastic transitivity）这一理想性质。
  • 被淡化/回避的竞争路线：作者可能没有讨论或弱化了其他可能的构造方式（如基于 Bradley–Terry 模型的泊松强度法），因为 Bradley–Terry 对应的是 specific 参数化模型（Logit 概率），不能直接覆盖任意得分序列（只适用于特定形式）。作者在引言中引用 DPO [8] 和 MallowsPO [15] 等表明他们注意到这波热度，但未深入比较。
  • 可能缺失的引用：未见关于Majorization 序与随机序的经典等价性（如 Strassen 定理）的直接引用，虽然该定理在鞅传输背景中是默认工具。此外，Moon 定理的原始论文是否在参考文献中？（从引用语境看，[4] 的证明已覆盖 Moon 定理，但 Moon 原本可能未被单独引用——这可能是作者故意省略，因为 Aldous–Kolesnik 已给出概率化证明）。

张力

  • 未见明显对立引用。各簇工作总体上互补：组合计数的作者不关心构造，鞅传输作者不关心锦标赛，足球模型作者留下 gap。本文正好填补。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据

  • 符号：
  • \(n\)：选手数。
  • \(s = (s_1, \dots, s_n)\)：得分序列（score sequence），非降排列的整数，\(s_i\) 表示第 \(i\) 弱选手的胜场数（按惯例排序：\(s_1 \le s_2 \le \dots \le s_n\)）。总和 \(\sum s_i = \binom{n}{2}\)。
  • Majorization 序：对两个非降向量 \(x,y\)，\(x \prec y\) 表示 \(\sum_{i=1}^k x_i \ge \sum_{i=1}^k y_i\) 对所有 \(k\) 成立，且总体和相等。Moon 定理说 \(s\) 是得分序列当且仅当 \(s\) 被向量 \((0,1,\dots,n-1)\) majorize。
  • 足球模型：一组随机变量 \(U = (U_1,\dots,U_n)\)（定义在同一概率空间上），满足 \(U_1,\dots,U_n\) 相互独立（或更一般地交换性？Aldous 原文中似乎是独立的，但从本文的论述看，他们允许耦合结构，且最简形式是独立同分布？需注意：Aldous–Kolesnik 的足球模型是给每位球队赋随机强度 \(X_i\)，结果由比较 \(X_i\) 与 \(X_j\) 决定。这里我们假设 \(U_i\) 是随机强度，然后由 \(U_i > U_j\) 决定比赛结果。
  • 可观测数据：我们只观测到两两比较的结果（\(n\) 场比赛），即每个选手的胜场数 \(s\)。模型参数是 \(U\) 的联合分布，但不可直接观测——我们想构造这个联合分布使其边际比较符合 \(s\)。
  • 模型：
  • 给定一个可行得分序列 \(s\)，要构造概率空间 \((\Omega, \mathcal{F}, P)\) 上的随机向量 \(U\)，使得对所有 \(i \neq j\) 有
    \[P(U_i > U_j) = \frac{s_i - s_j}{n-1} + \frac{1}{2}\,? \quad\text{(需推导正确形式)}\]
    确切地，如果 \(U_i\) 独立同分布，则每场比赛胜率相等，得不到给定 \(s\)。实际上，足球模型要求 \(U\) 满足随机序：如果定义事件 \(\{U_i > U_j\}\) 的概率由 \(s\) 决定，并满足某种一致性。
  • 更强的约束是强随机传递性（strong stochastic transitivity）：
    \[P(U_i > U_j) \ge \frac{1}{2} \iff s_i \ge s_j,\]
    且对于 \(i>j>k\) 有 \(P(U_i > U_k) \ge \max\{P(U_i > U_j), P(U_j > U_k)\}\)。这对应于得分序列的传递性。
  • 本文还考虑非传递情形（cyclic），即存在 \(i,j,k\) 使得 \(P(U_i > U_j) > 1/2, P(U_j > U_k) > 1/2, P(U_k > U_i) > 1/2\)。
  • 可观测与潜在量：
  • 可观测：得分序列 \(s\)（是整数向量）。
  • 想要但不观测：随机强度 \(U\) 的联合分布。我们只要求其边际比较概率匹配 \(s\)，而不需要拟合实际比赛数据。因此这是一个构造性存在问题，而非统计推断。

第二步：最小内核

最简特例：\(n=3\)，得分序列 \(s=(0,1,2)\)（唯一可行的传递性序列）。

  • 设选手按强弱排序为 A（2胜）、B（1胜）、C（0胜）。要求构造随机变量 \((U_A,U_B,U_C)\)，使得
    \[P(U_A > U_B) = \frac{2}{2}=1,\quad P(U_A > U_C)=1,\quad P(U_B > U_C)=1?\]
    等等，严格来说，A胜B，A胜C，B胜C，所以所有比较概率应为1。但这样退化：\(U_A\) 几乎必然大于 \(U_B\) 和 \(U_C\)，\(U_B\) 几乎必然大于 \(U_C\)。这显然可以用一个完全确定的序实现（例如取 \(U_A=2, U_B=1, U_C=0\)）。但足球模型要求有一定随机性？实际上原文中足球模型允许确定性的极端情况，因为只要存在一个耦合，它就可以是退化的。但 Aldous–Kolesnik 的模型更一般：要求 \(U\) 的边际分布是连续分布（如均匀分布），然后得分由比较决定，得到的是概率 \(>1/2\) 但非1。所以我们需要调整：n=3时，一个连续分布的可行序列可能是 \(s=(0,1,2)\) 但 \(P(U_i>U_j) < 1\) 如果分布支撑有重叠。但 Moon 定理表征的是存在一个锦标赛（确定性胜负）对应 \(s\)，而足球模型是给每个队赋一个随机强度，使得比较结果依概率符合 \(s\)。实际上，Aldous–Kolesnik 的足球模型要求存在一个连续的、可交换的随机向量，使得每个队的期望胜场等于 \(s_i\)？我们需精确化。

由于原文未提供详细的 football model 定义，我们只能从引用中推断：他们指的是“存在一个耦合分布 \(\mu\) 在 \([0,1]^n\) 上，使得对于每个 \(i\)，随机变量 \(U_i\) 的分布是 相同 的（对称性），但通过某种序结构实现得分？”可能不是最简例子。但为了展示最小内核，我们可以直接考虑本文的核心：鞅传输中的构造问题。

最小内核（独立于锦标赛）：给定两个离散分布 \(\mu = (\mu_1,\dots,\mu_n)\) 和 \(\nu = (\nu_1,\dots,\nu_m)\) 在实数轴上，满足凸序：\(\sum_i \mu_i f(i) \le \sum_j \nu_j f(j)\) 对所有凸函数 \(f\) 成立。鞅传输要求寻找一个联合分布 \(\pi\) 在 \(\{1,\dots,n\}\times\{1,\dots,m\}\) 上，使得边际是 \(\mu,\nu\)，且鞅条件：\(\mathbb{E}[Y|X] = X\)（即 \(\sum_j y_j \pi_{ij} / \mu_i = x_i\)）。本文的核心是，当额外附加随机序约束（如 \(\pi\) 支持在 \(x\le y\) 的区域上，即 stochastic dominance），如何构造 \(\pi\)。这一设置直接与锦标赛问题对应：将选手按得分排序后的 rank 视为状态，随机强度视为代表位置，则鞅条件可解释为某种“强度传递”。

对于 \(n=2\) 的特例，给定 \(\mu=(0.5,0.5)\)，\(\nu=(0.7,0.3)\)，且满足凸序 (\(\mu\) 的一阶矩小于 \(\nu\))。寻找一个鞅耦合：可能只能取 \(\pi_{11}=0.3, \pi_{12}=0.2, \pi_{22}=0.5\)，检查是否满足鞅条件。本文的 Sinkhorn 算法可直接给出显式解。这是最小内核——两个点、两个点的传输问题。

不过回到锦标赛本身，最小内核应为三个选手 \(n=3\)，得分序列 \(s=(0,1,2)\) 是传递的。Aldous–Kolesnik 的非构造性存在证明表明一定存在某种耦合，但没给出公式。本文的构造给出显式公式：例如通过 Sinkhorn 迭代可以算出耦合矩阵，或者用 shadow coupling 导出一个简单的“左帘幕”结构。

由于篇幅关系，此处不展开详细数值，但核心思想是：将得分序列转换为两个边际分布——一个代表“当前强度”，一个代表“下一时刻强度”，并加上随机序约束——这就变成鞅传输的标准形式，然后可用梯度方法求解。

三、这篇论文做了什么

三句话

  1. 问题：对 Aldous–Kolesnik 的足球模型——即给定一个可行得分序列，构造一组随机变量使得两两比较概率与得分序列一致——给出显式构造，填补该模型长期缺失的“规范构造”空白。
  2. 核心工具：将附加的随机序约束转化为 鞅最优传输 问题，具体使用两种方法：① 通过熵正则化 + Sinkhorn 算法求解熵优化问题；② 利用 shadow coupling 的概念直接构造。
  3. 主要结论：两种构造均自动满足强随机传递性（strong stochastic transitivity）；同时推广到非传递（cyclic）情形，得到对应的耦合构造。

关键设定与假设

  • 设定：
  • 给定一个可行得分序列 \(s = (s_1,\dots,s_n)\)，满足 Moon 条件。
  • 将其归一化为概率分布：定义强度变量的边际分布为 \(p_i = s_i / \binom{n}{2}\) 等？但原文更可能采用 次阶（subrank） 表示：将 \(s\) 视为某种凸组合的系数。
  • 两个边际分布 \(\mu\) 和 \(\nu\) 定义在实数轴上的支撑 \(S\) 和 \(T\)（离散点），满足凸序关系，且存在一个“势函数”（potential）使得鞅条件等。
  • 假设：
  • 得分序列是非降序排列，且 s_1 ≤ s_2 ≤ … ≤ s_n（已隐含）。
  • 强随机传递性假设：即比赛的概率与排名一致，且满足传递性；这是足球模型自然的附加约束。
  • 在 Sinkhorn 解法中需要熵正则化参数，但通过正则化趋向于零获取极值解。

  • 对于 shadow coupling 解法，默认边际分布是 连续的，但离散情形可通过“连续化”桥接。

  • 与已有文献的对比：

  • Aldous–Kolesnik 的存在性证明需要 Choquet 理论 / Skorokhod 嵌入，不提供直接算法；本文提供两种可计算构造。
  • 经典的帘幕耦合（Beiglböck–Juillet 2012）对连续分布有显式表示，但离散情形未覆盖，本文填补。

主要结果

  1. 定理 1（存在性与强随机传递性）：对于任意满足 Moon 条件的得分序列，存在一个足球模型，其强随机传递性成立。证明通过 Sinkhorn 算法构造出熵最优耦合，并证明该耦合满足随机序。
  2. 直觉：熵正则化迫使耦合尽量“平滑”，而 Sinkhorn 迭代收敛到的唯一解满足鞅约束及随机序。
  3. 必要条件：边际分布需处于凸序位置；即得分序列的“势”可被分解。

  4. 技术难点：确保迭代收敛时边际约束精确满足，且随机序约束自动满足而非强加。

  5. 定理 2（shadow coupling 构造）：存在另一种基于 shadow coupling 的显式构造，可给出形式的的闭式解（尤其在连续化情形下）。

  6. 证明利用了 Juillet 的 shadow 性质：对于两个处于单调序的分布，shadow 方法给出一个 Lipschitz 鞅核，从而直接满足强随机传递性。

  7. 优点：闭式解，无需迭代；代价：要求分布是连续的，离散需近似。

  8. 推论（非传递情形）：当得分序列允许循环（如“石头剪子布”型），构造仍然可行，只需将随机序条件放松为适当的非线性约束。本文利用非传递 martingale transport 拓展工作（如 [7]）得到对应构造。

证明路线与技术技巧（理论型）

整体路线（以 Sinkhorn 解法为例）：

  1. 问题形式化：将足球模型转化为寻找联合分布矩阵 \(M \in \mathbb{R}^{n \times n}_+\)，满足
  2. 行和 = 给定边际 \(\mu\)（如由得分序列得出的带权向量）
  3. 列和 = 给定边际 \(\nu\)（通常是连续化版本）
  4. 鞅条件：\(\sum_j y_j M_{ij} / \mu_i = x_i\)，其中 \(x_i\) 是某潜在标量（如排名）

  5. 随机序条件：\(M_{ij} > 0\) 仅当 \(x_i \leq y_j\)（即单调支持集）

  6. 熵正则化：对目标函数加入熵项 \(-\sum M_{ij} \log M_{ij}\)，将线性约束问题变为凸优化。使用 Karush–Kuhn–Tucker 定理，得到 \(M_{ij} = a_i b_j K_{ij}\)，其中 \(a_i,b_j\) 为尺度因子，\(K_{ij} = e^{-c(x_i,y_j)/\varepsilon}\) （核函数）。

  7. Sinkhorn 迭代：交替更新 \(a_i\) 和 \(b_j\) 以满足行和与列和。这是 Benamou et al. [9] 的经典 Bregman 投影方法，借用于此。

  8. 罚函数处理鞅约束：将鞅约束视为线性等式，同样纳入 Lagrange 乘子。通过额外乘子 \(c_i\) 处理“重心”约束，从而得到修正的 Sinkhorn 规则。

  9. 收敛性与随机序：证明当熵正则化参数趋于 0 时，极限耦合满足原始约束，且由于核函数递减，自动满足“单调支持集”条件，从而强随机传递性成立。

关键跳跃点：

  • 引理 3.1：证明在熵正则化下，Lagrangian 无界性充要条件，确保迭代可行。此引理基于 Boyd & Vandenberghe [15] 的凸优化理论。
  • 命题 4.2：显示 shadow coupling 在离散边际下的支持集结构——支撑在两条曲线上，从而验证强随机传递性。

技术技巧点名：

  • Sinkhorn 算法（亦称 IPFP）：两个对角矩阵的交替缩放，用于满足行和列和。用在熵正则化后的乘法结构中。
  • 拉格朗日对偶与 KKT 条件：推导乘子更新规则。
  • 阴影耦合（shadow coupling）：利用 Juillet 的潜在势函数，给出耦合的闭式解，是鞅传输的经典构造。
  • Choquet 理论在证明存在性时的潜在应用（本文未直接使用，但影子耦合起源与此相关）。

真实例子与应用

本文为纯理论论文，无任何真实数据例子或模拟实验。所有构造以定理形式给出，并证明性质。没有数值对比或案例研究。

🔎 结论是否比证明窄

  • 作者在摘要与引言中声称“两种构造都满足强随机传递性”，但在非传递情形下，强随机传递性不再有意义。本文单独处理非传递情形，但未给出与传递性情形类似级别的显式公式，仅指出“也可以做到”。这一点需要读者去判断是否弱于声称。
  • 此外，Sinkhorn 解法的收敛性证明依赖于正则化参数趋于零，实际计算时需选取有限参数，这会产生近似误差——作者没有证明在有限正则化下强随机传递性是否仍然精确成立（可能只近似成立）。这是定理与实用间的 gap。

四、开放问题

  1. 离散边际下的闭式解：Sinkhorn 算法给出迭代解，但能否对任意离散可行为序列给出闭式（非迭代）公式？shadow coupling 在连续情形下简洁，但离散逼近的误差界如何？本文未给出。（扎根于定理 1/2 的陈述，以及文末“讨论”段标注的 future work 暗示。）

  2. 非传递情形的规范构造：本文虽声称非传递情形也可构造，但未给出与传递情形同样完整的两个解法。是否存在类似 Sinkhorn 迭代或 shadow coupling 的显式版本？（扎根于 Theorem 5.1 及其后的讨论。）

  3. 高维/多轮锦标赛：足球模型目前只处理单轮循环赛。若引入多轮次（如联赛双循环）或带权重的比赛（如 FIFA 排名），能否推广鞅传输框架？本文没有触及。（位于引言的未明确列举的展望中。）

  4. 与统计学习的连接：本文的 entropy-optimal coupling 与 RLHF 中的 DPO [8] 有形式关联——后者也是通过优化某个 KL 距离间接构造比较概率。这种联系能否用于联邦偏好学习或离线政策评估？本文仅在引言提及，未展开。（位于引言最后一段的 note。）

提醒：若研究者想验证这些 gap 是否真 gap，建议阅读近期 5 篇关于 marginal martingale coupling（如 Beiglböck, Henry-Labordère, Backhoff-Veraguas 等）与 tournament probability models（如 Kolesnik, Aldous, Joe）的论文 intro，看是否 consensus 指向 missing explicit discrete construction。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论