教材一覧
教材一覧
教材検索

完備情報の静学ゲーム

ナッシュ均衡と支配される戦略の逐次消去の関係

目次

Twitter
Mailで保存

最適反応と戦略どうしの支配関係

戦略型ゲーム\(G\)において、プレイヤー\(i\in I\)の純粋戦略\(s_{i}^{\ast }\in S_{i}\)が他のプレイヤーたちの何らかの純粋戦略の組\(s_{-i}\in S_{-i}\)に対する広義の最適反応である場合、すなわち、\begin{equation}\exists s_{-i}\in S_{-i},\ \forall s_{i}\in S_{i}:u_{i}\left( s_{i}^{\ast
},s_{-i}\right) \geq u_{i}\left( s_{i},s_{-i}\right) \quad \cdots (1)
\end{equation}が成り立つ場合、この\(s_{i}^{\ast }\)は自身のいかなる純粋戦略によっても狭義支配されません。実際、\(s_{i}^{\ast }\)を狭義支配する純粋戦略\(s_{i}\)が存在するものと仮定すると、狭義支配の定義より、\begin{equation*}\forall s_{-i}\in S_{i}:u_{i}\left( s_{i},s_{-i}\right) >u_{i}\left(
s_{i}^{\ast },s_{-i}\right)
\end{equation*}が成り立ちますが、これは\(\left( 1\right) \)と矛盾だからです。

命題(広義の最適反応は狭義支配されない)
戦略型ゲーム\(G\)において、プレイヤー\(i\in I\)の純粋戦略\(s_{i}^{\ast }\in S_{i}\)が他のプレイヤーたちの何らかの純粋戦略の組\(s_{-i}\in S_{-i}\)に対する広義の最適反応であるならば、\(s_{i}\)は自身の他の任意の純粋戦略によって狭義支配されない。

混合戦略に関しても同様の主張が成り立ちます。

命題(広義の最適反応は狭義支配されない)
戦略型ゲーム\(G\)の混合拡張\(G\)において、プレイヤー\(i\in I\)の混合戦略\(\sigma _{i}^{\ast }\in \Delta \left( S_{i}\right) \)が他のプレイヤーたちの何らかの混合戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に対する広義の最適反応であるならば、\(\sigma _{i}\)は自身の他の任意の混合戦略によって狭義支配されない。
証明

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

広義の最適反応は狭義支配されないことが明らかになりましたが、別の戦略によって広義支配されることはあります。以下の例より明らかです。

例(広義の最適反応が広義支配されることはある)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。

$$\begin{array}{|c|c|c|}\hline
1/2 & L & R \\ \hline
T & 1^{\ast },1^{\ast } & 0^{\ast },0 \\ \hline
B & 0,0^{\ast } & 0^{\ast },0^{\ast } \\ \hline
\end{array}$$

表:利得行列

図にはプレイヤーが広義の最適反応を選んだ場合に得られる利得に\(\ast \)を記してあります。図より、プレイヤー\(1\)の純粋戦略\(B\)はプレイヤー\(2\)の純粋戦略\(R\)に対する広義の最適反応の1つです。その一方で、プレイヤー\(1\)の純粋戦略\(T\)は広義支配戦略であるため、\(B\)は\(T\)によって広義支配されます。

広義の最適反応は狭義支配されることはない一方で、広義支配される可能性があることが明らかになりました。一方、狭義の最適反応は広義支配される可能性はないため、狭義支配される可能性もありません。

命題(広義の最適反応は支配されない)
戦略型ゲーム\(G\)において、プレイヤー\(i\in I\)の純粋戦略\(s_{i}^{\ast }\in S_{i}\)が他のプレイヤーたちの何らかの純粋戦略の組\(s_{-i}\in S_{-i}\)に対する狭義の最適反応であるならば、\(s_{i}\)は自身の他の任意の純粋戦略によって広義支配されず、したがって狭義支配もされない。
証明

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

混合戦略に関しても同様の主張が成り立ちます。

