東京工業大学
デジタル創作同好会

2016年12月16日 | メンバーブログ

ゲーム理論 概要

Achat

ゲーム理論 概要

2016年12月17日

初めまして、17日目担当のAchatです。 今日は数学者ノイマンと経済学者モルゲンシュテルンによって創始され、経済学や社会学、生物学などに応用されている**ゲーム理論**について、素人による素人のための入門として語っていきたいと思います。

ゲーム理論とは

まず初めに, ゲーム理論はコンピューターゲーム(のみ)を対象とする理論ではありません。ゲーム理論とは、(基本的に、)

あるルールが定められたゲームに参加するプレイヤーは, 自分の利得を最大化するためにどのような戦略をとるのか

を数学的に求めるための理論です。
「ゲーム」とは娯楽としてのゲームだけではなく、人間の経済活動や生物(種)の生存のためのふるまいなど、複数の「プレイヤー」がそれぞれ「戦略」を選べる状況は「ゲーム」としてとらえることができます。経済活動の分析のために導入されたゲーム理論が生物学などのほかの学問に応用されていったのはこの汎用性によるところが大きいのではないでしょうか。
また、「プレイヤー」は必ずしも人である必要はなく、企業やヒトという生物種など、意図的かどうかにかかわらず「戦略」を選択できる物事が当てはまります。
まずはゲームのモデルとしてもっとも有名なもののの一つである囚人のジレンマゲームを例にゲーム理論の考え方の基本を見ていきます。

囚人のジレンマ ゲームと利得表

あるところに二人組の大悪党がいた。ベテラン刑事は彼らを刑務所に送り込みたかったが、いかんせん証拠が足りない。
そこで彼は二人を適当な軽犯罪で連行して、自白させようと試みた。二人を別々の取調室に入れてそれぞれにこう語りかける。

「このまま何も話さなければ1年の懲役になる。
だがお前の相棒の罪を告白すれば、相棒を4年の懲役にする代わりにお前は無罪放免にしてやろう。
両方が告白した場合は両方とも3年の懲役だ。」

結果二人とも告白し、刑事の大手柄となった。

この物語でなぜ二人は「告白」するという戦略をとることになるのでしょうか。ゲーム理論で考えるためにこの物語の情報を下にまとめました。

囚人のジレンマ ゲーム

*プレイヤー*
    囚人A, B (2人)
*選択肢*
    黙秘, 告白
*ルール*
**両方「黙秘」した**なら、両方懲役**1**年 **自分が「告白」して**、**相手が「黙秘」した**なら、自分は懲役**0**年、相手は懲役**4**年 **両方「告白」した**なら、両方懲役**3**年
*利得*
    懲役年数をマイナスにしたもの
このゲームの場合、利得はマイナス、つまり損失を意味します。囚人A, Bは利得を最大(=損失を最小)にするための戦略を考えます。ここで、ゲームをさらに簡潔に表現する、**利得表**の概念を導入します。利得表は早い話が「損得早見表」で、それぞれのプレイヤー(囚人A, B)がとりうる選択肢(黙秘, 告白)の組み合わせについてそれぞれの利得を表にしたものです。

囚人のジレンマ ゲームの利得表

A\B 黙秘 告白
**黙秘** $(-1, -1)$ $(-4, 0)$
**告白** $(0, -4)$ $(-3, -3)$
各行が囚人Aの選択肢、各列が囚人Bの選択肢です。それぞれの枠には(Aの利得, Bの利得)が書かれています。この利得表を見ながら、囚人Aの立場になって戦略を考えてみましょう。
  • 囚人Bが「黙秘」したとき、(左側の列)
    • 自分が「黙秘」する場合、利得は-1
    • 自分が「告白」する場合、利得は0
      • 囚人Aは「告白」すべきである
  • 囚人Bが「告白」したとき、(右側の列)
    • 自分が「黙秘」する場合、利得は-4
    • 自分が「告白」する場合、利得は-3
      • 囚人Aは「告白」すべきである

