有限な戦略型ゲームの混合拡張には必ず混合戦略ナッシュ均衡が存在します。これをナッシュの定理と呼びます。角谷の不動点定理を用いてナッシュの定理を証明します。
ナッシュの定理 ナッシュ均衡 角谷の不動点定理

対応の不動点

これまで何度か指摘したように、戦略型ゲーム\(G\)が有限ゲームである場合、その混合拡張\(G^{\ast }\)に必ず混合戦略ナッシュ均衡が存在します。これはナッシュの定理(Nash’s theorem)と呼ばれる命題ですが、今回はこの命題の理論的な根拠を解説します。

集合\(X\)のそれぞれの要素に対して集合\(Y\)の部分集合を1つずつ定める規則を\(X\)から\(Y\)への対応(correspondence)と呼び、これを、\begin{equation*}
f:X\twoheadrightarrow Y
\end{equation*}で表します。また、\(X\)を\(f\)の始集合(initial set)と呼び、\(Y\)を\(f\)の終集合(final set)と呼びます。対応\(f\)が始集合\(X\)の要素\(x\)に対して定める\(Y\)の部分集合を\(f\left( x\right)\)で表し、これを\(f\)による\(x\)の(image)と呼びます。

始集合と終集合がともに同じ集合\(X\)であるような対応\(f:X\twoheadrightarrow X\)に対して、\begin{equation*}
x^{\ast }\in f\left( x^{\ast }\right)
\end{equation*}を満たすような点\(x^{\ast }\in X\)が存在する場合には、この点\(x^{\ast }\)を\(f\)の不動点(fixed point)と呼びます。

例(対応の不動点)
始集合と終集合がともに\(\mathbb{R}\)上の閉区間\(\left[ 0,1\right] \)であるような対応\(f:\left[ 0,1\right] \twoheadrightarrow \left[ 0,1\right] \)を、\begin{equation*}
f\left( x\right) =\left\{
\begin{array}{cc}
\{1\} & if\ x<\frac{1}{2} \\
\left[ 0,1\right] & if\ x=\frac{1}{2} \\
\{0\} & if\ x>\frac{1}{2}\end{array}\right.
\end{equation*}と定義します。点\(\frac{1}{2}\in \left[ 0,1\right] \)に対して、\begin{equation*}
\frac{1}{2}\in \left[ 0,1\right] =f\left( \frac{1}{2}\right)
\end{equation*}が成り立つため、\(\frac{1}{2}\)はこの対応\(f\)の不動点です。

一般に、対応は不動点を持つとは限りません。

例(対応の不動点)
始集合と終集合がともに\(\mathbb{R}\)上の閉区間\(\left[ 0,1\right] \)であるような対応\(f:\left[ 0,1\right] \twoheadrightarrow \left[ 0,1\right] \)を、\begin{equation*}
f\left( x\right) =\left\{
\begin{array}{cc}
\{1\} & if\ x<\frac{1}{2} \\
\{0,1\} & if\ x=\frac{1}{2} \\
\{0\} & if\ x>\frac{1}{2}\end{array}\right.
\end{equation*}と定義します。\(f\)の定義より、任意の点\(x\in \left[ 0,1\right] \)に対して、\begin{equation*}
x\not\in f\left( x\right)
\end{equation*}が成り立つため(確認してください)、この対応\(f\)には不動点が存在しません。

後ほど解説するように、集合\(X\)が\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合である場合、対応\(f:X\twoheadrightarrow X\)に不動点が存在するための条件が知られています。これを角谷の不動点定理(Kakutani’s fixed point theorem)と呼びます。混合戦略ナッシュ均衡を何らかの対応の不動点として表現した上で、その対応が角谷の不動点定理が要求する条件を満たすことを保証できれば、不動点定理により、混合戦略ナッシュ均衡が常に存在することを保証できます。以上がナッシュの定理の証明戦略です。そこで、まずは、混合戦略ナッシュ均衡を対応の不動点として表現します。

 

不動点としての混合戦略ナッシュ均衡

復習になりますが、戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の最適反応は他のプレイヤーたちの戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に依存して変化します。また、それぞれの\(\sigma _{-i}\)に対するプレイヤー\(i\)の最適反応は1つであるとは限りません。以上を踏まえた上で、それぞれの\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に対して、それに対するプレイヤー\(i\)の最適反応からなる\(\Delta \left( S_{i}\right) \)の部分集合\begin{equation*}
b_{i}(\sigma _{-i})=\{\sigma _{i}^{\ast }\in \Delta \left( S_{i}\right) \ |\
F_{i}(\sigma _{i}^{\ast },\sigma _{-i})=\max_{\sigma _{i}\in \Delta \left(
S_{i}\right) }F_{i}(\sigma _{i},\sigma _{-i})\}
\end{equation*}を像として定める対応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)を定義し、これをプレイヤー\(i\)の混合最適反応対応(mixed best response correspondence)や最適反応対応(best response correspondence)などと呼びます。

プレイヤー\(i\)の最適反応対応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)を用いると、プレイヤー\(i\)の混合戦略\(\sigma _{i}^{\ast }\)が他のプレイヤーたちの混合戦略の組\(\sigma _{-i}\)に対する最適反応であることは、\begin{equation*}
\sigma _{i}^{\ast }\in b_{i}\left( \sigma _{-i}\right)
\end{equation*}が成り立つこととして表現可能です。したがって、混合戦略の組\(\sigma _{I}^{\ast }=\left( \sigma _{i}^{\ast }\right) _{i\in I}\)が混合戦略ナッシュ均衡であることとは、\begin{equation*}
\forall i\in I:\sigma _{i}^{\ast }\in b_{i}\left( \sigma _{-i}^{\ast
}\right)
\end{equation*}が成り立つこととして表現可能です。

