先日、予備校のノリで学ぶ「大学の数学・物理」さん(以下、ヨビノリさん)のYouTubeチャンネルにて、ゲーム理論 に関する動画が公開されました。
ゲーム理論に関する基本的な用語について、大変わかりやすく紹介されているのでぜひご覧になってください。ゲーム理論において、重要な「解」概念である「ナッシュ均衡点」や「パレート効率」といった概念も紹介されていました。
さて、今回私の記事で紹介したいテーマは 「ナッシュ均衡点の存在性」 についてです。(混合戦略を考えない)純粋戦略のゲームにおいては、ナッシュ均衡点の存在しないゲームが存在します。具体的には、動画にも紹介された「じゃんけんゲーム」などがそうですね。
A\B | グー | チョキ | パー |
---|---|---|---|
グー | |||
チョキ | |||
パー |
一方で、(これもまた動画内で触れられていますが)混合戦略 という、各プレーヤーが戦略を確率的に選ぶような状況に ゲームを拡大 すると、なんと 必ずナッシュ均衡点が存在する ということが知られています。
これは大変興味深い定理かと思います。
もちろん、ナッシュ自身が「ナッシュ均衡点」と呼んだわけではありません。ナッシュがこの定理を示したからナッシュ均衡点という名前がついたわけですね。そして今やゲーム理論における超重要概念になっています。
tsujimotterは、三年ぐらい前からこの定理の証明をブログに書きたいと思っていました。しかしながら、ゲーム理論の基本的な設定を説明するのが面倒で、断念しておりました。ヨビノリさんの動画をみて、これはすばらしい、ぜひ乗っからせていただこう!と思ったのが執筆の経緯です。笑
ヨビノリさんの素晴らしい動画に感謝しつつ、証明を紹介させていただきます。
なお「ナッシュの定理」の証明には、不動点定理 という定理が使われていまして、その定理の使いどころが今回の記事の一番のポイントになります。不動点定理自体の証明について今回はやりませんが、いったいどうやってナッシュ均衡点の存在を導くのかという点に着目して楽しんで頂ければと思います。
元々はヨビノリさんの動画からシームレスにつながるようなレベル感の記事にしようと思っていたのですが、どうもそれは難しそうです。内容が単純に難しいのです・・・。というわけで、それなりに数式も多くなってしまいますが、数学(特に集合と写像)にある程度慣れている人には読めるものにはなっているかと思います。
以前からゲーム理論を知っていた方でも、(ナッシュの定理の)証明は知らないという方も多いのではないでしょうか。有名な定理なので、一度はその証明に触れてみたいですよね。これを機にぜひ味わっていただきたいと思います。
最後まで通して読むのにはなかなか時間がかかると思いますので、読んでいる途中でも構いませんので
- 「(途中までしか読んでないけど)面白い!」とか
- 「ナッシュやばい!!」とか
- 「ベイマックスwww」とか
呟いていただけると嬉しいです。
それでは、じっくりお楽しみください!
目次:
1. ゲームの数学的定義
ヨビノリさんの動画は「数式なし」の解説をされていました。今回の記事は「証明の理解」が目的なので、数式を使ってゲーム理論を定式化していく必要があります。そのための準備をしたいと思います。
1-1. 標準形ゲーム
まず、標準形ゲーム を定義したいと思います。一般にゲームは、プレーヤー集合・各プレーヤーの戦略集合・各プレーヤーの利得関数の3点により定義されます。
(a) プレーヤー集合
人のプレーヤーの集合を
とします。任意のプレーヤーを取り出して表すときは、この集合の要素として と表します。
(b) 各プレーヤーの戦略集合
プレーヤー の戦略集合を
とします。じゃんけんゲームであれば、グーが 、チョキが 、パーが みたいな感じですね。プレーヤー一人一人の戦略が異なる状況も想定されるので、戦略集合はプレーヤーごとに設定します。
したがって、プレーヤー全体の戦略の組み合わせは、直積集合
で表せることになりますね。
(c) 各プレーヤーの利得関数
任意の戦略の組み合わせ に対して、プレーヤー の利得が決まります。よって、実数値関数
を、プレーヤー の利得関数としましょう。各プレーヤーの戦略の組 が与えられると、プレーヤー の利得 という実数値が定まります。
これで有限個の戦略を持つ標準形ゲームが定義されました。
(d) 具体例:囚人のジレンマ
ヨビノリさんの動画の「囚人のジレンマ」の例を利用しましょう。プレーヤー集合を
として、各プレーヤーの戦略集合はどちらも共通の集合
をとります。( が「黙秘」、 が「自白」という対応関係ですね。)
また、囚人のジレンマにおける利得関数の定義は次のようになります。
これは下記の利得表に対応していますので、確認してみてください。
A\B | 「黙秘」 | 「自白」 |
---|---|---|
「黙秘」 | ||
「自白」 |
1-2. 混合戦略ゲーム
ここからは 混合戦略 を定義したいと思います。
混合戦略のイメージとしては、標準形ゲームの各戦略を確率的に選ぶような感じです。簡単のために、プレーヤー が1人でプレーする「相手のいないゲーム」を考えてみましょう。利得としては
とします。つまり、戦略 を選ぶと利得が であり、戦略 を選ぶと利得が になる状況を考えるわけですね。右に行ったらゴール、左に行ったら落とし穴みたいなゲームですかね。(何が面白いんだろう、このゲーム。)
ここでプレーヤー が、右にいく確率を として、左にいく確率を とします。この確率のペア 自体を戦略だと思うことにしましょう。これを混合戦略と言います。プレーヤーの選択は確率に従うので、それぞれの戦略を選択する確率の和は となることに注意しましょう。
すると、プレーヤー が混合戦略 をとったとき、得られる利得(の期待値)は
となりますね。これが混合戦略における利得関数というわけです。
一方で、「確率 で戦略 を選ぶ(確率 で戦略 を選ぶ)」のようなものも、立派な混合戦略です。この場合 のように表現します。特に、このような混合戦略のことを純粋戦略といいます。
それでは、標準形ゲームの混合戦略への拡大を以下で定義します。
(a) プレーヤー集合
まず、プレーヤーの集合は変わらず
です。
(b) 各プレーヤーの戦略集合
次に、プレーヤー の混合戦略に拡大した戦略集合 ですが、プレーヤー が戦略 を選ぶ確率を 、戦略 を選ぶ確率を 、・・・のように定義していきます。最終的に、戦略それぞれに対しての選択確率の和は
となることに注意しましょう。したがって、プレーヤー の混合戦略の集合は
となります。だいぶややこしい集合ですが、意味するところは上で説明した通りです。
ちなみに、この集合 は数学的には「単体(simplex)」と呼ばれる集合になっています。 次元空間における「三角形」を表す図形なのですが、具体的に図示してみるとイメージしやすいかもしれません:
(戦略数: )のときは「点」(図左)、
(戦略数: )のときは「線分」(図中央)、
(戦略数: )のときは「三角形」(図右)
よって、プレーヤー全体の混合戦略の組み合わせは、 の直積となりますので
ということですね。
(c) 各プレーヤーの利得関数
プレーヤー の利得関数は、関数 だと思うことができます。 は、次で定義されます:
添え字が多くてややこしいですね。要するに、下線部が(純粋)戦略 が選択される確率を表していて、このときの期待利得が計算されているというわけです。総和記号は のすべての組に対する和をとっています。
(d) 具体例:じゃんけんの混合戦略
しばらく抽象的な議論が続いたので具体例を挟みます。じゃんけんゲームの時には、プレーヤー の取れる混合戦略は
- :「グー」を選択する確率
- :「チョキ」を選択する確率
- :「パー」を選択する確率
の組 となります。ここで、プレーヤー の混合戦略をどちらも
としてみましょう。これは、グー・チョキ・パーをそれぞれ確率 で出すということです。完全にランダムに出すということですね。
実は、上記の「確率 の混合戦略」をお互いに選択する解が、じゃんけんの混合戦略におけるナッシュ均衡点となっています。証明はしないですが、なんとなく直感的に正しそうですよね。そりゃ均等に出した方が良さそうです。
これによって標準形ゲームのときにはナッシュ均衡が存在しなかったじゃんけんゲームですが、混合戦略に拡大したことによってナッシュ均衡が現れたわけです。これが一般の有限ゲームについてに成り立つというのが、ナッシュの定理の主張ですね。
これは余談ですが、人間が完全にランダムで手を出すのは難しいみたいですね。だいたいみんな何かしらの出す手の傾向があって、それにしたがって手を出しているそうです。この傾向を機械に学習させてしまうと、人間が勝てなくなるみたいな実験があったのを聞いた覚えがあります。
1-3. その他、証明に必要な概念の導入
さて、これにて基本的な設定が定義できました。証明のためにはもうちょっとだけ道具が必要になりますので、もうしばらくお付き合いください。
まず、混合戦略の組を表す便利な表現を導入します。プレーヤー の戦略を としたとき
がすべてのプレーヤーの混合戦略の組を表します。ベクトルのようなものだと思ってくれていいのですが、1プレーヤーの混合戦略 自体は「各戦略を選択する確率の組」になっていることに注意しましょう。
また、特定のプレーヤー に着目したときに、 の要素を とそれ以外に分けて
と表現することがあります。 は 番目の要素以外のすべて要素の組だと思ってください。こうしておくと、 番目のプレーヤーだけ混合戦略を置き換える、みたいなことができるわけですね。これは大変便利な表現なので多用します。
これを使うと、ナッシュ均衡点の定義 が簡便に表現できます。
を満たすことをいう。
つまり、他のプレーヤーの混合戦略を に固定しつつ、プレーヤー の混合戦略だけを動かしたとき、プレーヤー にとっては が最適応答戦略になっている。これが全プレーヤーに対して成り立つ状況がナッシュ均衡点というわけですね。
次に、 上で定義される関数 を次のように定義しましょう。 に対して
と定義します。ここで、 とします。これは 番目だけ 、それ以外は であるような組です。意味としては「確率 で戦略 を選択する」というプレーヤー の純粋戦略を表現するものだと思ってください。
の部分だけ取り出すと
- は混合戦略の組 におけるプレーヤー が受け取る期待利得
- は混合戦略の組 に対して、プレーヤー だけ戦略 の純粋戦略に置き換えたときに、プレーヤー が受け取る期待利得
を表します。この差をとっていますので、(他のプレーヤーの戦略そのままに)プレーヤー だけ戦略 の純粋戦略に置き換えたときの期待利得の差を表しているわけです。
これと のmaxをとっているので、これが正であれば に値が現れるわけですね。それ以外のときは の値をとる関数です。
2. ブラウアーの不動点定理とその使いどころ
さて、定理の証明の一つのキーポイントとして、不動点定理 を紹介します。
一口に不動点定理といっても、実は色々なバリエーションがあります:
- ブラウアーの不動点定理
- 角谷の不動点定理(ブラウアーの不動点定理の一般化)
ナッシュ均衡の証明にも色々なバリエーションがあり、それぞれ使用する不動点定理が異なります。
ナッシュ自身は、最初は「角谷の不動点定理」を用いた証明を発表したようです。その後、証明を改良して、博士論文やThe Annals of Mathematicsに掲載された論文においては、「ブラウアーの不動点定理」を直接使った証明を紹介しています。今回はこちらの方法を紹介したいと思います。
つまり、 なる が存在する。
この定理の意味するところは比較的わかりやすいかと思います。つまり、空間内の条件を満たす集合があったときに、それを縮小するような写像を考えると、その縮小によって動かない点が存在するということです。
たとえば、平面内の凸集合の例として「ベイマックス」を考えます。
この集合を縮小する写像 を考えると、次のようになります。
— tsujimotter ロマ数本好評発売中!! (@tsujimotter) 2021年2月18日
よーく観察すると、少なくとも1点、移動前と移動後で動いていない点が現れます。そういう定理です。
不動点定理を適用するために、混合戦略の集合 が「コンパクト凸集合」の条件を満たすか確認してみましょう。
まず、プレーヤー の混合戦略の集合 は、先ほど述べたように単体集合ですが、特にコンパクト集合でもあります。さらに凸集合です。
なので、コンパクトがよくわからない人は「有界」かつ「閉集合」という理解でいいと思います。
また、コンパクト凸集合の直積もまたコンパクト凸集合です。したがって
もコンパクト凸集合です。これで が定理の条件を満たすことがわかりました。
よって、 から への連続写像 を考えて、 の不動点がちょうどナッシュ均衡になるようにできれば良さそうですね。これが証明の基本的な方針です。
問題は、その方針を実行するためにどんな をとったらよいかということです。ここが一番頭を使うポイントです。
結論から言うと、次のような関数 を考えます。
まず、準備として を次のように用意します:
ここで、プレーヤー全体の混合戦略の組を として、各プレーヤー が各戦略を選択する確率を としています。 はプレーヤー が戦略 を選ぶ確率です。
なんじゃこりゃというような関数ですが、これを並べたものが目的の です。
すなわち、任意の に対して
として、さらに
のように定義します。これによって、 が得られます。
実際、 が成り立つこと(つまり、 の要素をすべて足して になること)は確認する必要がありますが、次の通り示せます:
途中で を使っています。
よって、任意の で が成り立つこと、すなわち であることが示されました。
また、 は(よーく考えると)連続関数であることがわかり、 はその四則演算で得られるので連続関数。よって、 のすべての要素は連続なので、直積位相の性質により は連続写像です。
ゆえに、ブラウアーの不動点定理により、 は不動点を持つことになります。つまり、 なる が存在することになります。
3. ナッシュの定理の証明
不動点定理を使って、謎の関数 は不動点 を持つことがわかりました。
実はこの がナッシュ均衡点であった、というのが得たい結論です。これを示すことができれば証明が完結します。
不動点 について、 が成り立つわけですから、 の定義より
が成り立ちます。すなわち
が成立します。
ここで、次の補題を証明します:
が成り立つ。
(補題の証明)
の定義より
が成り立つ。(プレーヤー だけ純粋戦略に分解した。)
さて、補題の主張が誤りだと仮定する。このとき
が成り立つ。この を固定すると、関数 の定義より
が成り立つ。 より
が成り立つ。しかし、 と合わせると が成り立ってしまうがこれはおかしい。
ゆえに「補題の主張が誤り」という仮定が誤りであった。
補題の式 に ( の不動点)を代入すると、任意の に対してある が存在して
が成り立つことがわかります。ところが、式 を思い出すと
であったから、右辺が になります。左辺に着目すると、 より
であることがわかります。
は定義より 以上なので、これはつまり
であることを意味します。
言い換えると
ということです。(プレーヤー の混合戦略をいずれかの純粋戦略 に置き換えたとき、プレーヤー の利得は元の利得以下となる。)
これを用いると、任意の混合戦略 に対して
が成り立つことになります。
すなわち、任意の 、、および混合戦略 に対して
が成り立つことが示されました。これは がナッシュ均衡点であるという条件に他なりません。
4. おわりに
長かったですが、無事「ナッシュの定理」が証明できました。これで任意の有限ゲームは混合戦略の範囲でナッシュ均衡点を持つことが理解できましたね。
ポイントとしては、2点ありました。1つは連続関数 を人工的に作ったことでした。ブラウアーの不動点定理によって、 の不動点が が存在します。
もう1つのポイントは、上記の の構成によって、 がナッシュ均衡点であることが示せるということです。これによってナッシュの定理が証明されるわけですね。
なかなか面白い証明だと思うのですが、いかがだったでしょうか。私自身、3年前に証明を読んで感動した経験があり、いつかまとめたいなと思っていました。ヨビノリさんの動画が上がったこともちょうど良いタイミングだなと思い、今回まとめさせていただきました。
長い説明でしたが、最後まで読んでくださってありがとうございました!
それでは今日はこの辺で!
参考文献(?)
今回の証明は、私が3年前にとあるブログに書かれている証明を読んで、それをノートにまとめたものを再構成したものでした。その頃からブログに書きたいと思っていたのですが、なかなか重い腰が上がりませんでした。(実際今回も書き終えるのはなかなか大変でした。)
3年ぶりにそのノートを見つけてブログに書き起こしたのは良いのですが・・・。肝心の、元のブログが見つからない!!
本当は、こちらに記載した上でお礼を申し上げようと思っていたのですが、見当たらないので仕方ありません。時が経って消えてしまったのか、単に見つけられないだけなのか・・・。また見つかったらこちらに乗せたいと思います。
大変失礼ながら、どこのブログかわかりませんが、証明の解説をありがとうございました。
また、The Annals of Mathematicsに掲載されたナッシュの論文も、多少ですが参考にさせていただきました。以下のリンクから見ることができます: