WIIS

完備情報の動学ゲーム

純粋戦略部分ゲーム完全均衡の分離と合成

目次

関連知識

Mailで保存
Xで共有

純粋戦略部分ゲーム完全均衡の分離定理

問題としている戦略的状況が完備情報の動学ゲームであり、それが展開型ゲーム\(\Gamma \)として表現されているものとします。さらに、プレイヤーたちが純粋戦略を採用する状況を想定します。ただし、展開型ゲーム\(\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 \)に純粋戦略部分ゲーム完全均衡\(s_{I}^{\ast }\in S_{I}\)が存在する状況を想定します。ゲーム\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)を任意に選んだ上で先の均衡\(s_{I}^{\ast }\)を\(\Gamma \left( x\right) \)へ制限すれば、\(\Gamma \left( x\right) \)においてプレイヤーたちが選択する純粋戦略からなる組\(s_{I}^{\ast x}\)が得られます。部分ゲーム完全均衡の定義より\(s_{I}^{\ast x}\)は\(\Gamma \left( x\right) \)における純粋戦略ナッシュ均衡ですが、実は、\(s_{I}^{\ast x}\)は\(\Gamma \left( x\right) \)における純粋戦略部分ゲーム完全均衡でもあります。つまり、展開型ゲームにおける純粋戦略部分ゲーム完全均衡は、任意の部分ゲームに対しても純粋戦略部分ゲーム完全均衡になるということです。

