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

ナッシュの定理 ナッシュ均衡 角谷の不動点定理

ナッシュの定理の証明戦略

ナッシュの定理とは以下のような主張です。

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

ナッシュの定理を証明するために、角谷の不動点定理を利用します。

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

角谷の不動点定理を利用するために、混合ナッシュ均衡を以下のような不動点として表現します。

命題(不動点としての混合ナッシュ均衡)
戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)の混合最適反応を\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)で表す。その上で、混合戦略のそれぞれの組\(\sigma _{I}=(\sigma _{i})_{i\in I}\in \Delta \left( S_{I}\right) \)に対して、\begin{equation*}
b\left( \sigma _{I}\right) =\prod_{i\in I}b_{i}\left( \sigma _{-i}\right)
\end{equation*}を像として定める対応\(b:\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\)の不動点であることは、\(\sigma ^{\ast }\)が\(G^{\ast }\)の混合ナッシュ均衡であるための必要十分条件である。
ナッシュ均衡と不動点の関係について復習する

ここまでが復習です。上のように定義された対応\(b:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)が角谷の不動点定理が要求する条件をすべて満たすのであれば、角谷の不動点定理を適用することにより、ナッシュの定理を証明したことになります。具体的には、プレイヤーたちの混合戦略集合の直積に相当する集合\(\Delta \left( S_{I}\right) \)については、(1) 空集合ではなく、(2) コンパクト集合であり、(3) 凸集合でもあることを示すとともに、プレイヤーたちの混合最適反応の直積に相当する\(b\)については、(4) 非空値をとり、(5) 凸値をとり、(6) 上半連続性を満たすことを示すことに成功すれば目標を達成したことになります。以下ではこれらを順番に証明します。

 

混合戦略集合の直積は非空集合

有限な戦略型ゲームの混合拡張において、任意のプレイヤーは少なくとも1つの混合戦略を持ちます。有限なゲームにおいて任意のプレイヤーは有限個の純戦略を持ちますが、純戦略は特別な混合戦略でもあることから、この主張の正しさは自明です。

命題(混合戦略集合は非空集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\in I\)の混合戦略集合\(\Delta \left( S_{i}\right) \)は非空集合である。
証明を見る(プレミアム会員限定)

一般に、非空集合どうしの直積もまた非空集合です。したがって、上の命題から以下が導かれます。

