混合ナッシュ均衡を比較的簡単に導出するための具体的な方法を紹介します。

混合ナッシュ均衡

2019年5月18日:公開

混合ナッシュ均衡を導出する際に役立つ命題

混合ナッシュ均衡を導出するのは難しそうに見えますが、以前示した以下の命題を活用すると比較的簡単に導出することができます。

命題(混合ナッシュ均衡の特徴づけ)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、混合戦略の組\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)を選ぶ。このとき、任意のプレイヤー\(i\in I\)について、\(\sigma _{i}^{\ast }\)において正の確率を与えられている任意の純戦略が\(\sigma _{-i}^{\ast }\)に対する最適反応であることは、\(\sigma _{I}^{\ast }\)が\(G^{\ast }\)における混合ナッシュ均衡であるための必要十分条件である。
上の命題について復習する

この命題をどのように利用すればよいのでしょうか。以下では具体的な例を使いながら解説します。

 

混合ナッシュ均衡の導出例(基本)

以下の利得行列で表される完備情報の静学ゲームについて考えます。

$$\begin{array}{ccc}
\hline
1\diagdown 2 & L & R \\ \hline
U & 2,\ 1 & 0,\ 0 \\ \hline
D & 0,\ 0 & 1,\ 2 \\ \hline
\end{array}$$

表:利得行列

プレイヤー\(i\ (=1,2)\)の混合戦略を、\begin{equation*}
\sigma _{i}=(\sigma _{i},1-\sigma _{i})\quad (0\leq \sigma _{i}\leq 1)
\end{equation*}で表します。ただし、\(\sigma _{1}\)は混合戦略\(\sigma _{1}\)のもとでプレイヤー\(1\)が純戦略\(U\)を選ぶ確率\(\sigma _{1}(U)\)であり、純戦略\(D\)を選ぶ確率\(\sigma _{1}\left( D\right) \)は\(1-\sigma _{1}\)です。また、\(\sigma _{2}\)は混合戦略\(\sigma _{2}\)のもとでプレイヤー\(2\)が純戦略\(L\)を選ぶ確率\(\sigma _{2}\left( L\right) \)であり、純戦略\(R\)を選ぶ確率\(\sigma _{2}\left( R\right) \)は\(1-\sigma _{2}\)です。

このゲームには\(\left( U,L\right) \)と\(\left( D,R\right) \)の 2 つの純ナッシュ均衡が存在します。では、それ以外の混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)は存在するでしょうか。

まずは、プレイヤー\(1\)の均衡戦略について\(0<\sigma _{1}^{\ast }<1\)が成り立つ混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定します。\(\sigma _{1}^{\ast }\)は純戦略\(U\)と\(D\)の双方に対して正の確率を付与するということです。\(\sigma _{1}^{\ast }\)は\(\sigma _{2}^{\ast }\)に対する混合最適反応ですが、このとき先の命題より純戦略\(U,D\)はともに\(\sigma _{2}^{\ast }\)に対する最適反応であり、それらは等しい期待利得をもたらします。すなわち、\begin{eqnarray*}
F_{1}\left( U,\sigma _{2}^{\ast }\right) &=&2\sigma _{2}^{\ast }+0\left( 1-\sigma _{2}^{\ast }\right) =2\sigma _{2}^{\ast } \\
F_{1}\left( D,\sigma _{2}^{\ast }\right) &=&0\sigma _{2}^{\ast }+1\left( 1-\sigma _{2}^{\ast }\right) =1-\sigma _{2}^{\ast }
\end{eqnarray*}が等しくなることから\(2\sigma _{2}^{\ast }=1-\sigma _{2}^{\ast }\)すなわち\(\sigma _{2}^{\ast }=\frac{1}{3}\)が成り立ちます。つまり、プレイヤー\(1\)について\(0<\sigma _{1}^{\ast }<1\)が成り立つ混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定する場合には、プレイヤー\(2\)の均衡戦略は\(\sigma _{2}^{\ast }=\frac{1}{3}\)でなければならないということです。

