5分でわかる？ゲーム理論
〜囚人のジレンマとじゃんけんを例に〜
知能情報コース3年
Twitter：愛計@lovemeasure9
サークル：琉球大学Robotサークル (@RyudaiRobot)
アニメ「星屑テレパス」の漫画
実はこれもScrapboxに載せてあります
目次
ゲーム理論とは
囚人のジレンマと純粋支配戦略均衡
じゃんけんと混合戦略ナッシュ均衡
じゃんけんの必勝法を数理的に考えたくないですか？
じゃんけんに勝ちたいと思っているはずです
ゲーム理論勉強途中の僕が必勝法を5分で教えます
ゲーム理論とは
複数主体が関わる意思決定の問題や行動の相互依存的状況を数学的な数理モデルを用いて研究する学問
ゲーム理論はこのような状況(ゲーム)において、
各プレイヤー(意思決定の単位)がどのような行動をするかを考える
ゲームのAIとかを考える人にも参考になるかもしれません
ゲーム理論とは
仮定：プレイヤーは合理的
どういう結果が嬉しいかを一貫性を持って判断できる
結果に対してその嬉しさを実数で点数がつけられる
プレイヤーは完備性と推移性を選好関係を持つ
より嬉しい結果が得られるような行動を選択する
より嬉しい結果が得るために、どんな計算もできる
ゲームを熟知している
相手がどういう行動を取ってくるかを考える
自分もゲーム理論を完全に理解しているし相手もゲーム理論を完全に理解している
合理的なプレイヤーは将棋の全てのパターンを理解している
ゲーム理論によくある誤解
× ゲーム理論のプレイヤーは利己的
○ 利他的な行動を好むプレイヤーを想定すれば良い
そのプレイヤーの合理的な行動を考えることができるため
戦略形ゲームの例
今回は扱うのは非協力ゲームのなかの完備情報戦略形ゲーム
table:自爆スイッチが目の前にある状況(ゲーム)
A\B 押す 押さない
押す AとBは死ぬ(-4,-4) Aは死ぬ(-4,-1)
押さない Bは死ぬ(-1,-4) AとBは無事(0,0)
あなたがA、Bさんならどういう行動(戦略)を取る？
どちらもボタンを押さない(という戦略を取る)
合理的なプレイヤーはデタラメに意思決定をしない
できるだけ点数が高くなるように行動する
「Aが押さない、Bが押さない」はこのゲームの解
誰にとってもこれ以上良い点数は与えられなさそうな状態
このことをパレート最適という
ゲーム理論とはこのようなゲームの解を考える分野
囚人のジレンマ
ストーリー
A,Bが逮捕された
2人とも黙秘するとすぐ解放される
自分だけ自白すると罪が軽くなるが、片方の罪が重くなる
2人とも自白すると罪は軽くならない
https://scrapbox.io/files/6635b7ce9becb4002c274d82.png
囚人のジレンマ
囚人のジレンマを利得行列で表してみよう
利得行列というのは(プレイヤー,戦略(行動),利得(点数))の組の表現方法
table:囚人のジレンマの利得行列
A\B 自白する 自白しない
自白する (-5,-5) (0,-10)
自白しない (-10,0) (-1,-1)
A,Bがともに自白するよりも、自白しないしないほうがいい！
ゲーム理論的に分析してみよう
Aの視点
2つに場合分けして考える
Bが仮に自白するとき(の最適反応戦略は？)
Aが自白しないと……-10点
自白すれば……-5点
まぁ自白したほうが良さそうだ
Bが仮に自白しないとき(の最適反応戦略は？)
Aが自白しないと……-1点
Aが自白すると……0点
Bには悪いけど自白したほうが良さそうだ
結論
Aはどんな状況でも自白する(プレイヤーAの支配戦略)
相手の戦略に関わらずに同じ戦略を取るなら、その戦略をプレイヤーAの支配戦略という
同様に…
Bもどんな状況でも自白する(プレイヤーBの支配戦略)
囚人のジレンマのゲーム解
ゲームの解は「A,Bはともに自白する」でした
このようなゲームの解を支配戦略均衡と呼びます
驚きの結果ですね
パレード最適は一般にゲームの解になりません
支配戦略均衡→ゲームの解と言えそうです
ゲームの解の十分条件
支配戦略は存在すれば高々1つ
じゃんけん
いよいよじゃんけんの必勝法をゲーム理論的に考えてみよう！
まずは利得行列を考える
table:じゃんけんの利得行列
A\B グー✊ チョキ✌️ パー✋
グー✊ (0,0) (1,-1) (-1,1)
チョキ✌️ (-1,1) (0,0) (1,-1)
パー✋ (1,-1) (-1,1) (0,0)
Aの視点
3つに場合分けして考える
Bがグー✊のとき(の最適反応戦略は？)
Aはチョキ✌️
Bがチョキ✌️のとき(の最適反応戦略は？)
Aはグー✊
Bがグー✊のとき(の最適反応戦略は？)
Aはパー✋
う〜ん
支配戦略がなくて困った……
2つの概念の導入
ナッシュ均衡
全てのプレイヤーの混合戦略が最適反応戦略であるような状況
誰もが自分だけ戦略を変えると自分が損してしまう(これ以上得にならない)状況
極大値みたいなもの
自爆スイッチ
ボタンを押す
囚人のジレンマ
自白しない
ゲームの解→ナッシュ均衡と言える！！
必要条件ですね
混合戦略
今までは戦略Xを100%の確率で実行するという戦略だった(純戦略)
確率的に純戦略を取るいうのも戦略と考える
aの確率で戦略X,bの確率で戦略Y,cの確率で戦略Zを実行する(混合戦略)
ナッシュの定理
混合戦略ゲームの範囲では少なくとも1つのナッシュ均衡が存在する
これは角谷の不動点定理から証明できるらしいです
ゲームの解を考えたかったら、とりあえずナッシュ均衡を考えれば良い
じゃんけんにも少なくとも1つのナッシュ均衡が存在するはずだ！
じゃんけんのナッシュ均衡
A,Bはともに1/3の確率でグー,チョキ,パーを出す
直感的には正しそう
それでは求めてみましょう！
じゃんけんのナッシュ均衡
Bがpの確率でグー✊、qの確率でチョキ✌️,1-p-qの確率でパー✋を出す
Aの期待利得
Aがグーを出す
0×p + 1×q + -1×(1-p-q)= -1+p+2q
Aがチョキを出す
-1×p + 0×q + 1×(1-p-q)= 1-2p-q
Aがパーを出す
1×p + -1×q + 0×(1-p-q)= p-q
じゃんけんのナッシュ均衡
完全混合戦略(全ての戦略を選ぶ確率が0出ない、純戦略ではない)場合のナッシュ均衡を考える
このとき、プレイヤーAの期待利得は全て等しくなる
利得が等しくなければ、プレイヤーAは混合戦略を変更するだろう
しかし今はナッシュ均衡なのでそのような場合にはならない。
つまり利得が等しい状況
-1+p+2q = 1-2p-q = p-q
これを解くと
p=1/3,q=1/3,1-p-q=1/3
プレイヤーBがこのような混合戦略のとき、プレイヤーAも混合戦略を取る
じゃんけんのナッシュ均衡
同様にして、Aが1/3でグー、1/3でチョキ、1/3でパーをを出すとき
プレイヤーBも混合戦略を取る
じゃんけんの完全混合戦略の場合のナッシュ均衡
プレイヤーAが1/3でグー、1/3でチョキ、1/3でパーをを出す
プレイヤーBが1/3でグー、1/3でチョキ、1/3でパーをを出す
とわかる
まとめ
パレード最適はゲームの解とは限らない
支配戦略均衡→ゲームの解→ナッシュ均衡
支配戦略均衡は存在すれば高々1つ存在する
ナッシュ均衡は混合戦略の範囲では少なくとも1つ(複数)存在する
参考
『ゼミナールゲーム理論入門』