バックワードインダクションで展開形ゲームを解く

完全情報展開形ゲームとその解き方であるバックワードインダクション(backward induction)について「展開形ゲームとは?ゲームの木とは?」で,ざっくりと話しました.ここではバックワードインダクションによるゲームの解き方を,もう少し詳しく説明します.

バックワードインダクションでゲームを解く

バックワードインダクションは完全情報展開形ゲームの解き方です.各プレイヤーは自分よりあとに行動するプレイヤーの行動を先読みし,自分の利得を最大にするように行動を選ぶのでした.

これを言い換えるとゲームは「時間的に後から行動するプレイヤーの行動から順番に解いてゆく」ということになります(有限時間の場合).後から帰納的に(順番に)解くという意味でバックワードインダクションと呼ばれるのです.

バックワードインダクション(backward induction)は翻訳すると「後向き帰納法」「後向き遡及法」などと翻訳されるのですが,しっくりこないんでカタカナ語で書いたりすることが多いです.

具体的には,次のようにゲームを解いていきます.

1.最後のプレイヤー,つまり「そのプレイヤーが何を選んでもゲームが終わる」ようなプレイヤーの行動を求めます.そのプレイヤーは,自分が行動を選ぶと自分の利得が決まるので,そのプレイヤーが自分の利得を最大にする行動を決定することができます.
2.既に行動を求めたプレイヤーの直前に行動するプレイヤーの中から,<そのプレイヤー以降に行動するプレイヤーの行動がすべて決まっているプレイヤー>の行動を求めます.そのプレイヤーは,自分が行動を選ぶと,それ以降のプレイヤーの行動が決まっている(か,またはゲームが終わる)ために利得が決まるので,利得を最大にする行動を決定することができます.
3.2を繰り返して行き,一番最初のプレイヤーの行動が求められたら終わり…です.

例題

いくつかの例題を見てみましょう.説明をするためには,ゲームの木の点に名前がついていると便利ですので,そうしておきます.(正確には意思決定点にラベルを付けておきます.ゲームの木を少し詳しく説明!も参照してください.)

(例1)まず最初は「展開形ゲームとは?ゲームの木とは?」で説明した<コンビニ立地ゲーム>の例(図1)を,バックワードインダクションの手順の観点から,もう一度解いてみます.

図1:コンビニ立地ゲームの例

1.最後に行動するプレイヤーは,\(x2\),\(x3\)で行動するファミモなので,そこでの行動を決めます. \(x_2\)では,ファミモはAを選べば利得が400,Bを選べば利得が300となのでAを選びます. \(x_3\)では,ファミモはAを選べば利得が600,Bを選べば利得が200なのでAを選びます.こうして最後に行動するプレイヤーの行動が決まります.

2.次に,既に行動を求めたプレイヤーの直前に行動するプレイヤーは\(x_1\)で行動するセレブだけなので,そこでの行動を決めます.\(x_1\)では,セレブは,Aを選ぶと(ファミモがAを選ぶので)利得が200,Bを選ぶと(ファミモがAを選ぶので)利得が300となるのでBを選ぶ,というように行動が決定できます.これで最初のプレイヤーまで遡って行動が決まったので,おしまいです(図2).

図2:例1のバックワードインダクション

(例2)もう少し複雑な例を考えてみましょう(図3).今度は3人のゲームです.

図3はプレイヤー1,2,3の3人からなる,以下のようなゲームです.

図3:3人ゲーム,ゲームをプレイする順番は不規則
  • はじめにプレイヤー1が\(x_1\)で\(A\)か\(B\)を選びます.
  • もしプレイヤー1が\(A\)を選んだときは,プレイヤー3が\(x_2\)で\(C\)か\(D\)を選び,ゲームは終わります.
  • プレイヤー1が\(B\)を選んだときは,プレイヤー2が\(x_3\)で\(E\)か\(F\)を選びます.\(E\)を選ぶと,そこでゲームが終わります.
  • プレイヤー2が\(F\)を選ぶと,\(x_4\)でもう一度プレイヤー1の手番となり,プレイヤー1は\(G\)か\(H\)を選び,そこでゲームが終わります.

図3において,各点の上の数字は行動するプレイヤーを表しています.ゲームが終わったときの利得は,常に左からプレイヤー1,2,3の順になっています.

このゲームを,バックワードインダクションの手順に従い解いてみましょう.

