ミニマックス定理

ゲーム理論と凸最適化の数学の分野において、ミニマックス定理は次のような定理である。

${\displaystyle \max_{x\inX}\min_{y\inY}f(x,y)=\min_{y\inY}\max_{x\inX}f(x,y)}$

集合とおよび関数 に関する特定の条件下では、が成り立つ。^[1]左辺が右辺以下であることは常に真である（最大–最小不等式）が、等式はミニマックス定理によって特定される特定の条件下でのみ成り立つ。この意味での最初の定理は、 1928 年に発表された 2 人プレイのゼロ和ゲームに関するフォン ノイマンのミニマックス定理であり、^[2]これはゲーム理論の出発点と考えられている。フォン ノイマンは次のように述べている。「私の知る限り、その定理なしにはゲーム理論はあり得なかった... ミニマックス定理が証明されるまでは、発表する価値のあるものは何もないと思った」。^[3]それ以来、フォン ノイマンの元の定理のいくつかの一般化と代替バージョンが文献に登場している。^{[4] [5]}${\displaystyle X}$${\displaystyle Y}$${\displaystyle f}$

フォン・ノイマンの定理^[2]はゲーム理論に基づいており、次のような場合に適用される。

• ${\displaystyle X}$および は標準単体である:および、および${\displaystyle Y}$${\textstyle X=\{(x_{1},\dots ,x_{n})\in [0,1]^{n}:\sum _{i=1}^{n}x_{i}=1\}}$${\textstyle Y=\{(y_{1},\dots ,y_{m})\in [0,1]^{m}:\sum _{j=1}^{m}y_{j}= 1\}}$
• ${\displaystyle f(x,y)}$は両方の引数において線形関数（つまり、双線形）なので、有限行列 に対して記述することができ、または同等に と記述することができます。${\displaystyle f}$${\displaystyle f(x,y)=x^{\mathsf {T}}Ay}$${\displaystyle A\in \mathbb {R} ^{n\times m}}$${\textstyle f(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{m}A_{ij}x_{i}y_{j}}$

これらの仮定のもとで、フォン・ノイマンは

${\displaystyle \max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.}$

2人プレイのゼロサムゲームでは、集合とがそれぞれ1人目と2人目のプレイヤーの戦略集合に対応し、それぞれの行動に関するくじ引き（いわゆる混合戦略）で構成され、その利得は利得行列によって定義されます。関数は、1人目のプレイヤーが戦略を実行し、2人目のプレイヤーが戦略を実行した場合の、1人目のプレイヤーへの利得の期待値をエンコードします。 ${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle A}$${\displaystyle f(x,y)}$${\displaystyle x}$${\displaystyle y}$

フォン・ノイマンのミニマックス定理は、コンパクトかつ凸な領域、および第一引数が凹で第二引数が凸な関数（凹凸関数と呼ばれる）に一般化できる。形式的には、およびをコンパクト凸集合とする。が凹凸な連続関数である場合、すなわち ${\displaystyle X\subseteq \mathbb {R} ^{n}}$${\displaystyle Y\subseteq \mathbb {R} ^{m}}$ ${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$

${\displaystyle f(\cdot,y):X\to\mathbb{R}}$は任意の固定値に対して凹であり、${\displaystyle y\in Y}$

${\displaystyle f(x,\cdot ):Y\to \mathbb {R} }$任意の固定された に対して凸です。${\displaystyle x\in X}$

そして、

${\displaystyle \max_{x\inX}\min_{y\inY}f(x,y)=\min_{y\inY}\max_{x\inX}f(x,y).}$

シオンのミニマックス定理は、モーリス・シオンによるフォン・ノイマンのミニマックス定理^[6]の一般化であり、以下の要件を緩和している。^{[6] [7]}

を線型位相空間の凸部分集合とし、を線型位相空間のコンパクト凸部分集合とする。 が上の実数値関数で 、${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle f}$${\displaystyle X\times Y}$

${\displaystyle f(\cdot,y)}$ 任意の固定された に対して、の上部半連続 かつ準凹面であり、${\displaystyle X}$${\displaystyle y\in Y}$

${\displaystyle f(x,\cdot )}$任意の固定された に対して、は 上で半連続かつ準凸に下がります。${\displaystyle Y}$${\displaystyle x\in X}$

そして、

${\displaystyle \sup _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\sup _{x\in X}f(x,y).}$

• パルタサラシーの定理 – フォン・ノイマンのミニマックス定理の一般化
• 双対線形計画法は、ゼロサムゲームのミニマックス定理を証明するために使用できます。
• ヤオの原理 – ミニマックス定理の計算複雑性への応用