後ろ向き帰納法（バックワードインダクション）による純粋戦略部分ゲーム完全均衡の特定

後ろ向き帰納法（バックワード・インダクション）

問題としている戦略的状況が完備情報の動学ゲームであるとともに、それが展開型ゲーム\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 \)そのものは初期点\(x_{0}\)から始まる部分ゲーム\(\Gamma\left( x_{0}\right) \)と一致するため、部分ゲーム完全均衡\(s_{I}^{\ast }\)は\(\Gamma \left( x_{0}\right) \)すなわち\(\Gamma \)に対しても純粋戦略ナッシュ均衡を導きます。以上の事実は、\(\Gamma \)の部分ゲーム完全均衡は必ず\(\Gamma \)の純粋戦略ナッシュ均衡でもあることを意味します。つまり、\(\Gamma \)の純粋戦略ナッシュ均衡だけが\(\Gamma \)の部分ゲーム完全均衡になり得るため、\(\Gamma \)の部分ゲーム完全均衡を特定する際の基本方針としては、\(\Gamma \)の純粋戦略ナッシュ均衡をすべて特定した上で、その中でも、\(\Gamma \)の任意の部分ゲームに対して純粋戦略ナッシュ均衡を導くようなものを探すことになります。一方、展開型ゲーム\(\Gamma \)が有限な完全情報ゲームである場合には、後ろ向き帰納法と呼ばれるアルゴリズムを利用することにより、純粋戦略部分ゲーム完全均衡を容易に特定できます。まずは具体例を提示した上で、後に議論を一般化します。

例（後ろ向き帰納法）

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

プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。また、すべての情報集合が1点集合であるため\(\Gamma \)は完全情報ゲームです。したがって、\(\Gamma \)には広義の純粋戦略部分ゲーム完全均衡が存在します。プレイヤー\(1\)の純粋戦略集合は、\begin{eqnarray*}S_{1} &=&A\left( \left\{ x_{0}\right\} \right) \times A\left( \left\{
x_{2}\right\} \right) \times A\left( \left\{ x_{3}\right\} \right) \\
&=&\left\{ a_{11},a_{12}\right\} \times \left\{ a_{13},a_{14}\right\} \times
\left\{ a_{15},a_{16}\right\} \\
&=&\left\{ \left( a_{11},a_{13},a_{15}\right) ,\cdots ,\left(
a_{12},a_{14},a_{16}\right) \right\}
\end{eqnarray*}であるため、合計\(2\times2\times 2=8\)個の純粋戦略が存在します。プレイヤー\(2\)の純粋戦略集合は、\begin{eqnarray*}S_{2} &=&A\left( \left\{ x_{1}\right\} \right) \\
&=&\left\{ \left( a_{21}\right) ,\left( a_{22}\right) \right\}
\end{eqnarray*}であるため、合計\(2\)個の純粋戦略が存在します。したがって、\(\Gamma \)の戦略型\(G\left( \Gamma \right) \)を利得行列として表現するためには\(8\times 2\)行列が必要であり、そのような行列から均衡を特定する作業は煩雑です。そこで、以下の手法を用います。\(\Gamma \)の部分ゲームの中でも、初期点\(x_{0}\)から最も離れた場所にある手番\(x_{3}\)を初期点とする部分ゲーム\(\Gamma\left( x_{3}\right) \)に注目します。これはプレイヤー\(1\)だけをプレイヤーとする展開型ゲームであり、そこでの純粋戦略ナッシュ均衡は\(\left(a_{16}\right) \)です。部分ゲーム\(\Gamma \left( x_{3}\right) \)とそこでの均衡\(\left( a_{16}\right) \)が与えられれば\(\Gamma \)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{1}=\Gamma \left( x_{3}|\left( a_{16}\right) \right)
\end{equation*}で表記します。これは以下のゲームの木として表現される展開型ゲームです。