続いて、プレイヤー\(2\)についても同様に考えてみましょう。プレイヤー\(2\)の均衡戦略について\(0<\sigma _{2}^{\ast }<1\)が成り立つ混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定すると、先と同様に考えることにより、純戦略\(L,R\)はともに\(\sigma _{1}^{\ast }\)に対する最適反応であり、それらは等しい期待利得をもたらします。すなわち、\begin{eqnarray*}
F_{2}\left( L,\sigma _{1}^{\ast }\right) &=&1\sigma _{1}^{\ast }+0\left( 1-\sigma _{1}^{\ast }\right) =\sigma _{1}^{\ast } \\
F_{2}\left( R,\sigma _{2}^{\ast }\right) &=&0\sigma _{1}^{\ast }+2\left( 1-\sigma _{1}^{\ast }\right) =2-2\sigma _{1}^{\ast }
\end{eqnarray*}が等しくなることから\(\sigma _{1}^{\ast }=2-2\sigma _{1}^{\ast }\)すなわち\(\sigma _{1}^{\ast }=\frac{2}{3}\)が成り立ちます。つまり、プレイヤー\(2\)について\(0<\sigma _{2}^{\ast }<1\)が成り立つ混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定する場合には、プレイヤー\(1\)の均衡戦略は\(\sigma _{1}^{\ast }=\frac{2}{3}\)でなければならないということです。

ここまでは仮定の話です。そこで、以上の議論から浮かび上がった混合戦略の組\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) =\left( \frac{2}{3},\frac{1}{3}\right) \)が実際に混合ナッシュ均衡であるかどうかを検証します。具体的には、この混合戦略の組から逸脱する動機を持つプレイヤーが存在しないことを示すことになります。

まず、プレイヤー\(1\)にとって\(\sigma _{1}^{\ast }=\frac{2}{3}\)が\(\sigma _{2}^{\ast }=\frac{1}{3}\)に対する最適反応であることを確認します。\(\sigma _{2}^{\ast }=\frac{1}{3}\)に対しては\(F_{1}\left( U,\sigma _{2}^{\ast }\right) =F_{1}\left( D,\sigma _{2}^{\ast }\right) =\frac{2}{3}\)が成り立ちます。つまり、プレイヤー\(1\)は純戦略\(U,D\)のどちらを選んだ場合でも等しい期待利得が得られるため、それらを任意の割合で混ぜてもそれより大きい期待利得は得られません。したがって\(\sigma _{1}^{\ast }\)は\(\sigma _{2}^{\ast }\)に対する最適反応です。

続いて、プレイヤー\(2\)にとって\(\sigma _{2}^{\ast }=\frac{1}{3}\)が\(\sigma _{1}^{\ast }=\frac{2}{3}\)に対する最適反応であることを確認します。\(\sigma _{1}^{\ast }=\frac{2}{3}\)に対しては\(F_{2}\left( \sigma _{1}^{\ast },L\right) =F_{2}\left( \sigma _{1}^{\ast },R\right) =\frac{2}{3}\)が成り立ちます。つまり、プレイヤー\(2\)は純戦略\(L,R\)のどちらを選んだ場合でも等しい期待利得が得られるため、それらを任意の割合で混ぜてもそれより大きい期待利得は得られません。したがって\(\sigma _{2}^{\ast }\)は\(\sigma_{1}^{\ast }\)に対する最適反応です。

混合戦略の組\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) =\left( \frac{2}{3},\frac{1}{3}\right) \)から逸脱することで得するプレイヤーが存在しないことが明らかになったため、これが混合ナッシュ均衡であることが証明されました。

 

混合ナッシュ均衡の導出例(応用)

もう少し複雑な問題を考えます。以下の利得行列で表される完備情報の静学ゲームについて考えます。

$$\begin{array}{cccc}
\hline
1\diagdown 2 & r & s & p \\ \hline
R & 0,0 & 1,-1 & -1,1 \\ \hline
S & -1,1 & 0,0 & 1,-1 \\ \hline
P & 1,-1 & -1,1 & 0,0 \\ \hline
\end{array}$$

表:利得行列

