マックスミニ戦略とミニマックス戦略

マックスミニ戦略

問題としている戦略的状況が完備情報の静学ゲームであるとともに、それが戦略型ゲーム\begin{equation*}
G=\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in
I}\right)
\end{equation*}として記述されているものとします。ただし、$I$はプレイヤー集合、$S_{i}$はプレイヤー$i\in I$の純粋戦略集合、$u_{i}:S_{I}\rightarrow \mathbb{R} $はプレイヤー$i$の利得関数です。さらに、このゲーム$G$は2人ゼロ和ゲームであるものとします。つまり、以下の条件\begin{eqnarray*}&&\left( a\right) \ I=\left\{ 1,2\right\} \\
&&\left( b\right) \ \forall \left( s_{1},s_{2}\right) \in S_{1}\times
S_{2}:u_{1}\left( s_{1},s_{2}\right) +u_{2}\left( s_{1},s_{2}\right) =0
\end{eqnarray*}がともに成り立つということです。

プレイヤー$1$が純粋戦略$s_{1}\in S_{1}$を選択する状況を想定します。プレイヤー$1$は相手が選ぶ純粋戦略を事前に観察できないため、この場合に彼が直面し得る利得からなる集合は、\begin{equation*}\left\{ u_{1}\left( s_{1},s_{2}\right) \in \mathbb{R} \ |\ s_{2}\in S_{2}\right\}
\end{equation*}となります。この集合の最小値\begin{equation*}
\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right) =\min \left\{
u_{1}\left( s_{1},s_{2}\right) \in \mathbb{R} \ |\ s_{2}\in S_{2}\right\}
\end{equation*}は、プレイヤー$1$が純粋戦略$s_{1}$を選択した場合に、最悪のシナリオのもとでも確保できる利得に相当します。

プレイヤー$1$は自身がそれぞれの純粋戦略を選んだ場合に最低でも確保できる利得を導出した上で、それらを比較できます。その結果、最低でも確保できる利得が純粋戦略$s_{1}^{\ast }\in S_{1}$のもとで最大化されるのであれば、つまり、\begin{equation*}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1}^{\ast },s_{2}\right) =\max_{s_{1}\in
S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つならば、この純粋戦略$s_{1}^{\ast }$をプレイヤー$1$のマックスミニ戦略（maxmini strategy）と呼びます。また、マックスミニ戦略を選んだ場合に最低でも確保できる利得\begin{equation*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}を、プレイヤー$1$のマックスミニ値（maxmini value）や保証水準（security level）などと呼びます。

マックスミニ戦略とは、その名の通り「最小値を最大化する」戦略です。つまり、それぞれの純粋戦略を選んだ場合に最低でも確保できる利得どうしを比較した上で、その最低値を最大化する純粋戦略がマックスミニ戦略です。

プレイヤー$2$についても同様に考えます。つまり、プレイヤー$2$が純粋戦略$s_{2}\in S_{2}$を選択した場合に最低でも確保できる利得は、\begin{equation*}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}\right) =\min \left\{
u_{2}\left( s_{1},s_{2}\right) \in \mathbb{R} \ |\ s_{1}\in S_{1}\right\}
\end{equation*}であるため、プレイヤー$2$の純粋戦略$s_{2}^{\ast }\in S_{2}$がマックスミニ戦略であることは、\begin{equation*}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}^{\ast }\right) =\max_{s_{2}\in
S_{2}}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つこととして定義されます。また、プレイヤー$2$のマックスミニ値は、\begin{equation*}\max_{s_{2}\in S_{2}}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}\right)
\end{equation*}と定義されます。