1.最後に行動するプレイヤー(そのプレイヤーが何を選んでもゲームが終了するプレイヤー)の行動です.このゲームでは\(x_2\)で行動するプレイヤー3と,\(x_4\)で行動するプレイヤー1なので,そこでの行動を決めます. \(x_2\)では,プレイヤー3は\(C\)を選べば利得が1,\(D\)を選べば利得が0なので\(D\)を選びます.\(x_4\)ではプレイヤー1は\(G\)を選べば利得が6,\(H\)を選べば利得が1なので\(G\)を選びます.こうして最後に行動するプレイヤーの行動が決まります.

2.次に,<そのプレイヤー以降に行動するプレイヤーの行動がすべて決まっているプレイヤー>は,\(x_2\)で行動するプレイヤー2なので,そこでの行動を決めます.\(x_2\)でプレイヤー2は,\(E\)を選ぶと利得が5,\(F\)を選ぶと(プレイヤー1がGを選ぶので)利得が4,となるので\(E\)を選ぶ,ということになります.(図4)

図4:例2のバックワードインダクション-その1

3.次に,\(x_1\)で行動するプレイヤー1の行動を決めます.\(x_1\)でプレイヤー1は,\(A\)を選ぶと(プレイヤー3が\(C\)を選ぶので) 利得が4,\(B\)を選ぶと(プレイヤー2が\(E\)を選ぶので)利得が3となるので\(E\)を選ぶ,ということになります.

図5:例2のバックワードインダクション

解と結果(均衡経路)を区別する

以上,バックワードインダクションによる完全情報ゲームの解の求め方について解説しました.このときバックワードインダクションで得られるゲームの解と,それによって予測されるゲームの結果は何であるか,について区別しなければなりません.ここで

ゲームの解とは,すべての点で各プレイヤーが何を選ぶかを,すべて明らかにしていること
ゲームの結果とは,ゲームの解によって,最初(初期点)のプレイヤーから順番にどのような行動が選ばれゲームが進行して,どの点でゲームが終わるかを示したもの

です.

例えば最初の例1を見てみましょう(図6).

図6:ゲームの解と結果を区別する(例1)

このときゲームの解は「 \(x_1\)でセレブがBを選び,\(x_2\)と\(x_3\)でファミモはAを選ぶ」となります.このようにゲームの解はすべての点でプレイヤーが何を選ぶかを定めたものです.

これに対し,\(x_1\)でセレブがBを選べば,次に\(x_3\)でファミモがAを選んでゲームは終わり,実際には\(x_2\) は実現しません.ゲームの解によって,実際に起きる結果は解の一部です.

「すべての点(正しくは意思決定点)で何が選ばれるか」が決まると,「最初のプレイヤー(初期点)から,順番にどのプレイヤーがどの行動を選んでゲームが進行して,最後のプレイヤーの行動が決まって利得が決まるところ(終点)」まで一本の経路(path)ができます.この経路は均衡経路(equilibrium path)と呼ばれます.この均衡経路はゲームの結果であると考えられます. この例の場合,均衡経路(=ゲームの結果)は「 \(x_1\)でセレブがBを選び,\(x_3\)で,ファミモはAを選ぶ」となります.

「すべての意思決定点で何が選ばれるか」は「戦略の組(strategy profile)」に対応するものです.またこれは1つの経路を実現すると考えても良いし,1つの終点が決まると考えても良いです.なお途中で確率による選択(混合戦略)があると,経路は1つではなく,複数の経路が確率的に決定されると考えられます.

ゲームの解において,均衡経路ではない意思決定点は均衡外経路(off-equilibrium path)と呼ばれます. 例1では\(x_2\)は均衡外経路です.このことよりゲームの解が異なってもゲームの結果が同じになることがあることに注意しましょう.

例2で,ゲームの解とゲームの結果が何であるかを練習してみましょう.


図7:ゲームの解と結果を区別する(例2)

この例2の場合は

  • ゲームの解は,プレイヤー1が\(x_1\)で\(A\)を\(x_4\)で\(G\)を選び,プレイヤー2が\(x_3\)で\(E\)を選び,プレイヤー3が\(x_2\)で\(C\)を選ぶ.
  • ゲームの結果は,プレイヤー1が\(x_1\)で\(A\)を選び,プレイヤー3が\(x_2\)で\(C\)を選ぶ.

となります.いかがでしょうか.

バックワードインダクションはゲーム理論だけではない

