ゲーム理論

ランダム化しなければ、「後で」動く側（相手の戦略を知ってから選ぶ側）が有利になるため、maximin（先に行を確定する）は一般に minimax（先に列を確定する）以下である。この定理の驚くべき内容は、混合戦略のもとではこのギャップが完全に閉じることである: ランダム化により、後から動く側の有利さが消える。なぜなら相手は固定された選択をもはや予測 — そして利用 — できないからである。

弱双対性。 任意の固定した $x_0 \in \Delta_m$ と $y_0 \in \Delta_n$ に対して: $\min_y x_0^\top A y \le x_0^\top A y_0 \le \max_x x^\top A y_0$。左辺の $\max_{x_0}$ と右辺の $\min_{y_0}$ を取っても不等式は保たれる: $\max_x \min_y x^\top A y \le \min_y \max_x x^\top A y$。この向きはランダム化の議論をまったく必要としない。

線形計画への帰着。 $y \mapsto x^\top A y$ は線形であるため、単体 $\Delta_n$ 上でのその最小値はある頂点、すなわちある純粋戦略 $j$ で達成される: $\min_y x^\top A y = \min_{j} \sum_{i=1}^m x_i A_{ij}$。よって行プレイヤーの問題 $\max_x \min_y x^\top A y$ は次の線形計画である: $v$ を最大化、制約は $\sum_{i=1}^m A_{ij} x_i \ge v$（すべての $j = 1, \dots, n$ について）、かつ $x \in \Delta_m$。

双対問題。 線形計画の標準的な双対理論により、この線形計画の双対は: $w$ を最小化、制約は $\sum_{j=1}^n A_{ij} y_j \le w$（すべての $i = 1, \dots, m$ について）、かつ $y \in \Delta_n$ — これはまさに列プレイヤーの問題 $\min_y \max_x x^\top A y$ の線形計画による定式化である。

強双対性。 主問題と双対問題の実行可能領域（$\Delta_m$ と $\Delta_n$）はともに空でなくコンパクトであるため、この線形計画は実行可能かつ有界である；線形計画の強双対定理により主問題と双対問題の最適値は一致する: $\max_x \min_y x^\top A y = \min_y \max_x x^\top A y$。この向きにすでに $\le$ を与えていた弱双対性と合わせて、等号が成り立ち、定理が証明される。

証明は、すべての戦略プロファイルの空間上に、連続な「戦略を少し改善する」写像を構成する: 現在平均より良い成果を出している純粋戦略へ確率を寄せる。戦略プロファイルの空間はコンパクトかつ凸であるため、ブラウワーの不動点定理により、この写像は不動点 — 写像が変化させたくないプロファイル — を持つことが保証される。証明の残りの部分は、不動点がまさに有利な逸脱を持たないプロファイル、すなわちナッシュ均衡であることを示す。

$\Delta = \Delta_1 \times \cdots \times \Delta_n$ とする。これはプレイヤーたちの混合戦略単体の積であり、ユークリッド空間のコンパクトで凸な部分集合である。$x \in \Delta$、プレイヤー $i$、純粋戦略 $j \in S_i$ に対し、利得関数 $g_{ij}(x) = \max\big(0,\, u_i(s_{ij}, x_{-i}) - u_i(x)\big)$ を定義する。これはプレイヤー $i$ が純粋戦略 $j$ に完全に切り替えることで得られる利得（有利でなければ $0$）である。$f : \Delta \to \Delta$ を $f_i(x)_j = \dfrac{x_{ij} + g_{ij}(x)}{1 + \sum_{k \in S_i} g_{ik}(x)}$ により定める；$u_i$ は $x$ に関して連続（実際には多重線形）であるため $g_{ij}$ は連続であり、よって $f$ は連続であり、構成により各 $f_i(x)$ は再び確率ベクトルである。

ブラウワーの不動点定理により、コンパクト凸集合 $\Delta$ 上の連続写像 $f$ は不動点 $x^\star$（$f(x^\star) = x^\star$）を持つ。$S_i := \sum_{k \in S_i} g_{ik}(x^\star)$ とおくと、各 $(i,j)$ に対する不動点方程式は $x_{ij}^\star (1 + S_i) = x_{ij}^\star + g_{ij}(x^\star)$、すなわち $x_{ij}^\star S_i = g_{ij}(x^\star)$ である。

プレイヤー $i$ を固定し $d_{ij} := u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)$ とおくと $g_{ij}(x^\star) = \max(0, d_{ij})$ である。不動点方程式に $d_{ij}$ を掛けて $j \in S_i$ について足し合わせる: 左辺は $S_i \sum_j x_{ij}^\star d_{ij} = S_i\left(\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)\sum_j x_{ij}^\star\right) = S_i(u_i(x^\star) - u_i(x^\star)) = 0$ となる。ここで $\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) = u_i(x^\star)$ と $\sum_j x_{ij}^\star = 1$ を用いた。

右辺は $\sum_j g_{ij}(x^\star)\, d_{ij} = \sum_j \max(0,d_{ij})\, d_{ij} = \sum_{j:\, d_{ij} > 0} d_{ij}^2 \ge 0$ である。両辺を等置すると $\sum_{j:\, d_{ij}>0} d_{ij}^2 = 0$ となり、これは平方和がゼロであるから各項がゼロである: $d_{ij} > 0$ となる $j$ は存在しない。$i$ は任意であったから、すべてのプレイヤー $i$ とすべての純粋戦略 $j$ について $u_i(s_{ij}, x_{-i}^\star) \le u_i(x^\star)$ が成り立つ — これはまさにナッシュ均衡の条件である。したがって $x^\star$ はナッシュ均衡である。