純粋戦略によって強支配される戦略の逐次消去

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

純粋戦略によって強支配される戦略の逐次消去

問題としている戦略的状況が完備状況の静学ゲームであり、それが戦略型ゲーム\(G=\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in I}\right) \)として表現されているものとします。プレイヤー\(i\in I\)の純粋戦略\(s_{i}\in S_{i}\)が他の純粋戦略によって強支配されるとき、合理性の仮定のもとではプレイヤー\(i\)が\(s_{i}\)を選択しないことが保証されるため、\(s_{i}\)をプレイヤー\(i\)の選択肢から消去しても問題ありません。

以上を根拠に、与えられたゲームのそれぞれのプレイヤーに関して、何らかの純粋戦略によって強支配される純粋戦略が存在する場合、それをプレイヤーの純粋戦略集合から消去することを通じてプレイヤーたちが選択し得る戦略の組を絞り込む手法を純粋戦略によって強支配される戦略の逐次消去(iterated elimination of strategies strictly dominated by a pure strategy)と呼びます。

例(純粋戦略によって強支配される戦略の逐次消去)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。
$$\begin{array}{|c|c|c|c|}
\hline
1\diagdown 2 & L & C & R \\ \hline
U & 1,0 & 1,2 & 0,1 \\ \hline
D & 0,3 & 0,1 & 2,0 \\ \hline
\end{array}$$
表:利得行列

このゲームにおいて、プレイヤー\(1\)は純粋戦略に強支配される純粋戦略を持ちませんが、プレイヤー\(2\)については、純粋戦略\(R\)が純粋戦略\(C\)に強支配されます。したがって、プレイヤー\(2\)が合理的である限りにおいて、純粋戦略\(R\)を選びません。そのため、プレイヤー\(2\)の純粋戦略集合から\(R\)を消去することができ、その結果、以下の利得行列で表される新たな戦略型ゲームを得ます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & C \\ \hline
U & 1,0 & 1,2 \\ \hline
D & 0,3 & 0,1 \\ \hline
\end{array}$$

表:利得行列

この新たなゲームにおいて、プレイヤー\(2\)は純粋戦略によって強支配される純粋戦略を持ちませんが、プレイヤー\(1\)にとって純粋戦略\(D\)は純粋戦略\(U\)に強支配されます。したがって、プレイヤー\(1\)が合理的である限りにおいて、純粋戦略\(D\)を選びません。そのため、プレイヤー\(1\)の純粋戦略集合から\(D\)を消去することができ、その結果、以下の利得行列で表される新たな戦略型ゲームを得ます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & C \\ \hline
U & 1,0 & 1,2 \\ \hline
\end{array}$$

表:利得行列

この新たなゲームにおいて、プレイヤー\(2\)にとって純粋戦略\(L\)は純粋戦略\(C\)に強支配されます。したがって、プレイヤー\(1\)が合理的である限りにおいて、純粋戦略\(L\)を選びません。そのため、プレイヤー\(2\)の純粋戦略集合から\(L\)を消去することができ、その結果、以下の利得行列で表される新たな戦略型ゲームを得ます。
$$\begin{array}{|c|c|}
\hline
1\diagdown 2 & C \\ \hline
U & 1,2 \\ \hline
\end{array}$$

表:利得行列

これ以上は消去できないため、これが強支配される戦略の逐次消去の解です。

 

純粋戦略によって強支配される戦略の逐次消去のフォーマルな定義

戦略型ゲーム\(G=(I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in I})\)のそれぞれのプレイヤー\(i\in I\)について、純粋戦略集合の部分集合\(S_{i}^{\prime }\subset S_{i} \)を任意に選んだとき、プレイヤーたちが選択し得る純粋戦略の組からなる集合は\(S_{I}=\prod_{i\in I}S_{i}\)から\(S_{I}^{\prime }=\prod_{i\in I}S_{i}^{\prime }\)へと縮小されるため、それにあわせてプレイヤー\(i\)の利得関数\(u_{i}\)の定義域を\(S_{I}\)から\(S_{I}^{\prime }\)へ縮小する必要があります。すると新たな戦略型ゲーム\begin{equation*}
\left( I,\left\{ S_{i}^{\prime }\right\} _{i\in I},\left\{ u_{i}\right\}
_{i\in I}\right)
\end{equation*}が得られますが、これを\(G\)の制限(restriction)と呼びます。