命題(混合戦略最適反応対応と混合戦略ナッシュ均衡)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、それぞれのプレイヤー\(i\in I\)の混合戦略最適反応対応を\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)で表す。このとき、混合戦略の組\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)について、\begin{equation*}
\forall i\in I:\sigma _{i}^{\ast }\in b_{i}\left( \sigma _{-i}^{\ast
}\right)
\end{equation*}が成り立つことは、\(\sigma _{I}^{\ast }\)が混合戦略ナッシュ均衡であるための必要十分条件である。
証明を見る(プレミアム会員限定)
例(混合戦略最適反応対応)
以下の利得行列で表される戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)について考えます。
$$\begin{array}{ccc}
\hline
1\diagdown 2 & A & B \\ \hline
A & -1,1 & 1,-1 \\ \hline
B & 1,-1 & -1,1 \\ \hline
\end{array}$$
表:利得行列

プレイヤー\(i\ (=1,2)\)の混合戦略\(\sigma _{i}\)を、\begin{equation*}
\left( \sigma _{i}\left( A\right) ,\sigma _{i}\left( B\right) \right)
=(\sigma _{i},1-\sigma _{i})
\end{equation*}で表します。\(0\leq \sigma _{i}\leq 1\)です。プレイヤー\(1\)の最適反応対応\(b_{1}:\Delta \left( S_{2}\right) \twoheadrightarrow \Delta \left( S_{1}\right) \)は、\begin{equation*}
b_{1}\left( \sigma _{2}\right) =\left\{
\begin{array}{cc}
\left\{ 1\right\} & \left( if\ \sigma _{2}<\frac{1}{2}\right) \\
\Delta \left( S_{1}\right) & \left( if\ \sigma _{2}=\frac{1}{2}\right) \\
\left\{ 0\right\} & \left( if\ \sigma _{2}>\frac{1}{2}\right)
\end{array}\right.
\end{equation*}を満たし、プレイヤー\(2\)の最適反応対応\(b_{2}:\Delta \left( S_{1}\right) \twoheadrightarrow \Delta \left( S_{2}\right) \)は、\begin{equation*}
b_{2}\left( \sigma _{1}\right) =\left\{
\begin{array}{cc}
\left\{ 1\right\} & \left( if\ \sigma _{1}<\frac{1}{2}\right) \\
\Delta \left( S_{2}\right) & \left( if\ \sigma _{1}=\frac{1}{2}\right) \\
\left\{ 0\right\} & \left( if\ \sigma _{1}>\frac{1}{2}\right)
\end{array}\right.
\end{equation*}を満たします。このとき、\begin{eqnarray*}
1 &\in &b_{1}\left( 0\right) \\
0 &\in &b_{2}\left( 1\right)
\end{eqnarray*}が成り立つため、\(\left( \sigma _{1},\sigma _{2}\right) =\left( 1,0\right) \)は混合戦略ナッシュ均衡です。また、\begin{eqnarray*}
\frac{1}{2} &\in &b_{1}\left( \frac{1}{2}\right) \\
\frac{1}{2} &\in &b_{2}\left( \frac{1}{2}\right)
\end{eqnarray*}が成り立つため、\(\left( \sigma _{1},\sigma _{2}\right) =\left( \frac{1}{2},\frac{1}{2}\right) \)もまた混合戦略ナッシュ均衡です。さらに、\begin{eqnarray*}
0 &\in &b_{1}\left( 1\right) \\
1 &\in &b_{2}\left( 0\right)
\end{eqnarray*}が成り立つため、\(\left( \sigma _{1},\sigma _{2}\right) =\left( 0,1\right) \)もまた混合戦略ナッシュ均衡です。

プレイヤー集合が有限集合\(I=\left\{ 1,\cdots ,n\right\} \)であるものとします。すべてのプレイヤーの混合戦略最適反応対応\(\left\{ b_{i}\right\} _{i\in I}\)が与えられれば、混合戦略からなるそれぞれの組\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}を像として定める対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義できます。

混合戦略の組\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)がこの対応\(b_{I}\)の不動点であるものとします。すなわち、\begin{equation*}
\sigma _{I}^{\ast }\in b_{I}\left( \sigma _{I}^{\ast }\right)
\end{equation*}が成り立つということです。\(b_{I}\)の定義をもとに上の条件を詳しく書き直すと、\begin{equation*}
\left( \sigma _{1}^{\ast },\cdots ,\sigma _{n}^{\ast }\right) \in
b_{1}\left( \sigma _{-1}^{\ast }\right) \times \cdots \times b_{n}\left(
\sigma _{-n}^{\ast }\right)
\end{equation*}すなわち、\begin{equation*}
\forall i\in I:\sigma _{i}^{\ast }\in b_{i}\left( \sigma _{-i}^{\ast
}\right)
\end{equation*}となりますが、先の命題より、これは\(\sigma _{I}^{\ast }\)が混合戦略ナッシュ均衡であることと必要十分です。

