展開型ゲームにおける混合戦略ナッシュ均衡の分離と合成

混合戦略のもとでの展開型ゲームの分割

問題としている戦略的状況が完備情報の動学ゲームであり、それが展開型ゲーム\(\Gamma \)として表現されているものとします。さらに、プレイヤーたちが混合戦略を採用する状況を想定します。ただし、展開型ゲーム\(\Gamma \)におけるプレイヤー\(i\)の混合戦略とは、プレイヤー\(i\)のそれぞれの純粋戦略\(s_{ij}\in S_{i}\)に対して、それが選ばれる確率\(\sigma_{i}(s_{ij})\in \mathbb{R} \)を指定する確率関数\begin{equation*}\sigma _{i}:S_{i}\rightarrow \mathbb{R} \end{equation*}として定式化されます。

展開型ゲーム\(\Gamma \)においてプレイヤーたちが選択する混合戦略からなる組が\(\sigma _{I}\)であるものとします。展開型ゲーム\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)を選んだとき、プレイヤー\(i\)は先の混合戦略\(\sigma _{i}\)のもとで部分ゲーム\(\Gamma\left( x\right) \)においてどのような意思決定を行うでしょうか。部分ゲーム\(\Gamma \left( x\right) \)におけるプレイヤー\(i\)の純粋戦略集合は\(S_{i}^{x}\)であるため、プレイヤー\(i\)の混合戦略\(\sigma _{i}\)の定義域を\(S_{i}\)から\(S_{i}^{x}\)へ変更して、\begin{equation*}\sigma _{i}^{x}:S_{i}^{x}\rightarrow \mathbb{R} \end{equation*}とすれば、部分ゲーム\(\Gamma \left( x\right) \)におけるプレイヤー\(i\)の意思決定を記述する混合戦略が得られます。これを混合戦略\(\sigma _{i}\)の部分ゲーム\(\Gamma \left( x\right) \)への制限（restricted to the subgame \(\Gamma \left(x\right) \)）と呼びます。プレイヤー\(i\)の純粋戦略集合\(S_{i}\)を部分ゲーム\(\Gamma \left( x\right) \)へ制限したものが\(S_{i}^{x}\)であるため、もとのゲーム\(\Gamma \)における純粋戦略\(s_{i}\in S_{i}\)と\(\Gamma \)の部分ゲーム\(\Gamma \left(x\right) \)をそれぞれ任意に選んだとき、\begin{equation*}\sigma _{i}^{x}\left( s_{i}^{x}\right) =\sigma \left( s_{i}\right)
\end{equation*}という関係が成り立ちます。

それぞれのプレイヤー\(i\)の混合戦略\(\sigma _{i}\)を部分ゲーム\(\Gamma \left( x\right) \)へ制限すれば、部分ゲーム\(\Gamma \left( x\right) \)においてプレイヤーたちが選択する混合戦略からなる組\(\sigma _{I}^{x}\)が得られるため、部分ゲーム\(\Gamma \left( x\right) \)においてそれぞれのプレイヤーが直面する期待利得を算出でき、その結果、もとの展開型ゲーム\(\Gamma \)を縮約ゲーム\(\Gamma\left( x|\sigma _{I}^{x}\right) \)へ変換できます。

では、プレイヤー\(i\)は先の混合戦略\(\sigma _{i}\)のもとで縮約ゲーム\(\Gamma \left(x|\sigma _{I}^{x}\right) \)においてどのような意思決定を行うでしょうか。縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{x}\right) \)におけるプレイヤー\(i\)の純粋戦略集合は\(S_{i}^{x|\sigma_{I}^{x}}\)であるため、プレイヤー\(i\)の混合戦略\(\sigma_{i}\)の定義域を\(S_{i}\)から\(S_{i}^{x|\sigma _{I}^{x}}\)へ変更して、\begin{equation*}\sigma _{i}^{x|\sigma _{I}^{x}}:S_{i}^{x|\sigma _{I}^{x}}\rightarrow \mathbb{R} \end{equation*}とすれば、縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{x}\right) \)におけるプレイヤー\(i\)の意思決定を記述する混合戦略が得られます。これを混合戦略\(\sigma _{i}\)の縮約ゲーム縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{x}\right) \)への制限（restricted to the truncated game \(\Gamma\left( x|\sigma _{I}^{x}\right) \)）と呼びます。プレイヤー\(i\)の純粋戦略集合\(S_{i}\)を縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{x}\right) \)へ制限したものが\(S_{i}^{x|\sigma_{I}^{x}}\)であるため、もとのゲーム\(\Gamma \)における純粋戦略\(s_{i}\in S_{i}\)と\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)をそれぞれ任意に選んだとき、\begin{equation*}\sigma _{i}^{x|\sigma _{I}^{x}}\left( s_{i}^{x|\sigma _{I}^{x}}\right)
=\sigma \left( s_{i}\right)
\end{equation*}という関係が成り立ちます。

