ミニマックス定理

ゲーム理論や凸最適化の数学分野において、ミニマックス定理とは、

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

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

フォン・ノイマンの元の定理^{[ 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人ゼロサムゲームの文脈では、集合は${\displaystyle X}$そして${\displaystyle Y}$これらはそれぞれ、第1プレイヤーと第2プレイヤーの戦略セットに対応し、それらの戦略セットは、彼らの行動に関するくじ引き（いわゆる混合戦略）で構成され、その利得は利得行列によって定義される。${\displaystyle A}$. 機能${\displaystyle f(x,y)}$最初のプレイヤーが戦略を実行したときの最初のプレイヤーへの期待利得値をエンコードします${\displaystyle x}$そして2番目のプレイヤーは戦略を実行する${\displaystyle y}$。

フォン・ノイマンのミニマックス定理は、コンパクトかつ凸な領域、および第1引数​​で凹で第2引数で凸な関数（凹凸関数として知られる）に一般化できる。形式的には、${\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\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}$

モーリス・シオンが1958年に証明したシオンのミニマックス定理^{[ 6 ]}は、凸性を準凸性に緩和したさらなる一般化である。それは次のように述べている。

させて${\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).}$

この定理の初等的な証明は小宮によって与えられている。^{[ 7 ]}

次の例は、凸凸条件がない場合、最大値-最小値と最小値-最大値が等しくならないことを示しています。^{[ 8 ]}定義域 X = [0,1] および Y = [0,1] において、 f ( x . y ) = ( x - y ) ²とします。fは凸凸ですが、凸凹ではないことに注意してください。すると、次のようになります。

• 任意の固定されたxに対して、min _y f( x , y ) = 0 はy = xで達成されます。したがって、max _x min _y f(x,y) = 0 となります。
• 任意の固定された y に対して、max _x f( x , y ) = max( y ² , (1- y ) ² ) は、x =0 (y>0.5 の場合) またはx =1 (y<0.5 の場合) で達成されます。したがって、min _y max _x f(x,y) = 0.25 は、 y =0.5で達成されます。

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