\(\Gamma _{1}\)の部分ゲームの中でも、初期点\(x_{0}\)から最も離れた場所にある手番\(x_{2}\)を初期点とする部分ゲーム\(\Gamma _{1}\left(x_{2}\right) \)に注目します。これはプレイヤー\(1\)だけをプレイヤーとする展開型ゲームであり、そこでの純粋戦略ナッシュ均衡は\(\left(a_{13}\right) \)です。部分ゲーム\(\Gamma _{1}\left( x_{3}\right) \)とそこでの均衡\(\left( a_{13}\right) \)が与えられれば\(\Gamma _{1}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{2}=\Gamma _{1}\left( x_{2}|\left( a_{13}\right) \right)
\end{equation*}で表記します。これは以下のゲームの木として表現される展開型ゲームです。

\(\Gamma _{2}\)の部分ゲームの中でも、初期点\(x_{0}\)から最も離れた場所にある手番\(x_{1}\)を初期点とする部分ゲーム\(\Gamma _{2}\left(x_{1}\right) \)に注目します。これはプレイヤー\(2\)だけをプレイヤーとする展開型ゲームであり、そこでの純粋戦略ナッシュ均衡は\(\left(a_{22}\right) \)です。部分ゲーム\(\Gamma _{2}\left( x_{1}\right) \)とそこでの均衡\(\left( a_{22}\right) \)が与えられれば\(\Gamma _{2}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{3}=\Gamma _{2}\left( x_{1}|\left( a_{22}\right) \right)
\end{equation*}で表記します。これは以下のゲームの木として表現される展開型ゲームです。

\(\Gamma _{3}\)は自身以外の部分ゲームを持たないため、最後に、\(\Gamma _{3}\)の純粋戦略ナッシュ均衡を特定します。これはプレイヤー\(\quad 1\)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{3}\)の純粋戦略ナッシュ均衡は\(\left( a_{12}\right) \)です。さて、一連のプロセスにおいて導出したそれぞれの部分ゲームにおける純粋戦略ナッシュ均衡を改めて列挙すると、\begin{equation*}\left( a_{12}\right) ,\left( a_{22}\right) ,\left( a_{13}\right) ,\left(
a_{16}\right)
\end{equation*}を得ますが、これらを合成することにより、もとのゲーム\(\Gamma \)におけるプレイヤー\(1\)の純粋戦略\begin{eqnarray*}s_{1} &=&\left( s_{1}\left( \left\{ x_{0}\right\} \right) ,s_{1}\left(
\left\{ x_{2}\right\} \right) ,s_{1}\left( \left\{ x_{3}\right\} \right)
\right) \\
&=&\left( a_{12},a_{13},a_{16}\right)
\end{eqnarray*}と、プレイヤー\(2\)の純粋戦略\begin{eqnarray*}s_{2} &=&\left( s_{2}\left( \left\{ x_{1}\right\} \right) \right) \\
&=&\left( a_{22}\right)
\end{eqnarray*}が得られます。これらの組\begin{equation*}
\left( s_{1},s_{2}\right) =\left( \left( a_{12},a_{13},a_{16}\right) ,\left(
a_{22}\right) \right)
\end{equation*}をもとのゲーム\(\Gamma \)の純粋戦略部分ゲーム完全均衡です（演習問題）。

後ろ向き帰納法のフォーマルな定義

後ろ向き帰納法をフォーマルな形で定義します。

問題としている戦略的状況が完備情報の動学ゲームであるとともに、それが展開型ゲーム\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*}として記述されているものとします。ただし、\(\Gamma \)は有限な完全情報ゲームであるものとします。この場合、\(\Gamma \)には広義の純粋戦略部分ゲーム完全均衡が存在することが保証されます。加えて、それぞれのプレイヤー\(i\in I\)の利得関数\(u_{i}:Z\rightarrow \mathbb{R} \)は以下の条件\begin{equation*}\forall z,z^{\prime }\in Z:\left[ z\not=z^{\prime }\Rightarrow u_{i}\left(
z\right) \not=u_{i}\left( z^{\prime }\right) \right] \end{equation*}を満たすものとします。つまり、プレイヤーは異なる頂点からは異なる利得を得る状況を想定するということです。この仮定は、後ろ向き帰納法が常に一意的な結果を導くことを保証するために必要です。

