経済学とかデータサイエンスとか

こちらはQiita: 湧源クラブ Advent Calendar7日目の記事です！
qiita.com

今回はゲーム理論について前提知識ゼロで書いてみたいと思います。
（数学の基本的な表記方法は知っていることとします。）
定義など正確な記述をしたい部分はとてもリスペクトしている愛読書、神取道宏『ミクロ経済学の力』より引用しています。

作者:神取道宏
発売日: 2016/05/16
メディア: Kindle版

ゲーム理論とは
ナッシュ均衡
- ナッシュ均衡の定義
ナッシュ均衡の例
次回予告

ゲーム理論とは

ゲーム理論とは、複数の人間が相手の出方をうかがいながら行動する状況を考える学問でミクロ経済学の一分野とされています。このような状況は現実に多く存在し、非常に一般性の高い理論です。

ゲーム理論という学問分野は数学者John von Neumannと経済学者Oskar Morgensternの共著書『ゲームの理論と経済行動』によって1944年に誕生しました。
→「おいおい、ここでもvon Neumann出てくるんかい！」とツッコミたくなりますね。
現在でもゲーム理論はミクロ経済学の大きな一分野として研究されており、経済学だけでなく生物学や政治学など他の分野にも応用されています。
また、近年は現実の人々の行動を説明する方法としてゲーム理論だけでなく行動経済学も盛んに研究がされています。

ゲームとは

それではゲーム理論の内容に入っていきます。
まずはゲームの定義から！

ゲームとは、次の三つの項目からなるモデルである。

プレイヤー $i=1,2,\ldots,N$

プレイヤー $i$ の戦略 $a_i$ （プレイヤー $i$ が取ることのできる戦略全体の集合を $A_i$ と書く）

プレイヤー $i$ の利得 $g_i(a_1,\ldots,a_N)$

利得という言葉はあまり聞き馴染みないかもしれませんが、その人の嬉しさを表す（大きいほど嬉しい）ものだと思ってください。

ゲームの例

まず最初にゲームの代表的な例として有名な「囚人のジレンマ」を紹介します。
ある二人の囚人1と2が共犯で逮捕されており、別々に尋問を受けている。
二人ともある犯罪に加担したことはわかっているけれど、犯行の詳細は完全にはわからないので取り調べを受けている。
各囚人の取ることができる戦略は黙秘するか告白するかのいずれか。
各囚人は以下の共通認識を持っている。

二人とも黙秘すれば禁固1年で済む
二人とも告白すれば禁固3年になってしまう
一方が告白してもう一方が黙秘すれば、告白した方は無罪放免となるが黙秘した方は禁固5年になってしまう

ここでは禁固 $n$ 年を $-n$ の利得と捉えて利得関数を与えます。
これらを表にまとめてみると以下のようになります。
各セルの左側が囚人1の利得で右側が囚人2の利得です。

1＼2	黙秘	告白
黙秘	-1,-1	-5,0
告白	0,-5	-3,-3

このように各プレイヤーの戦略の組に対応させて利得を書いた表を利得表といいます。
これを見ると、二人にとって幸せな結果は（黙秘、黙秘）で両者利得−1を得る状態という感じがします。
もちろん自分だけ告白して利得0が一番嬉しいわけですが、
少なくとも（告白、告白）で両者利得-3という状態になるくらいだったら
（黙秘、黙秘）にして両者利得-1のほうがマシですよね...（フラグ）
それでは実際に各囚人はどのような行動をとることが予想されるでしょうか？
自分が囚人1になった気持ちで考えてみましょう。
囚人2の行動で場合分けしてみます。

もし囚人2が黙秘してくるなら
- 黙秘なら利得-1
- 告白なら利得0

→告白のほうがいい！

もし囚人2が告白してくるなら
- 黙秘なら利得-5
- 告白なら利得-3

→告白のほうがいい！
このことから囚人1は囚人2がどっちの戦略を取るとしても告白することが最善の戦略であることがわかります。
また囚人2も同様の考えで告白することが最善の戦略であることがわかります。
よって、予想される戦略は（告白、告白）で両者利得-3というお互いに嬉しくない状態になります！（フラグ回収）
（告白、告白）で両者利得-3よりは（黙秘、黙秘）で両者利得−1の方がお互いに嬉しいはずなのに、
なぜか悪い方である（告白、告白）が実現してしまうことがジレンマと呼ばれる所以です。

