ナッシュの定理の証明戦略はいくつか存在しますが、最も代表的なものは角谷の不動点定理を利用するアプローチです。そこで以下ではナッシュの定理を証明するための数学的準備として、角谷の不動点定理について解説します。

2019年5月19日:公開

ナッシュ均衡と不動点定理

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

混合ナッシュ均衡について復習する

ナッシュの定理の証明戦略はいくつか存在しますが、最も代表的なものは角谷の不動点定理(Kakutani’s fixed point theorem)を利用するアプローチです。そこで以下ではナッシュの定理を証明するための数学的準備として、角谷の不動点定理について解説します。

 

対応の不動点

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

対応について詳しく学ぶ

以下では始集合と終集合がともに同じ集合\(X\)であるような特別な対応\(f:X\twoheadrightarrow X\)について考えます。このような対応\(f:X\twoheadrightarrow X\)に対して\(x^{\ast }\in f\left( x^{\ast }\right) \)を満たすような点\(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\)の不動点です。

特に、集合\(X\)が\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合である場合には、対応\(f:X\twoheadrightarrow X\)に不動点が存在するための条件が知られています。これを角谷の不動点定理(Kakutani’s fixed point theorem)と呼びます。

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

以下ではこの命題について解説します。

 

角谷の不動点定理が集合に要求する条件

角谷の不動点定理が主張するように、対応\(f:X\twoheadrightarrow X\)が不動点を持つことを保証するためには\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合である\(X\)が 3 つの条件を満たす必要があります。

1つ目の条件は集合\(X\)が空集合ではない(nonempty set)こと、すなわち、\begin{equation*}
X\not=\phi
\end{equation*}が成り立つことです。

2つ目の条件は集合\(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) }\}\)が存在するということです。

3つ目の条件は集合\(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*}が成り立つということです。

 

角谷の不動点定理が対応に要求する条件

対応\(f:X\twoheadrightarrow X\)が不動点を持つことを保証するためには\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(X\)が上記の3つの条件を満たすことに加えて、対応\(f\)が以下の3つの条件を満たす必要があります。

1つ目の条件は対応\(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*}が成り立つことを意味します。

2つ目の条件は対応\(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*}が成り立つことを意味します。

3つ目の条件は対応\(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\)が上半連続であるための必要十分条件です。

 

角谷の不動点定理

\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(X\)と対応\(f:X\twoheadrightarrow X\)が上記の6個の条件を満たす場合には、\(f\)は必ず不動点を持ちます。これが角谷の不動点定理の主張です。

命題(角谷の不動点定理)
\(X\)は\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の空でないコンパクトな凸部分集合であるとする。さらに、対応\(f:X\twoheadrightarrow X\)は非空値かつ凸値をとり、上半連続性を満たすものとする。このとき、\(f\)は不動点を持つ。すなわち、\(x^{\ast }\in f\left( x^{\ast }\right) \)を満たす点\(x^{\ast }\in X\)が少なくとも 1 つ存在する。
例(角谷の不動点定理)
\(\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\)は不動点を持ちます。実際、点\(\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*}と定義します。集合\(\left[ 0,1\right] \)は角谷の不動点定理が要求する条件を満たしていますが、\(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 }\)には必ず混合ナッシュ均衡が存在するという主張です。さて、混合拡張\(G^{\ast }\)から何らかの形で\(n\)次元ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(X\)と対応\(f:X\twoheadrightarrow X\)を定義し、さらに、その対応\(f\)の不動点として混合ナッシュ均衡を表現できたとします。さらに、その集合\(X\)と対応\(f\)が角谷の不動点定理が要求する条件をすべて満たすのであれば、混合拡張\(G^{\ast }\)には混合ナッシュ均衡が必ず存在することを示したことになります。以上がナッシュの定理の証明戦略です。

そこで次回は、混合ナッシュ均衡を対応の不動点として表現します。
次へ進む 演習問題(プレミアム会員限定)