命題(不動点としての混合戦略ナッシュ均衡)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の混合最適反応を\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)で表す。その上で、混合戦略のそれぞれの組\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}を像として定める対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義する。このとき、混合戦略の組\(\sigma _{I}^{\ast }\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
\sigma _{I}^{\ast }\in b\left( \sigma _{I}^{\ast }\right)
\end{equation*}が成り立つこと、すなわち、点\(\sigma _{I}^{\ast }\)が対応\(b_{I}\)の不動点であることは、\(\sigma _{I}^{\ast }\)が\(G^{\ast }\)の混合戦略ナッシュ均衡であるための必要十分条件である。
証明を見る(プレミアム会員限定)

 

角谷の不動点定理

有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)におけるすべてのプレイヤーの混合最適反応対応から新たな対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義した上で、混合戦略ナッシュ均衡をこの対応\(b_{I}\)の不動点として表現することに成功しました。したがって、この対応\(b_{I}\)に不動点が存在することを保証できれば、混合戦略ナッシュ均衡が常に存在することを保証できます。

対応に不動点が存在することを保証するためには、その対応はどのような条件を満たしていればよいのでしょうか。この問いに答えるのが以下の命題です。

命題(角谷の不動点定理)
\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(X\)と対応\(f:X\twoheadrightarrow X\)をそれぞれ任意にとる。このとき、\(X\)は空集合ではなく、コンパクト集合であり、凸集合であるものとする。さらに、\(f\)は非空値をとり、凸値をとり、上半連続性を満たすものとする。このとき\(f\)は不動点を持つ。すなわち、\begin{equation*}
\exists x^{\ast }\in X:x^{\ast }\in f\left( x^{\ast }\right)
\end{equation*}が成り立つ。

角谷の不動点定理が要求する条件を順番に解説します。1つ目の条件は、対応\(f:X\twoheadrightarrow X\)の始集合であるとともに終集合でもある\(X\)が、\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合であるというものです。したがって、そこには位相が設定されています。