<後から解く>バックワードインダクションは,時間経過を伴う最適化問題である動的最適化(マクロ経済学,ファイナンス理論),ネットワーク最適化問題にも用いられる一般的手法です.この概念を方程式に直すといわゆるベルマン方程式となります.

以下も参考にしてください.

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

展開形ゲームとは?ゲームの木とは?

ゲーム理論のゲームには,戦略形ゲーム(strategic form)と展開形ゲーム(extensive form)という2つの「表現」があります.戦略形ゲームは,プレイヤーは同時に行動を選ぶと考えてゲームを表します.これに対し,展開形ゲームは,先手と後手のあるゲームなど,どんなゲームでも表現できて,プレイヤーは同時に行動しなくても良いのです.

このような展開形ゲームの中でも,プレイヤーが1人ずつ順番に行動を選び(同時に行動することはなく),各プレイヤーは自分より先に行動したプレイヤーが何を選んだかがすべて分かるゲームを完全情報(perfect information)の展開形ゲームと言います.代表的な例は,チェス,囲碁,将棋です.将棋で「自分より前に指した手が,何か分からん!」ってことはありませんよね?

完全情報ではないゲームは不完全情報(imperfect information)と呼びます,あたりまえですね.不完全情報ゲームの例としては,たとえば...「2人でじゃんけんをするとき,まず1人がグー・チョキ・パーを選んで紙に書いて相手に見えないように封筒に入れ,次にもう1人が改めてグー・チョキ・パーを選ぶ」という面倒なじゃんけんは不完全情報ゲームです.

...って,あれ?戦略形ゲームで勉強したように,これは同時に行動することと同じでした.「プレイヤーが同時に行動する戦略形ゲーム」は「不完全情報の展開形ゲーム」の典型的な例です.これはまた別の機会に.

ここでは完全情報の展開形ゲームとその解き方について学んで行きます.乱暴に言うと

  • 戦略形ゲームは利得行列で表しナッシュ均衡で解く
  • 完全情報展開形ゲームはゲームの木で表し,バックワードインダクションで解く

ということになります.乱暴すぎてかなり間違ってますが,細かいことは気にせず,ざっくり説明します.正確な定義や説明はゲーム理論のテキストなど読んでください.

完全情報展開形ゲームの例

以下の例を考えましょう.戦略形ゲームの支配戦略やナッシュ均衡の説明で使った例と同じです.今度はプレイヤーは同時に行動を選ぶのではなく,セレブ,ファミモの順に選びます.

2つのコンビニ,セレブ(セレブイレブン)とファミモ(ファミリーモール)が,A駅とB駅のどちらか一方に出店しようと考えている.コンビニを1日に利用する客はA駅が600人,B駅が300人である.セレブとファミモが違う駅を選べば利用客を独占できる.しかし同じ駅に出店すると,ファミモが人気で,ファミモはセレブの2倍の客数を獲得できる.すなわち両方がA駅に出店すると,セレブ200人,ファミモ400人.B駅に出店すると,セレブ250人,ファミモ500人である.ここで客数を利得と考える.

ここでは,まずセレブが先にどちらの駅を選ぶかを決定し,ファミモはそれを知ってから自分がどちらの駅に出店するかを決める.セレブとファミモはどちらの駅に出店するだろうか?

戦略形ゲームのように同時に行動するのではなく,プレイヤーが順番に行動をするゲームが展開形ゲームです.展開形ゲームは次のようなゲームの木で表します.

ゲームの木

ゲームの木の正確な定義は後でやろうと思いますが,ざっくりと理解したい人には,ゲームの木の説明は不要でしょう?まず最初にセレブがAかBかを選び,次にそれを知ってからファミモがAかBかを選ぶと,結果が決まるのでセレブとファミモの利得がそこに書いてある,とそんな感じです.

ゲームを解く

ではさっそく,このゲームを解いてみましょう.皆さんがセレブだったらAとBのどちらを選ぶでしょうか?セレブがAを選ぶと,うまく行けば(ファミモがBを選べば)600の利得を得られますし,Bを選ぶとヘタをすれば(ファミモがBを選べば)100の利得になってしまいますね.だから,セレブはAを選ぶことが答のように思えるかも知れません.

しかし,ゲーム理論の答ではセレブはBを選びます.

なぜでしょうか?このゲームでは,セレブだけではなく,相手プレイヤーのファミモも利得を大きくしたいと考えています.セレブは「うまく行けば」「ヘタをすると」と,自分勝手に考えるのではなく,ファミモの行動を考えて,自分の行動を選択する必要があります.このためにはセレブの次に行動するファミモの行動を先読みする必要があるわけです.