それぞれのプレイヤー\(i\)の混合戦略\(\sigma _{i}\)を縮約ゲーム\(\Gamma \left( x|\sigma_{I}^{x}\right) \)へ制限すれば、縮約ゲーム\(\Gamma \left( x|\sigma_{I}^{x}\right) \)においてプレイヤーたちが選択する混合戦略からなる組\(\sigma _{I}^{x|\sigma _{I}^{x}}\)が得られるため、縮約ゲーム\(\Gamma\left( x|\sigma _{I}^{x}\right) \)においてそれぞれのプレイヤーが直面する期待利得を算出できますが、これはもとのゲーム\(\Gamma \)においてプレイヤーたちが\(\sigma _{I}\)を選んだ場合に直面する期待利得と一致します。

以上を踏まえると、展開型ゲーム\(\Gamma \)においてプレイヤーたちが混合戦略からなる組\(\sigma _{I}\)にもとづいて意思決定を行うこととは、何らかの部分ゲーム\(\Gamma \left( x\right) \)に注目したとき、プレイヤーたちは部分ゲーム\(\Gamma\left( x\right) \)に属する情報集合においては\(\sigma _{I}\)の\(\Gamma\left( x\right) \)への制限\(\sigma _{I}^{x}\)にもとづいて意思決定を行い、縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{x}\right) \)に属する情報集合においては\(\sigma _{I}\)の\(\Gamma \left( x|\sigma _{I}^{x}\right) \)への制限\(\sigma _{I}^{x|\sigma _{I}^{x}}\)にもとづいて意思決定を行うことを意味します。

例（混合戦略のもとでの展開型ゲームの分割）

以下のゲームの木で表される展開型ゲーム\(\Gamma \)について考えます。