命題(狭義の最適反応は支配されない)
戦略型ゲーム\(G\)の混合拡張\(G\)において、プレイヤー\(i\in I\)の混合戦略\(\sigma _{i}^{\ast }\in \Delta \left( S_{i}\right) \)が他のプレイヤーたちの何らかの混合戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に対する狭義の最適反応であるならば、\(\sigma _{i}\)は自身の他の任意の混合戦略によって広義支配されず、したがって狭義支配もされない。
証明

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

 

ナッシュ均衡と戦略の支配関係

繰り返しになりますが、広義の最適反応は狭義支配されません。以上の事実に加え、広義の純粋戦略ナッシュ均衡は広義の最適反応の組として定義されることを踏まえると以下を得ます。

命題(広義の純粋戦略ナッシュ均衡は狭義支配される戦略を含まない)
戦略型ゲーム\(G\)において、純粋戦略の組\(s_{I}^{\ast}\in S_{I}\)が広義の純粋戦略ナッシュ均衡であるならば、任意のプレイヤー\(i\in I\)について、その均衡戦略\(s_{i}^{\ast }\in S_{i}\)は自身の他の任意の純粋戦略によって狭義支配されない。

広義の混合戦略ナッシュ均衡についても同様です。

命題(広義の混合戦略ナッシュ均衡は狭義支配される戦略を含まない)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、混合戦略の組\(\sigma _{I}^{\ast }\in \Delta\left( S_{I}\right) \)が広義の混合戦略ナッシュ均衡であるならば、任意のプレイヤー\(i\in I\)について、その均衡戦略\(\sigma _{i}^{\ast}\in \Delta \left( S_{i}\right) \)は自身の他の任意の混合戦略によって狭義支配されない。

繰り返しになりますが、広義の最適反応は狭義支配されない一方で、別の戦略によって広義支配されることはあります。したがって、広義のナッシュ均衡を構成する戦略が広義支配される事態は起こり得ます。以下の例より明らかです。

例(広義のナッシュ均衡の最適戦略が広義支配されることはある)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。

$$\begin{array}{|c|c|c|}\hline
1/2 & L & R \\ \hline
T & 1^{\ast },1^{\ast } & 0^{\ast },0 \\ \hline
B & 0,0^{\ast } & 0^{\ast },0^{\ast } \\ \hline
\end{array}$$

表:利得行列

図にはプレイヤーが広義の最適反応を選んだ場合に得られる利得に\(\ast \)を記してあります。図より、このゲームには2つの広義の純粋戦略ナッシュ均衡\(\left( T,L\right) ,\left( B,R\right) \)が存在します。その中でも\(\left( B,R\right) \)に注目すると、プレイヤー\(1\)の最適戦略である\(B\)は自身のもう一方の純粋戦略\(T\)によって広義支配されます。

繰り返しになりますが、狭義の最適反応は広義支配される可能性はないため、狭義支配される可能性もありません。以上の事実に加え、狭義の純粋戦略ナッシュ均衡は狭義の最適反応の組として定義されることを踏まえると以下を得ます。

命題(狭義の純粋戦略ナッシュ均衡は支配される戦略を含まない)
戦略型ゲーム\(G\)において、純粋戦略の組\(s_{I}^{\ast}\in S_{I}\)が狭義の純粋戦略ナッシュ均衡であるならば、任意のプレイヤー\(i\in I\)について、その均衡戦略\(s_{i}^{\ast }\in S_{i}\)は自身の他の任意の純粋戦略によって広義支配されず、したがって狭義支配もされない。

狭義の混合戦略ナッシュ均衡についても同様です。

命題(狭義の混合戦略ナッシュ均衡は支配される戦略を含まない)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、混合戦略の組\(\sigma _{I}^{\ast }\in \Delta\left( S_{I}\right) \)が狭義の混合戦略ナッシュ均衡であるならば、任意のプレイヤー\(i\in I\)について、その均衡戦略\(\sigma _{i}^{\ast}\in \Delta \left( S_{i}\right) \)は自身の他の任意の混合戦略によって広義支配されず、したがって狭義支配もされない。

 

ナッシュ均衡と支配される戦略の逐次消去