2つ目の条件は、集合\(X\)が空集合ではない(nonempty set)こと、すなわち、\begin{equation*}
X\not=\phi
\end{equation*}が成り立つことです。\(X\)が空集合である場合、対応\(f:X\twoheadrightarrow X\)は不動点を持ちえません。

3つ目の条件は、集合\(X\)が\(\mathbb{R} ^{n}\)におけるコンパクト集合(compact set)であることです。コンパクト集合は様々な形で定義可能ですが、ここでは点列を用いた定義を採用します。\(\mathbb{R} ^{n}\)の部分集合\(X\)がコンパクト集合であるとは、\(X\)の要素を項とする任意の点列が\(X\)の点に収束する部分列を持つことを意味します。より正確には、\begin{equation*}
\forall n\in \mathbb{N} :x_{n}\in X
\end{equation*}を満たす点列\(\{x_{n}\}\)を任意に選んだときに、それに対して、\begin{equation*}
\lim_{n\rightarrow \infty }x_{l\left( n\right) }\in X
\end{equation*}を満たす\(\{x_{n}\}\)の部分列\(\{x_{l\left( n\right) }\}\)が存在するということです。

4つ目の条件は、集合\(X\)が\(\mathbb{R} ^{n}\)における凸集合(convex set)であることです。ただし、集合\(X\)が凸集合であるとは、\(X\)に属する2つの点を任意に選んだとき、それらの点を結んで得られる線分上の任意の点もまた\(X\)の点であることを意味します。より正確には、\begin{equation*}
\forall x,x^{\prime }\in X,\ \forall \lambda \in \left[ 0,1\right] :\lambda
x+\left( 1-\lambda \right) x^{\prime }\in X
\end{equation*}が成り立つということです。

5つ目の条件は、対応\(f:X\twoheadrightarrow X\)が非空値をとる(nonempty-valued)ことです。ただし、対応\(f\)が非空値をとるとは、\(X\)に属する任意の点\(x\)の\(f\)による像\(f\left( x\right) \)が非空集合であること、すなわち、\begin{equation*}
\forall x\in X:f\left( x\right) \not=\phi
\end{equation*}が成り立つことを意味します。

6つ目の条件は、対応\(f:X\twoheadrightarrow X\)が凸値をとる(convex-valued)ことです。ただし、対応\(f\)が凸値をとるとは、\(X\)に属する任意の点\(x\)の\(f\)による像\(f\left( x\right) \)が凸集合であること、すなわち、\begin{equation*}
\forall x\in X,\ \forall x^{\prime },x^{\prime \prime }\in f\left( x\right)
,\ \forall \lambda \in \left[ 0,1\right] :\lambda x^{\prime }+\left(
1-\lambda \right) x^{\prime \prime }\in f\left( x\right)
\end{equation*}が成り立つことを意味します。

7つ目の条件は、対応\(f:X\twoheadrightarrow X\)が上半連続(upper hemi-continy)であることです。これは、それぞれの点\(x\in X\)に対して\(f\left( x\right) \subset U\)を満たす\(X\)の開集合\(U\)を任意に選んだときに、それに対して、\begin{eqnarray*}
&&\left( a\right) \ x\in V \\
&&\left( b\right) \ \forall v\in V:f\left( v\right) \subset U
\end{eqnarray*}を満たす\(X\)の開集合\(V\)が存在することを意味します。ただ、角谷の不動点定理は\(\mathbb{R} ^{n}\)の部分集合である\(X\)がコンパクト集合であることを要求しており、そのような場合には対応\(f:X\twoheadrightarrow X\)が上半連続であることを点列を用いて以下のように表現することも可能です。すなわち、\(\mathbb{R} ^{n}\)のコンパクト集合である\(X\)の要素を項とする収束点列\(\{x_{n}\},\{y_{n}\}\)の中でも、\begin{equation*}
\forall n\in \mathbb{N} :y_{n}\in f\left( x_{n}\right)
\end{equation*}を満たすものを任意に選んだとき、これらの点列の極限の間に、\begin{equation*}
\lim_{n\rightarrow \infty }y_{n}\in f\left( \lim_{n\rightarrow \infty
}x_{n}\right)
\end{equation*}という関係が成り立つことは、\(f\)が上半連続であるための必要十分条件です。