プレイヤーたちが選ぶ混合戦略からなる組\(\sigma _{I}=\left( \sigma _{1},\sigma _{2}\right) \)が、\begin{eqnarray*}\sigma _{1} &=&\left( \sigma _{1}\left( a_{11}\right) ,\sigma _{1}\left(
a_{12}\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right) \\
\sigma _{2} &=&\left( \sigma _{2}\left( a_{21},a_{23}\right) ,\sigma
_{2}\left( a_{21},a_{24}\right) ,\sigma _{2}\left( a_{22},a_{23}\right)
,\sigma _{2}\left( a_{22},a_{24}\right) \right) =\left( \frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)
\end{eqnarray*}を満たすものとします。この場合、頂点\(z_{1},z_{2},z_{3},z_{4}\)へ到達する確率はいずれも\(\frac{1}{4}\)であるため、プレイヤーたちが直面する期待利得は、\begin{eqnarray}F_{1}\left( \sigma _{I}\right) &=&\frac{1}{4}\left[ \left( -1\right)
+1+1+\left( -1\right) \right] =0 \quad \cdots (1) \\
F_{2}\left( \sigma _{I}\right) &=&\frac{1}{4}\left[ 1+\left( -1\right)
+\left( -1\right) +1\right] =0 \quad \cdots (2)
\end{eqnarray}となります。手番\(x_{1}\)を初期点とする部分ゲーム\(\Gamma \left( x_{1}\right) \)に注目します。先の混合戦略の組\(\sigma _{I}\)を\(\Gamma \left( x_{1}\right) \)に制限すると、\begin{eqnarray*}\sigma _{I}^{x_{1}} &=&\left( \sigma _{2}^{x_{1}}\right) \\
&=&\left( \sigma _{2}^{x_{1}}\left( a_{21}\right) ,\sigma _{2}^{x_{1}}\left(
a_{22}\right) \right) \\
&=&\left( \frac{1}{2},\frac{1}{2}\right)
\end{eqnarray*}となります。部分ゲーム\(\Gamma \left( x_{1}\right) \)においてプレイヤーたちが\(\sigma_{I}^{x_{1}}\)を選ぶ場合、すなわちプレイヤー\(2\)が混合戦略\(\sigma _{2}^{x_{1}}\)を選ぶ場合、頂点\(z_{1},z_{2}\)へ到達する確率はいずれも\(\frac{1}{2}\)であるため、プレイヤーたちが直面する期待利得は、\begin{eqnarray*}F_{1}^{x_{1}}\left( \sigma _{I}^{x_{1}}\right) &=&\frac{1}{2}\left[ \left(
-1\right) +1\right] =0 \\
F_{2}^{x_{1}}\left( \sigma _{I}^{x_{1}}\right) &=&\frac{1}{4}\left[
1+\left( -1\right) \right] =0
\end{eqnarray*}となります。したがって、縮約ゲーム\(\Gamma\left( x_{1}|\sigma _{I}^{x_{1}}\right) \)は以下のゲームの木として表現されます。

先の混合戦略の組\(\sigma _{I}\)を\(\Gamma \left( x_{1}|\sigma _{I}^{x_{1}}\right) \)に制限すると、\begin{eqnarray*}\sigma _{1}^{x_{1}|\sigma _{I}^{x_{1}}} &=&\left( \sigma _{1}^{x_{1}|\sigma
_{I}^{x_{1}}}\left( a_{11}\right) ,\sigma _{1}^{x_{1}|\sigma
_{I}^{x_{1}}}\left( a_{12}\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right) \\
\sigma _{2}^{x_{1}|\sigma _{I}^{x_{1}}} &=&\left( \sigma _{2}^{x_{1}|\sigma
_{I}^{x_{1}}}\left( a_{21}\right) ,\sigma _{2}^{x_{1}|\sigma
_{I}^{x_{1}}}\left( a_{22}\right) \right) =\left( \frac{1}{2},\frac{1}{2}\right)
\end{eqnarray*}となります。このとき、確率\(\frac{1}{2}\)で頂点\(x_{1}\)へ到達し、確率\(\frac{1}{4}\)で頂点\(z_{3}\)へ到達し、確率\(\frac{1}{4}\)で頂点\(z_{4}\)へ到達するため、プレイヤーたちが直面する期待利得は、\begin{eqnarray*}F_{1}^{x_{1}|\sigma _{I}^{x_{1}}}\left( \sigma _{I}^{x_{1}|\sigma
_{I}^{x_{1}}}\right) &=&\frac{1}{4}\cdot 0+\frac{1}{2}\left[ 1+\left(
-1\right) \right] =0 \\
F_{2}^{x_{1}|\sigma _{I}^{x_{1}}}\left( \sigma _{I}^{x_{1}|\sigma
_{I}^{x_{1}}}\right) &=&\frac{1}{4}\cdot 0+\frac{1}{2}\left[ \left(
-1\right) +1\right] =0
\end{eqnarray*}となりますが、これらは\(\left( 1\right) ,\left( 2\right) \)と一致します。

混合戦略ナッシュ均衡の分離定理

展開型ゲーム\(\Gamma \)に混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)が存在する状況を想定します。さらに、展開型ゲーム\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)の中でも、その初期点\(x\)が先の均衡\(\sigma _{I}^{\ast }\)のもとで到達可能なものを任意に選びます。つまり、\begin{equation*}P\left( x|\sigma _{I}^{\ast }\right) >0
\end{equation*}を満たす手番\(x\in X\backslash Z\)を初期点とする部分ゲーム\(\Gamma \left( x\right) \)を任意に選ぶということです。先の均衡\(\sigma _{I}^{\ast }\)を先の部分ゲーム\(\Gamma \left( x\right) \)へ制限すれば、\(\Gamma \left(x\right) \)においてプレイヤーたちが選択する混合戦略からなる組\(\sigma_{I}^{\ast x}\)が得られますが、これは\(\Gamma \left( x\right) \)において混合戦略ナッシュ均衡になることが保証されます。つまり、展開型ゲームにおける混合戦略ナッシュ均衡は、均衡において到達可能な手番を初期点とする任意の部分ゲームに対しても混合戦略ナッシュ均衡になるということです。