例（マックスミニ戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 0,0 & -1,1 \\ \hline
D & 1,-1 & 0,0 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。プレイヤー$1$にとって、純粋戦略$U$を選んだ場合に最低でも確保できる利得は、\begin{eqnarray*}\min_{s_{2}\in S_{2}}u_{1}\left( U,s_{2}\right) &=&\min \left\{ u_{1}\left(
U,L\right) ,u_{1}\left( U,R\right) \right\} \\
&=&\min \left\{ 0,-1\right\} \\
&=&-1
\end{eqnarray*}である一方で、純粋戦略$D$を選んだ場合に最低でも確保できる利得は、\begin{eqnarray*}\min_{s_{2}\in S_{2}}u_{1}\left( D,s_{2}\right) &=&\min \left\{ u_{1}\left(
D,L\right) ,u_{1}\left( D,R\right) \right\} \\
&=&\min \left\{ 1,0\right\} \\
&=&0
\end{eqnarray*}です。両者を比較すると、\begin{equation*}
\min_{s_{2}\in S_{2}}u_{1}\left( U,s_{2}\right) <\min_{s_{2}\in
S_{2}}u_{1}\left( D,s_{2}\right)
\end{equation*}であるため、プレイヤー$1$のマックスミニ戦略は$D$であり、マックスミニ値は、\begin{eqnarray*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
&=&\min_{s_{2}\in S_{2}}u_{1}\left( D,s_{2}\right) \\
&=&0
\end{eqnarray*}です。プレイヤー$2$についても同様に考えます。プレイヤー$2$にとって、純粋戦略$L$を選んだ場合に最低でも確保できる利得は、\begin{eqnarray*}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},L\right) &=&\min \left\{ u_{2}\left(
U,L\right) ,u_{2}\left( D,L\right) \right\} \\
&=&\min \left\{ 0,-1\right\} \\
&=&-1
\end{eqnarray*}である一方で、純粋戦略$R$を選んだ場合に最低でも確保できる利得は、\begin{eqnarray*}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},R\right) &=&\min \left\{ u_{2}\left(
U,R\right) ,u_{2}\left( D,R\right) \right\} \\
&=&\min \left\{ 1,0\right\} \\
&=&0
\end{eqnarray*}です。両者を比較すると、\begin{equation*}
\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},L\right) <\min_{s_{1}\in
S_{1}}u_{2}\left( s_{1},R\right)
\end{equation*}であるため、プレイヤー$2$のマックスミニ戦略は$R$であり、マックスミニ値は、\begin{eqnarray*}\max_{s_{2}\in S_{2}}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}\right)
&=&\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},R\right) \\
&=&0
\end{eqnarray*}です。

マックスミニ戦略は一意的に定まるとは限りません。以下の例より明らかです。

例（マックスミニ戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 1,-1 & -1,1 \\ \hline
D & -1,1 & 1,-1 \\ \hline
\end{array}$$

ゼロ和ゲームの混合拡張におけるマックスミニ戦略

プレイヤーたちが混合戦略を採用する場合にもマックスミニ戦略の概念は同様に定義されます。具体的には以下の通りです。

戦略型ゲーム\begin{equation*}
G=\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in
I}\right)
\end{equation*}が2人ゼロ和ゲームであるものとします。つまり、\begin{eqnarray*}
&&\left( a\right) \ I=\left\{ 1,2\right\} \\
&&\left( b\right) \ \forall \left( s_{1},s_{2}\right) \in S_{1}\times
S_{2}:u_{1}\left( s_{1},s_{2}\right) +u_{2}\left( s_{1},s_{2}\right) =0
\end{eqnarray*}がともに成り立つということです。

2人定和ゲーム$G$においてプレイヤーたちが混合戦略を採用する場合、その戦略的状況は$G$の混合拡張\begin{equation*}G^{\ast }=(I,\{\Delta \left( S_{i}\right) \}_{i\in I},\{F_{i}\}_{i\in I})
\end{equation*}として記述されます。ただし、$I$はプレイヤー集合、$\Delta \left( S_{i}\right) $はプレイヤー$i\in I$の混合戦略集合、$F_{i}:\Delta \left( S_{I}\right)\rightarrow \mathbb{R} $はプレイヤー$i$の期待利得関数です。

プレイヤー$1$が混合戦略$\sigma _{1}\in \Delta \left( S_{1}\right) $を選択する状況を想定します。プレイヤー$1$は相手が選ぶ混合戦略を事前に観察できないため、この場合に彼が直面し得る期待利得からなる集合は、\begin{equation*}\left\{ F_{1}\left( \sigma _{1},\sigma _{2}\right) \in \mathbb{R} \ |\ \sigma _{2}\in \Delta \left( S_{2}\right) \right\}
\end{equation*}となります。この集合の最小値\begin{equation*}
\min_{\sigma _{2}\in \Delta \left( S_{2}\right) }F_{1}\left( \sigma
_{1},\sigma _{2}\right) =\min \left\{ F_{1}\left( \sigma _{1},\sigma
_{2}\right) \in \mathbb{R} \ |\ \sigma _{2}\in \Delta \left( S_{2}\right) \right\}
\end{equation*}は、プレイヤー$1$が混合戦略$\sigma _{1}$を選択した場合に、最低でも期待できる期待利得に相当します。

プレイヤー$1$は自身がそれぞれの混合戦略を選んだ場合に最低でも期待できる期待利得を導出した上で、それらを比較できます。その結果、最低でも期待できる期待利得を混合戦略$\sigma_{1}^{\ast }\in \Delta \left( S_{1}\right) $のもとで最大化できるのであれば、つまり、\begin{equation*}\min_{\sigma _{2}\in \Delta \left( S_{2}\right) }F_{1}\left( \sigma
_{1}^{\ast },\sigma _{2}\right) =\max_{\sigma _{1}\in \Delta \left(
S_{1}\right) }\min_{\sigma _{2}\in \Delta \left( S_{2}\right) }F_{1}\left(
\sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つならば、この混合戦略$\sigma _{1}^{\ast }$をプレイヤー$1$のマックスミニ戦略（maxmini strategy）と呼びます。また、マックスミニ戦略を選んだ場合に最低でも確保できる期待利得\begin{equation*}\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }\min_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}を、プレイヤー$1$のマックスミニ値（maxmini value）や保証水準（security level）などと呼びます。