例(角谷の不動点定理)
始集合と終集合がともに\(\mathbb{R} \)上の閉区間\(\left[ 0,1\right] \)であるような対応\(f:\left[ 0,1\right] \twoheadrightarrow \left[ 0,1\right] \)を、\begin{equation*}
f\left( x\right) =\left\{
\begin{array}{cc}
\{1\} & if\ x<\frac{1}{2} \\
\left[ 0,1\right] & if\ x=\frac{1}{2} \\
\{0\} & if\ x>\frac{1}{2}\end{array}\right.
\end{equation*}と定義します。集合\(\left[ 0,1\right] \)は\(1\)次元ユークリッド空間\(\mathbb{R} \)の部分集合であるとともに、非空かつコンパクトな凸集合であるため(確認してください)、不動点定理が要求する条件を満たしています。また、\(f\)は非空値かつ凸値をとる上半連続対応であるため(確認してください)、不動点定理が要求する条件を満たしています。したがって、不動点定理より、この対応\(f\)には不動点が存在することが保証されます。実際、\begin{equation*}
\frac{1}{2}\in \left[ 0,1\right] =f\left( \frac{1}{2}\right)
\end{equation*}が成り立つため、\(\frac{1}{2}\)はこの対応\(f\)の不動点です。
例(角谷の不動点定理)
始集合と終集合がともに\(\mathbb{R} \)上の閉区間\(\left[ 0,1\right] \)であるような対応\(f:\left[ 0,1\right] \twoheadrightarrow \left[ 0,1\right] \)を、\begin{equation*}
f\left( x\right) =\left\{
\begin{array}{cc}
\{1\} & if\ x<\frac{1}{2} \\
\left\{ 0,1\right\} & if\ x=\frac{1}{2} \\
\{0\} & if\ x>\frac{1}{2}\end{array}\right.
\end{equation*}と定義します。集合\(\left[ 0,1\right] \)は不動点定理が要求する条件を満たしている一方、\(f\)は凸値をとらず、\(f\)は不動点定理が要求する条件を満たしていません。実際、\(f\)の定義より\(f\left( \frac{1}{2}\right) =\{0,1\}\)ですが、これに対して点\(0,1\in f\left( \frac{1}{2}\right) \)と\(\lambda =\frac{1}{2}\)を選ぶと、\begin{equation*}
\lambda 0+\left( 1-\lambda \right) 1=\frac{1}{2}\cdot 0+\left( 1-\frac{1}{2}\right) 1=\frac{1}{2}
\end{equation*}となり、これは\(f\left( \frac{1}{2}\right) \)の要素ではないため\(f\)は凸値をとりません。したがって、この対応\(f\)の不動点の存在を不動点定理から保証することはできません。ちなみに、この対応\(f\)には不動点は存在しません。

 

ナッシュの定理

有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)におけるすべてのプレイヤーの混合最適反応対応から新たな対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義した上で、混合戦略ナッシュ均衡をこの対応\(b_{I}\)の不動点として表現しましたが、この対応\(b_{I}\)は不動点定理が要求する条件を満たすでしょうか。

対応\(b_{I}\)に対して不動点定理を適用するためには、まず、この対応の始集合であり終集合でもある以下の集合\begin{equation*}
\Delta \left( S_{I}\right) =\Delta \left( S_{1}\right) \times \cdots \times
\Delta \left( S_{n}\right)
\end{equation*}がユークリッド空間の部分集合であるとともに、非空かつコンパクトな凸集合である必要があります。ただ、一般に、非空集合どうしの直積は非空であり、コンパクト集合どうしの直積はコンパクトであり、凸集合どうしの直積は凸であるため、任意のプレイヤー\(i\)の混合戦略集合\(\Delta \left( S_{i}\right) \)が非空かつコンパクトな凸集合であることを示せば、上のように定義される\(\Delta \left( S_{I}\right) \)もまた非空かつコンパクトな凸集合になります。そこで以降では、有限ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\)の混合戦略集合\(\Delta \left( S_{i}\right) \)がユークリッド空間の部分集合であるとともに、非空かつコンパクトな凸集合であることを示します。