ファミモの行動を先読みしてゲームを解いてみましょう.

  • セレブがAを選ぶと,ファミモはAを選べば利得が400,Bを選べば利得が300となるなのでAを選ぶ
  • セレブがBを選ぶと,ファミモはAを選べば利得が600,Bを選べば利得が200なのでAを選ぶ

これを先読みするとセレブは,Aを選ぶと(ファミモがAを選ぶので)利得が200,Bを選ぶと(ファミモがAを選ぶので)利得が300となるのでBを選ぶ,ということになります(下図).

ゲームは先読みで解く

結果は「セレブがBを選び,ファミモがAを選ぶ」となります.これが(完全情報)展開形ゲームの解き方です.この先読みによるゲームの解き方はバックワードインダクションと呼ばれます.

以上,とりあえず完全情報展開形ゲームについての簡単な説明と解き方でした.乱暴に言うと

  • 戦略形ゲームは利得行列で表しナッシュ均衡で解く
  • 完全情報展開形ゲームはゲームの木で表し,バックワードインダクションで解く

ということでしたね.乱暴すぎて,かなり間違ってますが,最初は細かいことは気にせず,そんな感じで覚えておけばよいでしょう.正確な定義や説明はゲーム理論のテキストなど読んでくださいね.なお.

  • バックワードインダクションによってゲームを解く方法は,「バックワードインダクションで展開形ゲームを解く」で,もう少し詳しく説明することにします.
  • ゲームの木については「ゲームの木について,ちょい詳しく」でお話します.
  • 一般の不完全情報ゲームとはどんなもので,どのように解くかは,またの機会に.お急ぎの方は「ゼミナールゲーム理論入門」で!

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

囚人のジレンマ

囚人のジレンマとは

囚人のジレンマは,ゲーム理論の中で,もっとも有名な例・モデルと言えるでしょう.
2人のプレイヤーが「協力するか」「協力しないか」を選ぶ問題で,以下の3つの条件が成立するときに,それは囚人のジレンマと呼ばれます.

(1)各プレイヤーは,相手が協力するならば,自分は協力しないほうが良い.
(2)各プレイヤーは,相手が協力しなくても,自分は協力しないほうが良い.
(3)しかし各プレイヤーは,2人が協力しないよりは,2人が協力したほうが良い.

(1)と(2)から,相手が何を選んでも自分は「協力する」より「協力しない」ほうが良いので,2人は協力しないことを選択します.しかしその結果が2人が協力することよりも悪くなっているために問題となるわけです.

ここで 「協力する」ことはゲーム理論では支配戦略と呼ばれます.支配戦略は,相手が何を選んでも,自分にとって他の選択より良い選択です.このことから支配戦略を選ぶことは自明のように思えるのですが, 囚人のジレンマを考えると支配戦略を選ぶことが必ずしも自明では思えなくなります.

囚人のジレンマの由来

この問題が囚人のジレンマと呼ばれるのは,タッカー(A. Tucker.カルーッシュ・クーン・タッカー条件(Karush-Kuhn-Tucker condition)のタッカーです)という数学者が上の状況を以下のようなストーリーで表現したことが由来であると言われています(以下はタッカーのオリジナルのストーリーとは違います).

(囚人ジレンマ ストーリー)重罪を犯しているが,証拠が不十分なため軽微な罪で逮捕されている2人の囚人がいる.彼らは別々な部屋で取引を持ちかけられる「お前だけが重罪について自白すれば無罪にしてやる」.
 もし2人が黙秘を続けると,軽微な罪で懲役1年である.しかし1人が自白し,1人が黙秘をすると,自白した方は釈放,黙秘した方は(捜査に協力しないことで罪が重くなり)懲役10年.しかし両方が自白すると(重罪で)懲役5年になる.
 さて,あなたが囚人ならば自白したほうが良いか,黙秘したほうが良いか?

この状況を表にすると,以下のようになります.

囚人のジレンマ

先に述べた「協力すること」を「黙秘」に,「協力しないこと」を「自白」に置き換えると,囚人のジレンマの3条件に当てはまることが分かります.すなわち,

(1)各囚人は,相手が黙秘するなら,自分は自白するほうが良い.
(2)各囚人は,相手が自白するとしても,自分は自白するほうが良い.
(3)しかし各囚人は,2人が自白するよりは,2人が黙秘したほうが良い.