仮定より\(\Gamma \)は有限ゲームであるため、ノード集合\(X\)は有限集合です。したがって手番集合\(X\backslash Z\)もまた有限集合です。手番の個数は\(n+1\)であるものとします。つまり、\begin{equation*}X\backslash Z=\left\{ x_{0},x_{1},\cdots ,x_{n}\right\}
\end{equation*}です。初期点\(x_{0}\)から手番\(x_{k}\)までの経路に存在する枝の本数を手番\(x_{k}\)までの経路の長さ（length）と呼ぶこととします。

便宜的に、与えられた展開型ゲーム\(\Gamma \)を初期ゲームと呼び、これを、\begin{equation*}\Gamma _{0}=\Gamma
\end{equation*}で表記します。初期ゲーム\(\Gamma _{0}\)において初期点\(x_{0}\)から最長の経路を持つ手番\(x_{n}\)を選び、それを初期点とする部分ゲーム\(\Gamma _{0}\left(x_{n}\right) \)に注目します。\(x_{n}\)は頂点の直前にある手番であり、\(\Gamma _{0}\left(x_{n}\right) \)はプレイヤー\(i\left(\left\{ x_{n}\right\} \right) \)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{0}\left(x_{n}\right) \)における純粋戦略ナッシュ均衡を、\begin{equation*}\left( s^{0}\right) ^{\ast x_{n}}
\end{equation*}で表記します。部分ゲーム\(\Gamma _{0}\left( x_{n}\right) \)とそこでの均衡\(\left( s^{0}\right) ^{\ast x_{n}}\)が与えられれば初期ゲーム\(\Gamma _{0}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{1}=\Gamma _{0}\left( x_{n}|\left( s^{0}\right) ^{\ast x_{n}}\right)
\end{equation*}で表記します。これを便宜的に第\(\mathbf{1}\)期のゲームと呼びます。

第1期のゲーム\(\Gamma _{1}\)において初期点\(x_{0}\)から最長の経路を持つ手番\(x_{n-1}\)を選び、それを初期点とする部分ゲーム\(\Gamma _{1}\left( x_{n-1}\right) \)に注目します。\(x_{n-1}\)は頂点の直前にある手番であり、\(\Gamma _{1}\left( x_{n-1}\right) \)はプレイヤー\(i\left( \left\{ x_{n-1}\right\} \right) \)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{1}\left( x_{n-1}\right) \)における純粋戦略ナッシュ均衡を、\begin{equation*}\left( s^{1}\right) ^{\ast x_{n-1}}
\end{equation*}で表記します。部分ゲーム\(\Gamma _{1}\left( x_{n-1}\right) \)とそこでの均衡\(\left( s^{1}\right) ^{\ast x_{n-1}}\)が与えられれば第1期のゲーム\(\Gamma _{1}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{2}=\Gamma _{1}\left( x_{n-1}|\left( s^{1}\right) ^{\ast
x_{n-1}}\right)
\end{equation*}で表記します。これを便宜的に第\(\mathbf{2}\)期のゲームと呼びます。

同様のプロセスを繰り返して第\(k-1\)期のゲーム\begin{equation*}\Gamma _{k-1}=\Gamma _{k-2}\left( x_{n-k+2}|\left( s^{k-2}\right) ^{\ast
x_{n-k+2}}\right)
\end{equation*}まで定まった時、\(\Gamma_{k-1}\)において初期点\(x_{0}\)から最長の経路を持つ手番\(x_{n-k+1}\)を選び、それを初期点とする部分ゲーム\(\Gamma _{k-1}\left( x_{n-k+1}\right) \)に注目します。\(x_{n-k+1}\)は頂点の直前にある手番であり、\(\Gamma _{k-1}\left(x_{n-k+1}\right) \)はプレイヤー\(i\left(\left\{ x_{n-k+1}\right\} \right) \)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{k-1}\left(x_{n-k+1}\right) \)における純粋戦略ナッシュ均衡を\(\left(s^{k-1}\right) ^{\ast x_{n-k+1}}\)で表記します。部分ゲーム\(\Gamma _{k-1}\left(x_{n-k+1}\right) \)とそこでの均衡\(\left( s^{k-1}\right) ^{\ast x_{n-k+1}}\)が与えられれば第\(k-1\)期のゲーム\(\Gamma _{k-1}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{k}=\Gamma _{k-1}\left( x_{n-k+1}|\left( s^{k-1}\right) ^{\ast
x_{n-k+1}}\right)
\end{equation*}で表記します。これを便宜的に第\(k\)期のゲームと呼びます。

最終的に、第\(n\)期のゲーム\begin{equation*}\Gamma _{n}=\Gamma _{n-1}\left( x_{1}|\left( s^{n-1}\right) ^{\ast
x_{1}}\right)
\end{equation*}が得られますが、これはプレイヤー\(i\left( \left\{x_{0}\right\} \right) \)だけをプレイヤーとする展開型ゲームであり、自身以外に部分ゲームを持ちません。\(\Gamma _{n}\)における純粋戦略ナッシュ均衡を\(\left( s^{n}\right) ^{\ast x_{0}}\)で表記します。

後ろ向き帰納法（backward induction）とは、与えられた展開型ゲーム\(\Gamma \)を、\begin{equation*}\Gamma =\Gamma _{0}\rightarrow \Gamma _{1}\rightarrow \Gamma _{2}\rightarrow
\cdots \rightarrow \Gamma _{n-1}\rightarrow \Gamma _{n}
\end{equation*}と縮約していく中で、各期のゲーム\(\Gamma _{k}\)の部分ゲーム\(\Gamma _{k}\left( x_{n-k}\right) \)の純粋戦略ナッシュ均衡\begin{equation}\left( s^{k}\right) ^{\ast x_{n-k}}\quad \left( k=0,1,\cdots ,n\right)
\quad \cdots (1)
\end{equation}を導出するプロセスとして定義されます。プレイヤーが異なる頂点から異なる利得を得る状況を想定しているため、各期のゲーム\(\Gamma _{k}\)の部分ゲーム\(\Gamma _{k}\left( x_{n-k}\right) \)に純粋戦略ナッシュ均衡\(\left(s^{k}\right) ^{\ast x_{n-k}}\)が1つずつ定まることが保証されます。その結果、後ろ向き帰納法は必ず完遂するとともに、その結果\(\left( 1\right) \)は一意的に定まります。

後ろ向き帰納法の結果\(\left( 1\right) \)はもとの展開型ゲーム\(\Gamma \)のそれぞれの情報集合\(\left\{ x_{n-k}\right\} \)に対して、そこで意思決定を行うプレイヤー\(i\left( \left\{ x_{n-k}\right\} \right) \)が選択すべき行動\(\left( s^{k}\right) ^{\ast x_{n-k}}\)を1つずつ指定しています。そこで、もとのゲーム\(\Gamma \)における純粋戦略ナッシュ均衡の組\(s_{I}^{\ast }\)を、\begin{equation*}\forall k\in \left\{ 0,1,\cdots ,n\right\} :s_{i\left( \left\{
x_{n-k}\right\} \right) }^{\ast }\left( \left\{ x_{n-k}\right\} \right)
=\left( s^{k}\right) ^{\ast x_{n-k}}
\end{equation*}を満たすものとして定義すれば、これはもとのゲーム\(\Gamma \)における唯一の広義の純粋戦略部分ゲーム完全均衡になることが保証されます。

後ろ向き帰納法において解が一意的に定まらない場合

先の命題では、展開型ゲーム\(\Gamma \)が有限な完全情報ゲームであるとともに、任意のプレイヤー\(i\in I\)の利得関数\(u_{i}:Z\rightarrow \mathbb{R} \)が以下の条件\begin{equation*}\forall z,z^{\prime }\in Z:\left[ z\not=z^{\prime }\Rightarrow u_{i}\left(
z\right) \not=u_{i}\left( z^{\prime }\right) \right] \end{equation*}を満たすことを仮定しました。つまり、プレイヤーは異なる頂点からは異なる利得を得る状況を想定するということです。この仮定を認める場合、\(\Gamma \)に後ろ向き帰納法を適用すると、各期のゲーム\(\Gamma _{k}\)の部分ゲーム\(\Gamma _{k}\left( x_{n-k}\right) \)における純粋戦略ナッシュ均衡\(\left( s^{k}\right) ^{\ast x_{n-k}}\)が一意的に定まることが保証されるため、後ろ向き帰納法の結果も一意的に定まります。逆に、先の仮定を認めない場合、何らかの期のゲーム\(\Gamma _{k}\)の部分ゲーム\(\Gamma_{k}\left( x_{n-k}\right) \)において、そこでの純粋戦略ナッシュ均衡\(\left( s^{k}\right) ^{\ast x_{n-k}}\)が一意的に定まらない事態が起こり得ます。以下が具体例です。

例（後ろ向き帰納法）

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

プレイヤーの人数とノードの個数は有限であるため\(\Gamma \)は有限ゲームです。また、すべての情報集合が1点集合であるため\(\Gamma \)は完全情報ゲームです。したがって、\(\Gamma \)には広義の純粋戦略部分ゲーム完全均衡が存在します。初期ゲーム\(\Gamma _{0}=\Gamma \)の部分ゲームの中でも、初期点\(x_{0}\)から最も離れた場所にある手番\(x_{3}\)を初期点とする部分ゲーム\(\Gamma _{0}\left( x_{3}\right) \)に注目します。\(\Gamma _{0}\left( x_{3}\right) \)における純粋戦略ナッシュ均衡として\(\left(a_{15}\right) \)と\(\left( a_{16}\right) \)の2つが存在するため、プロセスを先に進めるためにはどちらか一方を選ぶ必要があります。まずは\(\left( a_{15}\right) \)を選んだ場合について考えます。この場合、部分ゲーム\(\Gamma \left( x_{3}\right) \)とそこでの均衡\(\left(a_{15}\right) \)が与えられれば\(\Gamma _{0}\)の縮約ゲーム\begin{equation*}\Gamma _{1}=\Gamma _{0}\left( x_{3}|\left( a_{15}\right) \right)
\end{equation*}が得られます。\(\Gamma _{1}\)の部分ゲーム\(\Gamma _{1}\left( x_{2}\right) \)における純粋戦略ナッシュ均衡は\(\left( a_{13}\right) \)です。すると\(\Gamma _{1}\)の縮約ゲーム\begin{equation*}\Gamma _{2}=\Gamma _{1}\left( x_{2}|\left( a_{13}\right) \right)
\end{equation*}が得られます。\(\Gamma _{2}\)の部分ゲーム\(\Gamma _{1}\left( x_{1}\right) \)における純粋戦略ナッシュ均衡は\(\left( a_{22}\right) \)です。すると\(\Gamma _{2}\)の縮約ゲーム\begin{equation*}\Gamma _{3}=\Gamma _{2}\left( x_{1}|\left( a_{22}\right) \right)
\end{equation*}が得られます。\(\Gamma _{3}\)の純粋戦略ナッシュ均衡は\(\left( a_{12}\right) \)です。得られた均衡を列挙すると、\begin{equation*}\left( a_{12}\right) ,\left( a_{22}\right) ,\left( a_{13}\right) ,\left(
a_{15}\right)
\end{equation*}となるため、以下の純粋戦略の組\begin{equation}
\left( s_{1},s_{2}\right) =\left( \left( a_{12},a_{13},a_{15}\right) ,\left(
a_{22}\right) \right) \quad \cdots (1)
\end{equation}が得られます。続いて、\(\left( a_{16}\right) \)を選んだ場合について考えます。この場合、部分ゲーム\(\Gamma \left( x_{3}\right) \)とそこでの均衡\(\left( a_{16}\right) \)が与えられれば\(\Gamma _{0}\)の縮約ゲーム\begin{equation*}\Gamma _{1}=\Gamma _{0}\left( x_{3}|\left( a_{16}\right) \right)
\end{equation*}が得られます。\(\Gamma _{1}\)の部分ゲーム\(\Gamma _{1}\left( x_{2}\right) \)における純粋戦略ナッシュ均衡は\(\left( a_{13}\right) \)です。すると\(\Gamma _{1}\)の縮約ゲーム\begin{equation*}\Gamma _{2}=\Gamma _{1}\left( x_{2}|\left( a_{13}\right) \right)
\end{equation*}が得られます。\(\Gamma _{2}\)の部分ゲーム\(\Gamma _{1}\left( x_{1}\right) \)における純粋戦略ナッシュ均衡は\(\left( a_{21}\right) \)です。すると\(\Gamma _{2}\)の縮約ゲーム\begin{equation*}\Gamma _{3}=\Gamma _{2}\left( x_{1}|\left( a_{21}\right) \right)
\end{equation*}が得られます。\(\Gamma _{3}\)の純粋戦略ナッシュ均衡は\(\left( a_{11}\right) \)です。得られた均衡を列挙すると、\begin{equation*}\left( a_{11}\right) ,\left( a_{21}\right) ,\left( a_{13}\right) ,\left(
a_{16}\right)
\end{equation*}となるため、以下の純粋戦略の組\begin{equation}
\left( s_{1}^{\prime },s_{2}^{\prime }\right) =\left( \left(
a_{11},a_{13},a_{16}\right) ,\left( a_{21}\right) \right) \quad \cdots (2)
\end{equation}が得られます。2つの結果が\(\left( 1\right) ,\left( 2\right) \)が得られましたが、これらはともに、もとのゲーム\(\Gamma \)の純粋戦略部分ゲーム完全均衡です（演習問題）。

以上を踏まえた上で、後ろ向き帰納法を以下の形へ修正します。

問題としている戦略的状況が完備情報の動学ゲームであるとともに、それが展開型ゲーム\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*}として記述されているものとします。ただし、\(\Gamma \)は有限な完全情報ゲームであるものとします。この場合、\(\Gamma \)には広義の純粋戦略部分ゲーム完全均衡が存在することが保証されます
仮定より\(\Gamma \)は有限ゲームであるため、ノード集合\(X\)は有限集合です。したがって手番集合\(X\backslash Z\)もまた有限集合です。手番の個数は\(n+1\)であるものとします。つまり、\begin{equation*}X\backslash Z=\left\{ x_{0},x_{1},\cdots ,x_{n}\right\}
\end{equation*}です。初期点\(x_{0}\)から手番\(x_{k}\)までの経路に存在する枝の本数を手番\(x_{k}\)までの経路の長さ（length）と呼ぶこととします。