プレイヤー$2$についても同様に考えます。つまり、プレイヤー$2$が純粋戦略$s_{2}\in S_{2}$を選択した場合に最低でも確保できる期待利得は、\begin{equation*}\min_{\sigma _{1}\in \Delta \left( S_{1}\right) }F_{2}\left( \sigma
_{1},\sigma _{2}\right) =\min \left\{ F_{2}\left( \sigma _{1},\sigma
_{2}\right) \in \mathbb{R} \ |\ \sigma _{1}\in \Delta \left( S_{1}\right) \right\}
\end{equation*}であるため、プレイヤー$2$の混合戦略$\sigma_{2}^{\ast }\in \Delta \left( S_{2}\right) $がマックスミニ戦略であることは、\begin{equation*}\min_{\sigma _{1}\in \Delta \left( S_{1}\right) }F_{2}\left( \sigma
_{1},\sigma _{2}^{\ast }\right) =\max_{\sigma _{2}\in \Delta \left(
S_{2}\right) }\min_{\sigma _{1}\in \Delta \left( S_{1}\right) }F_{2}\left(
\sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つこととして定義されます。また、プレイヤー$2$のマックスミニ値は、\begin{equation*}\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }\min_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{2}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}と定義されます。

例（マックスミニ戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 0,0 & -1,1 \\ \hline
D & 1,-1 & 0,0 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。プレイヤー$1$の混合戦略を、\begin{equation*}\sigma _{1}=\left( \sigma _{1}\left( U\right) ,\sigma _{1}\left( D\right)
\right) =\left( \sigma _{1},1-\sigma _{1}\right)
\end{equation*}で表記し、プレイヤー$2$の混合戦略を、\begin{equation*}\sigma _{2}=\left( \sigma _{2}\left( L\right) ,\sigma _{2}\left( R\right)
\right) =\left( \sigma _{2},1-\sigma _{2}\right)
\end{equation*}と表記するものと定めます。プレイヤー$1$が混合戦略$\sigma _{1}$を選んだ場合に最低でも期待できる期待利得は、\begin{eqnarray*}\min_{\sigma _{2}\in \Delta \left( \sigma _{2}\right) }F_{1}\left( \sigma
_{1},\sigma _{2}\right) &=&\min \left\{ F_{1}\left( \sigma _{1},\sigma
_{2}\right) \ |\ \sigma _{2}\in \Delta \left( \sigma _{2}\right) \right\} \\
&=&\min \left\{ -\sigma _{1}\left( 1-\sigma _{2}\right) +\left( 1-\sigma
_{1}\right) \sigma _{2}\ |\ 0\leq \sigma _{2}\leq 1\right\} \\
&=&\min \left\{ -\sigma _{1}+\sigma _{2}\ |\ 0\leq \sigma _{2}\leq 1\right\}
\\
&=&-\sigma _{1}
\end{eqnarray*}です。したがって、プレイヤー$1$のマックスミニ戦略は、\begin{equation*}\sigma _{1}=0
\end{equation*}であり、マックスミニ値は、\begin{eqnarray*}
\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }\min_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right)
&=&\min_{\sigma _{2}\in \Delta \left( \sigma _{2}\right) }F_{1}\left(
0,\sigma _{2}\right) \\
&=&0
\end{eqnarray*}です。一方、プレイヤー$2$が混合戦略$\sigma _{2}$を選んだ場合に最低でも期待できる期待利得は、\begin{eqnarray*}\min_{\sigma _{1}\in \Delta \left( \sigma _{1}\right) }F_{2}\left( \sigma
_{1},\sigma _{2}\right) &=&\min \left\{ F_{2}\left( \sigma _{1},\sigma
_{2}\right) \ |\ \sigma _{1}\in \Delta \left( \sigma _{1}\right) \right\} \\
&=&\min \left\{ \sigma _{1}\left( 1-\sigma _{2}\right) -\left( 1-\sigma
_{1}\right) \sigma _{2}\ |\ 0\leq \sigma _{1}\leq 1\right\} \\
&=&\min \left\{ \sigma _{1}-\sigma _{2}\ |\ 0\leq \sigma _{1}\leq 1\right\}
\\
&=&-\sigma _{2}
\end{eqnarray*}です。したがって、プレイヤー$2$のマックスミニ戦略は、\begin{equation*}\sigma _{2}=0
\end{equation*}であり、マックスミニ値は、\begin{eqnarray*}
\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }\min_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{2}\left( \sigma _{1},\sigma _{2}\right)
&=&\min_{\sigma _{1}\in \Delta \left( \sigma _{1}\right) }F_{2}\left( \sigma
_{1},0\right) \\
&=&0
\end{eqnarray*}です。