相手が黙秘しても自白しても,自分は黙秘するより自白するほうが良いので,2人は自白を選びます.しかし,その結果は2人が黙秘するよりも悪くなります.

囚人のジレンマの例

この問題が興味を持たれるのは,社会や経済や政治の問題にこのジレンマが多く現れるからです.例えば

  • 2国間の軍備拡張の問題.相手国が軍備拡張しない場合,自国だけが軍備拡張をすれば相手に外交上優位な立場に立てる.相手国が軍備拡張しない場合は,自分も拡張して追いつかなければ,相手に優位に立たれてしまう.しかし,両国とも拡張すると,拡張前と力のバランスは変わらず,ただ軍事費だけが増えてしまう(核兵器の問題にも同様な文脈が使われます).
  • 安売りの問題.競争関係にある2店舗が,顧客を取り合うために,商品の価格を現状維持とするか,安売りをするかの問題.相手が現状維持の場合,自分だけが安売りをすれば顧客を奪い売上が増えるので,安売りをしたほうが良い.相手が安売りをしている場合,自分だけが現状維持をすると顧客を奪われ売上が減少するので,こちらも安売りをしたほうが良い.しかし両者が安売りをすると,顧客を奪うことはできず,価格の低下で売上だけが減ってしまう.

と言った現象です.なお安売りの問題は,安売りをしている企業にとっては問題ですが,消費者にとってはそれ以上に恩恵があります.市場の価格競争は,囚人のジレンマという構造を利用して消費者の厚生を高める仕組みだと言うこともできます.

囚人のジレンマの繰り返し

囚人のジレンマは,本来なら協力することが望ましい2人が協力しない方が良いという結果になってしまうジレンマです.これは,協力することをコミットするような契約(協力しなければ罰金を払うなど)を結ぶことで解決できる可能性がありますが,国家間の関係のように,このような契約を結ぶことが難しい場合もあります.このような場合,囚人のジレンマの状況は1回きりではなく,長期間に継続する問題でもあります.このような長期間に続く囚人のジレンマは,囚人のジレンマを何度も繰り返すようなゲームだと考え,繰り返しゲームという枠組みで分析されます.

注意点

囚人のジレンマを語るには,以下のことに注意する必要があります.

  • 2人ではなく3人以上の多人数版の囚人のジレンマは共有地の悲劇と呼ばれます.(3人以上でも,「囚人のジレンマ」と呼ばれることもありますが).
  • 「2人が協力しない」というゲームの解を支配戦略ではなく,ナッシュ均衡であるとしている解説もあります.全員が支配戦略を選ぶことは,ナッシュ均衡の特殊ケースなので,そうしても間違いではありません.しかしナッシュ均衡より強い支配戦略として理解するほうが適切です.
  • 囚人のジレンマと言われている状況でも,3つの条件のうち,(2)について抜けている場合があります.例えば
    X先生と2人で教授会で口論になり,教授会の時間がどんどん長引いている.(1′)X先生が折れるなら,自分は折れるより折れないほうがいい.(2′)自分が折れるなら,X先生は折れるより折れないほうがいい.(3′)でも2人が折れないなら,教授会は長引くばかりで,それなら2人とも折れたほうがいい(まったくの,まったくのフィクションです).
    一見すると条件が3つ揃ってるように見えますが,(1′)も(2′)も「相手が協力するなら,自分は協力しないほうが良い」という囚人のジレンマの条件(1)を2人のプレイヤーに分解して言い換えただけで,条件(2)(相手が折れないなら,自分は折れたほうが良いのか,折れないほうが良いのか)が特定されていません.もし「相手が折れないなら,自分は折れたほうがいい」ならば,これはチキンゲームです.