以上で準備が整ったため、純粋戦略によって強支配される戦略の逐次消去をフォーマルな形で定義します。戦略型ゲーム\(G=(I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in I})\)が与えられたとき、それを便宜的に初期ゲームと呼びます。初期ゲーム\(G\)において、それぞれのプレイヤー\(i\in I\)の純粋戦略集合\(S_{i}\)から、純粋戦略によって強支配されるプレイヤー\(i\)の純粋戦略をすべて消去して得られる新たな純粋戦略集合を\(S_{i}^{1}\)で表します。つまり、\begin{equation*}
S_{i}^{1}=S_{i}\backslash \left\{ s_{i}\in S_{i}\ |\ \exists s_{i}^{\prime
}\in S_{i}\backslash \left\{ s_{i}\right\} :s_{i}^{\prime }\text{は}s_{i}\text{を強支配する}\right\}
\end{equation*}です。それぞれのプレイヤー\(i\)の純粋戦略集合を\(S_{i}\)から\(S_{i}^{1}\)へ縮小すると、\(G\)の制限\begin{equation*}
G_{1}=(I,\left\{ S_{i}^{1}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in I})
\end{equation*}が得られるため、これを便宜的に第\(1\)期のゲームと呼びます。

第\(1\)期のゲーム\(G_{1}\)において、それぞれのプレイヤー\(i\in I\)の純粋戦略集合\(S_{i}^{1}\)から、純粋戦略によって強支配されるプレイヤー\(i\)の純粋戦略をすべて消去して得られる新たな純粋戦略集合を\(S_{i}^{2}\)で表します。つまり、\begin{equation*}
S_{i}^{2}=S_{i}^{1}\backslash \left\{ s_{i}\in S_{i}^{1}\ |\ \exists
s_{i}^{\prime }\in S_{i}^{1}\backslash \left\{ s_{i}\right\} :s_{i}^{\prime }\text{は}s_{i}\text{を強支配する}\right\}
\end{equation*}です。それぞれのプレイヤー\(i\)の純粋戦略集合を\(S_{i}^{1}\)から\(S_{i}^{2}\)へ縮小すると、\(G_{1}\)の制限\begin{equation*}
G_{2}=(I,\left\{ S_{i}^{2}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in I})
\end{equation*}が得られるため、これを便宜的に第\(2\)期のゲームと呼びます。

同様のプロセスを繰り返して第\(t-1\)期のゲーム\begin{equation*}
G_{t-1}=(I,\left\{ S_{i}^{t-1}\right\} _{i\in I},\left\{ u_{i}\right\}
_{i\in I})
\end{equation*}まで定まった時、\(G_{t-1}\)においてそれぞれのプレイヤー\(i\in I\)の純粋戦略集合\(S_{i}^{t-1}\)から、純粋戦略によって強支配されるプレイヤー\(i\)の純粋戦略をすべて消去して得られる新たな純粋戦略集合を\(S_{i}^{t}\)で表します。つまり、\begin{equation*}
S_{i}^{t}=S_{i}^{t-1}\backslash \left\{ s_{i}\in S_{i}^{t-1}\ |\ \exists
s_{i}^{\prime }\in S_{i}^{t-1}\backslash \left\{ s_{i}\right\}
:s_{i}^{\prime }\text{は}s_{i}\text{を強支配する}\right\}
\end{equation*}です。それぞれのプレイヤー\(i\)の純粋戦略集合を\(S_{i}^{t-1}\)から\(S_{i}^{t}\)へ縮小すると、\(G_{t-1}\)の制限\begin{equation*}
G_{t}=(I,\left\{ S_{i}^{t}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in I})
\end{equation*}が得られるため、これを便宜的に第\(t\)期のゲームと呼びます。