ミニマックス戦略

プレイヤー$1$が純粋戦略$s_{1}\in S_{1}$を選択する状況を想定します。2人ゼロ和ゲームではプレイヤー$2$が得る利益はプレイヤー$1$が被る損害と一致するため、すなわち、\begin{equation*}\forall \left( s_{1},s_{2}\right) \in S_{1}\times S_{2}:-u_{1}\left(
s_{1},s_{2}\right) =u_{2}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つため、この場合にプレイヤー$1$が被る可能性のある損害からなる集合は、\begin{equation*}\left\{ u_{2}\left( s_{1},s_{2}\right) \in \mathbb{R} \ |\ s_{2}\in S_{2}\right\}
\end{equation*}となります。この集合の最大値\begin{equation*}
\max_{s_{2}\in S_{2}}u_{2}\left( s_{1},s_{2}\right) =\max \left\{
u_{2}\left( s_{1},s_{2}\right) \in \mathbb{R} \ |\ s_{2}\in S_{2}\right\}
\end{equation*}は、プレイヤー$1$が純粋戦略$s_{1}$を選択した場合に、最悪のシナリオのもとで被る損害に相当します。

プレイヤー$1$は自身がそれぞれの純粋戦略を選んだ場合に最悪の状況において被る損害を導出した上で、それらを比較できます。その結果、最悪の状況において被る損害が純粋戦略$s_{1}^{\ast}\in S_{1}$のもとで最小化されるのであれば、つまり、\begin{equation*}\max_{s_{2}\in S_{2}}u_{2}\left( s_{1}^{\ast },s_{2}\right) =\min_{s_{1}\in
S_{1}}\max_{s_{2}\in S_{2}}u_{2}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つならば、この純粋戦略$s_{1}^{\ast }$をプレイヤー$1$のミニマックス戦略（minimax strategy）と呼びます。また、ミニマックス戦略を選んだ場合に最悪のシナリオのもとで被る損害\begin{equation*}\min_{s_{1}\in S_{1}}\max_{s_{2}\in S_{2}}u_{2}\left( s_{1},s_{2}\right)
\end{equation*}を、プレイヤー$1$のミニマックス値（minimax value）や保証水準（security level）などと呼びます。

ミニマックス戦略とは、その名の通り「最大値を最小化する」戦略です。つまり、それぞれの純粋戦略を選んだ場合に最悪のシナリオのもとで被る損害の大きさを比較した上で、その最大値を最小化する純粋戦略こそがミニマックス戦略です。

プレイヤー$2$についても同様に考えます。つまり、プレイヤー$2$が純粋戦略$s_{2}\in S_{2}$を選択した場合に、最悪のシナリオのもとで被る被害は、\begin{equation*}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right) =\max \left\{
u_{1}\left( s_{1},s_{2}\right) \in \mathbb{R} \ |\ s_{1}\in S_{1}\right\}
\end{equation*}であるため、プレイヤー$2$の純粋戦略$s_{2}^{\ast }\in S_{2}$がミニマックス戦略であることは、\begin{equation*}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}^{\ast }\right) =\min_{s_{2}\in
S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つこととして定義されます。また、プレイヤー$2$のミニマックス値は、\begin{equation*}\min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}と定義されます。

