教材一覧
教材一覧
教材検索
STATIC GAME OF COMPLETE INFORMATION

狭義支配される戦略の逐次消去

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

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

問題としている戦略的状況が完備情報の静学ゲームであり、それが戦略型ゲーム\(G\)として表現されているものとします。プレイヤー\(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\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}\)から、純粋戦略によって狭義支配される純粋戦略をすべて消去して得られる新たな純粋戦略集合を\(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}\)から、純粋戦略によって狭義支配される純粋戦略をすべて消去して得られる新たな純粋戦略集合を\(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}\)から、純粋戦略によって狭義支配される純粋戦略をすべて消去して得られる新たな純粋戦略集合を\(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=G_{0}\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\)は逐次消去によって解くことはできません。

 

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

プレイヤー\(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\)の混合拡張\(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\)の期待利得関数\(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)と呼びます。

戦略型ゲーム\(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) \)となります。

 

混合戦略によって狭義支配される逐次消去の一般性

戦略型ゲーム\(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\)を純粋戦略によって狭義に支配される戦略の逐次消去によって解いてください。

$$\begin{array}{|c|c|c|c|}\hline
1\diagdown 2 & L & C & R \\ \hline
U & 4,3 & 5,1 & 6,2 \\ \hline
M & 2,1 & 8,4 & 3,6 \\ \hline
D & 3,0 & 9,6 & 2,8 \\ \hline
\end{array}$$

表:利得行列
解答を見る

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

次回は広義支配される戦略の逐次消去について解説します。

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

囚人のジレンマ
非対称的な利得構造を持つ囚人のジレンマ

これまではプレイヤーたちが同一の利得関数を持つ囚人のジレンマについて考えてきましたが、状況を少し一般化して、プレイヤーたちが異なる利得関数を持つ場合の囚人のジレンマについて考えます。

クールノー競争
クールノー競争(クールノー均衡)

同質財を生産する複占市場における数量競争をモデル化したゲームをクールノー競争と呼び、そこでのナッシュ均衡をクールノー均衡と呼びます。

支配される戦略の逐次消去
広義支配される戦略の逐次消去

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

支配される戦略の逐次消去
支配される戦略を消去する順番

支配される戦略の逐次消去のプロセスにおいて、戦略を消去する順番が結果に与える影響について解説します。

支配される戦略の逐次消去
支配される戦略の逐次消去と合理性

プレイヤーたちが支配される戦略の逐次消去にしたがって意思決定を行うことを保証するためには、プレイヤーの合理性が共有知識であることを仮定する必要があります。

ナッシュ均衡
ナッシュ均衡と支配される戦略の逐次消去の関係

戦略型ゲームにナッシュ均衡が存在する場合、そのゲームに支配される戦略の逐次消去を適用すると、そのナッシュ均衡は最後まで残ります。特に、ゲームが逐次消去によって解ける場合、その解はゲームの一意的なナッシュ均衡であることが保証されます。

ナッシュ均衡
ナッシュ均衡と支配戦略均衡の関係

戦略型ゲームに支配戦略均衡が存在する場合、それはナッシュ均衡であることが保証されます。逆は成立するとは限りません。つまり、ナッシュ均衡は支配戦略均衡であるとは限りません。

支配される戦略の逐次消去
美人投票(平均の2/3の推測)

プレイヤーたちが0から100までの実数を1つずつ投票し、全体の平均の2/3に最も近い数字を投票したプレイヤーが勝者として賞金を得るゲームを美人投票や平均の2/3の推測などと呼びます。美人投票をゲームとして定式化した上で、そのナッシュ均衡を求めます。

完備情報の静学ゲーム