WIIS

完備情報の静学ゲーム

ミニマックス定理

目次

関連知識

Mailで保存
Xで共有

ゼロ和ゲームに純粋戦略の範囲で鞍点が存在するための条件

問題としている戦略的状況が完備情報の静学ゲームであるとともに、それが戦略型ゲーム\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*}がともに成り立つということです。

2人ゼロ和ゲーム\(G\)における鞍点マックスミニ戦略とマックスミニ値ミニマックス戦略とミニマックス値について簡単に復習します。

2人ゼロ和ゲーム\(G\)において純粋戦略からなる組\(\left( s_{1}^{\ast },s_{2}^{\ast }\right) \in S_{1}\times S_{2}\)が鞍点であることは、\begin{equation*}\forall s_{1}\in S_{1},\ \forall s_{2}\in S_{2}:u_{1}\left(
s_{1},s_{2}^{\ast }\right) \leq u_{1}\left( s_{1}^{\ast },s_{2}^{\ast
}\right) \leq u_{1}\left( s_{1}^{\ast },s_{2}\right)
\end{equation*}が成り立つことを意味します。加えて、\(\left( s_{1}^{\ast },s_{2}^{\ast }\right) \)が鞍点であることと、\(\left( s_{1}^{\ast},s_{2}^{\ast }\right) \)が広義の純粋戦略ナッシュ均衡であることは必要十分です。

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

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

どの結果が実現した場合においても2人が得る利得の和は\(0\)であるため、これは2人ゼロ和ゲームです。プレイヤーが相手の戦略に対する最適反応を選んだ場合に得られる利得に印\(\ast \)をつけてあります。表から明らかであるように、\begin{equation*}\left( U,R\right)
\end{equation*}は最適反応の組であるため、これは純粋戦略ナッシュ均衡であり、したがって鞍点でもあります。

プレイヤー\(1\)にとって純粋戦略\(s_{1}^{\ast }\in S_{1}\)がマックスミニ戦略であることとは、最悪のシナリオが起きた場合に自分が確保できる利益が\(s_{1}^{\ast }\)のもとで最大化されること、すなわち、\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*}が成り立つことを意味します。その上で、マックスミニ戦略を選んだ場合に最低でも確保できる利得\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\)のマックスミニ値と呼びます。

プレイヤー\(2\)にとって純粋戦略\(s_{2}^{\ast }\in S_{2}\)がミニマックス戦略であることとは、最悪のシナリオが起きた場合に自分が被る被害が\(s_{2}^{\ast }\)のもとで最小化されること、すなわち、\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*}が成り立つことを意味します。その上で、ミニマックス戦略を選んだ場合に最悪のシナリオのもとで被る損害\begin{equation*}
\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\)において、プレイヤー\(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 & 3,-3 & 1,-1 \\ \hline
D & 4,-4 & -2,2 \\ \hline
\end{array}$$

どの結果が実現した場合においても2人が得る利得の和は\(0\)であるため、これは2人ゼロ和ゲームです。先に例を通じて確認したように、\begin{equation*}\left( U,R\right)
\end{equation*}がこのゲームの鞍点です。さて、プレイヤー\(1\)にとって最悪の状況が常に起こることを想定した場合、純粋戦略\(U\)のもとで最低限確保できる利益は\(1\)であり、純粋戦略\(D\)のもとで最低限確保できる利益は\(-2\)です。したがって、プレイヤー\(1\)のマックスミニ戦略は\(U\)であり、プレイヤー\(1\)のマックスミニ値は、\begin{equation*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right) =1
\end{equation*}です。一方、プレイヤー\(2\)にとって最悪の状況が常に起こることを想定した場合、純粋戦略\(L\)のもとで被る最大の損害は\(4\)であり、純粋戦略\(R\)のもとで被る最大の損害は\(1\)です。したがって、プレイヤー\(2\)のミニマックス戦略は\(R\)であり、プレイヤー\(2\)のミニマックス値は、\begin{equation*}\min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right) =1
\end{equation*}です。以上より、鞍点\(\left( U,R\right) \)を構成する均衡戦略はプレイヤー\(1\)のマックスミニ戦略\(U\)とプレイヤー\(2\)のミニマックス戦略\(R\)と一致するとともに、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値の間には以下の関係\begin{equation*}\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}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つことが明らかになりました。