純粋戦略によって強支配される戦略の逐次消去とは、与えられた戦略型ゲーム\(G\)を、\begin{equation*}
G\rightarrow G_{1}\rightarrow G_{2}\rightarrow \cdots \rightarrow
G_{t-1}\rightarrow G_{t}\rightarrow \cdots
\end{equation*}と縮小していくプロセスとして定義されます。このようなプロセスを続けたとき、第\(T\)期のゲーム\(G_{T}\)において、純粋戦略によって強支配される純粋戦略を持つプレイヤーが存在しなくなった場合、すなわち、\begin{equation*}
G_{T}=G_{T+1}
\end{equation*}が成り立つ場合、\(G_{T}\)を結果(outcome)と呼びます。さらに、逐次消去の結果\(G_{T}\)においてそれぞれのプレイヤーに残されている純粋戦略が1つずつである場合、すなわち、\begin{equation*}
\forall i\in I:\left\vert S_{i}^{T}\right\vert =1
\end{equation*}が成り立つ場合、ゲーム\(G\)は逐次消去によって解ける(solvable)と言い、その場合の結果\(G_{T}\)におけるプレイヤーたちの純粋戦略の組\(\left( s_{i}\right) _{i\in I}\in S_{I}^{T}\)を逐次消去による(solution)と呼びます。解が存在するとき、逐次消去の定義より、それは一意的です。

例(純粋戦略によって強支配される戦略の逐次消去)
以下の利得行列で表される戦略型ゲーム\(G\)について再び考えます。
$$\begin{array}{|c|c|c|c|}
\hline
1\diagdown 2 & L & C & R \\ \hline
U & 1,0 & 1,2 & 0,1 \\ \hline
D & 0,3 & 0,1 & 2,0 \\ \hline
\end{array}$$
表:利得行列

初期ゲーム\(G\)の純粋戦略集合は、\begin{eqnarray*}
S_{1} &=&\left\{ U,D\right\} \\
S_{2} &=&\left\{ L,C,R\right\}
\end{eqnarray*}です。初期ゲーム\(G\)において、プレイヤー\(1\)は強支配される純粋戦略を持たず、プレイヤー\(2\)の純粋戦略\(R\)が純粋戦略\(C\)によって強支配されるため、第\(1\)期のゲーム\(G_{1}\)を構成する純粋戦略集合は、\begin{eqnarray*}
S_{1}^{1} &=&\left\{ U,D\right\} \\
S_{2}^{1} &=&\left\{ L,C\right\}
\end{eqnarray*}となります。第\(1\)期のゲーム\(G_{1}\)において、プレイヤー\(1\)の純粋戦略\(D\)が純粋戦略\(U\)によって強支配される一方、プレイヤー\(2\)は強支配される純粋戦略を持ちません。ゆえに第\(2\)期のゲーム\(G_{2}\)を構成する純粋戦略集合は、\begin{eqnarray*}
S_{1}^{2} &=&\left\{ U\right\} \\
S_{2}^{2} &=&\left\{ L,C\right\}
\end{eqnarray*}となります。第\(2\)期のゲーム\(G_{2}\)において、プレイヤー\(1\)は強支配される純粋戦略を持たず、プレイヤー\(2\)の純粋戦略\(L\)は純粋戦略\(C\)によって強支配されるため、第\(3\)期のゲーム\(G_{3}\)を構成する純粋戦略集合は、\begin{eqnarray*}
S_{1}^{3} &=&\left\{ U\right\} \\
S_{2}^{3} &=&\left\{ C\right\}
\end{eqnarray*}となります。これ以上消去できないため、\(G_{3}\)が逐次消去の解です。さらに、\(G_{3}\)において全員の純粋戦略集合には戦略が1つずつ含まれているため、\(G\)は逐次消去によって解けるとともに、その解は\(\left( U,C\right) \)となります。