結果、囚人Bが「黙秘」しようと「告白」しようと、囚人Aは「告白」することが自身の利得を最大化する戦略となります。同様に囚人Bも「告白」することが自分の利得を最大化する戦略となり、結果二人とも「告白」することになります。
このゲームの肝は二人が相談しあうことができないことにあります。利得表を見れば明らかなように、両方が「告白」したときの利得(3,3)(-3, -3)よりも両方が黙秘したときの利得(1,1)(-1, -1)のほうが二人にとって利益になり、またどちらか一方のみが「告白」したときの利得(0,4)(0, -4),(4,0)(-4, 0)も総和をとれば、両方が「告白」したときよりもましといえます。しかし、双方が自分の利得のみを最大化する戦略をとると最悪な結果になってしまいます。これが囚人のジレンマと呼ばれるゆえんです。
続いて、一般的には「チキンゲーム」と呼ばれるゲームのモデル、タカハトゲームを例に少し複雑な戦略について見ていきます。

タカハト ゲームと混合戦略

攻撃的なタカと非攻撃的なハトだけの世界を考えます。どちらもエサを探し回りますが、エサ場にほかの鳥がいた時、タカは相手を追い出そうと攻撃し、ハトは相手に攻撃されたらあきらめてほかのエサ場を探します。つまり、タカとタカが出会ったときは両方とも傷いて損をします。タカとハトが出会ったときはタカはすべてのエサを得られ、ハトは何も得られません(損もしません)。ハトとハトが出会ったときはエサを平等に分配します。
ここで、このゲームをゲーム理論的にとらえやすくするために少し発想の転換をします。プレイヤーを、ハトかタカのようにふるまうことができる鳥と考え、あるエサ場で2羽のプレイヤーが出会い、その場でタカのようにふるまうか、ハトのようにふるまうか
を選択するゲームととらえます。

タカハト ゲーム

*プレイヤー*
    鳥A, B (2羽)
*選択肢*
    タカ, ハト
*ルール*
**両方「タカのようにふるまった」**なら、両方傷ついて**損をする** **自分が「ハトのようにふるまい」**、**相手が「タカのようにふるまった」**なら、自分は**エサを得られず**、相手は**エサを独占できる** **両方「ハトのようにふるまった」**なら、両方**エサを半分得られる**
 

タカハト ゲームの利得表

A\B タカ ハト
**タカ** $(-2, -2)$ $(2, 0)$
**ハト** $(0, 2)$ $(1, 1)$
利得表の各枠は(A利得, Bの利得)です。鳥Aの立場になって利得を最大化する戦略を考えてみましょう。
  • 鳥Bが「タカのようにふるまった」とき、(左側の列)
    • 自分が「タカのようにふるまう」場合、利得は-2
    • 自分が「ハトのようにふるまう」場合、利得は0
      • 鳥Aは「ハトのようにふるまう」べきである
  • 鳥Bが「ハトのようにふるまった」とき、(右側の列)
    • 自分が「タカのようにふるまう」場合、利得は2
    • 自分が「ハトのようにふるまう」場合、利得は1
      • 鳥Aは「タカのようにふるまう」べきである

結果、囚人のジレンマ ゲームと違って、常に自分の利得を最大化する選択肢がないことがわかります。実は、囚人のジレンマ ゲームにおいて「戦略」と呼んでいたものは純粋戦略と呼ばれるもので、常に一つの選択肢を選び続ける戦略です。タカハト ゲームにおいては確率的に純粋戦略をとる混合戦略を考えなければ自分の利得を最大化できません。ここで、

鳥Aが「タカのようにふるまう」確率をpp、「ハトのようにふるまう」確率を1p1-p
鳥Bが「タカのようにふるまう」確率をqq、「ハトのようにふるまう」確率を1q1-q

として鳥Aの利得の期待値を最大化する戦略を考えます。

  • 鳥Bが「タカのようにふるまった」とき、(確率qq)
    • 自分が「タカのようにふるまう」場合、利得は-2
    • 自分が「ハトのようにふるまう」場合、利得は0
  • 鳥Bが「ハトのようにふるまった」とき、(確率1q1-q)
    • 自分が「タカのようにふるまう」場合、利得は2
    • 自分が「ハトのようにふるまう」場合、利得は1