上の例では、プレイヤー\(1\)のマックスミニ値はプレイヤー\(2\)のミニマックス値と一致していますが、一般に、両者は一致するとは限りません。以下の例より明らかです。

例(マックスミニ値とミニマックス値の関係)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。

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

どの結果が実現した場合においても2人が得る利得の和は\(0\)であるため、これは2人ゼロ和ゲームです。プレイヤーが相手の戦略に対する最適反応を選んだ場合に得られる利得に印\(\ast \)をつけてあります。表から明らかであるように、最適反応の組は存在しないため、このゲームには純粋戦略ナッシュ均衡は存在せず、したがって鞍点も存在しません。さて、プレイヤー\(1\)にとって最悪の状況が常に起こることを想定した場合、純粋戦略\(U\)のもとで最低限確保できる利益は\(-1\)であり、純粋戦略\(D\)のもとで最低限確保できる利益は\(-1\)です。したがって、プレイヤー\(1\)のマックスミニ戦略は\(U\)と\(D\)の双方であり、プレイヤー\(1\)のマックスミニ値は、\begin{equation*}\max_{s_{1}\in S_{1}}\min_{s_{2}\in S_{2}}u_{1}\left( s_{1},s_{2}\right) =-1
\end{equation*}です。一方、プレイヤー\(2\)にとって最悪の状況が常に起こることを想定した場合、純粋戦略\(L\)のもとで被る最大の損害は\(1\)であり、純粋戦略\(R\)のもとで被る最大の損害は\(1\)です。したがって、プレイヤー\(2\)のミニマックス戦略は\(L\)と\(R\)の双方であり、プレイヤー\(2\)のミニマックス値は、\begin{equation*}\min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right) =1
\end{equation*}です。以上より、\begin{equation*}
\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}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つことが明らかになりました。

最初に例として挙げた2人ゼロ和ゲームには鞍点が存在するとともに、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値は一致しています。他方で、2番目に例として挙げた2人ゼロ和ゲームには鞍点が存在せず、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値は一致しません。これは偶然ではなく、一般的に成り立つ現象です。

まずは、鞍点が存在する場合には、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値が一致することを示します。

命題(鞍点が存在するための必要条件)
2人ゼロ和ゲーム\(G\)において、純粋戦略の範囲で鞍点\(\left( s_{1}^{\ast },s_{2}^{\ast }\right)\in S_{1}\times S_{2}\)が存在する場合には、\begin{equation*}\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}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\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)
=\min_{s_{2}\in S_{2}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つ場合には、プレイヤー\(1\)のマックスミニ戦略\(s_{1}^{\ast }\in S_{1}\)とプレイヤー\(2\)のミニマックス戦略\(s_{2}^{\ast }\in S_{2}\)からなる純粋戦略の組\(\left( s_{1}^{\ast },s_{2}^{\ast }\right) \)が鞍点になる。
証明

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

以上の2つの命題を総合すると以下を得ます。

命題(鞍点が存在するための必要条件)
2人ゼロ和ゲーム\(G\)において、純粋戦略の範囲で鞍点\(\left( s_{1}^{\ast },s_{2}^{\ast }\right)\in S_{1}\times S_{2}\)が存在することと、\begin{equation*}\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}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つことは必要十分である。

2人ゼロ和ゲーム\(G\)において、純粋戦略ナッシュ均衡と鞍点は一致するため、上の命題を以下のように表現することもできます。