初期ゲーム\(G\)が有限ゲームである場合、それぞれのプレイヤーは有限個の純粋戦略を持つため、純粋戦略により強支配される戦略の逐次消去を適用すると、必ず有限ステップ\(T\)内で結果\(G_{T}\)へ到達します。ただ、結果\(G_{T}\)においてそれぞれのプレイヤーには複数の純粋戦略が残されている可能性があるため、たとえ初期ゲーム\(G\)が有限ゲームである場合でも、それは純粋戦略により強支配される戦略の逐次消去によって解けるとは限りません。

例(純粋戦略によって強支配される戦略の逐次消去)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。
$$\begin{array}{|c|c|c|c|}
\hline
1\diagdown 2 & L & C & R \\ \hline
T & 0,4 & 4,0 & 5,3 \\ \hline
M & 4,0 & 0,4 & 5,3 \\ \hline
B & 3,5 & 3,5 & 6,6 \\ \hline
\end{array}$$
表:戦略型ゲーム

初期ゲーム\(G\)においてプレイヤー\(1,2\)はともに強支配される純粋戦略を持たないため、\(G\)が結果に相当します。\(G\)においてプレイヤーたちは複数の純粋戦略を持つため、このゲーム\(G\)は逐次消去によって解くことはできません。

 

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

純粋戦略によって強支配される戦略の逐次消去をフォーマルな形で定義した際、それぞれのステップにおいてプレイヤーが複数の強支配される純粋戦略を持つ場合にはそれらを同時に消去するものと定めました。また、それぞれのステップにおいて複数のプレイヤーが強支配される純粋戦略を持つ場合には、そのようなプレイヤーたちの戦略を同時に消去するものと定めました。プレイヤーが合理的である場合、強支配される純粋戦略をすべて同時に消去しない特別な理由は見当たりません。

一方、逐次消去をアルゴリズムとみなすのであれば、各期のゲームにおいてあるプレイヤーが複数の強支配される戦略を持つ場合、それらをすべて同時に消去するのではなく、1つずつ順番に消去するような形で逐次消去のプロセスを進めることもできます。この場合、どのような順番で戦略を消去するかが問題になります。また、あるステップにおいて複数のプレイヤーが強支配される戦略を持つ場合、そのようなプレイヤーたちの戦略を同時に消去するのではなく、順番に消去するような形で逐次消去のプロセスを進めることもできます。この場合、どのプレイヤーの戦略を先に消去するかが問題になります。

消去可能な複数の戦略が存在する場合、それらの戦略を同時に消去するのではなく、順番に消去することで最終的に得られる結果は変わるのでしょうか。また、順番に消去する場合、消去する順番を変更すると最終的に得られる結果は変わるのでしょうか。

例(強支配される戦略を消去する順番)
以下の利得行列で表される戦略型ゲーム\(G\)について考えます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & R \\ \hline
T & 1,1 & 2,0 \\ \hline
M & 0,1 & 1,0 \\ \hline
B & 0,1 & 0,0 \\ \hline
\end{array}$$
表:初期のゲーム