鳥Aが「タカのようにふるまった」場合の利得の期待値は2q+2(1q)=24q-2q+2(1-q)=2-4q
鳥Aが「ハトのようにふるまった」場合の利得の期待値は0q+(1q)=1q0q+(1-q)=1-q
よって鳥Aが確率ppで「タカのようにふるまい」、確率1p1-pで「ハトのようにふるまう」戦略の利得の期待値は、p(24q)+(1p)(1q)p(2-4q)+(1-p)(1-q)
ppについて微分して、極大の条件を求めると, (24q)(1q)=0(2-4q)-(1-q)=0q=1/3q=1/3
これは、

  • q=1/3q=1/3のとき、ppがどんな値でも利得の期待値は2/32/3であること
  • q<1/3q<1/3のとき、p=1p=1で利得の期待値は最大24q2-4qであること
  • q>1/3q>1/3のとき、p=0p=0で利得の期待値は最大1q1-qであること

を意味しています。鳥Bについても同様なので、
自分の利得の期待値を最大化する安定な戦略の組は、p=q=1/3p=q=1/3の混合戦略の組で、利得の期待値は(2/3,2/3)(2/3, 2/3)となります。
つまり、3回に1回は「タカのようにふるまい」、残り2回は「ハトのようにふるまう」戦略で、平均して2/32/3の利得が得られます。

(ここから先は「利得の期待値」を単に「利得」と書きます。)

ナッシュ均衡とパレート効率性

ここまで囚人のジレンマ ゲームとタカハト ゲームを見てきましたが、ゲーム理論で扱えるゲームには、それぞれに特徴的な戦略の組があります。
その中でも重要なのがナッシュ均衡と呼ばれる戦略の組と「パレート効率的な」戦略の組です。

*ナッシュ均衡*
    相手の戦略が分かっていて、**相手が戦略を変えないとして**、自分だけが戦略を変えても利得が増えないような状況が全てのプレイヤーで起こっている戦略の組
*パレート効率的な戦略の組*
    相手の戦略が分かっていて、自分の利得を増やそうと戦略を変えたとき、必ず相手(の少なくとも一人)の利得が減ってしまうような状況がすべてのプレイヤーで起こっている戦略の組
ナッシュ均衡は誰も自分から戦略を変えようとしないという意味で**安定な戦略の組**です。また、n人のプレイヤーが参加するゲームには混合戦略の範囲でナッシュ均衡が存在することが証明されています(**ナッシュの定理**)。 パレート効率的な戦略の組はプレイヤー全体に対して**ある程度効率的な利得の分配ができている戦略の組**です。逆に、パレート効率的でない戦略の組は非効率的であると言えます。 囚人のジレンマ ゲームとタカハト ゲームのナッシュ均衡とパレート効率的な戦略の組を見ていきましょう。

囚人のジレンマ ゲームの利得表 (再掲)

A\B 黙秘 告白
**黙秘** $(-1, -1)$ $(-4, 0)$
**告白** $(0, -4)$ $(-3, -3)$
囚人のジレンマ ゲームにおいて両方が常に「告白」するという純粋戦略の組はナッシュ均衡ですが、パレート効率的ではありません。自分だけが「黙秘」に変えた場合、利得は$-3\rightarrow-4$となり損してしまうため、ナッシュ均衡です。一方、両方「黙秘」すれば囚人A、Bの利得は$(-3, -3)\rightarrow(-1, -1)$となり、両方増やすことができるので、パレート効率的ではありません。 また、それ以外の純粋戦略の組はナッシュ均衡ではありませんが全てがパレート効率的になっています。 囚人のジレンマ ゲームはナッシュ均衡とパレート効率的な戦略の組が一致しない典型例です。

タカハト ゲームの利得表 (再掲)

A\B タカ ハト
**タカ** $(-2, -2)$ $(2, 0)$
**ハト** $(0, 2)$ $(1, 1)$
タカハト ゲームでは純粋戦略を確率的に組み合わせる混合戦略を考えるため少し複雑です。 ($p$は鳥Aが「タカのようにふるまう」確率、$q$は鳥Bが「タカのようにふるまう」確率)

自分の利得の期待値を最大化する安定な戦略の組は、p=q=1/3p=q=1/3の混合戦略の組で、利得の期待値は(2/3,2/3)(2/3, 2/3)となります。