便宜的に、与えられた展開型ゲーム\(\Gamma \)を初期ゲームと呼び、これを、\begin{equation*}\Gamma _{0}=\Gamma
\end{equation*}で表記します。初期ゲーム\(\Gamma _{0}\)において初期点\(x_{0}\)から最長の経路を持つ手番\(x_{n}\)を選び、それを初期点とする部分ゲーム\(\Gamma _{0}\left(x_{n}\right) \)に注目します。\(x_{n}\)は頂点の直前にある手番であり、\(\Gamma _{0}\left(x_{n}\right) \)はプレイヤー\(i\left(\left\{ x_{n}\right\} \right) \)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{0}\left(x_{n}\right) \)における純粋戦略ナッシュ均衡を1つ任意に選び、それを、\begin{equation*}\left( s^{0}\right) ^{\ast x_{n}}
\end{equation*}で表記します。部分ゲーム\(\Gamma _{0}\left( x_{n}\right) \)とそこでの均衡\(\left( s^{0}\right) ^{\ast x_{n}}\)が与えられれば初期ゲーム\(\Gamma _{0}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{1}=\Gamma _{0}\left( x_{n}|\left( s^{0}\right) ^{\ast x_{n}}\right)
\end{equation*}で表記します。これを便宜的に第\(\mathbf{1}\)期のゲームと呼びます。

第1期のゲーム\(\Gamma _{1}\)において初期点\(x_{0}\)から最長の経路を持つ手番\(x_{n-1}\)を選び、それを初期点とする部分ゲーム\(\Gamma _{1}\left( x_{n-1}\right) \)に注目します。\(x_{n-1}\)は頂点の直前にある手番であり、\(\Gamma _{1}\left( x_{n-1}\right) \)はプレイヤー\(i\left( \left\{ x_{n-1}\right\} \right) \)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{1}\left( x_{n-1}\right) \)における純粋戦略ナッシュ均衡を1つ任意に選び、それを、\begin{equation*}\left( s^{1}\right) ^{\ast x_{n-1}}
\end{equation*}で表記します。部分ゲーム\(\Gamma _{1}\left( x_{n-1}\right) \)とそこでの均衡\(\left( s^{1}\right) ^{\ast x_{n-1}}\)が与えられれば第1期のゲーム\(\Gamma _{1}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{2}=\Gamma _{1}\left( x_{n-1}|\left( s^{1}\right) ^{\ast
x_{n-1}}\right)
\end{equation*}で表記します。これを便宜的に第\(\mathbf{2}\)期のゲームと呼びます。

同様のプロセスを繰り返して第\(k-1\)期のゲーム\begin{equation*}\Gamma _{k-1}=\Gamma _{k-2}\left( x_{n-k+2}|\left( s^{k-2}\right) ^{\ast
x_{n-k+2}}\right)
\end{equation*}まで定まった時、\(\Gamma_{k-1}\)において初期点\(x_{0}\)から最長の経路を持つ手番\(x_{n-k+1}\)を選び、それを初期点とする部分ゲーム\(\Gamma _{k-1}\left( x_{n-k+1}\right) \)に注目します。\(x_{n-k+1}\)は頂点の直前にある手番であり、\(\Gamma _{k-1}\left(x_{n-k+1}\right) \)はプレイヤー\(i\left(\left\{ x_{n-k+1}\right\} \right) \)だけをプレイヤーとする展開型ゲームです。\(\Gamma _{k-1}\left(x_{n-k+1}\right) \)における純粋戦略ナッシュ均衡を1つ任意に選び、それを\(\left( s^{k-1}\right) ^{\ast x_{n-k+1}}\)で表記します。部分ゲーム\(\Gamma_{k-1}\left( x_{n-k+1}\right) \)とそこでの均衡\(\left( s^{k-1}\right) ^{\ast x_{n-k+1}}\)が与えられれば第\(k-1\)期のゲーム\(\Gamma _{k-1}\)の縮約ゲームが得られるため、それを、\begin{equation*}\Gamma _{k}=\Gamma _{k-1}\left( x_{n-k+1}|\left( s^{k-1}\right) ^{\ast
x_{n-k+1}}\right)
\end{equation*}で表記します。これを便宜的に第\(k\)期のゲームと呼びます。

最終的に、第\(n\)期のゲーム\begin{equation*}\Gamma _{n}=\Gamma _{n-1}\left( x_{1}|\left( s^{n-1}\right) ^{\ast
x_{1}}\right)
\end{equation*}が得られますが、これはプレイヤー\(i\left( \left\{x_{0}\right\} \right) \)だけをプレイヤーとする展開型ゲームであり、自身以外に部分ゲームを持ちません。\(\Gamma _{n}\)における純粋戦略ナッシュ均衡を1つ任意に選び、それを\(\left( s^{n}\right) ^{\ast x_{0}}\)で表記します。

後ろ向き帰納法（backward induction）とは、与えられた展開型ゲーム\(\Gamma \)を、\begin{equation*}\Gamma =\Gamma _{0}\rightarrow \Gamma _{1}\rightarrow \Gamma _{2}\rightarrow
\cdots \rightarrow \Gamma _{n-1}\rightarrow \Gamma _{n}
\end{equation*}と縮約していく中で、各期のゲーム\(\Gamma _{k}\)の部分ゲーム\(\Gamma _{k}\left( x_{n-k}\right) \)の純粋戦略ナッシュ均衡\begin{equation}\left( s^{k}\right) ^{\ast x_{n-k}}\quad \left( k=0,1,\cdots ,n\right)
\quad \cdots (1)
\end{equation}を導出するプロセスとして定義されます。何らかの期のゲーム\(\Gamma _{k}\)の部分ゲーム\(\Gamma_{k}\left( x_{n-k}\right) \)において、そこでの純粋戦略ナッシュ均衡\(\left( s^{k}\right) ^{\ast x_{n-k}}\)が一意的に定まらない事態は起こり得るため、その中からどれを選ぶかに応じて後ろ向き帰納法の結果\(\left( 1\right) \)は変化します。

後ろ向き帰納法の結果\(\left( 1\right) \)は一意的であるとは構いませんが、その中から1つを選べば、もとの展開型ゲーム\(\Gamma \)のそれぞれの情報集合\(\left\{ x_{n-k}\right\} \)に対して、そこで意思決定を行うプレイヤー\(i\left( \left\{ x_{n-k}\right\} \right) \)が選択すべき行動\(\left( s^{k}\right) ^{\ast x_{n-k}}\)が1つずつ定まります。その上で、もとのゲーム\(\Gamma \)における純粋戦略ナッシュ均衡の組\(s_{I}^{\ast }\)を、\begin{equation*}\forall k\in \left\{ 0,1,\cdots ,n\right\} :s_{i\left( \left\{
x_{n-k}\right\} \right) }^{\ast }\left( \left\{ x_{n-k}\right\} \right)
=\left( s^{k}\right) ^{\ast x_{n-k}}
\end{equation*}を満たすものとして定義すれば、これはもとのゲーム\(\Gamma \)における唯一の広義の純粋戦略部分ゲーム完全均衡になることが保証されます。後ろ向き帰納法が複数の結果を導き得る場合、その中のどれを選んだ場合でも、同様の主張が成り立つことに注意してください。

演習問題

問題（純粋戦略部分ゲーム完全均衡）

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

本文中で明らかにしたように、このゲーム\(\Gamma \)に後ろ向き帰納法を適用すると、以下の純粋戦略の組\begin{equation*}\left( s_{1},s_{2}\right) =\left( \left( a_{12},a_{13},a_{16}\right) ,\left(
a_{22}\right) \right)
\end{equation*}が得られます。これが純粋戦略部分ゲーム完全均衡であることを、純粋戦略部分ゲーム完全均衡の定義にもとづいて確認してください。

問題（純粋戦略部分ゲーム完全均衡）

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

本文中で明らかにしたように、このゲーム\(\Gamma \)に後ろ向き帰納法を適用すると、以下の純粋戦略の組\begin{eqnarray*}\left( s_{1},s_{2}\right) &=&\left( \left( a_{12},a_{13},a_{15}\right)
,\left( a_{22}\right) \right) \\
\left( s_{1}^{\prime },s_{2}^{\prime }\right) &=&\left( \left(
a_{11},a_{13},a_{16}\right) ,\left( a_{21}\right) \right)
\end{eqnarray*}が得られます。これがともに純粋戦略部分ゲーム完全均衡であることを、純粋戦略部分ゲーム完全均衡の定義にもとづいて確認してください。