初期ゲーム\(G\)において、プレイヤー\(1\)の純粋戦略\(M,B\)は純粋戦略\(T\)によって強支配され、プレイヤー\(2\)の純粋戦略\(R\)は純粋戦略\(L\)によって強支配されます。純粋戦略によって強支配される戦略の逐次消去の本来の定義にしたがう場合、\(G\)では全員のすべての支配される戦略\(M,B,R\)を同時に消去するため、第\(1\)期のゲーム\(G_{1}\)の純粋戦略集合は、\begin{eqnarray*}
S_{1}^{1} &=&\left\{ T\right\} \\
S_{2}^{1} &=&\left\{ L\right\}
\end{eqnarray*}となります。したがって\(G\)は逐次消去によって解くことができ、その解は\(\left( T,L\right) \)です。では、消去可能な戦略を順番に消去した場合に何が起こるでしょうか。試しに、\(G\)においてプレイヤー\(2\)の戦略だけを先に消去すると、第\(1\)期のゲーム\(G_{1}\)の純粋戦略集合は、\begin{eqnarray*}
S_{1}^{1} &=&\{T,M,B\} \\
S_{2}^{1} &=&\left\{ L\right\}
\end{eqnarray*}となります。\(G_{1}\)においてプレイヤー\(1\)は複数の強支配される戦略\(M,B\)を持ちます。\(G_{1}\)においてこれらを同時に消去するのではなく1つだけ消去すると何が起こるでしょうか。\(G_{1}\)において\(M\)を消去する場合にも、\(G_{1}\)において\(B\)を消去する場合においても、ゲーム\(G\)は解くことができ、その解は\(\left( T,L\right) \)になります(確認してください)。では、\(G\)においてプレイヤー\(1\)の戦略だけを先に消去するとどうなるでしょうか。この場合、以降においてどのような順番で戦略を1つずつ消去しても、ゲーム\(G\)は解くことができ、その解はやはり\(\left( T,L\right) \)になります(確認してください)。つまり、いずれの場合にもいても\(G\)は解くことができ、解\(\left( T,L\right) \)が得られます。

上の例に限らず、問題としている戦略型ゲーム\(G\)が有限ゲームの場合には、純粋戦略によって強支配される純粋戦略の逐次消去のそれぞれのステップにおいて消去可能な戦略が複数存在する場合、それらを同時に消去するのではなく順番に消去しても、また消去する順番を変えても、最終的に得られる結果は同じです(証明は演習問題にします)。

命題(強支配される戦略を消去する順番)
戦略型ゲーム\(G\)が有限ゲームである場合、純粋戦略によって強支配される戦略を逐次消去する際、一度に消去する戦略の個数や消去の順番とは関係なく、結果は同じである。
証明を見る(プレミアム会員限定)

問題としている戦略型ゲームが無限ゲームである場合には、上の命題は成り立つとは限りません。これは以下の例から明らかです。

例(強支配される戦略を消去する順番)
戦略型ゲーム\(G\)のそれぞれのプレイヤー\(i\in I\)の純粋戦略集合は\(S_{i}=\mathbb{N} =\left\{ 1,2,\cdots \right\} \)であるとともに、利得関数\(u_{i}\)はそれぞれの\(s_{I}\in S_{I}\)に対して、\begin{equation*}
u_{i}\left( s_{I}\right) =s_{i}
\end{equation*}を定めるものとします。つまり、それぞれのプレイヤーは任意の自然数を純粋戦略として選ぶことができるとともに、自分が選んだ自然数を利得として得ます。このゲーム\(G\)に対して、純粋戦略により強支配される戦略の逐次消去を適用します。任意の自然数にはそれよりも大きい自然数が存在するため、任意のプレイヤーの任意の純粋戦略は別の純粋戦略によって強支配されます。したがって、初期ゲーム\(G\)において、すべてのプレイヤーのすべての強支配される戦略を同時に消去すると、全員のすべての純粋戦略が消去され、それが結果になります。一方、初期ゲーム\(G\)において、すべてのプレイヤーの\(2\)以上の純粋戦略をすべて同時に消去すると、第\(1\)期のゲーム\(G_{1}\)においてすべてのプレイヤーは純粋戦略\(1\)だけを持つため、これが解になります。また、各期のゲームにおいて戦略を1つずつ消去する場合、自然数は無限に存在することから、逐次消去は有限ステップで終わりません。

 

逐次消去を完遂するために必要な仮定

