2025-11-22T11:37:16.514818

The football model, stochastic ordering and martingale transport

Guo, Juillet, Tang

Tournaments are competitions between a number of teams, the outcome of which determines the relative strength or rank of each team. In many cases, the strength of a team in the tournament is given by a score. Perhaps, the most striking mathematical result on the tournament is Moon's theorem, which provides a necessary and sufficient condition for a feasible score sequence via majorization. To give a probabilistic interpretation of Moon's result, Aldous and Kolesnik introduced the football model, the existence of which gives a short proof of Moon's theorem. However, the existence proof of Aldous and Kolesnik is nonconstructive, leading to the question of a ``canonical'' construction of the football model. The purpose of this paper is to provide explicit constructions of the football model with an additional stochastic ordering constraint, which can be formulated by martingale transport. Two solutions are given: one is by solving an entropy optimization problem via Sinkhorn's algorithm, and the other relies on the idea of shadow couplings. It turns out that both constructions yield the property of strong stochastic transitivity. The nontransitive situations of the football model are also considered.

academic

The Football Model, Stochastic Ordering and Martingale Transport

基本信息

论文ID: 2503.07145
标题: The Football Model, Stochastic Ordering and Martingale Transport
作者: Gaoyue Guo, Nicolas Juillet, Wenpin Tang
分类: math.PR (概率论)
发表时间: 2025年10月17日
论文链接: https://arxiv.org/abs/2503.07145

锦标赛理论：锦标赛是多支队伍之间的两两比较，目的是确定队伍的相对强度或排名。在n队循环赛中，每支队伍都与其他每支队伍比赛。
Moon定理：这是随机锦标赛理论中最基本的数学结果，通过优势化提供了可行得分序列的充要条件。具体来说，对于得分向量x = (x₁,...,xₙ)，广义锦标赛矩阵集合Gₙ(x)非空当且仅当x ⪯ (0,1,...,n-1)。
现有模型的局限性：
- Zermelo-Bradley-Terry模型：每支队伍i的强度由正数uᵢ指定，但自由度有限
- 足球模型：Aldous和Kolesnik引入，具有更多自由度，但缺乏"规范"构造

研究动机

非建设性证明的问题：虽然足球模型的存在性为Moon定理提供了优雅的证明，但这种证明是非建设性的，缺乏显式构造方法。
规范构造的需求：Aldous和Kolesnik明确提出了寻找"规范"联合分布的挑战，这是凸序表示定理中长期存在的问题。
随机序约束：现有构造缺乏额外的结构约束，特别是强随机传递性(SST)约束。

核心贡献

提供了两种显式构造方法：
- 基于熵优化和Sinkhorn算法的构造
- 基于阴影耦合的构造
建立了随机序约束：证明了在足球模型中存在满足μ₁ ⪯ₛₜₒ ··· ⪯ₛₜₒ μₙ的元素
证明了强随机传递性：两种构造都产生满足SST性质的广义锦标赛矩阵
完整的理论框架：将问题与鞅运输理论联系起来，提供了理论基础
非传递性分析：研究了足球模型中的非传递情况，完整刻画了三元组(p₁₂, p₂₃, p₃₁)

方法详解

任务定义

给定得分向量x ⪯ (0,1,...,n-1)，构造(μ₁,...,μₙ) ∈ Θₙ(x)，其中：

Θₙ(x) := {(μ₁,...,μₙ) ∈ Θₙ : ∫y dμᵢ(y) = xᵢ for 1 ≤ i ≤ n}
Θₙ := {(μ₁,...,μₙ) ∈ P({0,...,n-1})ⁿ : Σᵢ₌₁ⁿ μᵢ = Σₖ₌₀ⁿ⁻¹ δₖ}

目标是找到满足随机序约束μ₁ ⪯ₛₜₒ ··· ⪯ₛₜₒ μₙ的显式构造。

问题转化：将Θₙ(x)识别为双随机矩阵M = (mᵢⱼ)，其中mᵢⱼ = μᵢ({j-1})
约束集合：定义三个约束集合
- C₁：行和约束（概率测度）
- C₂：列和约束（边际约束）
- C₃：重心约束（得分约束）
Sinkhorn迭代：
- 初始化：M⁰ = (1)ₙₓₙ
- 循环更新：
  - k=1: 行归一化
  - k=2: 列归一化
  - k=3: 重心归一化（通过求解多项式方程）

理论保证

唯一性：当x不可约时，熵函数有唯一最小值点
收敛性：Sinkhorn算法收敛到全局最优解
随机序性质：最优解自然满足随机序约束

初始设置：
- μ := U_{(x₁,...,xₙ)} (均匀测度)
- ν := U_{(0,...,n-1)}
阴影递归构造：对每个排列σ ∈ S(n)：
- η^σ₀ := 0, ν^σ₀ := ν
- 递归定义：η^σₖ := η^σₖ₋₁ + S_{ν^σₖ₋₁}(1/n δ_{x^σₖ})
对称化：π* := 1/n! Σ_{σ∈S(n)} π^σ