例(混合戦略集合)
プレイヤー\(i\)が2個の純粋戦略を持つ場合の混合戦略集合は、\begin{equation*}
\Delta \left( S_{i}\right) =\left\{ \left( \sigma _{i1},\sigma _{i2}\right)
\in
\mathbb{R} ^{2}\ |\ \sigma _{i1}+\sigma _{i2}=1,\ \forall j\in \left\{ 1,2\right\}
:0\leq \sigma _{ij}\leq 1\right\}
\end{equation*}となります。ただし、\(\sigma _{ij}\)は混合戦略\(\sigma _{i}\)が\(j\)番目の純粋戦略\(s_{ij}\)に付与する確率です。この集合は下図において実線で描かれた線分として表現できます。ただし端点を含みます。つまり、この線分上にある点はそれぞれ異なる混合戦略に対応しています。図から明らかであるように、\(\Delta \left( S_{i}\right) \)は\(2\)次元ユークリッド空間\(\mathbb{R} ^{2}\)の部分集合であるとともに、非空かつコンパクトな凸集合です。ちなみに、このような\(\mathbb{R} ^{2}\)の部分集合を1次元の基本単体(standard \(1\) simplex)と呼びます。
図:1次元の基本単体
図:1次元の基本単体
例(混合戦略集合)
プレイヤー\(i\)が3個の純粋戦略を持つ場合の混合戦略集合は、\begin{equation*}
\Delta \left( S_{i}\right) =\left\{ \left( \sigma _{i1},\sigma _{i2},\sigma
_{i3}\right) \in
\mathbb{R} ^{3}\ \left\vert \ \sigma _{i1}+\sigma _{i2}+\sigma _{i3}=1,\ \forall j\in
\{1,2,3\}:0\leq \sigma _{ij}\leq 1\right. \right\}
\end{equation*}となりますが、これは下図においてグレーで描かれた領域として表現できます。ただし境界を含みます。つまり、この領域上にある点はそれぞれ異なる混合戦略に対応しています。図から明らかであるように、\(\Delta \left( S_{i}\right) \)は\(3\)次元ユークリッド空間\(\mathbb{R} ^{3}\)の部分集合であるとともに、非空かつコンパクトな凸集合です。ちなみに、このような\(\mathbb{R} ^{3}\)の部分集合を2次元の基本単体(standard \(2\) simplex)と呼びます。
図:2次元の基本単体
図:2次元の基本単体

問題としている戦略型ゲーム\(G\)は有限ゲームであるため、それぞれのプレイヤー\(i\)は有限個の純粋戦略を持ちます。その個数が\(m\)である場合、混合戦略集合は、\begin{equation*}
\Delta \left( S_{i}\right) =\left\{ \left( \sigma _{i1},\cdots ,\sigma
_{im}\right) \in
\mathbb{R} ^{m}\ \left\vert \ \sum\limits_{j=1}^{m}\sigma _{ij}=1\ ,\forall j\in
\{1,\cdots ,m\}:0\leq \sigma _{ij}\leq 1\right. \right\}
\end{equation*}と定義されます。\(m=1,2\)の場合については先に例で扱いましたが、一般に、この\(\Delta \left( S_{i}\right) \)は\(m\)次元ユークリッド空間\(\mathbb{R} ^{m}\)の部分集合であるとともに、非空かつコンパクトな凸集合になります(演習問題にします)。ちなみに、\(\mathbb{R} ^{m}\)におけるこのような部分集合を\(m-1\)次元の基本単体(standard \(m-1\) simplex)と呼びます。

命題(有限ゲームにおける混合戦略集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)においてプレイヤー\(i\in I\)を任意に選んだとき、プレイヤー\(i\)の純粋戦略集合\(S_{i}\)に有限\(m\)個の純粋戦略が含まれている場合、混合戦略集合\(\Delta \left( S_{i}\right) \)は\(m\)次元ユークリッド空間\(\mathbb{R} ^{m}\)の部分集合であるとともに、非空かつコンパクトな凸集合である。
証明を見る(プレミアム会員限定)

繰り返しになりますが、一般に、非空集合どうしの直積は非空であり、コンパクト集合どうしの直積はコンパクトであり、凸集合どうしの直積は凸であるため、上の命題より以下を得ます。

命題(有限ゲームにおける混合戦略集合の直積)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、以下の集合\begin{equation*}
\Delta \left( S_{I}\right) =\Delta \left( S_{1}\right) \times \cdots \times
\Delta \left( S_{n}\right)
\end{equation*}はユークリッド空間の部分集合であるとともに、非空かつコンパクトな凸集合である。
証明を見る(プレミアム会員限定)