繰り返しになりますが、合理的なプレイヤーは純粋戦略によって強支配される純粋戦略を選びません。したがって、純粋戦略によって強支配される戦略の逐次消去における各期のゲームにおいて、プレイヤーが何らかの純粋戦略によって強支配される純粋戦略を持つとき、それをプレイヤーの選択肢から消去できます。

ただし、プレイヤーによる意思決定の帰結として純粋戦略によって強支配される戦略の逐次消去が完遂することを保証するためには、プレイヤーが合理的であるという仮定に加えて、すべてのプレイヤーは他のすべてのプレイヤーが合理的であることを知っており、さらに、そのことをすべてのプレイヤーが知っており、という仮定を必要なだけ積み重ねる必要があります。以下では例を用いてその意味を解説します。

例(逐次消去とプレイヤーの合理性)
以下の利得行列で表される戦略型ゲーム\(G\)およびその混合拡張\(G^{\ast }\)について考えます。
$$\begin{array}{|c|c|c|c|}
\hline
1\diagdown 2 & L & C & R \\ \hline
U & 1,0 & 1,2 & 0,1 \\ \hline
D & 0,3 & 0,1 & 2,0 \\ \hline
\end{array}$$
表:初期のゲーム

初期ゲーム\(G\)において、プレイヤー\(1\)は純粋戦略によって強支配される純粋戦略を持ちませんが、プレイヤー\(2\)は純粋戦略\(C\)に強支配される純粋戦略\(R\)を持ちます。そこで、\(G\)に対して強支配される戦略の逐次消去を適用すれば、プレイヤー\(2\)の純粋戦略\(R\)が消去され、以下の利得行列で表される新たなゲーム\(G_{1}\)を得ます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & C \\ \hline
U & 1,0 & 1,2 \\ \hline
D & 0,3 & 0,1 \\ \hline
\end{array}$$

表:第1期のゲーム

ただし、ゲームが\(G\)から\(G_{1}\)へ移行し、プレイヤー\(1,2\)がともにそのことを互いに認識し合っている状態へ到達するためには以下の仮定が必要です。

  1. \(2\)の合理性を仮定する。このとき、自身の利得を最大化する\(2\)は、\(G\)において\(R\)を選ばない。したがって、\(2\)は自身が直面するゲームが\(G\)から\(G_{1}\)へ移行することを認識できる。
  2. \(1\)は「\(2\)が合理的である」ことを知っているものと仮定する。このとき\(1\)は、\(2\)が\(G\)において\(R\)を選ばないと判断できる。したがって、\(1\)は自分と相手が直面するゲームが\(G_{0}\)から\(G_{1}\)へ移行することを認識できる。
  3. \(2\)は「\(1\)が「\(2\)が合理的である」ことを知っている」ことを知っているものと仮定する。このとき\(2\)は、「\(1\)は「\(2\)は\(G\)において\(R\)を選ばない」と考える」と判断できる。したがって、\(2\)は相手が直面するゲームが\(G\)から\(G_{1}\)へ移行することを認識できる。

第\(1\)期のゲーム\(G_{1}\)において、プレイヤー\(2\)は強支配される純粋戦略を持ちませんが、プレイヤー\(1\)は純粋戦略\(U\)に強支配される純粋戦略\(D\)を持ちます。そこで、\(G_{1}\)に対して強支配される戦略の逐次消去を適用すれば、プレイヤー\(1\)の純粋戦略\(D\)が消去され、以下の利得行列で表される新たなゲーム\(G_{2}\)を得ます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & C \\ \hline
U & 1,0 & 1,2 \\ \hline
\end{array}$$

表:第2期のゲーム

