ゲーム理論の重要な結果として，競技プログラミングでも登場するミニマックス定理（minimax theorem）
関数 $f: X\times Y \to \R$ が「ある仮定」を満たすとき，\begin{equation}\label{theorem} \min_{x \in X} \max_{y\in Y} f(x,y)= \max_{y\in Y} \min_{x \in X} f(x,y). \end{equation}
があります．
この記事ではミニマックス定理の意味を説明し，それほど高度な知識を使わない証明を紹介します．なかなか斬新な証明手法で面白いです！
ミニマックス定理のゲーム理論的意味
最適化理論的には，単に「ある仮定のもとでは $\min$ と $\max$ の順番を入れ替えても値は変わらない」ということを示しています．
この定理をゲーム理論的に解釈するために，以下の「ゲーム」を考えます:
- $2$ 人のプレイヤー $P_x, P_y$ がいる
- $P_x$ は $x\in X$ を選び，$P_y$ は $y\in Y$ を選ぶ
- $P_x$ は $f(x,y)$ の値を小さくしたい．$P_y$ は $f(x,y)$ の値を大きくしたい
式 \eqref{theorem} の左辺・右辺の意味
今，$2$ 人とも関数 $f(x,y)$ の形を完全に知っており，$2$ 人は十分賢く，相手の行動を読んで最適な行動を取るとします．さらに「$P_{\red{x}}$ が先手，$P_{\red{y}}$ が後手」つまり，$P_x$ が先に $x$ を選び，それを見て $P_y$ が $y$ を選ぶ状況を考えます．
このとき，後手の $P_y$ は $x$ に応じて $f(x,y)$ を最大にするように $y$ を選びます．先手 $P_x$ はこの $P_y$ の行動を読んで，$\dis \max_{y\in Y} f(x,y)$ を最小にするように $x$ を選びます．
すると，最終的な $f(x,y)$ の値は $ \dis \min_{x \in X} \max_{y\in Y} f(x,y) $ となります．これが式 \eqref{theorem} の左辺です！
同様に，式 \eqref{theorem} 右辺は「$P_{\red{y}}$ が先手，$P_{\red{x}}$ が後手」のときの $f(x,y)$ を表しています．
片側の不等式と定理の意味
明らかに後手の方が有利なため，不等式\[ \min_{x \in X} \max_{y\in Y} f(x,y) \red{{}\geq{}} \max_{y\in Y} \min_{x \in X} f(x,y). \]は簡単に分かります．ここまででは「ある仮定」は使っていません．
「ある仮定」があれば逆向きの不等式\begin{align} \label{minmax-ineq2} \min_{x \in X} \max_{y\in Y} f(x,y) \red{{}\leq{}} \max_{y\in Y} \min_{x \in X} f(x,y) \end{align}も成り立つというのが，ミニマックス定理のスゴい所です．上では「後手が有利」と書きましたが，実は（適切な仮定のもとでは）先手後手によって有利不利は無く，どちらでも $f(x,y)$ は同じ値になるということです．驚きですね！
「ある仮定」の詳細
簡単のため，$X, Y$ をそれぞれあるユークリッド空間上の集合とします．この記事では，以下の $4$ つの仮定のもとで，ミニマックス定理の逆側の不等式を証明します．
- 集合 $X$ は凸かつ有界かつ閉
- 集合 $Y$ は凸かつ有界かつ閉
- 任意の $y\in Y$ に対し，$f(x,y)$ は $x\in X$ について凸
- 任意の $x\in X$ に対し，$f(x,y)$ は $y\in Y$ について凹
仮定 1，2 より $\dis \min_{x\in X}$ と $\dis \max_{y \in Y}$ の存在は保証されます．
具体例
不等式 \eqref{minmax-ineq2} を証明する前に，仮定の重要性を理解するため，$2$ つの例を確認しておきましょう．
ミニマックス定理が使えない例
- $X = \{-1, 1\}$
- $Y = \{-1, 1\}$
- $f(x, y) = xy$
という状況を考えます．$P_x$ も $P_y$ も，$1$ または $-1$ を選びます．
$P_x$ が先手の場合（式 \eqref{theorem} 左辺）
$P_y$ は $f(x,y)$ を大きくしたいので，$P_x$ が $1$ を選んだなら $P_y$ も $1$ を，$P_x$ が $-1$ を選んだなら $P_y$ も $-1$ を選びます．このとき $f(x, y) = 1$ となります．つまり $\dis \min_{x \in X} \max_{y \in Y} f(x, y) = \red{1}$ です．
$P_y$ が先手の場合（式 \eqref{theorem} 右辺）
$P_x$ は $f(x,y)$ を小さくしたいので，$P_y$ が $1$ を選んだなら $P_x$ は $-1$ を，$P_y$ が $-1$ を選んだなら $P_x$ は $1$ を選びます．このとき $f(x, y) = -1$ となります．つまり $\dis \max_{y \in Y} \min_{x \in X} f(x, y) = \red{-1}$ です．
このように，式 \eqref{theorem} の左辺と右辺が等しくありません．これは $X, Y$ が凸集合ではなく，仮定 1 と 2 を満たしていないせいです．
ミニマックス定理が使える例
似た状況として，
- $X = [-1, 1]$
- $Y = [-1, 1]$
- $f(x, y) = xy$
を考えます．$P_x$ も $P_y$ も，$-1$ 以上 $1$ 以下の実数を選びます．
このとき $X, Y$ は凸集合で，仮定 1 〜 4 をすべて満たします．よってミニマックス定理より式 \eqref{theorem} が成り立ちます．
実際，定理左辺は \[ \min_{x \in [-1, 1]} \max_{y \in [-1, 1]} xy = \min_{x \in [-1, 1]} \max \{ x, -x \} = \red{0} \] となります．同様に右辺も $0$ となり，両者が一致します！
不等式 \eqref{minmax-ineq2} の証明
不等式 \eqref{minmax-ineq2} を証明しましょう．そのために，「$P_x$ が先手」のゲームを $T$ ラウンド繰り返す状況を考えます:
- 第 $t\,(=1,\dots,T)$ ラウンドでは，$P_x$ が $x_t\in X$ を選んだ後 $P_y$ が $y_t\in Y$ を選ぶ．
- $P_x$ は $T$ ラウンドの平均値 $\dis \frac{1}{T} \sum_{t=1}^T f(x_t, y_t)$ を小さくしたい．$P_y$ は大きくしたい．
$P_x$ は最初関数 $f$ の形を知らず，$y_t$ が選ばれた後，$x$ の関数 $f(x, y_t)$ の形を知るものとします．$P_x$ はこの情報を次ラウンド以降に使えます．一方，$P_y$ は関数 $f$ の形を最初から完全に知っているものとします．
証明の方針
$P_x$ と $P_y$ の $2$ 人がある意味で「賢い」行動をとったときの $\dis \frac{1}{T} \sum_{t=1}^T f(x_t, y_t)$ の値を上下から評価し，それらを組み合わせます．下からの評価で式 \eqref{minmax-ineq2} 左辺が，上からの評価で式 \eqref{minmax-ineq2} 右辺が現れます．
下からの評価（簡単）
$P_y$ は後手なので，$\dis f(x_t, y_t) = \max_{y\in Y} f(x_t, y)$ となるよう $y_t$ を選べます．このとき，\begin{align}\label{lower-bound} \indent \frac{1}{T} \sum_{t=1}^T f(x_t, y_t) &= \frac{1}{T} \sum_{t=1}^T \max_{y\in Y} f(x_t, y)\\ \notag &\geq \frac{1}{T} \sum_{t=1}^T \min_{x\in X} \max_{y\in Y} f(x, y)\\ \notag &= \red{\min_{x\in X} \max_{y\in Y} f(x, y)} \end{align} と下から評価できます．最後の行は式 \eqref{minmax-ineq2} 左辺そのものです！
上からの評価（難しい）
$P_y$ が $y_t$ をどのように選ぶとしても，$P_x$ がオンライン近接勾配法というアルゴリズムを使って $x_t$ を決めることで，\[ \sum_{t=1}^T f(x_t, y_t) \leq \min_{x\in X} \sum_{t=1}^T f(x, y_t) + O(\sqrt{T}) \]とできることが知られています（オンライン最適化とは？ オンライン近接勾配法のリグレット上界 の記事の定理 $1$ です）．この不等式の導出に仮定 1, 2, 3 を使っています1．
$P_x$ がオンライン近接勾配法を使った場合，\begin{align}\label{upper-bound} \indent \frac{1}{T} \sum_{t=1}^T f(x_t, y_t) &\leq \min_{x\in X} \frac{1}{T} \sum_{t=1}^T f(x, y_t) + o(1)\\ \notag &\leq \min_{x\in X} f\Big(x, \frac{1}{T} \sum_{t=1}^T y_t \Big) + o(1)\\ \notag &\leq \red{\max_{y\in Y} \min_{x\in X} f(x, y)} + o(1) \end{align}と上から評価できます．$2$ 行目の不等号にはイェンゼンの不等式を使いました．このために仮定 2, 4 を使っています．最後の行の第 $1$ 項は式 \eqref{minmax-ineq2} 右辺そのものです！
仕上げ
式 \eqref{lower-bound}，\eqref{upper-bound} を組み合わせると，\[ \min_{x \in X} \max_{y\in Y} f(x,y) \leq \max_{y\in Y} \min_{x \in X} f(x,y) + o(1) \]となります．$T\to \infty$ の極限を考えると，所望の不等式 \eqref{minmax-ineq2} を得ます！
余談
上の証明は，ブラウワーの不動点定理を使う古典的な証明よりずっと簡単です．このように，$2$ 人ゲームを考え，その戦略を解析することで，数学的な定理が簡単に証明できる場合があります．面白いですね！
同様の考え方で，証明が難しいことで有名な確率論の大数の強法則も簡単に証明できるらしいです（詳しくは理解していません）．
