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

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

逐次消去の範囲を混合戦略にまで広げるメリット

問題としている戦略的状況が完備状況の静学ゲームであり、それが戦略型ゲーム\(G\)として表現されているものとします。プレイヤー\(i\)の純粋戦略\(s_{i}\)が他の純粋戦略によって強支配されるとき、合理性の仮定のもとではプレイヤー\(i\)が\(s_{i}\)を選択しないことが保証されるため、\(s_{i}\)をプレイヤー\(i\)の選択肢から消去しても問題ありません。以上を根拠に、純粋戦略によって強支配される戦略の逐次消去と呼ばれる均衡概念を定義しました。

強支配される戦略の逐次消去の概念は、戦略型ゲームの\(G\)の混合拡張\(G^{\ast }\)においても容易に拡張されます。つまり、プレイヤー\(i\)の混合戦略\(\sigma _{i}\)が他の混合戦略によって強支配されるとき、期待効用仮説のもとではプレイヤー\(i\)が\(\sigma _{i}\)を選択しないことが保証されるため、\(\sigma _{i}\)をプレイヤーの選択肢から消去できます。以上を根拠に、与えられたゲームのそれぞれのプレイヤーに関して、何らかの混合戦略によって強支配される混合戦略が存在する場合、それをプレイヤーの混合戦略集合から消去することを通じてプレイヤーたちが選択し得る戦略の組を絞り込む手法を混合戦略によって強支配される戦略の逐次消去(iterated elimination of strategies strictly dominated by a mixed strategy)と呼びます。

純粋戦略どうしの強支配関係から戦略を逐次消去するだけでなく、混合戦略どうしの強支配関係にまで広げて戦略を逐次消去することには何らかのメリットがあるのでしょうか。以下の例が示唆するように、いかなる純粋戦略によっても強支配されない純粋戦略が混合戦略によって強支配されるという事態は起こり得るため、純粋戦略によって強支配される戦略の逐次消去によって解けないゲームが、混合戦略によって強支配される戦略の逐次消去によって解ける可能性があります。

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

プレイヤー\(1\)は純粋戦略によって強支配される純粋戦略を持たないため(確認してください)、純粋戦略の範囲で考えた場合、プレイヤー\(1\)の戦略を消去できません。一方、純粋戦略\(M\)は以下の混合戦略\begin{equation*}
\sigma _{1}=(\sigma _{1}(U),\sigma _{1}(M),\sigma _{1}(D))=\left( \frac{1}{2},0,\frac{1}{2}\right)
\end{equation*}によって強支配されるため(確認してください)、混合戦略の範囲で考えた場合、\(M\)を消去することができます。

 

強支配される純粋戦略を削除できる根拠

戦略型ゲームの\(G\)の混合拡張\(G^{\ast }\)を対象に強支配される戦略を消去しようとする場合、それぞれのプレイヤー\(i\)について、比較対象となる2つの混合戦略\(\sigma _{i},\sigma _{i}^{\prime }\)を任意に選んだ上で、それらの間に強支配関係が成立するか否かを調べることになります。ただ、プレイヤーは無数の混合戦略を持っているため、このような評価を行うのは実質的に不可能です。混合戦略を対象に強支配される戦略を消去する場合、作業を効率的に行うための指針が必要です。

最も重要な指針は、それぞれのプレイヤー\(i\)について、何らかの混合戦略によって強支配される純粋戦略\(s_{i}\)を探し、それらを優先的に消去するというものです。ただ、プレイヤーの選択肢から純粋戦略\(s_{i}\)を消去すると、\(s_{i}\)に正の確率を付与するすべての混合戦略がプレイヤー\(i\)の選択肢から同時に消去されてしまうため、この指針が妥当であるか否かを慎重に検討する必要があります。ただ、以下で示すように、プレイヤー\(i\)の純粋戦略\(s_{i}\)が何らかの混合戦略によって強支配される場合、\(s_{i}\)に正の確率を与える任意の混合戦略もまた何らかの混合戦略によって強支配されます。したがって、強支配される純粋戦略\(s_{i}\)を消去したときに、戦略を消去しすぎていることにはなりません。