上の命題は混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\)のもとで到達可能な部分ゲーム\(\Gamma \left( x\right) \)だけを対象にしている点に注意が必要です。つまり、もとのゲーム\(\Gamma \)における広義の混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\)のもとで部分ゲーム\(\Gamma \left( x\right) \)が到達可能ではない場合、\(\sigma _{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(\sigma _{I}^{\ast x}\)は\(\Gamma \left( x\right) \)における広義の混合戦略ナッシュ均衡であるとは限りません。

引き続き、展開型ゲーム\(\Gamma \)に混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\in S_{I}\)が存在する状況を想定します。部分ゲーム\(\Gamma \left( x\right) \)を任意に選びます。ただし、先の命題とは異なり、\(\Gamma \left( x\right) \)は\(\sigma _{I}^{\ast }\)のもとで到達可能である必要はありません。さて、均衡\(\sigma _{I}^{\ast }\)を部分ゲーム\(\Gamma \left( x\right) \)へ制限すれば\(\sigma _{I}^{\ast x}\)が得られるため、\(\Gamma \left( x\right) \)においてそれぞれのプレイヤーが直面する期待利得を算出でき、その結果、もとのゲーム\(\Gamma \)を縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)へ変換できます。さらに、先の均衡\(\sigma _{I}^{\ast }\)を縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)へ制限すれば\(\sigma _{I}^{\ast x|\sigma_{I}^{\ast x}}\)が得られますが、これは\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)における混合戦略ナッシュ均衡になることが保証されます。

得られた結果を1つの命題としてまとめます。

この命題はどのようなことを主張しているのでしょうか。展開型ゲーム\(\Gamma \)に広義の混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)が存在するものとします。さらに、\(\sigma _{I}^{\ast }\)のもとで到達可能な部分ゲーム\(\Gamma \left( x\right) \)を任意に選びます。均衡\(\sigma _{I}^{\ast }\)を部分ゲーム\(\Gamma\left( x\right) \)へ制限すれば\(\sigma_{I}^{\ast x}\)が得られるため、\(\Gamma \left( x\right) \)においてそれぞれのプレイヤーが直面する期待利得を算出でき、その結果、もとのゲーム\(\Gamma \)を縮約ゲーム\(\Gamma \left( x|\sigma_{I}^{\ast x}\right) \)へ変換できます。さて、もとのゲーム\(\Gamma \)においてプレイヤーたちがナッシュ均衡\(\sigma _{I}^{\ast }\)にもとづいて意思決定を行うことは、プレイヤーたちは部分ゲーム\(\Gamma\left( x\right) \)において\(\sigma _{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(\sigma_{I}^{\ast x}\)にもとづいて意思決定を行い、縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)において\(\sigma _{I}^{\ast }\)の\(\Gamma \left(x|\sigma _{I}^{\ast x}\right) \)への制限\(\sigma_{I}^{\ast x|\sigma _{I}^{\ast x}}\)にもとづいて意思決定を行うことを意味します。ただ、上の命題によると、\(\sigma _{I}^{\ast x}\)は\(\Gamma \left( x\right) \)におけるナッシュ均衡であり、\(\sigma _{I}^{\ast x|\sigma_{I}^{\ast x}}\)は\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)におけるナッシュ均衡であることが保証されます。したがって、上の命題は、展開型ゲーム\(\Gamma \)の混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\)を、それによって到達可能な部分ゲームにおける混合戦略ナッシュ均衡と、それに対応する縮約ゲームにおける混合戦略ナッシュ均衡に分離可能であることを主張しています。このような事情を踏まえた上で、先の命題を展開型ゲームにおける混合戦略ナッシュ均衡の分離定理（separation theorem）と呼びます。

混合戦略ナッシュ均衡の合成定理