命題(純粋戦略部分ゲーム完全均衡と部分ゲーム)
展開型ゲーム\(\Gamma \)に広義の純粋戦略部分ゲーム完全均衡\(s_{I}^{\ast }\in S_{I}\)が存在するものとする。\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)を任意に選ぶ。このとき、\(s_{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{x}\)は\(\Gamma \left( x\right) \)における広義の純粋戦略部分ゲーム完全均衡である。
証明

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

例(純粋戦略部分ゲーム完全均衡と部分ゲーム)
以下のゲームの木によって表現される展開型ゲーム\(\Gamma \)について考えます。

図:展開型ゲーム
図:展開型ゲーム

プレイヤー\(1\)の純粋戦略集合は、\begin{eqnarray*}S_{1} &=&A\left( \left\{ x_{0}\right\} \right) \times A\left( \left\{
x_{2}\right\} \right) \\
&=&\left\{ a_{11},a_{12}\right\} \times \left\{ a_{13},a_{14}\right\} \\
&=&\left\{ \left( a_{11},a_{13}\right) ,\left( a_{11},a_{14}\right) ,\left(
a_{12},a_{13}\right) ,\left( a_{12},a_{14}\right) \right\}
\end{eqnarray*}であり、プレイヤー\(2\)の純粋戦略集合は、\begin{eqnarray*}S_{2} &=&A\left( \left\{ x_{1}\right\} \right) \\
&=&\left\{ a_{21},a_{22}\right\}
\end{eqnarray*}です。このゲーム\(\Gamma \)の純粋戦略部分ゲーム完全均衡は、\begin{equation}\left( \left( a_{11},a_{14}\right) ,a_{22}\right) \quad \cdots (1)
\end{equation}です(演習問題)。部分ゲーム\(\Gamma \left( x_{0}\right) \)は\(\Gamma \)自身であるため、\(\left( 1\right) \)の\(\Gamma \left( x_{0}\right) \)への制限は\(\left( 1\right) \)自身であり、したがって\(\left( 1\right) \)は\(\Gamma \left( x_{0}\right) \)における純粋戦略部分ゲーム完全均衡です。\(\left( 1\right) \)の部分ゲーム\(\Gamma \left( x_{1}\right) \)への制限は、\begin{equation*}\left( a_{14},a_{22}\right)
\end{equation*}ですが、これは\(\Gamma \left(x_{1}\right) \)における純粋戦略部分ゲーム完全均衡です(演習問題)。\(\left( 1\right) \)の部分ゲーム\(\Gamma \left( x_{2}\right) \)への制限は、\begin{equation*}\left( a_{14}\right)
\end{equation*}ですが、これは\(\Gamma \left(x_{2}\right) \)における純粋戦略部分ゲーム完全均衡です。他に部分ゲームは存在しません。以上の結果は先の命題の主張と整合的です。

引き続き、展開型ゲーム\(\Gamma \)に純粋戦略部分ゲーム完全均衡\(s_{I}^{\ast}\in S_{I}\)が存在する状況を想定します。部分ゲーム\(\Gamma \left( x\right) \)を任意に選びます。均衡\(s_{I}^{\ast }\)を部分ゲーム\(\Gamma \left( x\right) \)へ制限すれば\(s_{I}^{\ast x}\)が得られるため、\(\Gamma \left(x\right) \)においてそれぞれのプレイヤーが直面する期待利得を算出でき、その結果、もとのゲーム\(\Gamma \)を縮約ゲーム\(\Gamma \left( x|s_{I}^{\ast x}\right) \)へ変換できます。さらに、先の均衡\(s_{I}^{\ast }\)を縮約ゲーム\(\Gamma \left( x|s_{I}^{\ast x}\right) \)へ制限すれば\(s_{I}^{\ast x|s_{I}^{\ast x}}\)が得られますが、これは\(\Gamma \left( x|s_{I}^{\ast x}\right) \)における純粋戦略部分ゲーム完全均衡になることが保証されます。証明では展開型ゲームにおける純粋戦略ナッシュ均衡の分離定理を利用します。

命題(純粋戦略部分ゲーム完全均衡と縮約ゲーム)
展開型ゲーム\(\Gamma \)に広義の純粋戦略部分ゲーム完全均衡\(s_{I}^{\ast }\in S_{I}\)が存在するものとする。\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)を任意に選ぶ。これと\(s_{I}^{\ast }\)の\(\Gamma \left(x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{\ast x}\)から\(\Gamma \)の縮約ゲーム\(\Gamma \left( x|s_{I}^{\ast x}\right) \)を構成する。さらに、\(s_{I}^{\ast }\)の\(\Gamma \left( x|s_{I}^{\ast x}\right) \)への制限\(s_{I}^{\ast x|s_{I}^{\ast x}}\in S_{I}^{\ast x|s_{I}^{\ast x}}\)をとると、これは\(\Gamma \left(x|s_{I}^{\ast x}\right) \)における広義の純粋戦略部分ゲーム完全均衡である。
証明

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

例(純粋戦略部分ゲーム完全均衡と縮約ゲーム)
繰り返しになりますが、以下のゲームの木で表される展開型ゲーム\(\Gamma \)について考えます。

図:展開型ゲーム
図:展開型ゲーム

プレイヤー\(1\)の純粋戦略集合は、\begin{eqnarray*}S_{1} &=&A\left( \left\{ x_{0}\right\} \right) \times A\left( \left\{
x_{2}\right\} \right) \\
&=&\left\{ a_{11},a_{12}\right\} \times \left\{ a_{13},a_{14}\right\} \\
&=&\left\{ \left( a_{11},a_{13}\right) ,\left( a_{11},a_{14}\right) ,\left(
a_{12},a_{13}\right) ,\left( a_{12},a_{14}\right) \right\}
\end{eqnarray*}であり、プレイヤー\(2\)の純粋戦略集合は、\begin{eqnarray*}S_{2} &=&A\left( \left\{ x_{1}\right\} \right) \\
&=&\left\{ a_{21},a_{22}\right\}
\end{eqnarray*}です。このゲーム\(\Gamma \)の純粋戦略部分ゲーム完全均衡は、\begin{equation}\left( \left( a_{11},a_{14}\right) ,a_{22}\right) \quad \cdots (1)
\end{equation}です。\(\left( 1\right) \)を部分ゲーム\(\Gamma \left( x_{2}\right) \)に制限すると、\begin{equation*}\left( a_{14}\right)
\end{equation*}となるため、\(\Gamma \left( x_{2}\right) \)においてプレイヤー\(1\)が直面する期待利得は\(1\)であり、プレイヤー\(2\)が直面する期待利得は\(2\)となります。したがって、縮約ゲーム\(\Gamma \left( x_{2}|\left( \left( a_{11},a_{14}\right),a_{22}\right) \right) \)は以下のゲームの木として表現されます。

図:縮約ゲーム
図:縮約ゲーム

 

先の均衡\(\left( 1\right) \)を\(\Gamma \left(x_{2}|\left( \left( a_{11},a_{14}\right) ,a_{22}\right) \right) \)に制限すると、\begin{equation*}\left( a_{11},a_{22}\right)
\end{equation*}となりますが、これは\(\Gamma \left( x_{2}|\left( \left( a_{11},a_{14}\right),a_{22}\right) \right) \)における純粋戦略部分ゲーム完全均衡です(演習問題)。また、\(\left( 1\right) \)を部分ゲーム\(\Gamma \left( x_{1}\right) \)に制限すると、\begin{equation*}\left( a_{14},a_{22}\right)
\end{equation*}となるため、\(\Gamma \left( x_{1}\right) \)においてプレイヤー\(1\)が直面する期待利得は\(1\)であり、プレイヤー\(2\)が直面する期待利得は\(2\)となります。したがって、縮約ゲーム\(\Gamma \left( x_{1}|\left( \left( a_{11},a_{14}\right),a_{22}\right) \right) \)は以下のゲームの木として表現されます。

図:縮約ゲーム
図:縮約ゲーム

先の均衡\(\left( 1\right) \)を\(\Gamma \left(x_{1}|\left( \left( a_{11},a_{14}\right) ,a_{22}\right) \right) \)に制限すると、\begin{equation*}\left( a_{11}\right)
\end{equation*}となりますが、これは\(\Gamma \left( x_{1}|\left( \left( a_{11},a_{14}\right),a_{22}\right) \right) \)における純粋戦略部分ゲーム完全均衡です(演習問題)。他に部分ゲームは存在しません。以上の結果は先の命題の主張と整合的です。

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

命題(純粋戦略部分ゲーム完全均衡の分離定理)
展開型ゲーム\(\Gamma \)に広義の純粋戦略部分ゲーム完全均衡\(s_{I}^{\ast }\in S_{I}\)が存在するものとする。このとき以下が成り立つ。

  1. \(\Gamma \)の部分ゲーム\(\Gamma\left( x\right) \)を任意に選ぶ。このとき、\(s_{I}^{\ast }\)の\(\Gamma\left( x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{x}\)は\(\Gamma \left( x\right) \)における広義の純粋戦略部分ゲーム完全均衡である。
  2. \(\Gamma \)の部分ゲーム\(\Gamma\left( x\right) \)を任意に選ぶ。これと\(s_{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{\ast x}\)から\(\Gamma \)の縮約ゲーム\(\Gamma\left( x|s_{I}^{\ast x}\right) \)を構成する。さらに、\(s_{I}^{\ast }\)の\(\Gamma\left( x|s_{I}^{\ast x}\right) \)への制限\(s_{I}^{\ast x|s_{I}^{\ast x}}\in S_{I}^{\ast x|s_{I}^{\ast x}}\)をとると、これは\(\Gamma \left( x|s_{I}^{\ast x}\right) \)における広義の純粋戦略部分ゲーム完全均衡である。

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

 

純粋戦略部分ゲーム完全均衡の合成定理

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

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

命題(純粋戦略部分ゲーム完全均衡の合成定理)
展開型ゲーム\(\Gamma \)における純粋戦略の組\(s_{I}^{\ast}\in S_{I}\)に対して以下の条件をともに満たす\(\Gamma \)の部分ゲーム\(\Gamma \left( x\right) \)が存在するならば、\(s_{I}^{\ast }\)は\(\Gamma \)における広義の純粋戦略部分ゲーム完全均衡均衡である。

  1. \(s_{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{\ast x}\)は\(\Gamma \left(x\right) \)における広義の部分ゲーム完全均衡である。
  2. \(s_{I}^{\ast }\)の\(\Gamma \left( x\right) \)への制限\(s_{I}^{\ast x}\in S_{I}^{\ast x}\)から\(\Gamma \)の縮約ゲーム\(\Gamma \left( x|s_{I}^{\ast x}\right) \)を構成する。さらに、\(s_{I}^{\ast }\)の\(\Gamma \left( x|s_{I}^{\ast x}\right) \)への制限\(s_{I}^{\ast x|s_{I}^{\ast x}}\in S_{I}^{\ast x|s_{I}^{\ast x}}\)をとると、これは\(\Gamma \left( x|s_{I}^{\ast x}\right) \)における広義の部分ゲーム完全均衡である。
証明

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

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

純粋戦略部分ゲーム完全均衡を導出するアルゴリズムとして後ろ向き帰納法(backward induction)と呼ばれる手法が存在しますが、その手法の妥当性を担保するのが合成定理です。後ろ向き帰納法については場を改めて解説します。

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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