例（ミニマックス戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 0,0 & -1,1 \\ \hline
D & 1,-1 & 0,0 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。プレイヤー$1$にとって、純粋戦略$U$を選んだ場合に最悪のシナリオのもとで被る損害は、\begin{eqnarray*}\max_{s_{2}\in S_{2}}u_{2}\left( U,s_{2}\right) &=&\max \left\{ u_{2}\left(
U,L\right) ,u_{2}\left( U,R\right) \right\} \\
&=&\max \left\{ 0,1\right\} \\
&=&1
\end{eqnarray*}である一方で、純粋戦略$D$を選んだ場合に最悪のシナリオのもとで被る損害は、\begin{eqnarray*}\max_{s_{2}\in S_{2}}u_{2}\left( D,s_{2}\right) &=&\max \left\{ u_{2}\left(
D,L\right) ,u_{2}\left( D,R\right) \right\} \\
&=&\max \left\{ -1,0\right\} \\
&=&0
\end{eqnarray*}です。両者を比較すると、\begin{equation*}
\max_{s_{2}\in S_{2}}u_{2}\left( U,s_{2}\right) >\max_{s_{2}\in
S_{2}}u_{2}\left( D,s_{2}\right)
\end{equation*}であるため、プレイヤー$1$のミニマックス戦略は$D$であり、ミニマックス値は、\begin{eqnarray*}\min_{s_{1}\in S_{1}}\max_{s_{2}\in S_{2}}u_{2}\left( s_{1},s_{2}\right)
&=&\max_{s_{2}\in S_{2}}u_{2}\left( D,s_{2}\right) \\
&=&0
\end{eqnarray*}です。一方、プレイヤー$2$にとって、純粋戦略$L$を選んだ場合に最悪のシナリオのもとで被る損害は、\begin{eqnarray*}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},L\right) &=&\max \left\{ u_{1}\left(
U,L\right) ,u_{1}\left( D,L\right) \right\} \\
&=&\max \left\{ 0,1\right\} \\
&=&1
\end{eqnarray*}である一方で、純粋戦略$R$を選んだ場合に最悪のシナリオのもとで被る損害は、\begin{eqnarray*}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},R\right) &=&\max \left\{ u_{1}\left(
U,R\right) ,u_{1}\left( D,R\right) \right\} \\
&=&\max \left\{ -1,0\right\} \\
&=&0
\end{eqnarray*}です。両者を比較すると、\begin{equation*}
\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},L\right) >\max_{s_{1}\in
S_{1}}u_{1}\left( s_{1},R\right)
\end{equation*}であるため、プレイヤー$2$のミニマックス戦略は$R$であり、ミニマックス値は、\begin{eqnarray*}\min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
&=&\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},R\right) \\
&=&0
\end{eqnarray*}です。

ミニマックス戦略は一意的に定まるとは限りません。以下の例より明らかです。

例（ミニマックス戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 1,-1 & -1,1 \\ \hline
D & -1,1 & 1,-1 \\ \hline
\end{array}$$

ゼロ和ゲームの混合拡張におけるミニマックス戦略

プレイヤーたちが混合戦略を採用する場合にもミニマックス戦略の概念は同様に定義されます。具体的には以下の通りです。

プレイヤー$1$が混合戦略$\sigma _{1}\in \Delta \left( S_{1}\right) $を選択する状況を想定します。2人ゼロ和ゲームではプレイヤー$2$が直面する期待利益はプレイヤー$1$が直面する期待損害と一致するため、すなわち、\begin{equation*}\forall \left( \sigma _{1},\sigma _{2}\right) \in \Delta \left( S_{1}\right)
\times \Delta \left( S_{2}\right) :-F_{1}\left( \sigma _{1},\sigma
_{2}\right) =F_{2}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つため、この場合にプレイヤー$1$が直面する期待損害からなる集合は、\begin{equation*}\left\{ F_{2}\left( \sigma _{1},\sigma _{2}\right) \in \mathbb{R} \ |\ \sigma _{2}\in \Delta \left( S_{2}\right) \right\}
\end{equation*}となります。この集合の最大値\begin{equation*}
\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }F_{2}\left( \sigma
_{1},\sigma _{2}\right) =\max \left\{ F_{2}\left( \sigma _{1},\sigma
_{2}\right) \in \mathbb{R} \ |\ \sigma _{2}\in \Delta \left( S_{2}\right) \right\}
\end{equation*}は、プレイヤー$1$が混合戦略$\sigma _{1}$を選択した場合に、最悪のシナリオのもとで直面する期待被害に相当します。

プレイヤー$1$は自身がそれぞれの混合戦略を選んだ場合に最悪の状況において直面する期待被害を導出した上で、それらを比較できます。その結果、最悪の状況において直面する期待被害が混合戦略$\sigma _{1}^{\ast}\in \Delta \left( S_{1}\right) $のもとで最小化されるのであれば、つまり、\begin{equation*}\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }F_{2}\left( \sigma
_{1}^{\ast },\sigma _{2}\right) =\max_{\sigma _{1}\in \Delta \left(
S_{1}\right) }\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }F_{2}\left(
\sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つならば、この混合戦略$\sigma _{1}^{\ast }$をプレイヤー$1$のミニマックス戦略（minimax strategy）と呼びます。また、ミニマックス戦略を選んだ場合に最悪のシナリオのもとで直面する期待被害\begin{equation*}\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }\max_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{2}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}を、プレイヤー$1$のミニマックス値（minimax value）や保証水準（security level）などと呼びます。