展開型ゲーム\(\Gamma \)に混合戦略ナッシュ均衡\(\sigma _{I}^{\ast }\)が存在する場合、\(\sigma _{I}^{\ast }\)のもとで到達可能な部分ゲーム\(\Gamma\left( x\right) \)を任意に選べば、\(\sigma _{I}\)は\(\Gamma \left( x\right) \)における混合戦略ナッシュ均衡と、それに対応する縮約ゲーム\(\Gamma\left( x|\sigma _{I}^{\ast x}\right) \)における混合戦略ナッシュ均衡とに分離可能であることが明らかになりましたが、実は、逆向きの議論もまた成立します。

展開型ゲーム\(\Gamma \)における混合戦略の組\(\sigma_{I}^{\ast }\)に注目します。ただし、これが\(\Gamma \)における混合戦略ナッシュ均衡であることは明らかではないものとします。部分ゲーム\(\Gamma \left( x\right) \)を任意に選んだとき、もとのゲーム\(\Gamma \)においてプレイヤーたちが先の混合戦略\(\sigma _{I}^{\ast }\)にもとづいて意思決定を行うことは、部分ゲーム\(\Gamma \left( x\right) \)では\(\sigma _{I}^{\ast }\)の\(\Gamma\left( x\right) \)への制限\(\sigma _{I}^{\ast x}\)にもとづいて意思決定を行い、縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)では\(\sigma _{I}^{\ast }\)の\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)への制限\(\sigma _{I}^{x|\sigma _{I}^{\ast x}}\)にもとづいて意思決定を行うことを意味します。以上を踏まえたとき、何らかの部分ゲーム\(\Gamma \left( x\right) \)のもとでは、\(\sigma _{I}^{\ast x}\)が\(\Gamma \left( x\right) \)における混合戦略ナッシュ均衡であり、なおかつ、\(\sigma_{I}^{x|\sigma _{I}^{\ast x}}\)が\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)における混合戦略ナッシュ均衡になるのであれば、\(\sigma _{I}^{\ast }\)はもとのゲーム\(\Gamma \)における混合戦略ナッシュ均衡であることが保証されます。

この命題はどのようなことを主張しているのでしょうか。展開型ゲーム\(\Gamma \)における混合戦略の組\(\sigma _{I}^{\ast}\in \Delta \left( S_{I}\right) \)に注目します。\(\sigma _{I}^{\ast }\)を部分ゲーム\(\Gamma \left( x\right) \)へ制限すれば\(\sigma _{I}^{\ast x}\)が得られるため、\(\Gamma \left( x\right) \)においてそれぞれのプレイヤーが直面する期待利得を算出でき、その結果、もとのゲーム\(\Gamma \)を縮約ゲーム\(\Gamma\left( x|\sigma _{I}^{\ast x}\right) \)へ変換できます。さて、もとのゲーム\(\Gamma \)においてプレイヤーたちが\(\sigma_{I}^{\ast }\)にもとづいて意思決定を行うことは、プレイヤーたちは部分ゲーム\(\Gamma \left( x\right) \)では\(\sigma _{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(\sigma _{I}^{\ast x}\)にもとづいて意思決定を行い、縮約ゲーム\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)では\(\sigma _{I}^{\ast }\)の\(\Gamma \left(x|\sigma _{I}^{\ast x}\right) \)への制限\(\sigma_{I}^{\ast x|\sigma _{I}^{\ast x}}\)にもとづいて意思決定を行うことを意味します。ただ、上の2つの命題によると、少なくとも1つの部分ゲーム\(\Gamma \left(x\right) \)において、\(\sigma _{I}^{\ast x}\)は\(\Gamma \left( x\right) \)におけるナッシュ均衡であり、なおかつ\(\sigma _{I}^{\ast x|\sigma _{I}^{\ast x}}\)は\(\Gamma \left( x|\sigma _{I}^{\ast x}\right) \)におけるナッシュ均衡であるならば、\(\sigma _{I}^{\ast }\)はもとのゲーム\(\Gamma \)におけるナッシュ均衡になることが保証されます。したがって、上の命題は、展開型ゲーム\(\Gamma \)の部分ゲームの混合戦略ナッシュ均衡と、それに対応する縮約ゲームの混合戦略ナッシュ均衡が与えられれば、それらを合成することにより、もとのゲーム\(\Gamma \)の混合戦略ナッシュ均衡が得られることを主張しています。このような事情を踏まえた上で、先の命題を展開型ゲームにおける混合戦略ナッシュ均衡の合成定理（composition theorem）と呼びます。