第 3 章 展開形ゲーム 28
3.5 課題
演習3.1 (最重要; 展開形ゲームを戦略形に) 以下の展開形ゲーム (交互ゲーム)が与えられている.
(i)このゲームを戦略形(同時ゲーム)に直せ.
2 k g
g
k g k
2 (45,25)
(30,70) (70,30)
(25,5) 1
(ii) Player 2のkg という戦略を展開形ゲーム上に表現せよ.
(iii)このゲームをバックワードインダクションで解くことにより,(純粋戦略による)部分ゲーム完全均衡を 求めよ.
(iv)このゲームの(純粋戦略による)ナッシュ均衡をすべて列挙せよ.
正解例. (i)左の利得表.ただしPlayer 2の戦略は2文字で,1番目の文字が上の点における選択肢,2番目の文字が下
Player 2
gg gk kg kk
Player 1 g 45,25 45,25 70,30 70,30 k 30,70 25,5 30,70 25,5
2 k g
g
k g k
2 (45,25)
(30,70) (70,30)
(25,5) 1
の点における選択肢を表す.
(ii) Player 2の戦略kgは右図で「2」とあるふたつの点から描かれた矢印付きの赤い枝で表されている.
(iii) 部分ゲーム完全均衡は右図の矢印付きの赤い枝が表すとおり (g, kg) となる.つまり Player 1 の戦略が g で
Player 2の戦略がkgとなる.
(iv)戦略形より,ナッシュ均衡は(g,kg)と(g, kk)のふたつである.解き方は演習2.2 (iv)と同様.
リマーク3.1 戦略の意味を誤解している学生が過去ひじょうに多かった.本文の説明をきちんと読んで正しく理解して おくこと.
演習3.2 (最重要; 戦略の特定)「時間差じゃんけん」あるいは「後出しじゃんけん」と呼べる次のゲームを考
える.最初に先手(Player 1)がg (グー), c (チョキ). p (パー)のいずれかの行動(選択肢)を選び,次にその 行動を見た後手(Player 2)がg, c, pのいずれかを選ぶ.(利得はじゃんけんにしたがって「勝ち」が1,「負 け」が−1,「あいこ」が0とすればよい.)時間差じゃんけんでは後手の戦略はいくつあるか? すべて列 挙せよ.
正解例. 後手の戦略をg (グー), c (チョキ). p (パー)のいずれかの文字を3つ並べた文字列s1s2s3で表す.ただし 展開 形を 追加
• 1番目の文字s1は先手がgを出した場合の後手の出す手,
• 2番目の文字s2は先手がcを出した場合の後手の出す手,
• 3番目の文字s3は先手がpを出した場合の後手の出す手
とする.(交互ゲームにおけるあるプレーヤーの「戦略」とは,そのプレーヤーの意思決定するすべての点(より一般的に は情報集合)で,どの選択肢を選ぶかを記述したものであることに注意.テキストによっては後手の戦略は(s1, s2, s3)と いう表記になるところだが,この教材ではその表記を短縮して文字列s1s2s3で表すことにする.)たとえば戦略cpgは
「先手がgを出したらcを,先手がcを出したらpを,先手がpを出したらgを出す」
という,必ず負ける戦略を表す.
すると後手の戦略は3×3×3 = 27個あって,それらは以下のとおり: ggg ggc ggp
gcg gcc gcp gpg gpc gpp cgg cgc cgp ccg ccc ccp cpg cpc cpp
pgg pgc pgp pcg pcc pcp ppg ppc ppp
リマーク3.2 後手の戦略は自分の取るべき行動をすべての可能な場合について指定する一方で,先手の行動を指定するこ とはできない.したがって「先手がgで後手がc」といった「経路」(9個ある)は戦略とはべつものである.また,「先手 がgならば自分はc」という特定の意思決定点における「選択肢」(ひとつの枝に対応)も戦略ではない.後手の戦略が9 個あると誤答した人は,これらいずれかの誤解をしていると思われる.
演習3.3 (最重要; 情報集合,部分ゲーム,戦略の数) 3人のプレイヤー1, 2, 3が,それぞれ2つの選択肢a, a′;b,b′;c,c′を持っている.1, 2, 3はこの順番で選択肢の1つを選んでいくが,先に決定したプレーヤーの 選択内容が必ずしも他のプレーヤーに伝わらないとし,次の3つのケースを考える:
Case 1 先に決定したプレーヤーの選択内容はすべて他のプレーヤーの知るところとなる.
Case 2 Player 1の選択内容は2, 3 の両方にわかるが,2の選択内容は3にはわからない.
Case 3 Player 1の選択内容は2だけにわかり2の選択内容は3にわかる.
Cases 1, 2, 3のそれぞれについて(利得は無視した上で), (i)情報集合に注意しながら展開形ゲームで表現せよ; (ii)全体ゲーム以外の部分ゲームをすべて特定せよ; (iii) Player 3の純粋戦略の個数を求めよ.
正解例. (i)展開形ゲームは以下のとおり: いずれのケースにおいてもPlayer 2はPlayer 1の選択内容が分かる.このこ
a′ a
b
b′
b
b′
2
2 1
c
c
c
c c′
c′
c′
c′ 3 3 3 3
a′ a
b
b′
b
b′
2
2 1
c
c
c
c c′
c′
c′
c′ 3 3
a′ a
b
b′
b
b′
2
2 1
c
c
c
c c′
c′
c′
c′ 3 3
Case 1 Case 2 Case 3
とはPlayer 2の上の決定点と下の決定点が異なる情報集合に属することで表現されている.Case 1ではPlayer 3は1,
2の選択内容が分かる.このことはPlayer 3の4つの決定点が異なる情報集合に属することで表現されている.Case 2
ではPlayer 3は1の選択内容が分かるが2の選択内容は分からない.このことはPlayer 3の上2つの決定点が同じ情
報集合に,下2つの決定点が別の情報集合に属することで表現されている.たとえば上2つの点からなる情報集合は,1 がaを選んだ結果到達したことは分かるが,2がbを選んだのかb′を選んだのかは分からないことを表す.Case 3では
Player 3は2の選択内容が分かるが1の選択内容は分からない.このことはPlayer 3の上から1つ目と3つ目の決定点
が同じ情報集合に,上から2つ目と4つ目の決定点が別の情報集合に属することで表現されている.たとえば上から1つ 目と3つ目の点からなる情報集合は,2がbを選んだ結果到達したことは分かるが,1がaを選んだのかa′を選んだのか は分からないことを表す.
(ii) Case 1では全体ゲーム以外に6個部分ゲームがある.Player 2の決定点から始まるものが2個で,Player 3の決 定点から始まるものが4個である.Case 2では全体ゲーム以外に2個部分ゲームがある.Player 2の決定点から始まる もの2個である.Case 3では全体ゲーム以外に部分ゲームはない.Player 2の決定点以降の点をすべてふくむ木は情報 集合を切ってしまうからである.Player 3の決定点以降の点をすべてふくむ木も同様に情報集合を切ってしまう.
(iii)プレーヤー3の純粋戦略の個数はCase 1では2×2×2×2 = 16個(ひとつの戦略はcc′cc′のような4文字で表 せる),Case 2では2×2 = 4個(上の情報集合でcとc′の2個の選択肢,下の情報集合でもcとc′の2個の選択肢が ある;ひとつの戦略はc′cのような2文字で表せる),Case 3では2×2 = 4個である.
演習3.4 (最重要; 展開形ゲームのナッシュ均衡と部分ゲーム完全均衡: 利得の順序に注意) 以 下 の 展 開 形 ゲームの部分ゲーム完全均衡とナッシュ均衡を求めなさい.なお,利得は Player A のものを先に書いて いる.
正解例. 展開形は以下の左図のようになる.バックワードインダクション(逆向き帰納法)により,部分ゲーム完全均衡は
B V D
D
V
D
V A
A
(7,3)
(5,5)
(4,6)
(6,4)
Player B
D V
Player A DD 7,3 4,6 DV 7,3 6,4 VD 5,5 4,6 VV 5,5 6,4
(DV,V)となる(赤い矢印で表示).ただしPlayer Aの戦略DVは上の決定点で(Aが Dを選択した場合) Dを選び,
下の決定点(AがVを選択した場合) Vを選ぶような戦略である.
戦略形は右表のようになる.ただし,Player Aの戦略の最初の文字は上の決定点で選ぶ枝を,2文字目は下の決定点で 選ぶ枝を表す.最適反応に対応する利得にマークすることにより,ナッシュ均衡は(DV, V)と求まる.
演習3.5 (展開形ゲームを作って解く) 次の戦略形で表される同時ゲームに時間を導入して以下のように修正
する: まずPlayer AがD かV を選び,その結果を見てPlayer BがD かVを選ぶ.
Player B
D V
Player A D 7,3 4,6 V 5,5 6,4
修正された交互ゲームの展開形と戦略形を書き,部分ゲーム完全均衡とナッシュ均衡を求めよ.
正解例. 展開形は以下のようになる.バックワードインダクション (逆向き帰納法)により,部分ゲーム完全均衡は(V, VD)となる(赤い矢印で表示).ただしPlayer Bの戦略VDはAがDを選択した場合Vを選び,AがVを選択した 場合Dを選ぶような戦略である.
戦略形は以下のようになる.
B V D
D
V
D
V
B (7,3)
(5,5) (4,6)
(6,4) A
Player B
DD DV VD VV
Player A D 7,3 7,3 4,6 4,6 V 5,5 6,4 5,5 6,4
ただし,Player Bの戦略の最初の文字は上の決定点で選ぶ枝を,2文字目は下の決定点で選ぶ枝を表す.最適反応に対応
する利得にマークすることにより,ナッシュ均衡は(V,VD)と求まる.
演習3.6 (展開形ゲームを解く; 利得の順序に注意) 以下の展開形ゲームの部分ゲーム完全均衡とナッシュ均
衡を求めよ.なお,利得はPlayer Aのものを先に書いている.
B
A
A
6,4
0,0
0,0
4,6 X
Y
X
X
Y Y
正解例. バックワードインダクション(逆向き帰納法)により,部分ゲーム完全均衡は(XY, Y) となる(左図に赤い矢印 で表示).ただしPlayer Aの戦略XYはBがXを選択した場合Xを選び,BがYを選択した場合Yを選ぶような戦 略である.
B
A
A
6,4
0,0
0,0
4,6 X
Y X
X
Y Y
Player B
X Y
Player A XX 6,4 0,0 XY 6,4 4,6 YX 0,0 0,0 YY 0,0 4,6
戦略形は右表のようになる.ただし,Player Aの戦略の最初の文字は上の決定点で選ぶ枝を,2文字目は下の決定点 で選ぶ枝を表す.最適反応に対応する利得にマークすることにより,ナッシュ均衡は(XX, X), (XY, Y), (YY, Y)と求 まる.
演習3.7 (最重要; 展開形ゲームの部分ゲーム完全均衡と弱支配) 次の展開形ゲームにおいて,部分ゲーム完
全均衡が弱支配される戦略をふくむことをしめせ.ただし第2段階の点線で結ばれた上下2点はPlayer 2の 情報集合を表す.
正解例. このゲームには全体ゲーム以外の部分ゲームがないため,次の戦略形より,(a, d)と(c, e)がナッシュ均衡かつ部 分ゲーム完全均衡になる.ところが後者の部分ゲーム完全均衡にふくまれるeはdに弱支配される.
Player 2
d e
Player 1 a 4,3 0,2 b 1,2 2,1 c 3,2 3,2 リマーク3.3 以下の点に注意:
• Player 1の決定点から始まる部分ゲームはa,b,cの3つの枝を含まなければならない.cを外してしまうと,部
分ゲームの条件のひとつである「全体の展開形ゲームの部分で,ひとつの点を含む情報集合から後に続くすべての 点を含む」に反してしまう.
•「完全ベイジアン均衡」という均衡概念をもちいれば,弱支配される戦略eは均衡にふくまれないことをしめせる (演習4.6).
•「部分ゲーム完全均衡が弱支配される戦略をふくむ」という結論はゲームを若干修正すれば変わってしまう.
Player 1が選択肢a,b,cからひとつを選ぶのを以下の展開形ゲームのように2段階に分ける.つまりcを選ぶか
どうかをまず決め,cを選ばなかったばあい次にa,bのどちらを選ぶかを決める.このゲームの部分ゲーム完全均
衡は弱支配される戦略eをふくまないことを以下のように示せる: 2段階目のPlayer 1の決定点から始まる部分 ゲームの戦略形は以下の通りであり,この部分ゲームにおける均衡は(a, d)のみである.
Player 2
d e
Player 1 a 4,3 0,2 b 1,2 2,1
逆向き帰納法により第1段階に戻って解くと,Player 1がyを選んだときの利得は4でcを選んだときの利得は 3なので,部分ゲーム完全均衡は(ya, d)となる.
演習3.8 (展開形ゲームのナッシュ均衡と部分ゲーム完全均衡; 部分ゲームが複数均衡を持つ場合) 最 初 に
Player 2がy (yes)または n(no)を選び,y を選んだばあい次にPlayers 1と2が同時ゲームをプレーする
ような,以下の図で表された展開ゲームを考える.ただし終点の利得はPlayer 1 のものを先に書いている. (i)この展開形ゲームを戦略形に直せ.
n
2,2 y
2
b a
1 d 0,0
c 3,1
d 1,3 c 0,0 2
(ii)この展開形ゲームのナッシュ均衡をすべて求めよ.
(iii)この展開形ゲームの部分ゲーム完全均衡をすべて求めよ.
正解例. (i)以下の通り.ここでたとえばycとは「最初の情報集合でyを,最後の情報集合でcを取る戦略」である.(利
得に引いた下線は問(ii)でもちいる.)
Player 2
yc yd nc nd
Player 1 a 3,1 0,0 2,2 2,2 b 0,0 1,3 2,2 2,2
(ii)前問の利得表で最適反応に対応する利得に下線を引くことによりナッシュ均衡は(a, nc), (a, nd), (b, yd)の3つで ある.
(iii)部分ゲーム完全均衡は(a, nc)と(b, yd)の2つである.解き方をふたつしめす.
まず,部分ゲーム完全均衡とはあらゆる部分ゲーム(全体ゲームをふくむ)についてナッシュ均衡となるような戦略の組 である.ここで部分ゲームは,(a)全体ゲームおよび(b) 点1ではじまる同時ゲーム部分だけである.よって部分ゲーム 完全均衡は(a)全体ゲームのナッシュ均衡である(a, nc), (a, nd), (b, yd)のうち,(b)同時ゲームにあたる部分(最初の 文字と最後の文字;べつの言い方をすればnとyを除いた部分)がそのゲームのナッシュ均衡になっているものである.
ここで同時ゲームの戦略形は次の利得行列で表されるので,
Player 2
c d
Player 1 a 3,1 0,0 b 0,0 1,3 この部分のナッシュ均衡は(a, c)と(b, d)になる.
以上から部分ゲーム完全均衡は(a, nc), (a, nd), (b, yd)のうち(a, c)または(b, d)をふくむ,(a, nc)と(b, yd)となる.
別解として,逆向き帰納法で部分ゲーム完全均衡を求めよう.まず,点1ではじまる部分ゲームの解は上記の通り(a, c) と(b, d)である.
• この部分ゲームの解が(a, c)のときPlayer 2の利得は1なので,第1段階でPlayer 2はnを選んで利得2を確 保するのがベストである.よって部分ゲーム完全均衡は(a, c)とnを組み合わせた(a, nc)となる.
• この部分ゲームの解が(b, d)のときPlayer 2の利得は3なので,第1段階でPlayer 2はyを選んで利得3を得 るのがベストである(nを選んで2を確保するよりもよい).よって部分ゲーム完全均衡は(b, d)とyを組み合わ せた(b, yd)となる.
なお,ナッシュ均衡(a, nd)が部分ゲーム完全均衡にならないのは,(a, nd)のうち点1ではじまる部分ゲームにあたる
(a, d)がその部分ゲームの均衡でないためである.
演習3.9 (重要; 繰り返し囚人のジレンマ) 以下のそれぞれのステートメントの真偽を答えよ.ただし割引因