続いて、対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)が非空値をとることを示します。ただ、この対応\(b_{I}\)がそれぞれの\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して定める像は、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}として定義されるため、それぞれのプレイヤー\(i\)の混合最適反応対応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)が非空値をとることを示せば、非空集合どうしの直積もまた非空であることにより、上のように定義される\(b_{I}\)もまた非空値をとります。そこで以降では、有限ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\)の混合最適反応対応\(b_{i}\)が非空値をとることを示します。

プレイヤー\(i\)の混合最適反応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)が他のプレイヤーたちの混合戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に対して定める像は、\begin{equation*}
b_{i}(\sigma _{-i})=\{\sigma _{i}^{\ast }\in \Delta \left( S_{i}\right) \ |\
F_{i}(\sigma _{i}^{\ast },\sigma _{-i})=\max_{\sigma _{i}\in \Delta \left(
S_{i}\right) }F_{i}(\sigma _{i},\sigma _{-i})\}
\end{equation*}です。したがって、それぞれの\(\sigma _{-i}\)に対して、以下の最大化問題\begin{equation*}
\max_{\sigma _{i}\in \Delta \left( S_{i}\right) }F_{i}(\sigma _{i},\sigma
_{-i})
\end{equation*}に必ず解が存在することを証明できれば\(b_{i}(\sigma _{-i})\not=0\)となり、目標を達成したことになります。ここで役立つのが以下の命題です。

命題(最大値・最小値の原理)
\(n\)次元ユークリッド集合\(\mathbb{R} ^{n}\)における非空なコンパクト集合\(X\)上に定義された連続関数\(f:X\rightarrow \mathbb{R} \)は\(X\)において最大値をとる。
証明を見る(プレミアム会員限定)

先の最大化問題の目的関数である\(F_{i}\left( \sigma _{i},\sigma _{-i}\right) \)は混合戦略集合\(\Delta \left( S_{i}\right) \)上に定義された変数\(\sigma _{i}\)に関する関数です。\(\Delta \left( S_{i}\right) \)が非空なコンパクト集合であることは先ほど示したため、あとは\(F_{i}\left( \sigma _{i},\sigma _{-i}\right) \)が変数\(\sigma _{i}\)に関して連続であることを示せば最大値・最小値の原理を利用できます。実際、以下の命題が成り立ちます(演習問題にします)。

命題(期待利得関数の連続性)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\in I\)の期待利得関数\(F_{i}:\Delta \left( S_{I}\right) \rightarrow \mathbb{R} \)をとる。また、他のプレイヤーたちの混合戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)を任意にとる。このとき、関数\(F_{i}\left( \cdot ,\sigma _{-i}\right) :\Delta \left( S_{i}\right) \rightarrow \mathbb{R} \)は連続である。
証明を見る(プレミアム会員限定)

以上の諸命題より、それぞれのプレイヤーの混合最適反応が非空値をとることが示されました。

命題(有限ゲームにおける混合戦略最適反応対応)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\in I\)の混合戦略最適反応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)は非空値をとる。
証明を見る(プレミアム会員限定)

繰り返しになりますが、一般に、非空集合どうしの直積は非空であるため、上の命題から以下が導かれます。

命題(有限ゲームにおける混合戦略最適反応対応の直積)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の混合最適反応を\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)で表す。その上で、混合戦略のそれぞれの組\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}を像として定める対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義する。この対応\(b_{I}\)は非空値をとる。
証明を見る(プレミアム会員限定)

続いて、対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)が凸値をとることを示します。ただ、この対応\(b_{I}\)がそれぞれの\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して定める像は、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}として定義されるため、それぞれのプレイヤー\(i\)の混合最適反応対応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)が凸値をとることを示せば、凸集合どうしの直積もまた凸集合であることにより、上のように定義される\(b_{I}\)もまた凸値をとります。そこで以降では、有限ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\)の混合最適反応対応\(b_{i}\)が凸値をとることを示します。証明のスケッチは以下の通りです。