このゲームはジャンケンを表しています。つまり、\(R\)ないし\(r\)はグー(Rock)、\(S\)ないし\(s\)はチョキ(Scissors)、\(P\)ないし\(p\)はパー(Paper)にそれぞれ対応しています。ジャンケンの勝者の利得を\(1\)、敗者の利得を\(-1\)、あいこの場合は両者の利得を\(0\)と定めています。また、2人の混合戦略を、\begin{eqnarray*}
\sigma _{1} &=&(\sigma _{1}\left( R\right) ,\sigma _{1}\left( S\right) ,\sigma _{1}\left( P\right) )=(q_{R},q_{S},1-q_{R}-q_{S}) \\
\sigma _{2} &=&\left( \sigma _{2}\left( r\right) ,\sigma _{2}\left( s\right) ,\sigma _{2}\left( p\right) \right) =(q_{r},q_{s},1-q_{r}-q_{s})
\end{eqnarray*}でそれぞれ表現します。

このゲームには純ナッシュ均衡は存在しません。では、混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)は存在するでしょうか。

まずは、プレイヤー\(1\)の均衡戦略\(\sigma _{1}^{\ast }\)が純戦略\(R,S,P\)をいずれも正の確率で選ぶような混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定します。\(\sigma _{1}^{\ast }\)は\(\sigma _{2}^{\ast }\)に対する混合最適反応ですが、このとき先の命題より純戦略\(R,S,P\)はいずれも\(\sigma _{2}^{\ast }\)に対する最適反応であり、それらは等しい期待利得をもたらします。すなわち、\begin{eqnarray*}
&&F_{1}\left( R,\sigma _{2}^{\ast }\right) =0q_{r}+q_{s}-\left( 1-q_{r}-q_{s}\right) =2q_{s}+q_{r}-1 \\
&&F_{1}\left( S,\sigma _{2}^{\ast }\right) =-q_{r}+0q_{s}+\left( 1-q_{r}-q_{s}\right) =-2q_{r}-q_{s}+1 \\
&&F_{1}\left( P,\sigma _{2}^{\ast }\right) =1q_{r}-q_{s}+0\left( 1-q_{r}-q_{s}\right) =q_{r}-q_{s}
\end{eqnarray*}が等しくなることから\(q_{r}^{\ast }=q_{s}^{\ast }=1-q_{r}^{\ast }-q_{s}^{\ast }=\frac{1}{3}\)が成り立ちます。

続いて、プレイヤー\(2\)についても同様に考えてみましょう。プレイヤー\(2\)の均衡戦略\(\sigma _{2}^{\ast }\)が純戦略\(r,s,p\)をいずれも正の確率で選ぶような混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定すると、先と同様に考えることにより、純戦略\(r,s,p\)はいずれも\(\sigma _{1}^{\ast }\)に対する最適反応であり、それらは等しい期待利得をもたらします。すなわち、\begin{eqnarray*}
&&F_{2}\left( \sigma _{1}^{\ast },r\right) =0q_{R}+q_{S}-\left( 1-q_{R}-q_{S}\right) =2q_{S}+q_{R}-1 \\
&&F_{2}\left( \sigma _{1}^{\ast },s\right) =-q_{R}+0q_{S}+\left( 1-q_{R}-q_{S}\right) =-2q_{R}-q_{S}+1 \\
&&F_{2}\left( \sigma _{1}^{\ast },p\right) =1q_{R}-q_{S}+0\left( 1-q_{R}-q_{S}\right) =q_{R}-q_{S}
\end{eqnarray*}が等しくなることから\(q_{R}^{\ast }=q_{S}^{\ast }=1-q_{R}^{\ast }-q_{S}^{\ast }=\frac{1}{3}\)が成り立ちます。

ここまでは仮定の話です。そこで、以上の議論から浮かび上がった混合戦略の組\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) =\left( \left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) ,\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \right) \)が実際に混合ナッシュ均衡であるかどうかを検証します。具体的には、この混合戦略の組から逸脱する動機を持つプレイヤーが存在しないことを示すことになります。

まず、プレイヤー\(1\)にとって\(\sigma _{1}^{\ast }=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \)が\(\sigma _{2}^{\ast }=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \)に対する最適反応であることを確認します。\(\sigma _{2}^{\ast }=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \)に対しては\(F_{1}\left( R,\sigma _{2}^{\ast }\right) =F_{1}\left( S,\sigma _{2}^{\ast }\right) =F_{1}\left( P,\sigma _{2}^{\ast }\right) =0\)が成り立ちます。つまり、プレイヤー\(1\)は純戦略\(R,S,P\)のどれを選んだ場合でも等しい期待利得が得られるため、それらを任意の割合で混ぜてもそれより大きい期待利得は得られません。したがって、\(\sigma _{1}^{\ast }\)は\(\sigma _{2}^{\ast }\)に対する最適反応です。