命題(純粋戦略ナッシュ均衡が存在するための必要条件)
2人ゼロ和ゲーム\(G\)において、広義の純粋戦略ナッシュ均衡\(\left( s_{1}^{\ast},s_{2}^{\ast }\right) \in S_{1}\times S_{2}\)が存在することと、\begin{equation*}\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}}\max_{s_{1}\in S_{1}}u_{1}\left( s_{1},s_{2}\right)
\end{equation*}が成り立つことは必要十分である。

 

ゼロ和ゲームに混合戦略の範囲で鞍点が存在するための条件

プレイヤーたちが混合戦略を採用する場合にも同様の議論が成立します。具体的には以下の通りです。

戦略型ゲーム\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\)の期待利得関数です。

2人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において混合戦略からなる組\(\left(\sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) \in \Delta \left( S_{1}\right) \times \Delta \left( S_{2}\right) \)が鞍点であることは、\begin{equation*}\forall \sigma _{1}\in \Delta \left( S_{1}\right) ,\ \forall \sigma _{2}\in
\Delta \left( S_{2}\right) :F_{1}\left( \sigma _{1},\sigma _{2}^{\ast
}\right) \leq F_{1}\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right)
\leq F_{1}\left( \sigma _{1}^{\ast },\sigma _{2}\right)
\end{equation*}が成り立つことを意味します。加えて、\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) \)が鞍点であることと、\(\left(\sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) \)が広義の混合戦略ナッシュ均衡であることは必要十分です。

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

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

先に確認したように、このゲームは2人ゼロ和ゲームである一方で純粋戦略ナッシュ均衡は存在しません。その一方で、以下の2つの混合戦略\begin{eqnarray*}
\sigma _{1}^{\ast } &=&\left( \sigma _{1}^{\ast }\left( U\right) ,\sigma
_{1}^{\ast }\left( D\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right)
\\
\sigma _{2}^{\ast } &=&\left( \sigma _{2}^{\ast }\left( L\right) ,\sigma
_{2}^{\ast }\left( R\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right)
\end{eqnarray*}からなる組\(\left( \sigma _{1}^{\ast },\sigma_{2}^{\ast }\right) \)はこのゲーム\(G\)の混合拡張\(G^{\ast }\)の混合戦略ナッシュ均衡であり(演習問題)、したがって鞍点でもあります。

プレイヤー\(1\)にとって混合戦略\(\sigma _{1}^{\ast }\in \Delta \left(S_{1}\right) \)がマックスミニ戦略であることとは、最悪のシナリオが起きた場合に自分が直面する期待利得が\(\sigma _{1}^{\ast }\)のもとで最大化されること、すなわち、\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*}が成り立つことを意味します。その上で、マックスミニ戦略を選んだ場合に最低でも確保できる期待利得\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\)のマックスミニ値と呼びます。

プレイヤー\(2\)にとって混合戦略\(\sigma _{2}^{\ast }\in \Delta \left(S_{2}\right) \)がミニマックス戦略であることとは、最悪のシナリオが起きた場合に自分が直面する期待被害が\(\sigma _{2}^{\ast }\)のもとで最小化されること、すなわち、\begin{equation*}\max_{\sigma _{1}\in \Delta \left( S_{1}\right) }F_{1}\left( \sigma
_{1},\sigma _{2}^{\ast }\right) =\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*}が成り立つことを意味します。その上で、ミニマックス戦略を選んだ場合に最悪のシナリオのもとで直面する期待被害\begin{equation*}
\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\)のミニマックス値と呼びます。

2人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(1\)のマックスミニ値はプレイヤー\(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*}が成り立ちます。

例(マックスミニ値とミニマックス値の関係)
以下の利得行列で表される戦略型ゲーム\(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}$$