プレイヤー$2$についても同様に考えます。つまり、プレイヤー$2$が混合戦略$\sigma _{2}\in \Delta \left(S_{2}\right) $を選択した場合に、最悪のシナリオのもとで直面する期待被害は、\begin{equation*}\left\{ F_{1}\left( \sigma _{1},\sigma _{2}\right) \in \mathbb{R} \ |\ \sigma _{1}\in \Delta \left( S_{1}\right) \right\}
\end{equation*}であるとともに、プレイヤー$2$の混合戦略$\sigma _{2}^{\ast }\in \Delta \left( S_{2}\right) $がミニマックス戦略であることとは、\begin{equation*}\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }F_{1}\left( \sigma
_{1},\sigma _{2}^{\ast }\right) =\max_{\sigma _{2}\in \Delta \left(
S_{2}\right) }\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }F_{1}\left(
\sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つこととして定義されます。また、プレイヤー$2$のミニマックス値は、\begin{equation*}\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }\max_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}と定義されます。

例（ミニマックス戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 0,0 & -1,1 \\ \hline
D & 1,-1 & 0,0 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。プレイヤー$1$の混合戦略を、\begin{equation*}\sigma _{1}=\left( \sigma _{1}\left( U\right) ,\sigma _{1}\left( D\right)
\right) =\left( \sigma _{1},1-\sigma _{1}\right)
\end{equation*}で表記し、プレイヤー$2$の混合戦略を、\begin{equation*}\sigma _{2}=\left( \sigma _{2}\left( L\right) ,\sigma _{2}\left( R\right)
\right) =\left( \sigma _{2},1-\sigma _{2}\right)
\end{equation*}と表記するものと定めます。プレイヤー$1$が混合戦略$\sigma _{1}$を選んだ場合に最悪のシナリオのもとで直面する期待被害は、\begin{eqnarray*}\max_{\sigma _{2}\in \Delta \left( \sigma _{2}\right) }F_{2}\left( \sigma
_{1},\sigma _{2}\right) &=&\max \left\{ F_{2}\left( \sigma _{1},\sigma
_{2}\right) \ |\ \sigma _{2}\in \Delta \left( \sigma _{2}\right) \right\} \\
&=&\max \left\{ \sigma _{1}\left( 1-\sigma _{2}\right) -\left( 1-\sigma
_{1}\right) \sigma _{2}\ |\ 0\leq \sigma _{2}\leq 1\right\} \\
&=&\max \left\{ \sigma _{1}-\sigma _{2}\ |\ 0\leq \sigma _{2}\leq 1\right\}
\\
&=&\sigma _{1}
\end{eqnarray*}です。したがって、プレイヤー$1$のミニマックス戦略は、\begin{equation*}\sigma _{1}=0
\end{equation*}であり、ミニマックス値は、\begin{eqnarray*}
\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }\max_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{2}\left( \sigma _{1},\sigma _{2}\right)
&=&\max_{\sigma _{2}\in \Delta \left( \sigma _{2}\right) }F_{2}\left(
0,\sigma _{2}\right) \\
&=&0
\end{eqnarray*}です。一方、プレイヤー$2$が混合戦略$\sigma _{2}$を選んだ場合に最悪のシナリオのもとで直面する期待被害は、\begin{eqnarray*}\max_{\sigma _{1}\in \Delta \left( \sigma _{1}\right) }F_{1}\left( \sigma
_{1},\sigma _{2}\right) &=&\max \left\{ F_{1}\left( \sigma _{1},\sigma
_{2}\right) \ |\ \sigma _{1}\in \Delta \left( \sigma _{1}\right) \right\} \\
&=&\max \left\{ -\sigma _{1}\left( 1-\sigma _{2}\right) +\left( 1-\sigma
_{1}\right) \sigma _{2}\ |\ 0\leq \sigma _{1}\leq 1\right\} \\
&=&\max \left\{ -\sigma _{1}+\sigma _{2}\ |\ 0\leq \sigma _{1}\leq 1\right\}
\\
&=&\sigma _{2}
\end{eqnarray*}です。したがって、プレイヤー$2$のミニマックス戦略は、\begin{equation*}\sigma _{2}=0
\end{equation*}であり、ミニマックス値は、\begin{eqnarray*}
\max_{\sigma _{2}\in \Delta \left( S_{2}\right) }\max_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right)
&=&\max_{\sigma _{1}\in \Delta \left( \sigma _{1}\right) }F_{1}\left( \sigma
_{1},0\right) \\
&=&0
\end{eqnarray*}です。

マックスミニ戦略とミニマックス戦略の違い

マックスミニ戦略は「最悪のシナリオが起きた場合でも自分が確保できる利益を最大化する」戦略である一方で、ミニマックス戦略は「最悪のシナリオが起きた場合に自分が被る損害を最小化する」戦略です。どちらの戦略も最悪のケースを想定している点において共通していますが、マックスミニ戦略では自身が確保できる利益を最大化しようとする一方で、ミニマックス戦略では自身が被る被害を最小化しようとします。

マックスミニ戦略とミニマックス戦略は一致するとは限りません。以下の例より明らかです。