続いて、プレイヤー\(2\)にとって\(\sigma _{2}^{\ast }=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \)が\(\sigma _{1}^{\ast }=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \)に対する最適反応であることを確認します。\(\sigma _{1}^{\ast }=\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \)に対しては\(F_{2}\left( \sigma _{1}^{\ast },r\right) =F_{2}\left( \sigma _{1}^{\ast },s\right) =F_{2}\left( \sigma _{1}^{\ast },p\right) =0\)が成り立ちます。つまり、プレイヤー\(2\)は純戦略\(r,s,p\)のどれを選んだ場合でも等しい期待利得が得られるため、それらを任意の割合で混ぜてもそれより大きい期待利得は得られません。

混合戦略の組\(\left( \sigma _{1}^{\ast },\sigma _{2}^{\ast }\right) =\left( \left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) ,\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right) \right) \)から逸脱することで得するプレイヤーが存在しないことが明らかになったため、これが混合ナッシュ均衡であることが証明されました。

これまではプレイヤーが 3 つの純戦略をいずれも正の確率で選ぶような混合戦略を均衡戦略とする混合ナッシュ均衡について考えましたが、プレイヤーが 2 つの純戦略にのみ正の確率を付与するような混合戦略を均衡戦略とする混合ナッシュ均衡は存在するでしょうか。

プレイヤー\(2\)の均衡戦略\(\sigma _{2}^{\ast }\)が純戦略\(r,s\)をともに正の確率で選び、純戦略\(p\)を確率\(0\)で選ぶような混合ナッシュ均衡\((\sigma _{1}^{\ast },\sigma _{2}^{\ast })\)が存在するものと仮定します。このとき、プレイヤー\(1\)について、\begin{eqnarray*}
&&F_{1}\left( R,\sigma _{2}^{\ast }\right) =0q_{r}^{\ast }+q_{s}^{\ast }=q_{s}^{\ast } \\
&&F_{1}\left( S,\sigma _{2}^{\ast }\right) =-q_{r}^{\ast }+0q_{s}^{\ast }=-q_{r}^{\ast }
\end{eqnarray*}が成り立ちます。つまり、プレイヤー\(1\)にとって純戦略\(R\)は純戦略\(S\)よりも大きい期待利得をもたらすため、先の命題より、均衡戦略\(\sigma _{1}^{\ast }\)において\(\sigma _{1}^{\ast }\left( S\right) =0\)が成り立ちます。しかし、これを前提とすると、プレイヤー\(2\)について、\begin{eqnarray*}
&&F_{2}\left( \sigma _{1}^{\ast },r\right) =0q_{R}^{\ast }-q_{P}^{\ast }=-q_{P}^{\ast } \\
&&F_{2}\left( \sigma _{1}^{\ast },s\right) =-q_{R}^{\ast }+q_{P}^{\ast }=-\left( 1-q_{P}^{\ast }\right) +q_{P}^{\ast }=2q_{P}^{\ast }-1
\end{eqnarray*}となります。つまり、プレイヤー\(2\)にとって純戦略\(s\)は純戦略\(r\)よりも大きい期待利得をもたらすため、先の命題より\(\sigma _{2}^{\ast }\left( r\right) =0\)が成り立ちます。つまり、均衡戦略\(\sigma _{2}^{\ast }\)においてプレイヤー\(2\)は純戦略\(s\)を確率\(1\)で選びますが、これは\(\sigma _{2}^{\ast }\)が純戦略\(r,s\)をともに正の確率で選ぶという仮定と矛盾します。

均衡戦略\(\sigma _{2}^{\ast }\)が正の確率で選ぶ2つの純戦略を変えても同様の議論が成立します。また、プレイヤー\(1\)についても同様の議論が成立します。したがって、プレイヤーが 2 つの純戦略にのみ正の確率を付与するような混合戦略を均衡戦略とする混合ナッシュ均衡は存在しません。

次回からナッシュの定理について解説します。
次へ進む 演習問題(プレミアム会員限定)