どの結果が実現した場合においても2人が得る利得の和は\(0\)であるため、これは2人ゼロ和ゲームです。先に例を通じて確認したように、以下の2つの混合戦略\begin{eqnarray*}\sigma _{1}^{\ast } &=&\left( \sigma _{1}^{\ast }\left( U\right) ,\sigma
_{1}^{\ast }\left( D\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right)
\\
\sigma _{2}^{\ast } &=&\left( \sigma _{2}^{\ast }\left( L\right) ,\sigma
_{2}^{\ast }\left( R\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right)
\end{eqnarray*}からなる組\(\left( \sigma _{1}^{\ast },\sigma_{2}^{\ast }\right) \)はこのゲーム\(G\)の混合拡張\(G^{\ast }\)の鞍点です。さらに、プレイヤー\(1\)のマックスミニ戦略は\(\sigma _{1}^{\ast }\)と一致し、プレイヤー\(1\)のマックスミニ値は、\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) =0
\end{equation*}です。また、プレイヤー\(2\)のミニマックス戦略は\(\sigma _{2}^{\ast }\)と一致し、プレイヤー\(2\)のミニマックス値は、\begin{equation*}\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) =0
\end{equation*}です(演習問題)。以上より、プレイヤー\(1\)のマックスミニ値とプレイヤー\(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)
=\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人ゼロ和ゲームの混合拡張には鞍点が存在するとともに、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値は一致しています。これは偶然ではなく、一般的に成り立つ現象です。

まずは、鞍点が存在する場合には、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値が一致することを示します。

命題(鞍点が存在するための必要条件)
2人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において、混合戦略の範囲で鞍点\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) \in \Delta\left( S_{1}\right) \times \Delta \left( S_{2}\right) \)が存在する場合には、\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)
=\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人ゼロ和ゲーム\(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)
=\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\)のマックスミニ戦略\(\sigma _{1}^{\ast }\in\Delta \left( S_{1}\right) \)とプレイヤー\(2\)のミニマックス戦略\(\sigma _{2}^{\ast }\in \Delta \left( S_{2}\right) \)からなる混合戦略の組\(\left( \sigma_{1}^{\ast },\sigma _{2}^{\ast }\right) \)が鞍点になる。
証明

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

以上の2つの命題を総合すると以下を得ます。

命題(鞍点が存在するための必要条件)
2人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において、混合戦略の範囲で鞍点\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) \in \Delta\left( S_{1}\right) \times \Delta \left( S_{2}\right) \)が存在することと、\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)
=\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人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において、混合戦略ナッシュ均衡と鞍点は一致するため、上の命題を以下のように表現することもできます。

命題(混合戦略ナッシュ均衡が存在するための必要条件)
2人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において、広義の混合戦略ナッシュ均衡\(\left( \sigma _{1}^{\ast },\sigma_{2}^{\ast }\right) \in \Delta \left( S_{1}\right) \times \Delta \left(
S_{2}\right) \)が存在することと、\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)
=\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人ゼロ和ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値が一致することは、そのゲームに混合戦略ナッシュ均衡が存在することと必要十分であることが明らかになりました。

一方、2人ゼロ和ゲーム\(G\)が有限ゲームである場合、ナッシュの定理より、その混合拡張\(G^{\ast }\)には混合戦略ナッシュ均衡が存在することが保証されます。

以上の議論より、2人ゼロ和ゲーム\(G\)が有限ゲームである場合には、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値は一致することが保証されます。これをミニマックス定理(minimax theorem)と呼びます。

命題(ミニマックス定理)
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)
=\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人ゼロ和ゲーム\(G\)が有限ゲームであるならば、その混合拡張\(G^{\ast }\)において、プレイヤー\(1\)がマックスミニ戦略を採用し、プレイヤー\(2\)がミニマックス戦略を採用するという混合戦略の組み合わせが混合戦略ナッシュ均衡かつ鞍点となり、なおかつ、その均衡結果において、プレイヤー\(1\)のマックスミニ値とプレイヤー\(2\)のミニマックス値が一致します。そこで、両者が一致するその値をゲーム\(G^{\ast }\)の(value)と呼びます。

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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