例（マックスミニ戦略とミニマックス戦略の違い）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 3,-3 & 2,-2 \\ \hline
D & 1,-1 & 4,-4 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。プレイヤー$1$にとって、純粋戦略$U$を選んだ場合に最低でも確保できる利得は、\begin{eqnarray*}\min_{s_{2}\in S_{2}}u_{1}\left( U,s_{2}\right) &=&\min \left\{ u_{1}\left(
U,L\right) ,u_{1}\left( U,R\right) \right\} \\
&=&\min \left\{ 3,2\right\} \\
&=&2
\end{eqnarray*}である一方で、純粋戦略$D$を選んだ場合に最低でも確保できる利得は、\begin{eqnarray*}\min_{s_{2}\in S_{2}}u_{1}\left( D,s_{2}\right) &=&\min \left\{ u_{1}\left(
D,L\right) ,u_{1}\left( D,R\right) \right\} \\
&=&\min \left\{ 1,4\right\} \\
&=&1
\end{eqnarray*}です。両者を比較すると、\begin{equation*}
\min_{s_{2}\in S_{2}}u_{1}\left( U,s_{2}\right) >\min_{s_{2}\in
S_{2}}u_{1}\left( D,s_{2}\right)
\end{equation*}となるため、プレイヤー$1$のマックスミニ戦略は$U$であるとともに、マックスミニ値は、\begin{equation*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right) =2
\end{equation*}となります。一方、プレイヤー$1$にとって、純粋戦略$U$を選んだ場合に最悪のシナリオのもとで被る損害は、\begin{eqnarray*}\max_{s_{2}\in S_{2}}u_{2}\left( U,s_{2}\right) &=&\max \left\{ u_{2}\left(
U,L\right) ,u_{2}\left( U,R\right) \right\} \\
&=&\max \left\{ -3,-2\right\} \\
&=&-2
\end{eqnarray*}である一方で、純粋戦略$D$を選んだ場合に最悪のシナリオのもとで被る損害は、\begin{eqnarray*}\max_{s_{2}\in S_{2}}u_{2}\left( D,s_{2}\right) &=&\max \left\{ u_{2}\left(
D,L\right) ,u_{2}\left( D,R\right) \right\} \\
&=&\max \left\{ -1,-4\right\} \\
&=&-1
\end{eqnarray*}です。両者を比較すると、\begin{equation*}
\max_{s_{2}\in S_{2}}u_{2}\left( U,s_{2}\right) <\max_{s_{2}\in
S_{2}}u_{2}\left( D,s_{2}\right)
\end{equation*}となるため、プレイヤー$1$のミニマックス戦略は$D$であるとともに、ミニマックス値は、\begin{equation*}\min_{s_{1}\in S_{1}}\max_{s_{2}\in S_{2}}u_{2}\left( s_{1},s_{2}\right) =-1
\end{equation*}となります。以上より、プレイヤー$1$のマックスミニ戦略とミニマックス戦略は異なることが明らかになりました。

マックスミニ値とミニマックス値の関係

2人ゼロ和ゲームにおいて、一方のプレイヤーのマックスミニ値は、他方のプレイヤーのミニマックス値以下になることが保証されます。

命題（マックスミニ値とミニマックス値の関係）

2人ゼロ和ゲーム$G$において、\begin{equation*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
\leq \min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left(
s_{1},s_{2}\right)
\end{equation*}が成り立つ。

証明

プレミアム会員専用コンテンツです
【ログイン】【会員登録】

2人ゼロ和ゲームにおいて、以下の関係\begin{equation*}
\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
\leq \min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left(
s_{1},s_{2}\right)
\end{equation*}が成り立つことが明らかになりました。左辺はプレイヤー$1$のマックスミニ値であり、右辺はプレイヤー$2$のミニマックス値です。2人の立場を交換することにより、\begin{equation*}\max_{s_{2}\in S_{2}}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}\right)
\leq \min_{s_{1}\in S_{1}}\max_{s_{2}\in S_{2}}u_{2}\left(
s_{1},s_{2}\right)
\end{equation*}もまた導かれます。左辺はプレイヤー$2$のマックスミニ値であり、右辺はプレイヤー$1$のミニマックス値です。

例（マックスミニ値とミニマックス値の関係）

以下の利得行列で表される戦略型ゲームGについて考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 0,0 & -1,1 \\ \hline
D & 1,-1 & 0,0 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。先に明らかにしたように、プレイヤー$1$のマックスミニ戦略は$D$であり、マックスミニ値は、\begin{equation*}\max_{s_{2}\in S_{2}}\min_{s_{1}\in S_{1}}u_{2}\left( s_{1},s_{2}\right) =0
\end{equation*}です。その一方で、プレイヤー$2$のミニマックス戦略は$R$であり、ミニマックス値は、\begin{equation*}\min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right) =0
\end{equation*}です。したがって、以下の関係\begin{equation*}
\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
\leq \min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left(
s_{1},s_{2}\right)
\end{equation*}が成立していますが、これは先の命題の主張と整合的です。

