有限な完全情報ゲームには純粋戦略ナッシュ均衡が存在する
問題としている戦略的状況が完備情報の動学ゲームであるとともに、それが展開型ゲーム\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 \)はプレイヤーたちが順番に意思決定を行う動学ゲームを記述するモデルです。ただ、プレイヤーたちが展開型ゲーム\(\Gamma \)において純粋戦略を選択することは、自身が直面し得るそれぞれの情報集合においてどの行動を選択するか、その包括的な行動計画をあらかじめ立てた上でゲームに臨むことを意味します。展開型ゲーム\(\Gamma \)の開始時点においてプレイヤーたちはそのような行動計画を表明します。ゲームの開始後には先の行動計画を変更できず、自身が先に表明した行動計画にもとづいて意思決定を行います。つまり、展開型ゲームにおいてプレイヤーたちが純粋戦略を採用する状況は、プレイヤーたちが純粋戦略を同時に表明する静学ゲームと解釈できるため、そこでの戦略的状況を戦略型ゲーム\(G\left( \Gamma \right) \)として表現できるということです。
展開型ゲーム\(\Gamma \)においてプレイヤー\(i\in I\)の純粋戦略\(s_{i}^{\ast }\in S_{i}\)が他のプレイヤーたちの純粋戦略の組\(s_{-i}\in S_{-i}\)に対する広義の最適反応であることとは、\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}\)が広義の純粋戦略ナッシュ均衡であることとは、それぞれのプレイヤー\(i\)の純粋戦略\(s_{i}^{\ast }\)が他のプレイヤーたちの純粋戦略の組\(s_{-i}^{\ast }\)に対する広義の最適反応であること、すなわち、\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 \)が有限な完全情報ゲームである場合には、広義の純粋戦略ナッシュ均衡が存在することを保証できます。ただし、展開型ゲーム\(\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 \)は有限ゲームです。また、すべての情報集合が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) \\
&&\left( \left( a_{12}\right) ,\left( a_{21},a_{22}\right) \right)
\end{eqnarray*}はともに広義の最適反応からなる組であるため、これらは広義の純粋戦略ナッシュ均衡です。この結果は先の命題の主張と整合的です。
不完全情報ゲームには純粋戦略ナッシュ均衡が存在するとは限らない
展開型ゲーム\(\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 \)は有限ゲームです。その一方で、情報集合\(\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 \)が無限な完全情報ゲームである場合、広義の純粋戦略ナッシュ均衡は存在するとは限りません。以下の例より明らかです。
つまり、情報集合\(\left\{x_{0}\right\} \)においてプレイヤー\(1\)は\(0\)以上かつ\(1\)より小さい何らかの実数\(a\)を選び、その結果、プレイヤー\(1\)は自身が選んだ\(a\)に等しい利得を得るということです。頂点集合は\([0,1)\)という無限集合であるため\(\Gamma \)は無限ゲームです。その一方で、唯一の情報集合\(\left\{x_{0}\right\} \)は1点集合であるため\(\Gamma \)は完全情報ゲームです。このゲーム\(\Gamma \)には純粋戦略ナッシュ均衡は存在しません（演習問題）。
完全記憶ゲームには純粋戦略ナッシュ均衡が存在するとは限らない
展開型ゲーム\(\Gamma \)が完全記憶ゲームであることとは、以下の条件を満たすこととして定義されます。
- 頂点\(z\in Z\)と情報集合\(H\in \mathcal{H}\)をそれぞれ任意に選んだとき、頂点\(z\)への経路上にあり、なおかつ情報集合\(H\)の要素でもあるような手番の個数は\(0\)または\(1\)である。
- プレイヤー\(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 \)は有限ゲームです。複数の手番を要素として持つ情報集合は\(\left\{ x_{1},x_{2}\right\} \)だけですが、この情報集合は特定の頂点への経路と複数の手番で交わらないため、\(\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*}はともに純粋戦略ナッシュ均衡です。
完備情報の静学ゲームにおける純粋戦略ナッシュ均衡との関係
問題としている戦略的状況が完備情報の静学ゲームであるとともに、それが戦略型ゲーム\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\)には純粋戦略の範囲でナッシュ均衡は存在するとは限りません。以下の例より明らかです。
$$\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}$$
表にはそれぞれのプレイヤーが広義の最適反応を選んだときに得る利得に\(\ast \)を記してあります。表から明らかであるように広義の最適反応の組は存在しないため、このゲームには広義の純粋戦略ナッシュ均衡が存在しません。
以上の事実と、展開型ゲームにおける純粋戦略ナッシュ均衡に関する先の命題の間にはどのような関係があるのでしょうか。完備情報の静学ゲームを表す戦略型ゲーム\(G\)を展開型ゲーム\(\Gamma \)として表現する場合、それは不完全情報ゲームにならざるを得ません。したがって、先の命題を利用できず、戦略型ゲーム\(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}$$
このゲームを展開型ゲーム\(\Gamma \)として表現すると以下のようになります。
プレイヤー\(2\)の情報集合\(\left\{ x_{1},x_{2}\right\} \)は複数の手番を要素として持つため、このゲームは不完全情報ゲームです。したがって、先の命題を用いて純粋戦略ナッシュ均衡が存在することを保証することはできません。実際、この展開型ゲーム\(\Gamma \)の戦略型\(G\left( \Gamma \right) \)はもとの戦略型ゲーム\(G\)に他ならず、やはり広義の純粋戦略ナッシュ均衡は存在しません。
完備情報の静学ゲームにおいてプレイヤーたちが純粋戦略を採用する場合にはナッシュ均衡は存在するとは限りません。一方、先の命題によると、考察対象を動学ゲームにまで広げ、その中でも完全情報ゲームというクラスのゲームに注目すると、純粋戦略の範囲においてもナッシュ均衡が存在することを保証できます。
演習問題
つまり、情報集合\(\left\{x_{0}\right\} \)においてプレイヤー\(1\)は\(0\)以上かつ\(1\)より小さい何らかの実数\(a\)を選び、その結果、プレイヤー\(1\)は自身が選んだ\(a\)に等しい利得を得るということです。このゲームには純粋戦略ナッシュ均衡が存在しないことを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】