教材一覧
教材検索
STATIC GAME OF COMPLETE INFORMATION

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

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

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

戦略型ゲーム\(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}\)は唯一の広義の純粋戦略ナッシュ均衡である。
証明

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

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

囚人のジレンマ

非対称的な利得構造を持つ囚人のジレンマ

これまではプレイヤーたちが同一の利得関数を持つ囚人のジレンマについて考えてきましたが、状況を少し一般化して、プレイヤーたちが異なる利得関数を持つ場合の囚人のジレンマについて考えます。

狭義支配

戦略どうしの狭義の支配関係

プレイヤーの純粋戦略が別の純粋戦略を狭義支配することの意味、混合戦略が別の混合戦略を狭義支配することの意味などを解説します。

クールノー競争

クールノー競争(クールノー均衡)

同質財を生産する複占市場における数量競争をモデル化したゲームをクールノー競争と呼び、そこでのナッシュ均衡をクールノー均衡と呼びます。

広義支配

戦略どうしの広義の支配関係

プレイヤーの純粋戦略が別の純粋戦略を広義支配することの意味、混合戦略が別の混合戦略を広義支配することの意味などを解説します。

支配される戦略の逐次消去

狭義支配される戦略の逐次消去

与えられたゲームにおいてそれぞれのプレイヤーが何らかの戦略によって狭義支配される純粋戦略を持つ場合、それをプレイヤーの純粋戦略集合から消去することを通じてプレイヤーたちが選択し得る戦略の組を絞り込む手法を狭義支配される戦略の逐次消去と呼びます。

支配される戦略の逐次消去

広義支配される戦略の逐次消去

与えられたゲームにおいてそれぞれのプレイヤーが何らかの戦略によって広義支配される純粋戦略を持つ場合、それをプレイヤーの純粋戦略集合から消去することを通じてプレイヤーたちが選択し得る戦略の組を絞り込む手法を広義支配される戦略の逐次消去と呼びます。

支配される戦略の逐次消去

支配される戦略を消去する順番

支配される戦略の逐次消去のプロセスにおいて、戦略を消去する順番が結果に与える影響について解説します。

支配される戦略の逐次消去

支配される戦略の逐次消去と合理性

プレイヤーたちが支配される戦略の逐次消去にしたがって意思決定を行うことを保証するためには、プレイヤーの合理性が共有知識であることを仮定する必要があります。

ナッシュ均衡

広義の純粋戦略ナッシュ均衡

戦略型ゲームにおいてプレイヤーたちの純粋戦略の組に注目したときに、その組を構成する戦略がお互いに最適反応になっているならば、その組を純粋戦略ナッシュ均衡と呼びます。純粋戦略ナッシュ均衡は存在するとは限らず、存在する場合にも一意的であるとは限りません。

ナッシュ均衡

狭義の純粋戦略ナッシュ均衡

戦略型ゲームにおいてプレイヤーたちの純粋戦略の組に注目したときに、その組を構成する戦略がお互いに狭義の最適反応になっているならば、その組を狭義の純粋戦略ナッシュ均衡と呼びます。

ナッシュ均衡

広義の混合戦略ナッシュ均衡

戦略型ゲームの混合拡張においてプレイヤーたちの混合戦略の組に注目したときに、その組を構成する混合戦略がお互いに広義の最適反応になっているならば、その組を広義の混合戦略ナッシュ均衡と呼びます。

ナッシュ均衡

狭義の混合戦略ナッシュ均衡

戦略型ゲームの混合拡張においてプレイヤーたちの混合戦略の組に注目したときに、その組を構成する混合戦略がお互いに狭義の最適反応になっているならば、その組を狭義の混合戦略ナッシュ均衡と呼びます。

ナッシュ均衡

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

戦略型ゲームに支配戦略均衡が存在する場合、それはナッシュ均衡であることが保証されます。逆は成立するとは限りません。つまり、ナッシュ均衡は支配戦略均衡であるとは限りません。

ナッシュ均衡

ナッシュ均衡の正当性

合理性の仮定や期待効用仮説を採用する限りにおいて、完備情報の静学ゲームにおける均衡概念はナッシュ均衡しか存在しません。しかし、これはあくまでもゲームの分析者の立場から見たときの考え方であり、プレイヤーの視点から考えてみると話が少し複雑になります。

ナッシュ均衡

ナッシュ均衡と自己拘束的な合意

プレイヤーたちが事前交渉を行い何らかの合意に至った場合、それを強制する仕組みが存在しないにも関わらず合意が守られるのであれば、そのような合意は自己拘束的であると言われます。自己拘束的な合意は必ずナッシュ均衡である一方、その逆は成立するとは限りません。

DISCUSSION

質問とコメント

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

完備情報の静学ゲーム