戦略型ゲーム\(G\)に広義の純粋戦略ナッシュ均衡\(s_{I}^{\ast }\in S_{I}\)が存在するものとします。先に示したように、任意のプレイヤー\(i\in I\)について、\(s_{I}^{\ast }\)を構成する最適戦略\(s_{i}^{\ast }\)は自身の他の任意の純粋戦略によって狭義支配されません。したがって、このゲーム\(G\)に対して純粋戦略によって狭義支配される戦略の逐次消去を適用した場合、\(s_{I}^{\ast}\)を構成する任意の最適戦略は消去されないはずです。したがって、このゲームが\(G\)が逐次消去によって解けるかどうかとは関係なく、その結果の中には必ず\(s_{I}^{\ast }\)が含まれることが保証されます。

命題(広義のナッシュ均衡と狭義支配される戦略の逐次消去)
戦略型ゲーム\(G\)に広義の純粋戦略ナッシュ均衡\(s_{I}^{\ast }\in S_{I}\)が存在するならば、純粋戦略によって狭義支配される戦略の逐次消去の結果の中に\(s_{I}^{\ast }\)が含まれる。
証明

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

アルゴリズムを混合戦略によって狭義支配される戦略の逐次消去に拡大した場合にも同様の結論が得られます。

命題(広義のナッシュ均衡と狭義支配される戦略の逐次消去)
戦略型ゲーム\(G\)の混合拡張\(G\)に広義の混合戦略ナッシュ均衡であるような純粋戦略の組\(s_{I}^{\ast }\in S_{I}\)が存在するならば、混合戦略によって狭義支配される戦略の逐次消去の結果の中に\(s_{I}^{\ast }\)が含まれる。
証明

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

戦略型ゲームに広義の純粋戦略ナッシュ均衡が存在する場合、それは狭義支配される戦略の逐次消去によって消去されずに最後まで残ることが明らかになりました。ただ、ゲームは逐次消去によって解けるとは限らず、最終的に複数の戦略の組が残る場合もあります。そのような場合、先の命題より、残された戦略の組の中にはナッシュ均衡が必ず含まれますが、その一方で、ナッシュ均衡ではないような戦略の組が残る場合もあります。以下の例より明らかです。

例(広義のナッシュ均衡と狭義支配される戦略の逐次消去)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。

$$\begin{array}{|c|c|c|c|}\hline
1/2 & L & C & R \\ \hline
T & 0,4^{\ast } & 4^{\ast },0 & 5,3 \\ \hline
M & 4^{\ast },0 & 0,4^{\ast } & 5,3 \\ \hline
B & 3,5 & 3,5 & 6^{\ast },6^{\ast } \\ \hline
\end{array}$$

表:利得行列

図にはプレイヤーが広義の最適反応を選んだ場合に得られる利得に\(\ast \)を記してあります。図より、純粋戦略の組\(\left( B,R\right) \)が広義の純粋戦略ナッシュ均衡である一方、それ以外の任意の純粋戦略の組は広義の純粋戦略ナッシュ均衡ではありません。一方、任意のプレイヤーは広義支配される純粋戦略を持たないため、狭義支配される戦略の逐次消去を適用するとすべての純粋戦略の組が消去されずに残ります。

戦略型ゲームに広義の純粋戦略ナッシュ均衡が存在する場合、それは狭義支配される戦略の逐次消去によって消去されずに最後まで残りますが、その一方で、ナッシュ均衡とは異なる戦略の組もまた消去されずに場合もあることが明らかになりました。一方、そのゲームが狭義支配される戦略の逐次消去によって解ける場合、最終的に残るのは純粋戦略の1つの組だけですが、それは広義の純粋戦略ナッシュ均衡であることが保証されます。しかも、それはゲームにおける唯一の広義の純粋戦略ナッシュ均衡です。

命題(純粋戦略によって狭義支配される逐次消去と広義の純粋戦略ナッシュ均衡の関係)
戦略型ゲーム\(G\)が有限ゲームであるとともに、純粋戦略によって狭義支配される戦略の逐次消去によって解くことができる場合、その解\(s_{I}^{\ast }\in S_{I}\)は唯一の広義の純粋戦略ナッシュ均衡である。
証明

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

次回はナッシュ均衡と支配戦略均衡の関係について解説します。

Twitter
Mailで保存

質問とコメント