ゲームの分類

ゲームにはいろいろな分類の方法があります。
囲碁、将棋、麻雀、7並べを例に以下に簡単にまとめます。

意思決定の回数で分類
- 標準形ゲーム：1度だけ意思決定するゲーム（例：囚人のジレンマ）
- 展開型ゲーム：囲碁や将棋のように段階的に意思決定を何度も行うゲーム（例：囲碁、将棋、麻雀、7並べ）

プレイヤーが持つ最初の情報で分類
- 完備情報ゲーム：プレイヤーの集合、それぞれの戦略集合と利得関数すべてを全員が知っているゲーム（例：囲碁、将棋）
- 不完備情報ゲーム：完備情報でないゲーム（例：麻雀、7並べ）

プレイヤーが獲得する情報で分類
- 完全情報ゲーム：過去の全員の意思決定がすべてのプレイヤーに知られているゲーム（例：囲碁、将棋、7並べ）
- 不完全情報ゲーム：完全情報でないゲーム（例：麻雀）

馴染みのあるゲームを例にしましたが、ゲーム理論ではもっと社会的に意味のある状況を考えることが多いです。
そのような例も紹介したいところですが今回は割愛します。
以下では、標準形かつ完備情報かつ完全情報なゲームについて述べます。

ナッシュ均衡

囚人のジレンマゲームではお互いに「相手がどんな戦略をとってきても告白をしたほうが良い」という状況でした。このようなとき、告白は強支配戦略であるといいます。
お互いに強支配戦略をもっているときはゲームの結果を予想することは簡単ですが、現実的にはそのようなことは稀だと思います。
それではゲームにおいて結果を予想するような均衡概念（＝ゲームの解）はどのようなものなのでしょうか。
標準形ゲームにおいては、ナッシュ均衡と呼ばれる均衡が中心的な解概念の役割を果たしています。

ナッシュ均衡の定義

ナッシュ均衡を定義する前にまず記号の約束をします。
$a^*=(a^*_1,\ldots,a^*_N)$ をある戦略の組として、プレイヤー $i$ 一人だけが戦略 $a^*_i$ から $a_i$ へ変えた状態を
$(a^*_{-i},a_i)$ と書くことにします。

定義：戦略の組 $a^*$ が、すべてのプレイヤー $i$ とすべての戦略 $a_i$ について
$g_i(a^*)\ge g_i(a^*_{-i},a_i)$
を満たすとき、 $a^*$ をナッシュ均衡という。

数式の定義だけだと直感的にはどのようなこと言っているのかわかりにくいかもしれないので、日常的な言葉で言い換えると、

ナッシュ均衡とは、自分一人だけが戦略を変えても特をしない（ということがすべての人について成り立っている）状態

ナッシュ均衡とは、各人の戦略がお互いに最適反応になっている状態

となります。

ナッシュ均衡の例

囚人のジレンマを例にナッシュ均衡について考えてみましょう。
囚人のジレンマの利得表は以下でした。

1＼2	黙秘	告白
黙秘	-1,-1	-5,0
告白	0,-5	-3,-3

先ほどの常識的な思考の結果から、（告白、告白）のみがナッシュ均衡であってほしいですが、どうなるでしょうか。（フラグ）
それぞれの戦略の組がナッシュ均衡であるかを定義に従って確認してみます。

（黙秘、黙秘）について→プレイヤー1は告白に変えることで特をするのでナッシュ均衡でない
（黙秘、告白）について→プレイヤー1は告白に変えることで特をするのでナッシュ均衡でない
（告白、黙秘）について→プレイヤー2は告白に変えることで特をするのでナッシュ均衡でない
（告白、告白）について→両者とも戦略を変えても特をしないのでナッシュ均衡

よって、ナッシュ均衡は（告白、告白）のみであることがわかりました！（フラグ回収ならず）
とりあえず常識的な思考の結果と一致したので、よほど変な均衡概念ではなさそうだということがわかりましたね（当たりまえ）

次回予告

プレイヤーが確定的にただ一つの戦略を選ぶような状況では、ナッシュ均衡は必ずしも存在するとは限りません。
しかし、確率的に戦略を選ぶという戦略（混合戦略）を含めれば、ナッシュ均衡は必ず存在することが知られています。（すご！）
次回はこのことについて書きたいと思います。
お楽しみに！