証明のスケッチは以下の通りです。復習になりますが、戦略型ゲーム\(G\)においてプレイヤー\(i\)の純粋戦略\(s_{i}\)が別の混合戦略\(\sigma _{i}\)によって強支配されることは、\begin{equation}
\forall s_{-i}\in S_{-i}:F_{i}\left( \sigma _{i},s_{-i}\right) >u_{i}\left(
s_{i},s_{-i}\right) \tag{1}
\end{equation}が成り立つことと必要十分です。この純粋戦略\(s_{i}\)に正の確率を与える混合戦略\(\sigma _{i}^{\prime }\)を任意に選びます。すなわち、\begin{equation}
\sigma _{i}^{\prime }\left( s_{i}\right) >0 \tag{2}
\end{equation}です。この\(\sigma _{i}^{\prime }\)を強支配する混合戦略が存在することを示すことが目標になります。具体的には、任意の\(s_{-i}\in S_{-i}\)に対して、\begin{eqnarray*}
F_{i}\left( \sigma _{i}^{\prime },s_{-i}\right) &=&\sum_{t_{i}\in S_{i}}
\left[ \sigma _{i}^{\prime }\left( t_{i}\right) \cdot u_{i}\left(
t_{i},s_{-i}\right) \right] \quad \because F_{i}\text{の定義} \\
&=&\sigma _{i}^{\prime }\left( s_{i}\right) \cdot u_{i}\left(
s_{i},s_{-i}\right) +\sum_{t_{i}\in S_{i}\backslash \left\{ s_{i}\right\} }
\left[ \sigma _{i}^{\prime }\left( t_{i}\right) \cdot u_{i}\left(
t_{i},s_{-i}\right) \right] \quad \because s_{i}\in S_{i} \\
&<&\sigma _{i}^{\prime }\left( s_{i}\right) \cdot F_{i}\left( \sigma
_{i},s_{-i}\right) +\sum_{t_{i}\in S_{i}\backslash \left\{ s_{i}\right\} }
\left[ \sigma _{i}^{\prime }\left( t_{i}\right) \cdot u_{i}\left(
t_{i},s_{-i}\right) \right] \quad \because \left( 1\right) ,\left( 2\right)
\\
&=&\sum_{t_{i}\in S_{i}}\left[ \sigma _{i}^{\prime }\left( s_{i}\right)
\cdot \sigma _{i}\left( t_{i}\right) \cdot u_{i}\left( t_{i},s_{-i}\right) \right] +\sum_{t_{i}\in S_{i}\backslash \left\{ s_{i}\right\} }\left[ \sigma
_{i}^{\prime }\left( t_{i}\right) \cdot u_{i}\left( t_{i},s_{-i}\right) \right] \quad \because F_{i}\text{の定義} \\
&=&\sigma _{i}^{\prime }\left( s_{i}\right) \cdot \sigma _{i}\left(
s_{i}\right) \cdot u_{i}\left( s_{i},s_{-i}\right) +\sum_{t_{i}\in
S_{i}\backslash \left\{ s_{i}\right\} }\left\{ \left[ \sigma _{i}^{\prime
}\left( s_{i}\right) \cdot \sigma _{i}\left( t_{i}\right) +\sigma
_{i}^{\prime }\left( t_{i}\right) \right] \cdot u_{i}\left(
t_{i},s_{-i}\right) \right\} \quad \because s_{i}\in S_{i}
\end{eqnarray*}が成り立つため、純粋戦略\(s_{i}\)を確率\(\sigma _{i}^{\prime }\left( s_{i}\right) \cdot \sigma _{i}\left( s_{i}\right) \)で選び、\(s_{i}\)以外のそれぞれの純粋戦略\(t_{i}\)を確率\(\sigma _{i}^{\prime }\left( s_{i}\right) \cdot \sigma _{i}\left( t_{i}\right) +\sigma _{i}^{\prime }\left( t_{i}\right) \)で選ぶような混合戦略\(\sigma _{i}^{\prime\prime }\)をとれば、上の不等式は、\begin{equation*}
F_{i}\left( \sigma _{i}^{\prime },s_{-i}\right) <F_{i}\left( \sigma _{i}^{\prime\prime
},s_{-i}\right)
\end{equation*}と言い換えられますが(確認してください)、これは\(\sigma _{i}^{\prime\prime }\)が\(\sigma _{i}^{\prime} \)を強支配することと必要十分であるため、目標が達成されました。

