Game Theory 101

不動点定理（Kakutani）
点を集合に対応させる関数をコンパクト凸な定義域で考える。もし値域が定義域と同じ集合に含まれ、かつ関数が連続ならば、関数は必ず不動点をもつ。

前回、アイとノノの簡単なゲームに角谷が適用できるということを説明しましたが、プレーヤーと戦略の数が増えても角谷の定理は使えます。そしてこのことが角谷を応用してナッシュの定理を証明するということなのです。

定理（Nash）
ゲームを混合戦略の範囲で考える。プレーヤーの数とその純粋戦略の数が有限ならば、ナッシュ均衡は必ず存在する。

3人の囚人のジレンマを考えましょう。戦略は協調する確率だけで表わされるので、戦略の組み合わせは (p, q, r) と書くことができます。

このゲームのナッシュ均衡は (p, q, r) = (0, 0, 0) です。（裏切りが支配戦略なので。）

いま3人の戦略の組み合わせ (p, q, r) に対し、最適反応の組み合わせを返す関数をFとします。（ここでの最適反応とは他の2人の戦略の組に対するものです。たとえば (q, r) = (1, 1) に対しては p=0 が最適反応。）

などの対応があります。（いちおう形式的に確認してみてください。）

こういうときでも角谷の定理はそのまま何も考えずに適用できて、Fには不動点があることが言えます。じっさい (0, 0, 0) が不動点になります。

つぎにアイとノノのじゃんけんゲームを考えてみましょう。

アイとノノの戦略の組み合わせは (p₁, p₂, q₁, q₂) と書くことができます。（パーの比率は自動的に決まるので。ただし p₁+p₂≦1, q₁+q₂≦1 です。）

このゲームのナッシュ均衡は階段じゃんけんで計算したように (p₁, p₂, q₁, q₂) = (2/8, 5/8, 2/8, 5/8) です。

いまアイとノノの戦略の組み合わせ (p₁, p₂, q₁, q₂) に対し、最適反応の組み合わせを返す関数をFとします。

(1, 0, 0, 0) → (0, 1, 0, 0)
(0, 1, 1, 0) → (0, 0, 1, 0)
(2/8, 5/8, 2/8, 5/8) → ([0, 1], [0, 1], [0, 1], [0, 1])

などの対応があります。（また確認してみてください。たすきがけの要領です。）

こういう関数でも角谷の定理はやはりそのまま適用できて、Fには不動点があることが言えます。じっさい (2/8, 5/8, 2/8, 5/8) が不動点になります。（ (2/8, 5/8, 2/8, 5/8) ∈ ([0, 1], [0, 1], [0, 1], [0, 1]) ）

最後に3人がそれぞれ同じ3つの戦略 L, C, R をもつゲームを考えてみましょう。たとえば L, C, R は3人の待ち合わせ場所だとします。

3人の戦略の組み合わせは (p₁, p₂, q₁, q₂, r₁, r₂) と書くことができます。（たとえばp₁はプレーヤー1がLをとる確率。ただし p₁+p₂≦1, q₁+q₂≦1, r₁+r₂≦1 です。）

そしてこれに最適反応の組み合わせを返す関数をFとすると、 Fには

(1, 0, 1, 0, 1, 0) → (1, 0, 1, 0, 1, 0)
(0, 0, 0, 0, 0, 0) → (0, 0, 0, 0, 0, 0)
(1, 0, 1, 0, 0, 1) → (any, any, any, any, 1, 0)

などの対応があります。（any は [0, 1] の意味。）待ち合わせなので同じ戦略をとるのがいいのです。また他の2人がバラバラなら、どこに行っても同じです。

3×3ゲームでも角谷の定理は無条件に使えて、Fには不動点があることが言えます。じっさい (1, 0, 1, 0, 1, 0) などが不動点になります。

このように複数プレーヤー・複数戦略のゲームにも角谷の不動点定理があてはまるわけです。

詳しい説明は難しいのでここではしませんが、ナッシュの定理の条件＜有限プレーヤー・有限戦略＞というのはつねに角谷の条件＜コンパクト凸・連続＞を満たすのです。それゆえナッシュの定理は角谷の定理を使って証明できるのです。

全6回にわたりましたが、以上でナッシュ均衡と不動点定理（Kakutani）の関係はつかめてもらえたと思います。

Kakutani's Fixed Point Theorem
Let S be any nonempty, convex, bounded, and closed subset of a finite-dimensional vector space. Let F: S→S be any upper-hemicontinuous point-to-set correspondence such that, for every x in S, F(x) is a nonempty convex subset of S. Then there exists some x^* in S such that x^*∈F(x^*).