囚人のジレンマのブックガイド

  • 囚人のジレンマ--フォンノイマンとゲームの理論 (1995),ウィリアム・パウンドストーン(著),松浦俊輔(訳),青土社,\2600,ISBN:4791753607.
    • まさに「囚人のジレンマ」をタイトルにした本だが,それのみではなくゲーム理論の歴史と逸話に,ゲーム理論の初歩的な考え方を絡めた読み物である,ゲーム理論とは何かを知る入門書としても面白い.囚人のジレンマの誕生や囚人のジレンマに関する多くの研究について知ることができる.キューバ危機ではノイマン自身が原子力安全委員会の委員長として,ソ連とアメリカの囚人のジレンマにどう対応したかなどが興味深く記されている.原著はW. Poundstone, Prisonaer’s Dillemma (1992),Doubleday.
  • つきあい方の科学―バクテリアから国際関係まで (1984),R. アクセルロッド (著),Robert Axelrod (原著),松田 裕之 (翻訳),Minerva21世紀ライブラリー(ミネルヴァ書房),\2600,ISBN:4623029239.
    • 「囚人のジレンマ」の研究の中で,一般の人に有名で影響が強く,分かりやすいのはロバート・アクセエルロッドのコンピュータプログラムどうしのトーナメントによる実験であろう.この本は,その詳細をな結果や経緯をもとに,囚人のジレンマ研究のビジネスへの応用が解かれている.
  • 信頼の構造--こころと社会の進化ゲーム (1998),山岸敏男(著),東京大学出版会,\3200,ISBN:413011086
    • 社会心理学の立場から実験やゲーム理論の成果などをふまえて囚人のジレンマや社会的ジレンマがどのように起こり,どのように解決されるかの要因を探り,分かりやすく解説した本.馴れ合いや安易な集団主義に警告を発し,真の信頼関係を築くために何が必要なのかを語る.出版当時は,これからの日本がどうあるべきかを示唆すると共に実験経済学などの方面を踏まえて,これからのゲーム理論がどのように進むべきかも考えさせられた.
  • 社会的ジレンマ--環境破壊からいじめまで(2000),山岸敏男(著),PHP新書,\660,ISBN:4569611745
    • 前述の本が社会的ジレンマ研究のサーベイや実験経過などを理論的に解説する研究者向けの本であるのに対して,同著者のこの本は社会的ジレンマとその解決を一般向けに解説した本であった.
  • 対立と協調の科学-エージェント・ベース・モデルによる複雑系の解明 (2003)、ロバート・アクセルロッド (著),寺野 隆雄 (翻訳),ダイヤモンド社,\3800,ISBN:447819047X ロバート・アクセルロッド最新刊 

支配戦略

支配戦略とは

戦略形ゲームにおいては,各プレイヤーがどの戦略(選択,行動,代替案)を選ぶかを決めることが分析の主たる目的となります.

このとき1人のプレイヤーに対して

自分以外のプレイヤーが何を選んでも,自分の他の戦略よりも良い戦略(利得を高くする戦略)

があれば,その戦略を(そのプレイヤーの)支配戦略と呼びます.
プレイヤーに支配戦略があれば,そのプレイヤーはその支配戦略を選ぶと考えます.

支配戦略の例

例を挙げましょう.

支配戦略の例(コンビニ戦争2):2つのコンビニ,セレブ(セレブイレブン)とファミモ(ファミリーモール)が,まだコンビニがないA駅とB駅のどちらか一方に出店しようと考えている.コンビニを1日に利用する客はA駅が1200人,B駅が300人である.セレブとファミモがもし違う駅を選べば,利用客を独占できる.しかし同じ駅に出店すると,ファミモが人気で,ファミモはセレブの2倍の客数を獲得できる.すなわち両方がA駅に出店すると,セレブ400人,ファミモ800人.B駅に出店すると,セレブ100人,ファミモ200人である.ここで客数を利得と考える.セレブとファミモはどちらの駅に出店するだろうか?

ゲーム理論を持ち出すまでもなく,ちょっと考えるとセレブもファミモもA駅を選ぶことが分かるでしょう.B駅を独占しても高々300人ですからね.でも最初はこの例から始めましょう.

このゲームを利得行列で書くと下のようになります.

コンビニ戦争2

このときセレブの視点に立ってみましょう.セレブは

  • ファミモがA駅を選ぶならB駅(300)よりA駅(400)を選ぶほうが良い.
  • セレブは,ファミモがB駅を選んでも B駅(100)よりA駅(1200)を選ぶほうが良い.

と言うことが分かります.セレブは,ファミモが何を選んでも,B駅よりはA駅の方が良い戦略です.したがってA駅はセレブの支配戦略です(以下の図).

セレブの支配戦略

同様に ファミモの視点に立って考えてみます.

ファミモの支配戦略

セレブは,ファミモが何を選んでも,B駅よりはA駅の方が良い戦略です.したがってA駅はセレブの支配戦略です.