命題(強支配される純粋戦略に正の確率を付与する混合戦略)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の純粋戦略\(s_{i}\in S_{i}\)が何らかの混合戦略によって強支配されるとき、\(s_{i}\)に正の確率を与える任意の混合戦略もまた何らかの混合戦略によって強支配される。
証明を見る(プレミアム会員限定)

上の命題の証明と同様の議論により、以下が成り立つことも証明可能です。

命題(強支配される純粋戦略に正の確率を付与する混合戦略)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の純粋戦略\(s_{i}\in S_{i}\)が何らかの純粋戦略によって強支配されるとき、\(s_{i}\)に正の確率を与える任意の混合戦略もまた何らかの混合戦略によって強支配される。
証明を見る(プレミアム会員限定)

以上の2つの命題より、純粋戦略を含めた何らかの混合戦略によって強支配される純粋戦略を消去しても、戦略を消去しすぎていることにはならないことが明らかになりました。この事実を踏まえた上で、混合戦略によって強支配される戦略の逐次消去という概念を定義します。

 

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

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

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

第\(1\)期のゲーム\(G_{1}^{\ast }\)において、それぞれのプレイヤー\(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 \sigma
_{i}\in \Delta \left( S_{i}^{1}\right) \backslash \left\{ s_{i}\right\}
:\sigma _{i}\text{は}s_{i}\text{を強支配する}\right\}
\end{equation*}です。強支配される純粋戦略に正の確率を付与する任意の混合戦略もまた強支配されることを踏まえると、プレイヤー\(i\)が直面する新たな混合戦略からなる集合を\(\Delta \left( S_{i}^{2}\right) \)とみなしても問題は発生しません。そこで、それぞれのプレイヤー\(i\)の混合戦略集合を\(\Delta \left( S_{i}^{1}\right) \)から\(\Delta \left( S_{i}^{2}\right) \)へ縮小すると、\(G_{1}^{\ast }\)の制限\begin{equation*}
G_{2}^{\ast }=(I,\left\{ \Delta \left( S_{i}^{2}\right) \right\} _{i\in
I},\left\{ F_{i}\right\} _{i\in I})
\end{equation*}が得られるため、これを便宜的に第\(2\)期のゲームと呼びます。

同様のプロセスを繰り返して第\(t-1\)期のゲーム\begin{equation*}
G_{t-1}^{\ast }=(I,\left\{ \Delta \left( S_{i}^{t-1}\right) \right\} _{i\in
I},\left\{ F_{i}\right\} _{i\in I})
\end{equation*}まで定まった時、\(G_{t-1}^{\ast }\)においてそれぞれのプレイヤー\(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
\sigma _{i}\in \Delta \left( S_{i}^{t-1}\right) \backslash \left\{
s_{i}\right\} :\sigma _{i}\text{は}s_{i}\text{を強支配する}\right\}
\end{equation*}です。強支配される純粋戦略に正の確率を付与する任意の混合戦略もまた強支配されることを踏まえると、プレイヤー\(i\)が直面する新たな混合戦略からなる集合を\(\Delta \left( S_{i}^{t}\right) \)とみなしても問題は発生しません。そこで、それぞれのプレイヤー\(i\)の混合戦略集合を\(\Delta \left( S_{i}^{t-1}\right) \)から\(\Delta \left( S_{i}^{t}\right) \)へ縮小すると、\(G_{t-1}^{\ast }\)の制限\begin{equation*}
G_{t}^{\ast }=(I,\left\{ \Delta \left( S_{i}^{t}\right) \right\} _{i\in
I},\left\{ F_{i}\right\} _{i\in I})
\end{equation*}が得られるため、これを便宜的に第\(t\)期のゲームと呼びます。