プレイヤー\(i\)の混合最適反応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)が他のプレイヤーたちの混合戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に対して定める像は、\begin{equation*}
b_{i}(\sigma _{-i})=\{\sigma _{i}^{\ast }\in \Delta \left( S_{i}\right) \ |\
F_{i}(\sigma _{i}^{\ast },\sigma _{-i})=\max_{\sigma _{i}\in \Delta \left(
S_{i}\right) }F_{i}(\sigma _{i},\sigma _{-i})\}
\end{equation*}です。あるプレイヤー\(i\)について、他のプレイヤーたちの混合戦略からなるある組\(\sigma _{-i}\)に対して、上の集合\(b_{i}\left( \sigma _{-i}\right) \)が凸集合ではないものと仮定して矛盾を導きます。つまり、あるプレイヤー\(i\)について、\begin{equation*}
\exists \alpha _{i},\beta _{i}\in b_{i}(\sigma _{-i}),\ \exists t\in \left[
0,1\right] :t\alpha _{i}+\left( 1-t\right) \beta _{i}\not\in b_{i}(\sigma
_{-i})
\end{equation*}が成り立つものと仮定します。\(\sigma _{-i}\)に対する混合最適反応\(\alpha _{i},\beta _{i}\)をある一定の割合で組み合わせて得られる混合戦略\(t\alpha _{i}+\left( 1-t\right) \beta _{i}\)が\(\sigma _{-i}\)に対する混合戦略最適反応にならないということです。しかし、実際には、\begin{equation*}
F_{i}\left( t\alpha _{i}+\left( 1-t\right) \beta _{i},\sigma _{-i}\right)
=F_{i}\left( \alpha _{i},\sigma _{-i}\right) =F_{i}\left( \beta _{i},\sigma
_{-i}\right)
\end{equation*}が成り立つため(確認してください)、\(t\alpha _{i}+\left( 1-t\right) \beta _{i}\)もまた\(\sigma _{-i}\)に対する混合戦略最適反応となり、矛盾です。

命題(有限ゲームにおける混合戦略最適反応対応)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\in I\)の混合戦略最適反応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)は凸値をとる。
証明を見る(プレミアム会員限定)

繰り返しになりますが、一般に、凸集合どうしの直積は凸であるため、上の命題から以下が導かれます。

命題(有限ゲームにおける混合戦略最適反応対応の直積)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の混合最適反応を\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)で表す。その上で、混合戦略のそれぞれの組\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}を像として定める対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義する。この対応\(b_{I}\)は凸値をとる。
証明を見る(プレミアム会員限定)

最後に、対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)が上半連続であることを示します。先に示したように対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)の終集合\(\Delta \left( S_{I}\right) \)はコンパクト集合であるため、\(b_{I}\)が任意の点\(\sigma _{I}\in \Delta \left( S_{I}\right) \)において閉じていることを示せば目標は達成されます。そこで、\(b_{I}\)がある点\(\sigma _{I}\in \Delta \left( S_{I}\right) \)において閉じていないものと仮定して矛盾を導きます。詳細は演習問題にします。

命題(有限ゲームにおける混合戦略最適反応対応の直積)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の混合最適反応を\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)で表す。その上で、混合戦略のそれぞれの組\(\sigma _{I}\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
b_{I}\left( \sigma _{I}\right) =b_{1}\left( \sigma _{-1}\right) \times
\cdots \times b_{n}\left( \sigma _{-n}\right)
\end{equation*}を像として定める対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義する。この対応\(b_{I}\)は上半連続性を満たす。
証明を見る(プレミアム会員限定)

有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、すべてのプレイヤーの混合戦略最適反応対応から新たな対応\(b_{I}:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を定義したとき、この対応は角谷の不動点定理が要求するすべての条件を満たすことが明らかになりました。したがって、この対応\(b_{I}\)には不動点が存在します。この対応\(b_{I}\)の不動点は\(G^{\ast }\)の混合戦略ナッシュ均衡であることは先に指摘した通りです。したがって、有限ゲーム\(G\)の混合拡張\(G^{\ast }\)には混合戦略ナッシュ均衡が必ず存在することが明らかになりました。

命題(ナッシュの定理)

有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)には少なくとも1つの混合戦略ナッシュ均衡が存在する。

証明を見る(プレミアム会員限定)

次回からはナッシュ均衡の性質や正当性などに関する議論を行います。

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

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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

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