系(混合戦略集合の直積は非空集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、すべてのプレイヤーの混合戦略集合の直積\(\Delta \left( S_{I}\right) =\prod_{i\in I}\Delta \left( S_{i}\right) \)は非空集合である。

つまり、すべてのプレイヤーが有限個の純戦略を持っている場合には、すべてのプレイヤーは少なくとも1つの混合戦略を持っていることになるため、すべてのプレイヤーの混合戦略の組が少なくとも1つ存在するということです。

 

混合戦略集合の直積はコンパクト集合

有限な戦略型ゲームの混合拡張において、任意のプレイヤーの混合戦略集合はユークリッド空間上のコンパクト集合になります。

命題(混合戦略集合はコンパクト集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\in I\)の混合戦略集合\(\Delta \left( S_{i}\right) \)はコンパクト集合である。
証明を見る(プレミアム会員限定)

一般に、コンパクト集合どうしの直積もまたコンパクト集合です。したがって、上の命題から以下が導かれます。

系(混合戦略集合の直積はコンパクト集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、すべてのプレイヤーの混合戦略集合の直積\(\Delta \left( S_{I}\right) =\prod_{i\in I}\Delta \left( S_{i}\right) \)はコンパクト集合である。

 

混合戦略集合の直積は凸集合

続いて、プレイヤーの混合戦略集合がユークリッド空間上の凸集合になることを示しますが、その前にこの性質の意味を確認します。一般に、\(n\)次元空間\(\mathbb{R} ^{n}\)の部分集合\(X\)が凸集合であるとは、任意の点\(x,y\in X\)と任意の\(t\in \left[ 0,1\right] \)に対して、\begin{equation*}
tx+\left( 1-t\right) y\in X
\end{equation*}が成り立つことを意味します。つまり、\(X\)に属する 2 つの点を任意に選んだとき、それらを任意の割合で混ぜて得られる新たな点もまた\(X\)の点になるということです。

凸集合の定義を踏まえた上で、混合戦略集合が凸集合であることの意味について考えましょう。話を分かりやすくするために、プレイヤー\(i\)は
2 つの純戦略を持つ場合を想定します。この場合、プレイヤー\(i\)の混合戦略集合は、\begin{equation*}
\Delta \left( S_{i}\right) =\left\{ \left( \sigma _{i1},\sigma _{i2}\right)
\in \mathbb{R} ^{2}\ |\ \sigma _{i1}+\sigma _{i2}=1,\ 0\leq \sigma _{i1}\leq 1\ 0\leq \sigma _{i2}\leq 1\right\}
\end{equation*}と定義されます。この集合に属する混合戦略を 2 つ任意に選びます。例えば、\(\left( \frac{1}{2},\frac{1}{2}\right) \)と\(\left( \frac{1}{3},\frac{2}{3}\right) \)を選びましょう。例えば、これらを\(3:1\)の割合で混ぜると、\begin{equation*}
\frac{3}{4}\left( \frac{1}{2},\frac{1}{2}\right) +\frac{1}{4}\left( \frac{1}{3},\frac{2}{3}\right) =\left( \frac{11}{24},\frac{13}{24}\right)
\end{equation*}となりますが、これは確率分布としての要件を満たしているため混合戦略です。混合戦略集合\(\Delta \left( S_{i}\right) \)が凸集合であることは、その中から 2 つの混合戦略を任意に選び、それらを任意の割合で混ぜても同じ議論が成り立つことを意味します。

有限な戦略型ゲームの混合拡張においてプレイヤーの混合戦略集合が凸集合になることは、プレイヤーが任意の有限個の純戦略を持つ場合にも上と同様の議論が成り立つことを意味します。プレイヤーが有限個の純戦略を持つ場合には、そのプレイヤーの混合戦略を 2 つ任意に選び、それらを任意の割合で混ぜると、得られるものもまた混合戦略になるということです。

命題(混合戦略集合は凸集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、任意のプレイヤー\(i\in I\)の混合戦略集合\(\Delta \left( S_{i}\right) \)は凸集合である。
証明を見る(プレミアム会員限定)

一般に、非空な集合どうしの直積もまた凸集合になります。したがって、上の命題から以下が導かれます。

系(混合戦略集合の直積は凸集合)
有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、すべてのプレイヤーの混合戦略集合の直積\(\Delta \left( S_{I}\right) =\prod_{i\in I}\Delta \left( S_{i}\right) \)は凸集合である。

つまり、すべてのプレイヤーの純戦略の個数が有限であれば、すべてのプレイヤーの混合戦略の組を2つ任意に選び、それらを任意の割合で混ぜると、それもまたプレイヤーたちの混合戦略の組になるということです。

 

混合最適反応対応の直積は非空値をとる

まずは、それぞれのプレイヤー\(i\)の混合最適反応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)が非空値をとることを示します。つまり、有限な戦略型ゲームにおいてプレイヤーたちが混合戦略を採用するとき、任意のプレイヤーは、他のプレイヤーたちの混合戦略の組に対する最適戦略を必ず持つということです。

さて、プレイヤー\(i\)の混合最適反応\(b_{i}\)が他のプレイヤーたちの混合戦略の組\(\sigma _{-i}\)に対して定める像は、\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) \)に対して\(b\left( \sigma _{I}\right) =\prod_{i\in I}b_{i}\left( \sigma _{-i}\right) \)を像として定める対応\(b:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)は非空値をとる。

 

混合最適反応対応の直積は凸値をとる

それぞれのプレイヤー\(i\)の混合最適反応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)が凸値をとることを示します。つまり、他のプレイヤーたちの混合戦略の組\(\sigma _{-i}\)を任意に選んだとき、それに対するプレイヤー\(i\)の混合最適反応からなる集合\(b_{i}\left( \sigma _{-i}\right) \)は凸集合になるという主張です。

命題(混合最適反応対応は凸値をとる)
有限な戦略型ゲーム\(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) \)に対して\(b\left( \sigma _{I}\right) =\prod_{i\in I}b_{i}\left( \sigma _{-i}\right) \)を像として定める対応\(b:\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) \)に対して\(b\left( \sigma _{I}\right) =\prod_{i\in I}b_{i}\left( \sigma _{-i}\right) \)を像として定める対応\(b:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)は上半連続性を満たす。
証明を見る(プレミアム会員限定)

以上で角谷の不動点定理が要求するすべての条件が成り立つことが示されたため、ナッシュの定理の証明が完了しました。

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

次へ進む 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
Share on print

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するためにはログインが必要です
ログイン

現在地
目次
アカウント
ログイン