初期ゲーム\(G^{\ast }\)を出発点に、以上の要領で、\begin{equation*}
G^{\ast }\rightarrow G_{1}^{\ast }\rightarrow G_{2}^{\ast }\rightarrow
\cdots \rightarrow G_{t-1}^{\ast }\rightarrow G_{t}^{\ast }\rightarrow
\cdots
\end{equation*}と縮小していったとき、第\(T\)期のゲーム\(G_{T}^{\ast }\)において、純粋戦略を含めた何らかの混合戦略によって強支配される純粋戦略を持つプレイヤーが存在しなくなった場合、すなわち、\begin{equation*}
G_{T}^{\ast }=G_{T+1}^{\ast }
\end{equation*}が成り立つ場合、プロセスを一旦停止します。\(G_{T}^{\ast }\)にはもはや強支配される純戦略は存在しませんが、強支配される混合戦略が存在する可能性は残されています。そこで、それぞれのプレイヤー\(i\)について、\(G_{T}^{\ast }\)における混合戦略集合\(\Delta \left( S_{i}^{T}\right) \)から強支配される混合戦略をすべて消去します。その結果、それぞれのプレイヤーに残されている混合戦略が1つずつである場合、ゲーム\(G^{\ast }\)は逐次消去によって解ける(solvable)と言い、最終的に得られた混合戦略の組を逐次消去による(solution)と呼びます。

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

初期ゲーム\(G^{\ast }\)の純粋戦略集合は、\begin{eqnarray*}
S_{1} &=&\left\{ U,M,D\right\} \\
S_{2} &=&\left\{ L,R\right\}
\end{eqnarray*}です。初期ゲーム\(G^{\ast }\)において、すべてのプレイヤーは純粋戦略によって強支配される純粋戦略を持ちません。一方、プレイヤー\(1\)の純粋戦略\(M\)は混合戦略\begin{equation*}
\sigma _{1}=\left( \sigma _{1}\left( U\right) ,\sigma _{1}\left( M\right)
,\sigma _{1}\left( D\right) \right) =\left( \frac{1}{2},0,\frac{1}{2}\right)
\end{equation*}によって強支配されます。したがって、プレイヤー\(1\)が合理的であれば\(M\)を選びませんし、\(M\)に正の確率を付与する任意の混合戦略も選びません。以上を踏まえると、第\(1\)期のゲーム\(G_{1}^{\ast }\)を構成する純粋戦略集合は、\begin{eqnarray*}
S_{1}^{1} &=&\left\{ U,D\right\} \\
S_{2}^{1} &=&\left\{ L,R\right\}
\end{eqnarray*}となります。第\(1\)期のゲーム\(G_{1}^{\ast }\)において、プレイヤー\(1\)は強支配される純粋戦略を持たない一方、プレイヤー\(2\)の純粋戦略\(R\)は純粋戦略\(L\)によって強支配されます。したがって、プレイヤー\(2\)が合理的であれば\(R\)を選びませんし、\(R\)に正の確率を付与する任意の混合戦略も選びません。以上を踏まえると、第\(2\)期のゲーム\(G_{2}^{\ast }\)を構成する純粋戦略集合は、\begin{eqnarray*}
S_{1}^{2} &=&\left\{ U,D\right\} \\
S_{2}^{2} &=&\left\{ L\right\}
\end{eqnarray*}となります。第\(2\)期のゲーム\(G_{2}^{\ast }\)において、プレイヤー\(1\)の純粋戦略\(D\)は純粋戦略\(U\)によって強支配されます。したがって、プレイヤー\(1\)が合理的であれば\(D\)を選びませんし、\(D\)に正の確率を付与する任意の混合戦略も選びません。以上を踏まえると、第\(3\)期のゲーム\(G_{3}^{\ast }\)を構成する純粋戦略集合は、\begin{eqnarray*}
S_{1}^{3} &=&\left\{ U\right\} \\
S_{2}^{3} &=&\left\{ L\right\}
\end{eqnarray*}となります。これ以上、強支配される純粋戦略は存在しないため、プロセスを一旦停止します。\(G_{3}^{\ast }\)を構成する混合戦略集合は、\begin{eqnarray*}
\Delta \left( S_{1}^{3}\right) &=&\left\{ U\right\} \\
\Delta \left( S_{2}^{3}\right) &=&\left\{ L\right\}
\end{eqnarray*}であり、それぞれのプレイヤーには混合戦略が1つずつ残されているため、\(G^{\ast }\)は逐次消去によって解けるとともに、その解は\(\left( U,L\right) \)となります。

 

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

