展開型ゲームに純粋戦略部分ゲーム完全均衡が存在するための条件

有限な完全情報ゲームには純粋戦略部分ゲーム完全均衡が存在する

問題としている戦略的状況が完備情報の動学ゲームであるとともに、それが展開型ゲーム\begin{equation*}
\Gamma =\left( I\cup \left\{ 0\right\} ,A,X,>,a,\mathcal{H},i,p,\left\{
u_{i}\right\} _{i\in I}\right)
\end{equation*}として記述されているものとします。ただし、\(I\cup \left\{ 0\right\} \)は自然に相当するプレイヤー\(0\)を含めたプレイヤー集合、\(A\)は行動集合、\(\left( X,>\right) \)はゲームの木、\(a:X\backslash \left\{ x_{0}\right\} \rightarrow A\)はそれぞれの手番へ到達する直前に選択される行動を特定する写像、\(\mathcal{H}\)は情報分割、\(i:\mathcal{H}\rightarrow I\cup \left\{ 0\right\} \)はそれぞれの情報集合において意思決定を行うプレイヤーを特定する写像、\(p:\mathcal{H}_{0}\times A\rightarrow \left[0,1\right] \)は自然による意思決定を記述する確率分布、\(u_{i}:Z\rightarrow \mathbb{R} \)はプレイヤー\(i\)の利得関数です。

展開型ゲーム\(\Gamma \)におけるプレイヤー\(i\)の純粋戦略とは、ゲームにおいて彼が直面し得るそれぞれの情報集合\(H\in \mathcal{H}_{i}\)に対して、そこで彼が選択する行動\(s_{i}\left( H\right) \in A_{i}\)を1つずつ指定する写像\begin{equation*}s_{i}:\mathcal{H}_{i}\rightarrow A_{i}
\end{equation*}として定式化されます。展開型ゲーム\(\Gamma \)においてプレイヤーたちが純粋戦略を採用する場合に直面する戦略的状況は\(\Gamma \)の戦略型\begin{equation*}G\left( \Gamma \right) =\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{
U_{i}\right\} _{i\in I}\right)
\end{equation*}として記述されます。ただし、\(I\)はプレイヤー集合、\(S_{i}\)はプレイヤー\(i\)の純粋戦略集合、\(U_{i}:S_{I}\rightarrow \mathbb{R} \)はプレイヤー\(i\)の期待利得関数です。同様の想定のもと、部分ゲーム\(\Gamma \left( x\right) \)という\(\Gamma \)の局所的な局面においてプレイヤーたちが直面する戦略的状況は\(\Gamma \left( x\right) \)の戦略型\begin{equation*}G\left( \Gamma \left( x\right) \right) =\left( I,\left\{ S_{i}^{x}\right\}
_{i\in I},\left\{ U_{i}^{x}\right\} _{i\in I}\right)
\end{equation*}として記述されます。ただし、\(I\)はプレイヤー集合、\(S_{i}^{x}\)はプレイヤー\(i\)の純粋戦略集合\(S_{i}\)の部分ゲーム\(\Gamma\left( x\right) \)への制限、\(U_{i}^{x}:S_{I}^{x}:\rightarrow \mathbb{R} \)はプレイヤー\(i\)の期待利得関数\(U_{i}:S_{I}\rightarrow \mathbb{R} \)の部分ゲーム\(\Gamma \left( x\right) \)への制限です。

展開型ゲーム\(\Gamma \)においてプレイヤー\(i\in I\)の純粋戦略\(s_{i}^{\ast }\in S_{i}\)が他のプレイヤーたちの純粋戦略の組\(s_{-i}\in S_{-i}\)に対する広義の最適反応であることとは、\(\Gamma \)の戦略型\(G\left( \Gamma \right) \)において、\begin{equation*}\forall s_{i}\in S_{i}:U_{i}\left( s_{i}^{\ast },s_{-i}\right) \geq
U_{i}\left( s_{i},s_{-i}\right)
\end{equation*}が成り立つことを意味します。また、プレイヤーたちの純粋戦略の組\(s_{I}^{\ast }=\left( s_{i}^{\ast }\right)_{i\in I}\)が展開型ゲーム\(\Gamma \)における広義の純粋戦略ナッシュ均衡であることとは、それぞれのプレイヤー\(i\)の純粋戦略\(s_{i}^{\ast }\)が他のプレイヤーたちの純粋戦略の組\(s_{-i}^{\ast }\)に対する広義の最適反応になっていること、すなわち、\(\Gamma \)の戦略型\(G\left( \Gamma \right) \)において、\begin{equation*}\forall i\in I,\ \forall s_{i}\in S_{i}:U_{i}\left( s_{i}^{\ast
},s_{-i}^{\ast }\right) \geq U_{i}\left( s_{i},s_{-i}^{\ast }\right)
\end{equation*}が成立していることを意味します。