2人ゼロ和ゲームの混合拡張においても同様の命題が成り立ちます。

命題（マックスミニ値とミニマックス値の関係）

2人ゼロ和ゲーム$G$の混合拡張$G^{\ast }$において、\begin{equation*}\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }\min_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right) \leq
\min_{\sigma _{2}\in \Delta \left( S_{2}\right) }\max_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つ。

証明

プレミアム会員専用コンテンツです
【ログイン】【会員登録】

2人ゼロ和ゲームの混合拡張において、以下の関係\begin{equation*}
\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }\min_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right) \leq
\min_{\sigma _{2}\in \Delta \left( S_{2}\right) }\max_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{1}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}が成り立つことが明らかになりました。左辺はプレイヤー$1$のマックスミニ値であり、右辺はプレイヤー$2$のミニマックス値です。2人の立場を交換することにより、\begin{equation*}\max_{\sigma _{2}\in \Delta \left( S_{1}\right) }\min_{\sigma _{1}\in \Delta
\left( S_{1}\right) }F_{2}\left( \sigma _{1},\sigma _{2}\right) \leq
\min_{\sigma _{1}\in \Delta \left( S_{1}\right) }\max_{\sigma _{2}\in \Delta
\left( S_{2}\right) }F_{2}\left( \sigma _{1},\sigma _{2}\right)
\end{equation*}もまた導かれます。左辺はプレイヤー$2$のマックスミニ値であり、右辺はプレイヤー$1$のミニマックス値です。

例（マックスミニ値とミニマックス値の関係）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 0,0 & -1,1 \\ \hline
D & 1,-1 & 0,0 \\ \hline
\end{array}$$

演習問題

問題（ピッチャーとバッターの対決）

野球をプレーしているバッター（プレイヤー$1$）とピッチャー（プレイヤー$2$）の対決について考えます。ピッチャーはストレート（$F$で表記）もしくはカーブ（$C$で表記）のどちらか一方を投げます。バッターは相手がストレートもしくはカーブのどちらか一方を投げることを知っており、相手の球種を予測した上でバットを振ります。打率は以下の通りです。\begin{eqnarray*}&&\text{バッターが}F\text{と予測しピッチャーが}F\text{を投げる場合の打率は}3\text{割} \\
&&\text{バッターが}F\text{と予測しピッチャーが}C\text{を投げる場合の打率は}2\text{割} \\
&&\text{バッターが}C\text{と予測しピッチャーが}F\text{を投げる場合の打率は}1\text{割} \\
&&\text{バッターが}C\text{と予測しピッチャーが}C\text{を投げる場合の打率は}4\text{割}
\end{eqnarray*}打率を利得とみなした上で、バッターのマックスミニ戦略とミニマックス戦略を特定してください。

解答を見る

プレミアム会員専用コンテンツです
【ログイン】【会員登録】

問題（マックスミニ戦略）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 3,-3 & 1,-1 \\ \hline
D & 4,-4 & -2,2 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。純粋戦略の範囲においてプレイヤー$1$のマックスミニ値とプレイヤー$2$のミニマックス値を求めた上で、以下の関係\begin{equation*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right)
\leq \min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left(
s_{1},s_{2}\right)
\end{equation*}が成り立つことを確認してください。

解答を見る

プレミアム会員専用コンテンツです
【ログイン】【会員登録】

問題（マックスミニ戦略とミニマックス戦略の違い）

以下の利得行列で表される戦略型ゲーム$G$について考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & a,-a & b,-b \\ \hline
D & c,-c & d,-d \\ \hline
\end{array}$$

ただし、$a,b,c,d\in \mathbb{R} $です。どの結果が実現した場合においても2人が得る利得の和は$0$であるため、これは2人ゼロ和ゲームです。以下の条件\begin{equation*}c<b<a<d
\end{equation*}が成り立つ場合には、純粋戦略の範囲において、プレイヤー$1$のマックスミニ戦略とミニマックス戦略が一致しないことを示してください。

解答を見る

プレミアム会員専用コンテンツです
【ログイン】【会員登録】

WIIS

数学のコース

経済学のコース

アカウント

WIIS

完備情報の静学ゲーム

目次

関連知識

マックスミニ戦略

ゼロ和ゲームの混合拡張におけるマックスミニ戦略

ミニマックス戦略

ゼロ和ゲームの混合拡張におけるミニマックス戦略

マックスミニ戦略とミニマックス戦略の違い

マックスミニ値とミニマックス値の関係

演習問題

関連知識

質問とコメント

LEARN MORE

さらに深く学びたい人のための会員サービス

論理

集合

実数

ユークリッド空間

微分積分

測度

確率