混合戦略によって強支配される戦略の逐次消去は、強支配される純粋戦略を逐次消去していく第1ステージと、強支配される混合戦略を逐次消去していく第2ステージから構成されます。特に、第1ステージにおける各期のゲームにおいて、プレイヤーが複数の強支配される純粋戦略を持つ場合には、それらを同時に消去するものと定めました。また、第1ステージの各期のゲームにおいて、複数のプレイヤーが強支配される純粋戦略を持つ場合には、そのようなプレイヤーたちの戦略を同時に消去するものと定めました。プレイヤーが合理的である場合、強支配される純粋戦略をすべて同時に消去しない特別な理由は見当たりません。

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

問題としている戦略型ゲーム\(G\)が有限ゲームの場合には、第1ステージの各期のゲームにおいて複数の純粋戦略を同時に消去するのではなく1つずつ消去しても、また、消去する順番を変えても、最終的に得られる結果は同じです(証明は演習問題にします)。

第1ステージ終了後にすべてのプレイヤーに残されている純粋戦略が1つずつである場合、それは自動的に逐次消去の解になります。一方、第1ステージ終了後に複数の純粋戦略が残されているプレイヤーが存在する場合、第2ステージにおいて、そのようなプレイヤーが持つ強支配される混合戦略をすべて消去します。その上で、全員について混合戦略が1つだけ残る場合にはそれが解になるため、解が存在する場合、それは一意的です。

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

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

例(強支配される戦略を消去する順番)
戦略型ゲーム\(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^{\ast }\)において、混合戦略により強支配される戦略の逐次消去を適用します。任意の自然数にはそれよりも大きい自然数が存在するため、任意のプレイヤーの任意の純粋戦略は別の純粋戦略によって強支配されます。したがって、初期ゲーム\(G^{\ast }\)において、すべてのプレイヤーのすべての強支配される純粋戦略を同時に消去すると、全員のすべての純粋戦略が消去され、それが結果になります。一方、初期ゲーム\(G^{\ast }\)において、すべてのプレイヤーの\(2\)以上の純粋戦略をすべて同時に消去すると、第\(1\)期のゲーム\(G_{1}^{\ast }\)においてすべてのプレイヤーは純粋戦略\(1\)だけを持つため、これが解になります。

 

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

繰り返しになりますが、合理的なプレイヤーは強支配される純粋戦略や、そのような純粋戦略に正の確率を付与する任意の混合戦略を選びません。したがって、逐次消去の第1ステージにおける各期のゲームにおいて、プレイヤーが強支配される純粋戦略を持つとき、それをプレイヤーの選択肢から消去できます。また、合理的なプレイヤーは強支配される混合戦略を選びません。したがって、逐次消去の第2ステージにおいて、プレイヤーが強支配される混合戦略を持つとき、それをプレイヤーの選択肢から消去できます。

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

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

初期ゲーム\(G^{\ast }\)においてすべてのプレイヤーは純粋戦略によって強支配される純粋戦略を持ちません。一方、プレイヤー\(1\)の純粋戦略\(M\)は混合戦略\begin{equation*}
\sigma _{1}=\left( \sigma _{1}\left( U\right) ,\sigma _{1}\left( M\right)
,\sigma _{1}\left( D\right) \right) =\left( \frac{1}{2},0,\frac{1}{2}\right)
\end{equation*}によって強支配されます。そこで、プレイヤー\(1\)の純粋戦略\(M\)を消去すれば、以下の利得行列で表される戦略型ゲーム\(G_{1}\)の混合拡張\(G_{1}^{\ast }\)が得られます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & R \\ \hline
U & 2,0 & -1,0 \\ \hline
D & -1,1 & 2,0 \\ \hline
\end{array}$$