とあるのは、この戦略の組がまさしくナッシュ均衡であるということです。p=t(0t1)p=t (0\le t\le 1)としても鳥Aの利得は2/32/3のままで利得は増えず、鳥Bについても同様なので、ナッシュ均衡です。一方でp=q=0p=q=0とすることで、つまり両方が常に「ハトのようにふるまう」純粋戦略をとることで鳥A、Bの利得は(2/3,2/3)(1,1)(2/3, 2/3)\rightarrow(1, 1)となり両方の利得を増やすことができるので、p=q=1/3p=q=1/3の戦略の組はパレート効率的ではありません。
p=1,q=0p=1, q=0の純粋戦略の組はナッシュ均衡でかつパレート効率的です。p=1δp=1-\deltaとすると鳥Aの利得は22δ2\rightarrow2-\deltaとなり損をし、またq=0+δq=0+\deltaとすると鳥Bの利得は02δ0\rightarrow-2\deltaとなり損をするのでナッシュ均衡です。同時に、あらゆる混合戦略(純粋戦略を含む)の利得の最大値は22であることから、鳥Aの利得はこれ以上増やすことはできず、また鳥Bの利得を増やそうとq=t(0<t1)q=t (0<t\le 1)と変えたとき、p=0p=0でない限り必ずタカ同士出会うときの損失が鳥Aの利得に現れ、鳥Aの利得は減少するのでパレート効率的です。同様に、p=0,q=1p=0, q=1の純粋戦略の組もナッシュ均衡かつパレート効率的です。
p=q=0p=q=0の純粋戦略の組はパレート効率的ですがナッシュ均衡ではありません。この純粋戦略の組における利得の総和は22であり、あらゆる混合戦略の利得の総和の最大値は22であることから、この純粋戦略の組からほかの混合戦略の組に変えるとき、鳥A, Bの利得は「トレードオフである」もしくは「総和が減少する」から、パレート効率的です。一方、例えばp=1p=1とすると、鳥Aの利得は121\rightarrow2となり増えるので、ナッシュ均衡ではありません。

ゲーム理論の展開

ここまで囚人のジレンマ ゲームとタカハト ゲームについて語ってきましたが、これでもこの二つのゲームモデルについてすら語り切れていません(例えば、「囚人のジレンマ ゲームを無限回繰り返すときの最良の戦略は有限回の場合と同じかどうか」、「タカハト ゲームのプレイヤーにイーヴスドロッパー(盗聴者:タカに対してはハト、ハトに対してはタカのようにふるまおうとする)を追加した場合にタカとハトとイーヴスドロッパーの割合はどのようなるか」など)。また、ゲーム理論関連の発見や実験には興味深いものが数多くあります。例えば最後通牒 ゲームではゲーム理論による解と実際の人間の行動が一致しないように見え、その解消を進めるうちにプレイヤーのとる戦略にはいくつか種類があることがわかり、同時に、逆に脳神経科学的に人間を分析することでその人のとる戦略の傾向ひいては人間性の一部を説明できることがわかりました。また、量子ゲーム理論という、ゲーム理論を量子論に当てはめようという試みもあります。これは、複数の状態を同時にとる量子的な粒子についてその複数の状態を混合戦略ととらえて様々な状況を説明するものです。
このように、ゲーム理論は応用範囲が広く、ゲーム理論を展開してノーベル経済学賞を受賞した学者も多数います。また、ゲーム理論自体面白いです。私がゲーム理論に初めて興味を持った理由はその名前でしたが、実際、問題をゲームとしてモデル化して解を求める姿勢は「ゲームのようだ」と感じました。図書館で関連本を探したり、ネットで検索してみてはいかがでしょうか?

明日はkzshiroとOsa_Pyonさんの記事です。
皆様も、ゲーム理論的な問題分析・解決手法で、日々を豊かにお過ごしください。

参考文献

鈴木光男(2003)『ゲーム理論入門』共立出版.
ジーグフリード,トム(2008)『最も美しい数学 ゲーム理論』冨永星訳,文藝春秋.

この記事を書いた人
Achat

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2016年12月25日
署名付きクッキー / Omniauth Strategyを書く / GitLabで独自認証
kaz
2016年12月24日
お絵描きのススメ
KNJ
2016年12月24日
After Effectsで昼夜グラデーション画像を作ろう
Souring

活動の紹介

カテゴリ

タグ