逐次消去の範囲を混合戦略にまで広げるメリット
問題としている戦略的状況が完備情報の静学ゲームであるとともに、それが戦略型ゲーム\begin{equation*}
G=\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in
I}\right)
\end{equation*}として記述されているものとします。ただし、\(I\)はプレイヤー集合、\(S_{i}\)はプレイヤー\(i\in I\)の純粋戦略集合、\(u_{i}:S_{I}\rightarrow \mathbb{R} \)はプレイヤー\(i\)の利得関数です。
プレイヤー\(i\)の純粋戦略\(s_{i}\)が他の純粋戦略によって狭義支配される場合、合理性の仮定のもとではプレイヤー\(i\)が\(s_{i}\)を選択しないことが保証されるため、\(s_{i}\)をプレイヤー\(i\)の選択肢から消去しても問題ありません。以上を根拠に、純粋戦略によって狭義支配される戦略の逐次消去と呼ばれる均衡概念を定義しました。狭義支配される戦略の逐次消去の概念は戦略型ゲームの混合拡張を対象とするプロセスとして容易に拡張できます。具体的には以下の通りです。
戦略型ゲーム\(G\)においてプレイヤーたちが混合戦略を選択する状況を想定する場合、その戦略的状況は\(G\)の混合拡張\begin{equation*}G^{\ast }=(I,\{\Delta \left( S_{i}\right) \}_{i\in I},\{F_{i}\}_{i\in I})
\end{equation*}として表現されます。ただし、\(I\)はプレイヤー集合、\(\Delta \left( S_{i}\right) \)はプレイヤー\(i\in I\)の混合戦略集合、\(F_{i}:\Delta \left( S_{I}\right)\rightarrow \mathbb{R} \)はプレイヤー\(i\)の期待利得関数です。
プレイヤー\(i\)の混合戦略\(\sigma _{i}\)が自分の他の混合戦略\(\sigma _{i}^{\prime }\)によって狭義支配されるものとします。つまり、\begin{equation*}\exists \sigma _{i}^{\prime }\in \Delta \left( S_{i}\right) \backslash
\left\{ \sigma _{i}\right\} ,\ \forall \sigma _{-i}\in \Delta \left(
S_{-i}\right) :F_{i}\left( \sigma _{i}^{\prime },\sigma _{-i}\right)
>F_{i}\left( \sigma _{i},\sigma _{-i}\right)
\end{equation*}が成り立つ状況を想定します。このとき、プレイヤー\(i\)は\(\sigma_{i}^{\prime }\)によって狭義支配される\(\sigma _{i}\)を選ぶ代わりに\(\sigma _{i}^{\prime }\)を選べば、他のプレイヤーたちが選ぶ戦略\(\sigma _{-i}\)がどれであっても、自分は常により大きい期待利得に直面します。したがって、プレイヤー\(i\)が合理的であり、合理的なプレイヤーの目的が自己の期待利得の最大化である限りにおいて、プレイヤー\(i\)は狭義支配される戦略\(\sigma _{i}\)を選びません。プレイヤー\(i\)が自身の何らかの混合戦略\(\sigma _{i}^{\prime }\)によって狭義支配される混合戦略\(\sigma _{i}\)を選ぶのであれば、それは期待効用仮説と矛盾します。
以上を根拠に、与えられたゲームのそれぞれのプレイヤーに関して、何らかの混合戦略によって狭義支配される混合戦略が存在する場合、それをプレイヤーの混合戦略集合から消去することを通じてプレイヤーたちが選択し得る戦略の組を絞り込む手法を混合戦略によって狭義支配される戦略の逐次消去（iterated elimination of strategies strictly dominated by a mixed strategy）と呼びます。
純粋戦略どうしの狭義支配関係から戦略を逐次消去するだけでなく、混合戦略どうしの狭義支配関係に広げてまで戦略を逐次消去することには何らかのメリットがあるのでしょうか。以下の例が示唆するように、いかなる純粋戦略によっても狭義支配されない純粋戦略が混合戦略によって狭義支配されるという事態は起こり得るため、純粋戦略によって狭義支配される戦略の逐次消去によって解けないゲームが、混合戦略によって狭義支配される戦略の逐次消去によって解ける可能性があります。
$$\begin{array}{|c|c|c|}
\hline
1\diagdown 2 & L & R \\ \hline
U & 2,0 & -1,0 \\ \hline
M & 0,0 & 0,0 \\ \hline
D & -1,0 & 2,0 \\ \hline
\end{array}$$
プレイヤー\(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*}によって狭義支配されます。混合戦略を含めた戦略間の支配関係を検討する際には、他のプレイヤーが純粋戦略を採用する状況を想定しても一般性は失われません。相手が純粋戦略\(L\)を選択する場合には、\begin{eqnarray*}F_{1}\left( \sigma _{1},L\right) &=&\frac{1}{2}\cdot 2+0\cdot 0+\frac{1}{2}\left( -1\right) =\frac{1}{2} \\
F_{1}\left( M,L\right) &=&0
\end{eqnarray*}であるため、\begin{equation*}
F_{1}\left( \sigma _{1},L\right) >F_{1}\left( M,L\right)
\end{equation*}が成り立ち、相手が純粋戦略\(R\)を採用する場合には、\begin{eqnarray*}F_{1}\left( \sigma _{1},R\right) &=&\frac{1}{2}\left( -1\right) +0\cdot 0+\frac{1}{2}\cdot 2=\frac{1}{2} \\
F_{1}\left( M,R\right) &=&0
\end{eqnarray*}であるため、\begin{equation*}
F_{1}\left( \sigma _{1},R\right) >F_{1}\left( M,R\right)
\end{equation*}が成り立ちます。したがって、\(\sigma _{1}\)は\(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}\)を消去したときに戦略を消去しすぎていることにはならないことが保証されます。
純粋戦略は特別な混合戦略であることを踏まえると、上の命題より以下を得ます。
以上の2つの命題より、純粋戦略を含めた何らかの混合戦略によって狭義支配される純粋戦略を消去しても、戦略を消去しすぎていることにはならないことが明らかになりました。
混合戦略によって狭義支配される戦略の逐次消去
これまでの議論を踏まえた上で、混合戦略によって狭義支配される戦略の逐次消去という概念をフォーマルな形で定義します。
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)が与えられたとき、それぞれのプレイヤー\(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\)の期待利得関数\(F_{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）と呼びます。
問題としている戦略的状況が完備情報の静学ゲームであるとともに、それが戦略型ゲーム\begin{equation*}
G=\left( I,\left\{ S_{i}\right\} _{i\in I},\left\{ u_{i}\right\} _{i\in
I}\right)
\end{equation*}として表現されているものとします。その混合拡張は、\begin{equation*}
G^{\ast }=\left( I,\left\{ \Delta \left( S_{i}\right) \right\} _{i\in
I},\left\{ F_{i}\right\} _{i\in I}\right)
\end{equation*}ですが、これを便宜的に初期ゲームと呼びます。
初期ゲーム\(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 }=\left( I,\left\{ \Delta \left( S_{i}^{1}\right) \right\}
_{i\in I},\left\{ F_{i}\right\} _{i\in I}\right)
\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 }=\left( I,\left\{ \Delta \left( S_{i}^{2}\right) \right\}
_{i\in I},\left\{ F_{i}\right\} _{i\in I}\right)
\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 }=\left( I,\left\{ \Delta \left( S_{i}^{t}\right) \right\}
_{i\in I},\left\{ F_{i}\right\} _{i\in I}\right)
\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）と呼びます。
$$\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 }\)は逐次消去によって解けるとともに、その解は、\begin{equation*}\left( U,L\right)
\end{equation*}となります。
混合戦略によって狭義支配される逐次消去の一般性
戦略型ゲーム\(G\)が純粋戦略によって狭義支配される戦略の逐次消去によって解けるものとし、その解を\(s_{I}^{\ast }\in S_{I}\)で表します。同じゲーム\(G\)の混合拡張\(G^{\ast }\)に対して混合戦略によって狭義支配される戦略の逐次消去を適用すると、第1ステージの終了時に\(s_{I}^{\ast }\)を得て、なおかつそれが最終的な解になります。したがって以下の命題を得ます。
上の命題の逆は成立するとは限りません。つまり、戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)が混合戦略によって狭義支配される戦略の逐次消去によって解くことができるとき、\(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\)は純粋戦略によって狭義支配される戦略の逐次消去によって解くことができません。
逐次消去の範囲を混合戦略へ拡大しても、ゲームは狭義支配される戦略の逐次消去によって解けることは限りません。
$$\begin{array}{|c|c|c|c|c|}
\hline
1\diagdown 2 & A_{2} & B_{2} & C_{2} & D_{2} \\ \hline
A_{1} & 5,0 & 1,1 & 0,2 & 0,2 \\ \hline
B_{1} & 1,6 & 1,4 & 2,5 & 1,3 \\ \hline
C_{1} & 2,0 & 4,0 & 1,0 & 0,4 \\ \hline
D_{1} & 0,1 & 1,0 & 0,1 & 4,0 \\ \hline
\end{array}$$
このゲームは混合戦略によって狭義支配される戦略の逐次消去によって解くことはできません（演習問題）。
演習問題
$$\begin{array}{|c|c|c|c|c|}
\hline
1\diagdown 2 & A_{2} & B_{2} & C_{2} & D_{2} \\ \hline
A_{1} & 5,0 & 1,1 & 0,2 & 0,2 \\ \hline
B_{1} & 1,6 & 1,4 & 2,5 & 1,3 \\ \hline
C_{1} & 2,0 & 4,0 & 1,0 & 0,4 \\ \hline
D_{1} & 0,1 & 1,0 & 0,1 & 4,0 \\ \hline
\end{array}$$
以下の問いに答えてください。
- 純粋戦略\(B_{2}\)が混合戦略によって狭義支配されることを示してください。
- 純粋戦略\(B_{2}\)を消去した次のステージのゲームにおいて、純粋戦略\(C_{1}\)が混合戦略によって狭義支配されることを示してください。
- 最終的に、このゲームは混合戦略によって狭義支配される戦略の逐次消去によって解けるでしょうか。検討してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】