角谷の不動点定理を用いてナッシュの定理を証明するための準備として、ナッシュ均衡を不動点として表現します。

< 前のページ
次のページ >

不動点としての純ナッシュ均衡

戦略型ゲーム\(G\)において、プレイヤー\(i\in I\)以外のプレイヤーたちの純戦略の組\(s_{-i}\in S_{-i}\)に対するプレイヤー\(i\)の純最適反応は一意的に定まるとは限りません。そこで、\(s_{-i}\)に対するプレイヤー\(i\)の純最適反応からなる集合を、\begin{equation*}
b_{i}(s_{-i})=\{s_{i}^{\ast }\in S_{i}\ |\ u_{i}(s_{i}^{\ast },s_{-i})=\max_{s_{i}\in S_{i}}u_{i}(s_{i},s_{-i})\}
\end{equation*}で表します。その上で、プレイヤー\(i\)以外のプレイヤーたちの純戦略のそれぞれの組\(s_{-i}\in S_{-i}\)に対して,プレイヤー\(i\)の純最適反応からなる集合\(b_{i}(s_{-i})\subset S_{i}\)を定める対応\(b_{i}:S_{-i}\twoheadrightarrow S_{i}\)をプレイヤー\(i\)の最適反応対応(best response correspondence)や純最適反応対応(pure best response correspondence)などと呼びます。

純最適反応について復習する

すべてのプレイヤーの最適反応対応\(\{b_{i}\}_{i\in I}\)が与えられれば、純戦略のそれぞれの組\(s_{I}=\left( s_{i}\right) _{i\in I}\in S_{I}\)に対して、\begin{eqnarray*}
b\left( s_{I}\right) &=&\prod_{i\in I}b_{i}\left( s_{-i}\right) \\
&=&b_{1}\left( s_{-1}\right) \times \cdots \times b_{n}\left( s_{-n}\right)
\end{eqnarray*}を像として定める対応\(b:S_{I}\twoheadrightarrow S_{I}\)を構成できます。純ナッシュ均衡はこの対応\(b\)の不動点として特徴づけられます。

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

戦略型ゲーム\(G\)の純ナッシュ均衡を上のように定義された対応\(b:S_{I}\twoheadrightarrow S_{I}\)の不動点として表現したとき、角谷の不動点定理を適用するためには集合\(S_{I}\)と対応\(b\)は角谷の不動点定理が要求する条件を満たしていなければなりません。その中の条件の1つは\(S_{I}\)がコンパクト集合であるというものです。

角谷の不動点定理について復習する

\(S_{I}\)はすべてのプレイヤーの純戦略集合の直積ですが、そもそもそれぞれのプレイヤー\(i\)の純戦略集合\(S_{i}\)には位相が設定されていないため、それらの直積である\(S_{I}\)はコンパクト集合であるとは限りません。したがって、この対応\(b\)に角谷の不動点定理を適用することはできません。言い換えると、戦略型ゲーム\(G\)に純ナッシュ均衡が存在することを不動点定理を使って証明することはできないということです。他の方法によって純ナッシュ均衡の存在を保証できるように考えるかもしれませんが、以下の例が示すように、戦略型ゲームには純ナッシュ均衡は存在するとは限りません。

例(純ナッシュ均衡)
以下の利得行列で表される完備情報の静学ゲームについて考えます。

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

表:利得行列

表にはそれぞれのプレイヤーが純最適反応を選んだときに自身が得る利得に下線を引いてあります。表から明らかであるように純最適反応の組は存在しないため、このゲームには純ナッシュ均衡が存在しません。

 

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

ナッシュの定理とは、有限な戦略型ゲームの混合拡張には必ず混合ナッシュ均衡が存在するという主張です。この主張の正しさを角谷の不動点定理を用いて証明するために、準備として混合ナッシュ均衡を対応の不動点として表現します。

戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)において、プレイヤー\(i\in I\)以外のプレイヤーたちの混合戦略の組\(\sigma _{-i}\in \Delta \left( S_{-i}\right)\)に対するプレイヤー\(i\)の混合最適反応は一意的に定まるとは限りません。そこで、\(\sigma _{-i}\)に対するプレイヤー\(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 S_{i}}F_{i}(\sigma _{i},\sigma _{-i})\}
\end{equation*}で表します。その上で、プレイヤー\(i\)以外のプレイヤーたちの混合戦略のそれぞれの組\(\sigma _{-i}\in \Delta \left( S_{-i}\right) \)に対して、プレイヤー\(i\)の混合最適反応からなる集合\(b_{i}\left( \sigma _{-i}\right) \subset \Delta \left( S_{i}\right) \)を定める対応\(b_{i}:\Delta \left( S_{-i}\right) \twoheadrightarrow \Delta \left( S_{i}\right) \)をプレイヤー\(i\)の最適反応対応(best response correspondence)や混合最適反応対応(mixed best response correspondence)などと呼びます。

混合最適反応について復習する

すべてのプレイヤーの最適反応対応\(\{b_{i}\}_{i\in I}\)が与えられれば、混合戦略のそれぞれの組\(\sigma _{I}=\left( \sigma _{i}\right) _{i\in I}\in \Delta \left( S_{I}\right) \)に対して、\begin{eqnarray*}
b\left( \sigma _{I}\right) &=&\prod_{i\in I}b_{i}\left( \sigma _{-i}\right) \\
&=&b_{1}\left( \sigma _{-1}\right) \times \cdots \times b_{n}\left( \sigma _{-n}\right)
\end{eqnarray*}を像として定める対応\(b:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)を構成できます。混合ナッシュ均衡はこの対応\(b\)の不動点として特徴づけられます。

命題(不動点としての混合ナッシュ均衡)
戦略型ゲーム\(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 }\)の混合ナッシュ均衡であるための必要十分条件である。
証明を見る(プレミアム会員限定)

有限な戦略型ゲーム\(G\)の混合拡張\(G^{\ast }\)の混合ナッシュ均衡を上のように定義された対応\(b:\Delta \left( S_{I}\right) \twoheadrightarrow \Delta \left( S_{I}\right) \)の不動点として表現したとき、角谷の不動点定理を適用するためには集合\(\Delta \left( S_{I}\right) \)と対応\(b\)が角谷の不動点定理が要求する条件を満たしていなければなりません。次回はそのことを確認することでナッシュの定理を証明します。

次へ進む 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
Share on print
< 前のページ
次のページ >

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

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

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

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

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