展開型ゲーム\(\Gamma \)におけるプレイヤーたちの純粋戦略の組\(s_{I}^{\ast }\in S_{I}^{\ast }\)が広義の純粋戦略部分ゲーム完全均衡であることとは、\(\Gamma \)の部分ゲーム\(\Gamma \left(x\right) \)を任意に選んだとき、\(s_{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{\ast x}\)が\(\Gamma\left( x\right) \)における広義の純粋戦略ナッシュ均衡になっていること、すなわち、\(\Gamma \)の任意の部分ゲーム\(\Gamma \left(x\right) \)の戦略型\(G\left( \Gamma \left( x\right)\right) \)において、\begin{equation*}\forall i\in I,\ \forall s_{i}^{x}\in S_{i}^{x}:U_{i}^{x}\left( s_{i}^{\ast
x},s_{-i}^{\ast x}\right) \geq U_{i}^{x}\left( s_{i}^{x},s_{-i}^{\ast
x}\right)
\end{equation*}が成立していることを意味します。

展開型ゲーム\(\Gamma \)が有限な完全情報ゲームである場合には、広義の純粋戦略部分ゲーム完全均衡が存在することを保証できます。ただし、展開型ゲーム\(\Gamma \)が有限ゲームであることとはプレイヤー集合\(I\)とノード集合\(X\)がともに有限であることを意味し、展開型ゲーム\(\Gamma \)が完全情報ゲームであることとは、すべての情報集合が1点集合であること、すなわち、\begin{equation*}\forall i\in I,\ \forall H\in \mathcal{H}_{i}:\left\vert H\right\vert =1
\end{equation*}が成り立つことを意味します。

例（有限な完全情報ゲーム）

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

プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。また、すべての情報集合が1点集合であるため\(\Gamma \)は完全情報ゲームです。したがって、先の命題より、\(\Gamma \)には広義の純粋戦略部分ゲーム完全均衡が存在することが保証されます。プレイヤー\(1\)の純粋戦略集合は、\begin{eqnarray*}S_{1} &=&A\left( \left\{ x_{0}\right\} \right) \\
&=&\left\{ \left( a_{11}\right) ,\left( a_{12}\right) \right\}
\end{eqnarray*}であり、プレイヤー\(2\)の純粋戦略集合は、\begin{eqnarray*}S_{2} &=&A\left( \left\{ x_{1}\right\} \right) \times A\left( \left\{
x_{2}\right\} \right) \\
&=&\left\{ \left( a_{21},a_{21}\right) ,\left( a_{21},a_{22}\right) ,\left(
a_{22},a_{21}\right) ,\left( a_{22},a_{22}\right) \right\}
\end{eqnarray*}です。\(\Gamma \)の戦略型\(G\left(\Gamma \right) \)は以下の利得行列として得られます。

$$\begin{array}{ccccc}
\hline
1\backslash 2 & \left( a_{21},a_{21}\right) & \left( a_{21},a_{22}\right) & \left( a_{22},a_{21}\right) & \left( a_{22},a_{22}\right) \\ \hline
\left( a_{11}\right) & -1,1^{\ast } & -1^{\ast },1^{\ast } & 1^{\ast },-1 & 1^{\ast },-1 \\ \hline
\left( a_{12}\right) & 1^{\ast },-1 & -1^{\ast },1^{\ast } & 1^{\ast },-1 & -1,1^{\ast } \\ \hline
\end{array}$$

上の表ではプレイヤーが広義の最適反応を選択した場合に直面する期待利得に印\(\ast \)をつけてあります。表から明らかであるように、\begin{eqnarray}&&\left( \left( a_{11}\right) ,\left( a_{21},a_{22}\right) \right)
\quad \cdots (1) \\
&&\left( \left( a_{12}\right) ,\left( a_{21},a_{22}\right) \right)
\quad \cdots (2)
\end{eqnarray}はともに広義の最適反応からなる組であるため、これらは広義の純粋戦略ナッシュ均衡です。部分ゲーム\(\Gamma \left( x_{1}\right) \)の戦略型\(G\left( \Gamma \left( x_{1}\right) \right) \)は以下の利得行列として得られます。

$$\begin{array}{ccc}
\hline
2 & \left( a_{21}\right) & \left( a_{22}\right) \\ \hline
\quad & 1^{\ast } & -1 \\ \hline
\end{array}$$

\(\left( 1\right) \)と\(\left( 2\right) \)の\(\Gamma \left(x_{1}\right) \)への制限は、\begin{eqnarray*}&&\left( a_{21}\right) \\
&&\left( a_{21}\right)
\end{eqnarray*}ですが、これらはともに\(\Gamma \left( x_{1}\right) \)における広義の純粋戦略ナッシュ均衡です。部分ゲーム\(\Gamma \left( x_{2}\right) \)の戦略型\(G\left( \Gamma \left( x_{2}\right) \right) \)は以下の利得行列として得られます。

$$\begin{array}{ccc}
\hline
2 & \left( a_{21}\right) & \left( a_{22}\right) \\ \hline
\quad & -1 & 1^{\ast } \\ \hline
\end{array}$$

\(\left( 1\right) \)と\(\left( 2\right) \)の\(\Gamma \left(x_{2}\right) \)への制限は、\begin{eqnarray*}&&\left( a_{22}\right) \\
&&\left( a_{22}\right)
\end{eqnarray*}ですが、これらはともに\(\Gamma \left( x_{2}\right) \)における広義の純粋戦略ナッシュ均衡です。以上より、\(\left( 1\right) \)と\(\left( 2\right) \)はともに\(\Gamma \)の任意の部分ゲームに対して広義の純粋戦略ナッシュ均衡を導くことが明らかになりました。したがって、\(\left( 1\right) \)と\(\left( 2\right) \)はともに\(\Gamma \)における広義の純粋戦略部分ゲーム完全均衡です。

不完全情報ゲームには純粋戦略部分ゲーム完全均衡が存在するとは限らない

展開型ゲーム\(\Gamma \)が有限な完全情報ゲームであるならば、広義の純粋戦略部分ゲーム完全均衡が存在することが明らかになりました。一方、展開型ゲーム\(\Gamma \)が有限な不完全情報ゲームである場合、広義の純粋戦略部分ゲーム完全均衡は存在するとは限りません。以下の例より明らかです。

例（純粋戦略部分ゲーム完全均衡を持たない不完全情報ゲーム）

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

プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。その一方で、情報集合\(\left\{x_{1},x_{2}\right\} \)は複数の手番を要素として持つため、\(\Gamma \)は不完全情報ゲームです。したがって、このゲーム\(\Gamma \)は先の命題が要求する条件を満たしません。プレイヤー\(1\)の純粋戦略集合は、\begin{eqnarray*}S_{1} &=&A\left( \left\{ x_{0}\right\} \right) \\
&=&\left\{ \left( a_{11}\right) ,\left( a_{12}\right) \right\}
\end{eqnarray*}であり、プレイヤー\(2\)の純粋戦略集合は、\begin{eqnarray*}S_{2} &=&A\left( \left\{ x_{1},x_{2}\right\} \right) \\
&=&\left\{ \left( a_{21}\right) ,\left( a_{22}\right) \right\}
\end{eqnarray*}です。\(\Gamma \)の戦略型\(G\left(\Gamma \right) \)は以下の利得行列として得られます。

$$\begin{array}{ccc}
\hline
1\backslash 2 & \left( a_{21}\right) & \left( a_{22}\right) \\ \hline
\left( a_{11}\right) & -1,1^{\ast } & 1^{\ast },-1 \\ \hline
\left( a_{12}\right) & 1^{\ast },-1 & -1,1^{\ast } \\ \hline
\end{array}$$

上の表ではプレイヤーが広義の最適反応を選択した場合に直面する期待利得に印\(\ast \)をつけてあります。表から明らかであるように広義の最適反応からなる組は存在しないため、このゲームには広義の純粋戦略ナッシュ均衡が存在しません。したがって、広義の純粋戦略部分ゲーム完全均衡も存在しません。

不完全情報ゲームには広義の純粋戦略部分ゲーム完全均衡は存在するとは限らないことが明らかになりました。ちなみに、不完全情報ゲームには広義の純粋戦略ナッシュ均衡は必ず存在しないというわけではありません。広義の純粋戦略ナッシュ均衡が存在するような不完全情報ゲームは存在します。以下の例より明らかです。

例（純粋戦略部分ゲーム完全均衡を持つ不完全情報ゲーム）

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

プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。その一方で、情報集合\(\left\{x_{1},x_{2}\right\} \)は複数の手番を要素として持つため、\(\Gamma \)は不完全情報ゲームです。したがって、このゲーム\(\Gamma \)は先の命題が要求する条件を満たしません。プレイヤー\(1\)の純粋戦略集合は、\begin{eqnarray*}S_{1} &=&A\left( \left\{ x_{0}\right\} \right) \\
&=&\left\{ \left( a_{11}\right) ,\left( a_{12}\right) \right\}
\end{eqnarray*}であり、プレイヤー\(2\)の純粋戦略集合は、\begin{eqnarray*}S_{2} &=&A\left( \left\{ x_{1},x_{2}\right\} \right) \\
&=&\left\{ \left( a_{21}\right) ,\left( a_{22}\right) \right\}
\end{eqnarray*}です。\(\Gamma \)の戦略型\(G\left(\Gamma \right) \)は以下の利得行列として得られます。

$$\begin{array}{ccc}
\hline
1\backslash 2 & \left( a_{21}\right) & \left( a_{22}\right) \\ \hline
\left( a_{11}\right) & 2^{\ast },1^{\ast } & 0,0 \\ \hline
\left( a_{12}\right) & -1,1 & 3^{\ast },2^{\ast } \\ \hline
\end{array}$$

上の表ではプレイヤーが広義の最適反応を選択した場合に直面する期待利得に印\(\ast \)をつけてあります。表から明らかであるように、\begin{eqnarray*}&&\left( \left( a_{11}\right) ,\left( a_{21}\right) \right) \\
&&\left( \left( a_{12}\right) ,\left( a_{22}\right) \right)
\end{eqnarray*}はともに広義の最適反応からなる組であるため、これらは広義の純粋戦略ナッシュ均衡です。\(\Gamma \)自身は\(\Gamma \)の唯一の部分ゲームであるため、これらは広義の純粋戦略部分ゲーム完全均衡でもあります。

無限ゲームには純粋戦略部分ゲーム完全均衡が存在するとは限らない

展開型ゲーム\(\Gamma \)が有限な完全情報ゲームであるならば、広義の純粋戦略部分ゲーム完全均衡が存在することが明らかになりました。一方、展開型ゲーム\(\Gamma \)が無限な完全情報ゲームである場合、広義の純粋戦略部分ゲーム完全均衡は存在するとは限りません。以下の例より明らかです。

例（純粋戦略部分ゲーム完全均衡を持たない完全情報ゲーム）

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

つまり、情報集合\(\left\{x_{0}\right\} \)においてプレイヤー\(1\)は\(0\)以上かつ\(1\)より小さい何らかの実数\(a\)を選び、その結果、プレイヤー\(1\)は自身が選んだ\(a\)に等しい利得を得るということです。頂点集合は\([0,1)\)という無限集合であるため\(\Gamma \)は無限ゲームです。その一方で、唯一の情報集合\(\left\{x_{0}\right\} \)は1点集合であるため\(\Gamma \)は完全情報ゲームです。このゲーム\(\Gamma \)には純粋戦略部分ゲーム完全均衡は存在しません（演習問題）。

完全記憶ゲームには純粋戦略部分ゲーム完全均衡が存在するとは限らない

展開型ゲーム\(\Gamma \)が完全記憶ゲームであることとは、以下の条件を満たすこととして定義されます。

1. 1. 頂点\(z\in Z\)と情報集合\(H\in \mathcal{H}\)をそれぞれ任意に選んだとき、頂点\(z\)への経路上にあり、なおかつ情報集合\(H\)の要素でもあるような手番の個数は\(0\)または\(1\)である。
   2. プレイヤー\(i\in I\)と、プレイヤー\(i\)の情報集合\(H\in \mathcal{H}_{i}\)およびその要素である手番\(x,\hat{x}\in H\)をそれぞれ任意に選ぶ。初期点\(x_{0}\)から手番\(x\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}x_{i}^{1},x_{i}^{2},\cdots ,x_{i}^{L}
      \end{equation*}で表記する。また、初期点\(x_{0}\)から手番\(\hat{x}\)への経路上にあるノードの中でもプレイヤー\(i\)が意思決定を行う手番を初期点から近い順に、\begin{equation*}\hat{x}_{i}^{1},\hat{x}_{i}^{2},\cdots ,\hat{x}_{i}^{\hat{L}}
      \end{equation*}で表記する。このとき、\begin{eqnarray*}
      &&\left( a\right) \ L=\hat{L} \\
      &&\left( b\right) \ \forall l\in \left\{ 1,\cdots ,L\right\} :a_{i}\left(
      x_{i}^{l}\rightarrow x\right) =a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right) \\
      &&\left( c\right) \ \forall l\in \left\{ 1,\cdots ,L\right\} :H\left(
      x_{i}^{l}\right) =H\left( \hat{x}_{i}^{l}\right)
      \end{eqnarray*}が成り立つ。ただし、\(a_{i}\left( x_{i}^{l}\rightarrow x\right) \)はプレイヤー\(i\)が手番\(x\)へ到達するために手番\(x_{i}^{l}\)において選択すべき行動であり、\(a_{i}\left( \hat{x}_{i}^{l}\rightarrow \hat{x}\right) \)はプレイヤー\(i\)が手番\(\hat{x}\)へ到達するために手番\(\hat{x}_{i}^{l}\)において選択すべき行動である。また、\(H\left(x_{i}^{l}\right) \)は手番\(x_{i}^{l}\)が属する情報集合であり、\(H\left( \hat{x}_{i}^{l}\right) \)は手番\(\hat{x}_{i}^{l}\)が属する情報集合である。

   条件1は、任意のプレイヤーについて、そのプレイヤーが意思決定を行う複数の手番が同一経路上に存在する場合、それらが同一の情報集合に属するような事態は起こり得ないことを意味します。条件2は、プレイヤーと、そのプレイヤーが意思決定を行う情報集合、そしてその情報集合に属する手番\(x,\hat{x}\)をそれぞれ任意に選んだとき、初期点\(x_{0}\)から手番\(x\)へ到達するために選択すべき行動の列と、初期点\(x_{0}\)から手番\(\hat{x}\)へ到達するために選択すべき行動の列が完全に一致することを意味します。同一の情報集合上にある手番へは、常に同じ行動の列のもとで到達する必要があるということです。

   展開型ゲーム\(\Gamma \)が完全記憶ゲームである場合でも、広義の純粋戦略部分ゲーム完全均衡は存在するとは限りません。以下の例より明らかです。

   例（純粋戦略部分ゲーム完全均衡を持たない完全記憶ゲーム）

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

   

   プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。複数の手番を要素として持つ情報集合は\(\left\{ x_{1},x_{2}\right\} \)だけですが、この情報集合は特定の頂点への経路と複数の手番で交わらないため、\(\Gamma \)は完全記憶ゲームです。その一方で、先に示したように、このゲームには広義の純粋戦略部分ゲーム完全均衡が存在しません。

   完全記憶ゲームには広義の純粋戦略部分ゲーム完全均衡は存在するとは限らないことが明らかになりました。ちなみに、完全記憶ゲームには広義の純粋戦略部分ゲーム完全均衡は必ず存在しないというわけではありません。広義の純粋戦略部分ゲーム完全均衡が存在するような完全記憶ゲームは存在します。以下の例より明らかです。

   例（純粋戦略部分ゲーム完全均衡を持つ完全記憶ゲーム）

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

   

   プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。複数の手番を要素として持つ情報集合は\(\left\{ x_{1},x_{2}\right\} \)だけですが、この情報集合は特定の頂点への経路と複数の手番で交わらないため、\(\Gamma \)は完全記憶ゲームです。先に示したように、\begin{eqnarray*}&&\left( \left( a_{11}\right) ,\left( a_{21}\right) \right) \\
   &&\left( \left( a_{12}\right) ,\left( a_{22}\right) \right)
   \end{eqnarray*}はともに純粋戦略部分ゲーム完全均衡です。

    

   演習問題

   問題（純粋戦略部分ゲーム完全均衡を持たない完全情報ゲーム）

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

   

   つまり、情報集合\(\left\{x_{0}\right\} \)においてプレイヤー\(1\)は\(0\)以上かつ\(1\)より小さい何らかの実数\(a\)を選び、その結果、プレイヤー\(1\)は自身が選んだ\(a\)に等しい利得を得るということです。このゲーム\(\Gamma \)には純粋戦略部分ゲーム均衡が存在しないことを示してください。

   解答を見る

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