ただし、ゲームが\(G_{1}\)から\(G_{2}\)へ移行し、プレイヤー\(1,2\)がともにそのことを互いに認識し合っている状態へ到達するためには以下の仮定が必要です。

  1. \(1\)の合理性を仮定する。このとき、自身の利得を最大化する\(1\)は、\(G_{1}\)において\(D\)を選ばない。したがって、\(1\)は自身が直面するゲームが\(G_{1}\)から\(G_{2}\)へ移行することを認識できる。
  2. \(2\)は「\(1\)が合理的である」ことを知っているものと仮定する。このとき\(2\)は、\(1\)が\(G_{1}\)において\(D\)を選ばないと判断できる。したがって、\(2\)は自分と相手が直面するゲームが\(G_{1}\)から\(G_{2}\)へ移行することを認識できる。
  3. \(1\)は「\(2\)が「\(1\)が合理的である」ことを知っている」ことを知っているものと仮定する。このとき\(1\)は、「\(2\)は「\(1\)は\(G_{1}\)において\(D\)を選ばない」と考える」と判断できる。したがって、\(1\)は相手が直面するゲームが\(G_{1}\)から\(G_{2}\)へ移行することを認識できる。

第\(2\)期のゲーム\(G_{2}\)において、プレイヤー\(2\)は純粋戦略\(C\)に強支配される純粋戦略\(L\)を持ちます。そこで、\(G_{2}\)に対して強支配される戦略の逐次消去を適用すれば、プレイヤー\(2\)の純粋戦略\(L\)が消去され、以下の利得行列で表される新たなゲーム\(G_{3}\)を得ます。
$$\begin{array}{|c|c|}
\hline
1\diagdown 2 & C \\ \hline
U & 1,2 \\ \hline
\end{array}$$

表:第3期のゲーム

ただし、ゲームが\(G_{2}\)から\(G_{3}\)へ移行し、プレイヤー\(1,2\)がともにそのことを互いに認識し合っている状態へ到達するためには、先ほどと同様の仮定を積み重ねる必要があります(新たにどのような仮定が必要になるか確認してください)。このような仮定を積み重ねながら支配される戦略の逐次消去を適用することにより、最終的に\(\left( U,C\right) \)という純粋戦略の組が得られます。

上の例で扱ったゲーム\(G\)のように、それが有限ゲームであるとともに純粋戦略によって強支配される戦略の逐次消去によって解ける場合、逐次消去は必ず有限ステップで完了するため、プレイヤーの合理性に関する仮定を無限の深さまで積み重ねる必要はありません。

一方、問題としているゲーム\(G\)が無限ゲームであるとともに純粋戦略によって強支配される戦略の逐次消去によって解ける場合、逐次消去は有限ステップで完了するとは限らないため、そのような場合にはプレイヤーの合理性に関する仮定を無限に積み重ねる必要があります。言い換えると、プレイヤーが合理的であるという事実が共有知識であることを仮定する必要があるということです。以下のゲームはそのような例になっています。

例(逐次消去とプレイヤーの合理性)
戦略型ゲーム\(G\)のプレイヤー集合は\(I=\{1,2\}\)です。プレイヤー\(i\)の純粋戦略集合を\(S_{i}=\mathbb{R} _{+}\)と定めます。これは無限集合であるため、このゲーム\(G\)は無限ゲームです。プレイヤー\(1\)の利得関数\(u_{1}:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R}\)は、\begin{equation*}
u_{1}\left( s_{1},s_{2}\right) =\left[ a-b\left( s_{1}+s_{2}\right) -c\right] \cdot s_{1}
\end{equation*}であり、プレイヤー\(2\)の利得関数\(u_{2}:\mathbb{R} _{+}^{2}\rightarrow \mathbb{R}\)は、\begin{equation*}
u_{2}\left( s_{1},s_{2}\right) =\left[ a-b\left( s_{1}+s_{2}\right) -c\right] \cdot s_{2}
\end{equation*}であるものとします。ただし、\(a,b,c>0\)はいずれも定数であり、\(a>c\)が成り立つものとします。このゲームは純粋戦略によって強支配される戦略の逐次消去によって解くことができ、その解は、\begin{equation*}
\left( s_{1},s_{2}\right) =\left( \frac{a-c}{3b},\frac{a-c}{3b}\right)
\end{equation*}となります。ただし、逐次消去を完遂させるためには、プレイヤーの合理性に関する仮定を無限の深さまで積み重ねる必要があります(以上の確認を演習問題にします)。言い換えると、プレイヤーが合理的であるという事実が共有知識である必要があります。ちなみに、これはクールノー競争(Cournot competition)と呼ばれるゲームです。

