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

フットボールモデル、確率的順序付けとマルチンゲール輸送

基本情報

論文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

要旨

本論文はトーナメント理論におけるフットボールモデルを研究する。このモデルは有名なMoon定理の確率論的解釈である。Moon定理は優越化(majorization)を通じて実行可能なスコア列の必要十分条件を与える。AldousとKolesnikが導入したフットボールモデルはMoon定理の簡潔な証明を提供するが、その構成は非構成的である。本論文の目的は、確率的順序付け制約の下でフットボールモデルの明示的構成を提供することであり、これはマルチンゲール輸送を通じて定式化できる。本論文は2つの解決策を提示する：1つはSinkhorn アルゴリズムによるエントロピー最適化問題の求解であり、もう1つは影の結合(shadow coupling)の考え方に基づくものである。両方の構成は強確率的推移性(strong stochastic transitivity)の性質を生成する。

研究背景と動機

問題背景

トーナメント理論：トーナメントは複数チーム間の対比較であり、チームの相対的強度またはランキングを決定することを目的とする。n チームのリーグ戦では、各チームは他のすべてのチームと試合する。
Moon定理：確率的トーナメント理論における最も基本的な数学的結果であり、優越化を通じて実行可能なスコア列の必要十分条件を提供する。具体的には、スコアベクトル x = (x₁,...,xₙ) に対して、一般化トーナメント行列集合 Gₙ(x) が非空であることと x ⪯ (0,1,...,n-1) は同値である。
既存モデルの制限：
- Zermelo-Bradley-Terryモデル：各チーム i の強度は正数 uᵢ で指定されるが、自由度が限定的である
- フットボールモデル：AldousとKolesnikが導入し、より多くの自由度を持つが、「規範的」構成が欠けている

研究動機

非構成的証明の問題：フットボールモデルの存在性はMoon定理の優雅な証明を提供するが、この証明は非構成的であり、明示的構成方法が欠けている。
規範的構成の必要性：AldousとKolesnikは「規範的」結合分布を探す課題を明確に提起しており、これは凸順序表現定理における長年の問題である。
確率的順序付け制約：既存の構成は追加的な構造制約、特に強確率的推移性(SST)制約が欠けている。

核心的貢献

2つの明示的構成方法の提供：
- エントロピー最適化とSinkhorn アルゴリズムに基づく構成
- 影の結合に基づく構成
確率的順序付け制約の確立：フットボールモデルに μ₁ ⪯ₛₜₒ ··· ⪯ₛₜₒ μₙ を満たす要素が存在することを証明
強確率的推移性の証明：両方の構成は強確率的推移性を満たす一般化トーナメント行列を生成
完全な理論的枠組み：問題をマルチンゲール輸送理論と関連付け、理論的基礎を提供
非推移性分析：フットボールモデルにおける非推移的な場合を研究し、三つ組 (p₁₂, p₂₃, p₃₁) を完全に特徴付け

方法の詳細

タスク定義

スコアベクトル x ⪯ (0,1,...,n-1) が与えられたとき、(μ₁,...,μₙ) ∈ Θₙ(x) を構成する。ここで：

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

目標は確率的順序付け制約 μ₁ ⪯ₛₜₒ ··· ⪯ₛₜₒ μₙ を満たす明示的構成を見つけることである。

方法1：エントロピー最適化構成

核心的考え方

エントロピー関数 H(M) = Σᵢ,ⱼ mᵢⱼ log(mᵢⱼ) を最小化することにより、所要の確率測度を構成する。

アルゴリズムの流れ

問題の変換：Θₙ(x) を二重確率行列 M = (mᵢⱼ) として識別する。ここで mᵢⱼ = μᵢ({j-1})
制約集合の定義：3つの制約集合を定義
- C₁：行和制約（確率測度）
- C₂：列和制約（周辺制約）
- C₃：重心制約（スコア制約）
Sinkhorn反復：
- 初期化：M⁰ = (1)ₙₓₙ
- ループ更新：
  - k=1: 行正規化
  - k=2: 列正規化
  - k=3: 重心正規化（多項式方程式の求解を通じて）

理論的保証

一意性：x が既約である場合、エントロピー関数は一意の最小値点を持つ
収束性：Sinkhorn アルゴリズムは大域最適解に収束する
確率的順序付け性質：最適解は自然に確率的順序付け制約を満たす

方法2：影の結合構成

核心的概念

影(shadow)の概念を利用してマルチンゲール輸送計画 π* を構成する。

アルゴリズムのステップ

初期設定：
- μ := U_{(x₁,...,xₙ)} (均一測度)
- ν := U_{(0,...,n-1)}
影の再帰的構成：各順列 σ ∈ S(n) に対して：
- η^σ₀ := 0, ν^σ₀ := ν
- 再帰的定義：η^σₖ := η^σₖ₋₁ + S_{ν^σₖ₋₁}(1/n δ_{x^σₖ})
対称化：π* := 1/n! Σ_{σ∈S(n)} π^σ

理論的性質

マルチンゲール性質：π* はマルチンゲール制約を満たす
周辺分布：正しい周辺分布
確率的順序付け：自然に確率的順序付け制約を生成

技術的革新点

エントロピー最適化方法の適応：標準的なエントロピー最適化方法をマルチンゲール輸送問題に適応させ、重心制約という技術的困難を処理
影の結合の応用：影の結合理論をフットボールモデルの構成に革新的に応用
統一的な理論的枠組み：2つの一見異なる方法をマルチンゲール輸送の枠組みの下で統一
既約な場合の処理：既約なスコアに対して、ブロック処理の完全な方案を提供

実験設定

理論的検証

本論文は主に理論的研究であり、実験部分は以下に集中している：

アルゴリズム収束性の検証：異なるパラメータの下でのSinkhorn アルゴリズムの収束性を検証
数値安定性テスト：異なる規模の問題における2つの方法の数値安定性をテスト
SST性質の検証：構成された行列が実際に強確率的推移性を満たすことを検証

実装の詳細

多項式求解：Sinkhorn アルゴリズムの第3ステップにおいて、Newton法を使用して単変数多項式方程式を求解
数値精度：すべての計算は倍精度浮動小数点数精度を保持
収束判定：相対誤差を収束判定基準として使用

実験結果

主要な理論的結果

存在性定理（命題2.2）：x ⪯ (0,...,n-1) に対して、(μ₁,...,μₙ) ∈ Θₙ(x) が存在し、(μᵢ) は確率的順序付けで増加する
SST性質（命題2.4）：確率的順序付け制約の下で、対応する一般化トーナメント行列は強確率的推移性を満たす
エントロピー最適化収束性（定理3.6）：既約なスコアに対して、Sinkhorn アルゴリズムは一意のエントロピー最小値点に収束する
影の構成の有効性（定理4.2）：影の構成方法はすべての制約を満たす解を生成