もしすべてのプレイヤーに支配戦略があれば,すべてのプレイヤーが支配戦略を選ぶことがゲームの答となり,そのゲームは解けたことになると言えるでしょう.今回の例では,セレブもファミモも支配戦略はA駅でしたから,両方ともA駅を選ぶと予測でき,ゲームは解けたことになります.

支配戦略はゲーム理論における「強い解」

支配戦略は,相手の選択に関わらず,自分にとって他の選択より良いような選択がある場合です.このときプレイヤーは,相手や自分にとっての知識が完全でなくても行動を確定することができます.例えば,

(禅が好きなアリス)アリスと文太は,それぞれ禅寺に行くか,ショッピングセンターに行くか悩んでいる.アリスはとにかく禅寺に行きたいので,文太が禅寺に行っても行かなくても,ショッピングセンターよりは禅寺がいい.

この場合,アリスにとって禅寺に行くことが支配戦略になり,アリスは禅寺に行くことが確定します(だから「悩んでいる」って問題設定はおかしいんだけど).しかも

  • 文太の利得は全く分かっていない.つまりプレイヤーに支配戦略があれば,相手の行動どころか,利得さえ分からなくても,そのプレイヤーの行動は確定する.
  • アリスも結果に対する好みがすべて確定しているわけではない.例えば「文太と一緒に禅寺に行くこと」と「アリスだけが禅寺に行き,文太はショッピングセンターに行くこと」のどちらが良いかは問題には定められていない(文太が好きなのか,嫌いなのか?).つまりプレイヤーは,相手の選択それぞれに対する自分の好みだけが分かっていれば行動は確定する.

ということになります.つまり支配戦略があれば,細かい情報はなくてもプレイヤーはそれを選ぶことになります.このことは,支配戦略によるプレイヤーの行動の予測は,かなり確かなものになっているということで,支配戦略がないゲーム(その解はナッシュ均衡)よりも,より確からしい予測を与えているということになります.

  • 「禅が好きなアリス」は文太の好みが分からないと,文太が何を選ぶかは分からない.この例の続きは(未完).
  • 支配戦略がない場合は,ゲームの解としてはナッシュ均衡を考えることになる.

このように支配戦略があればゲームの解は自明なように思えますが,必ずしもそうではないように見えるゲームがあります.それが囚人のジレンマであり,共有地の悲劇です.

戦略形ゲームとは?利得行列とは?

戦略形ゲームは,展開形ゲームと並ぶ非協力ゲームの表現形式です(参照:戦略形ゲームと展開形ゲーム).戦略形ゲームは,プレイヤー,戦略,利得の3つの要素から構成されます.すべてのプレイヤーは同時に戦略を選び,その結果,各プレイヤーの利得が決まります.

戦略形ゲームの例

戦略形ゲームの例として,次のような問題を考えてみましょう.

戦略形ゲームの例(コンビニ戦争1):2つのコンビニ,セレブ(セレブイレブン)とファミモ(ファミリーモール)が,まだコンビニがないA駅とB駅のどちらか一方に出店しようと考えている.コンビニを1日に利用する客はA駅が600人,B駅が300人である.セレブとファミモがもし違う駅を選べば,利用客を独占できる.しかし同じ駅に出店すると,ファミモが人気で,ファミモはセレブの2倍の客数を獲得できる.すなわち両方がA駅に出店すると,セレブ200人,ファミモ400人.B駅に出店すると,セレブ100人,ファミモ200人である.ここで客数を利得と考える.セレブとファミモはどちらの駅に出店するだろうか?

本題に入る前に言っておきたいのですが,別にこのページはコンビニの戦略の話をしたいのではなくて,ゲーム理論とは何かを話すための「例」ですからね.「両方に出店するというのはないのでしょうか」とか聞く人がいるけど(本当にたくさんいる),そうしたければ,そういう例を勝手に考えてください.むかし,あるビジネス系の雑誌に,こういう例を出したら,雑誌の編集部の人がコンビニの会社の人に聞きに行って,そしたら「うちには『客を取り合う』という発想はない.2つのコンビニに同じ駅に出店すると集積効果があって,利用客は増える」とか言われてしまったのですが,そうならば,そういう例を作ればいいですよ.でも増えたりしたら,例として分かりにくいじゃないですか.ここはリアリティを求めてるんじゃなくて,わかりやすい例にしてるんです.

で,本題です.上記の例の場合,戦略形ゲームの3要素(プレイヤー,戦略,利得)は

  • プレイヤー:セレブとファミモ
  • セレブの戦略:A駅に出店する,B駅に出店する
  • ファミモの戦略:A駅に出店する,B駅に出店する
  • 利得:上記に書かれている客数