上の例が示唆するように、プレイヤーの合理性が共有知識である場合には、逐次消去のプロセスが必ず完遂します。なおかつ、問題としているゲームが逐次消去によって解けるとき、合理的なプレイヤーはその解を実際にプレーします。

命題(純粋戦略によって強支配される戦略の逐次消去による解が実現する根拠)
戦略型ゲーム\(G\)が純粋戦略によって強支配される戦略の逐次消去によって解ける場合、すなわちその解\(s_{I}^{\ast }\in S_{I}\)が存在する場合、合理性の仮定と、プレイヤーの合理性が共有知識であるという仮定のもとでは、プレイヤーたちは\(s_{I}^{\ast }\)をプレーする。
証明を見る(プレミアム会員限定)

 

強支配純粋戦略均衡と逐次消去による解の関係

戦略型ゲーム\(G\)に強支配純粋戦略均衡\(s_{I}^{\ast }\in S_{I}\)が存在するものとします。同じゲーム\(G\)に対して純粋戦略によって強支配される戦略の逐次消去を適用すると、プロセスの最初のステップにおいて先の\(s_{I}^{\ast }\)に含まれる純粋戦略以外のすべての戦略が消去されるため、結局、\(G\)は逐次消去によって解くことができ、その解は\(s_{I}^{\ast }\)と一致します。

命題(強支配純粋戦略均衡と逐次消去による解の関係)
戦略型ゲーム\(G\)に強支配純粋戦略均衡\(s_{I}^{\ast }\in S_{I}\)が存在する場合、\(G\)は純粋戦略によって強支配される戦略の逐次消去によって解くことができ、その解は\(s_{I}^{\ast }\)と一致する。
証明を見る(プレミアム会員限定)

上の命題の逆は成立するとは限りません。つまり、戦略型ゲーム\(G\)が純粋戦略によって強支配される戦略の逐次消去によって解くことができるとき、その解は\(G\)の強支配純粋戦略均衡であるとは限りません。これは以下の例から明らかです。

例(強支配純粋戦略均衡と逐次消去による解の関係)
以下の利得行列で表される戦略型ゲーム\(G\)について再び考えます。
$$\begin{array}{|c|c|c|c|}
\hline
1\diagdown 2 & L & C & R \\ \hline
U & 1,0 & 1,2 & 0,1 \\ \hline
D & 0,3 & 0,1 & 2,0 \\ \hline
\end{array}$$
表:戦略型ゲーム

先に確認したように、このゲーム\(G\)は純粋戦略によって強支配される戦略の逐次消去によって解くことができ、その解は\(\left( U,C\right) \)です。一方、\(G\)においてプレイヤー\(1,2\)はともに強支配純粋戦略を持たないため、\(G\)には強支配純粋戦略均衡は存在しません。

戦略型ゲームに強支配純粋戦略均衡が存在するとき、それが実際にプレーされることが保証するためには、合理性の仮定さえあれば十分です。ただ、戦略の組が強支配純粋戦略均衡であるための条件は厳しいため、ゲームに強支配純粋戦略均衡が存在しないという状況は多々起こり得ます。一方、ゲームに強支配純粋戦略均衡が存在しない場合でも、そのゲームが純粋戦略によって強支配される戦略の逐次消去によって解ける場合があります。ただ、その解が実際にプレーされることを保証するためには、合理性の仮定に加えて、合理性が共有知識であるという仮定が必要になります。

次回は純粋戦略によって弱支配される戦略の逐次消去について解説します。

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

完備情報の静学ゲーム
アカウント
ログイン