表:第1期のゲーム

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

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

第\(1\)期のゲーム\(G_{1}^{\ast }\)において、プレイヤー\(1\)は強支配される純粋戦略を持ちませんが、プレイヤー\(2\)は純粋戦略\(R\)は純粋戦略\(L\)によって強支配されます。そこで、プレイヤー\(2\)の純粋戦略\(R\)を消去すれば、以下の利得行列で表される戦略型ゲーム\(G_{2}\)の混合拡張\(G_{2}^{\ast }\)が得られます。
$$\begin{array}{|c|c|}
\hline
1\diagdown 2 & L \\ \hline
U & 2,0 \\ \hline
D & -1,1 \\ \hline
\end{array}$$

表:第2期のゲーム

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

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

第\(2\)期のゲーム\(G_{2}^{\ast }\)において、プレイヤー\(1\)は純粋戦略\(U\)に強支配される純粋戦略\(D\)を持ちます。そこで、プレイヤー\(1\)の純粋戦略\(D\)を消去すれば、以下の利得行列で表される戦略型ゲーム\(G_{3}\)の混合拡張\(G_{3}^{\ast }\)が得られます。
$$\begin{array}{|c|c|}
\hline
1\diagdown 2 & L \\ \hline
U & 2,0 \\ \hline
\end{array}$$

表:第3期のゲーム

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

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

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

命題(混合戦略によって強支配される戦略の逐次消去による解が実現する根拠)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)が混合戦略によって強支配される戦略の逐次消去によって解ける場合、すなわちその解\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)が存在する場合、期待効用仮説と、プレイヤーたちが期待効用仮説にしたがうことが共有知識であるという仮定のもとでは、プレイヤーたちは\(\sigma _{I}^{\ast }\)をプレーする。
証明を見る(プレミアム会員限定)

 

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

戦略型ゲーム\(G\)が純粋戦略によって強支配される戦略の逐次消去によって解けるものとし、その解を\(s_{I}^{\ast }\in S_{I}\)で表します。同じゲーム\(G\)の混合拡張\(G^{\ast }\)に対して混合戦略によって強支配される戦略の逐次消去を適用すると、第1ステージの終了時に\(s_{I}^{\ast }\)を得て、なおかつそれが最終的な解になります。

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

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

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

先に確認したように、このゲームの混合拡張\(G^{\ast }\)は混合戦略によって強支配される戦略の逐次消去によって解くことができ、その解は\(\left( U,L\right) \)となります。一方、\(G\)のプレイヤーは純粋戦略によって強支配される純粋戦略を持たないため、\(G\)は純粋戦略によって強支配される戦略の逐次消去によって解くことができません。

 

強支配混合戦略均衡との関係

戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)に強支配混合戦略均衡\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)が存在するものとします。復習になりますが、\(G^{\ast }\)に強支配混合戦略均衡\(\sigma _{I}^{\ast }\)が存在することと、\(G\)に強支配純粋戦略均衡\(s_{I}^{\ast }\)が存在することは必要十分であるとともに、\(\sigma _{I}^{\ast }=s_{I}^{\ast }\)が成立します。強支配純粋戦略均衡の定義より、任意のプレイヤー\(i\)の均衡戦略\(s_{i}^{\ast }\)は強支配純粋戦略であるため、これは他の純粋戦略を強支配します。この事実は、\(s_{i}^{\ast }\)が他の純粋戦略によって強支配されないことを含意します。したがって、\(G^{\ast }\)に対して混合戦略によって強支配される戦略の逐次消去を適用すると、第1ステージにおいて\(s_{I}^{\ast }\)は消去されずに残るとともに、これが最終的な解になります。

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

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

例(強支配混合戦略均衡との関係)
以下の利得行列で表される戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)について考えます。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & R \\ \hline
U & 2,0 & -1,0 \\ \hline
M & 0,0 & 0,1 \\ \hline
D & -1,1 & 2,0 \\ \hline
\end{array}$$
表:戦略型ゲーム

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

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

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

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

プレミアム会員サービス

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

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

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