のようになります.このようにプレイヤーが2人のゲームを2人ゲームと呼び,その中でも両プレイヤーの戦略の数が2つの場合は2✕2ゲーム(ツーバイツーゲーム,と呼ぶ)と呼ばれます.2✕2ゲームは,戦略形ゲームの中で最も簡単なゲームであると言えます.

「利得は上記に書かれている」と言われても見にくいので,このような2人戦略形ゲームを表すには,以下のような利得行列という表を使います.

利得行列

この表では,セレブが行(水平方向)を選択し,ファミモが列(垂直方向)を選択し,交わったセルの左側の数値がセレブの利得,右側の数値がファミモの利得を表します.例えば,セレブがA駅,ファミモがB駅を選ぶと…

セレブがA駅,ファミモがB駅を選択

このようになり,セレブの利得が600,ファミモの利得が300になることが分かります.

利得行列にはいろいろな書き方があり,下の図のようにセルを左下と右上に区切り,左下に第1プレイヤー(行を選ぶプレイヤー,今回はセレブ)の利得,右上に第2プレイヤーの利得を書く場合もあります.

利得行列の別の書き方

ゲームを解く

戦略形ゲームにおいて,「プレイヤーが選ぶ戦略の組合せはどこになるのか」を求めることをゲームを解くと呼びます.ゲームを解くポイントは,支配戦略とナッシュ均衡です.

戦略形ゲームと展開形ゲーム

ものすごく乱暴に言うと「ゲーム理論(非協力ゲーム)には,戦略形ゲーム展開形ゲームがあり,戦略形ゲームは利得行列で表し,展開形ゲームはゲームの木で表す」ということになります.乱暴すぎて,かなり間違ってますが,最初から細かいことは覚えられないので,ざっくりこうしておきましょう.

さらに戦略形と展開形について,初めて学ぶときは

  • 戦略形ゲームは,プレイヤーが同時に行動を選ぶ「同時ゲーム」.代表的なゲームはじゃんけんなど.
  • 展開形ゲームは,プレイヤーが順番で行動を選ぶ「交互ゲーム」を含む「すべてのゲームを表現する」ゲーム.代表的なゲームはチェスや将棋など.

くらいに考えると良いです.これも乱暴すぎますけど.

ゲーム理論では「同時か,逐次か」と言った「時間」が重要なのではなく,相手の行動が観察できるかどうかが重要です.例えば,2人でじゃんけんをするとき,

  1. まず1人(先手)が相手に分からないように「ぐー,ちょき,ぱー」のどれかを選んで紙に書いて封筒に入れ,
  2. もう1人(後手)は封筒を開けずに 後から「ぐー,ちょき,ぱー」を選び
  3. 先手の書いた紙が公表されて勝負をする

としましょう.この場合は,時間としては交互に行動していますが,同時にじゃんけんをしているのと変わりありません(同時にじゃんけんすると,後出しっぽくなる人がいるのを考えると,こっちのほうがずっと「同時」かも知れない) .先手は後手の行動を知らず,後手も先手の行動を知りません.この場合は戦略形ゲームになっていると言えます.

同時のゲームとは時間を指しているのではない

このように(すべてのプレイヤーが)他のプレイヤーの行動が観察できずに行動を選ぶ場合は戦略形ゲームです.オークションや競りを例に挙げれば,封印された紙に価格を書いて,最後に競り人がそれを開いて一番高額の人に出品された物を売る,と言った「封印入札」なども戦略形ゲームの典型的な例と言えます.

これに対して,チェスや将棋や囲碁では,自分より前に行動した人がどのような行動をしたかがすべて分かります.このようなゲームは完全情報ゲームと呼ばれますが,展開形ゲームで分析されるゲームの代表例です.オークションや競りでは,オークションハウスでの絵画の取引やマグロの競りなど,誰かが値段をつけたのを見て,それより高く買いたい人は更に高い価格をつける...などの「イングリッシュオークション」は展開形ゲームの典型例と言えます.同じ競りやオークションでも,ルールや形式によって違うゲームと考えられる点に注意です.

戦略形ゲームは「利得行列」と呼ばれる道具を用いて表現し,展開形ゲームは「ゲームの木」と言う道具を用いて表現します.戦略形ゲームと展開形ゲームについては,別の投稿で詳しく説明します.