ゲーム理論 : 補助教材
三原麗珠 (H. Reiju Mihara)
∗香川大学図書館
2011 年 1 月
目 次
1 2011 年度ゲーム理論受講者へ 1
2 戦略形ゲーム 3
3 展開形ゲーム 15
4 情報不完備ゲーム 19
5 追加問題 20
1 2011 年度ゲーム理論受講者へ
ゲーム理論 (学問基礎科目 数学 B) の授業で配布する予定のハンドアウト, 必読文献,課題をまとめておく.変更があるばあいは,Web 上の講義ページ でアナウンスする.
まず,配布するハンドアウトおよびいちぶ書籍の必要部分を列挙する (括 弧内に識別コード).特に重要な部分,あるいはこれら以外の必読文献・参考 文献については,シラバスの「必読文献・参考文献」を参照のこと.
公開分 (Google サイトの講義ページから入手できるもの) は以下のとおり:
• 三原麗珠. シラバス (babygames11syllabus).
• 三原麗珠. ゲーム理論: 補助教材, 2011 年 1 月 (game1101notes; この文 書).
• 三原麗珠. 課題のあつかい (暫定版).
∗http://www5.atwiki.jp/reiju/
• 三原麗珠. 演習問題の正解 (game04ans). 演習問題番号などの修正が必 要かも.
• 三原麗珠. 渡辺 (2004) への訂正・コメントなど (watanabe04comm11). 非公開分 (香川大学 Moodle 上の本コース用ページに入手方法を掲載) は 以下のとおり:
• 茨木俊秀. 情報学のための離散数学. 昭晃堂, 2004. 第 1 章 (ibaraki04ch1). 参考.
• 奥野正寛. ミクロ経済学. 東京大学出版会, 2008. 第 4 章 (okuno08ch4). 参考.
• 三原麗珠. 板書の一部を再現したノート (babygames-notes).
• 梶井厚志, 松井彰彦. ミクロ経済学: 戦略的アプローチ. 日本評論社, 2000. 以下が必読部分:
– ホテリングモデルにかかわる部分 (238–242 頁,251 頁,305 頁) (kajii-m00p239)
– ホテリングモデルにかかわる三原ノート (kajii-m00p239notes). 次に,課題を授業の進行順にほぼ合わせて挙げる.各課題に取り組むべき タイミングはシラバスの「授業計画」に,この授業で解説する時期は「課題 のあつかい」という文書にまとめてある.正解は補助教材自体または「演習 問題の正解」に載っている.
• 補助教材 演習 2.4, 追加演習 2.1, 演習 2.6, 2.8 (似た問題をふくめると 演習 2.1-2.8),
• 補助教材 演習 5.1–5.5
• 補助教材 演習 2.9, 2.10 (この 2 題はやや発展的)
• 補助教材 演習 3.12
• 補助教材 演習 3.1–3.4
• 武藤 114–115 頁 練習問題 1–5
• 補助教材 演習 3.13, 3.6, 3.8, 5.6
• 武藤 68 頁,練習問題 1 (マックスミニ戦略,マックスミニ値は除外)
• 補助教材 演習 5.7 (やや発展的), 5.8
• 補助教材 演習 4.3–4.7, 5.9, 5.10
• 武藤 135 頁 練習問題 1, 2
• 補助教材 演習 3.10 (梶井・松井練習問題 13.1, 13.2)
2 戦略形ゲーム
このセクションでは非協力ゲーム理論 (noncooperative game theory) のう ち,行動決定が同時に行われる場合をあつかう.
最初に,非協力ゲーム理論の分野でもっとも有名な例である囚人のジレン マ (The Prisoner’s Dilemma) を考える.「ジレンマ」とは窮地,板挟み,困難 な状況のこと.
ある犯罪の容疑者2人 (じつは共犯) が別件で逮捕された.自白を引きだ すために,取り調べ人 (検事?) は2人を隔離してそれぞれの容疑者に脅し (はったり?) をかける (共犯であることは見抜いている; あとは自白が欲し い) :
• 2人とも黙秘を続ければともに 1 年の刑 (別件で) ,
• 1人だけが自白すれば直ちに釈放で相手は 9 年の刑,
• 2人とも自白すればともに 6 年の刑になる. この状況を非協力ゲーム理論の言葉に直そう.
リマーク2.1 具体的なシチュエーションである上の寓話を一歩抽象化したいわけで ある.具体的ケースをたくさん並べることに終わっていては大学で勉強する意味が半 減するから.
この戦略ゲーム (strategic game) の
• プレーヤー (players) は囚人 1 と囚人2で,
• それぞれのプレーヤーは〈黙秘〉と〈自白〉という2つの 戦略 (strate- gies) を持つ.
• 2人の戦略の組 (ペア) のおのおのにたいして,それぞれのプレーヤの 利得 (payoff) を表 (利得行列) にすれば下のようになる.たとえば戦略 ペア 〈黙秘, 自白〉—つまり囚人 1 が黙秘して囚人 2 が自白する状況— での利得の組は (−9, 0).(ただし第 1 項が囚人 1 の利得,第 2 項が囚人 2 の利得; 刑期をマイナスの利得とみなしている.)
囚人2
黙秘 自白
囚人 1 黙秘 −1, −1 −9, 0 自白 0, −9 −6, −6
リマーク2.2 後述するように,この特定の利得行列で表されたゲームはさまざまな 具体的シチュエーションを抽象化している.しかしわれわれはこの行列で表された特 定のゲーム以外のさまざまなゲーム(たとえば後で述べるBattle of the Sexes)をも 同時に考えるための言葉が欲しい.よって抽象化をさらにすすめてみよう.そのため に,以下では「ゲーム」を数学的オブジェクト(対象物)として一般的に定義するこ とにする.読者は「ここまで極端に抽象化をする必要があるのか!」と思うかもしれな い.たしかに実社会で接するレベルの抽象度は超えている.しかしせっかく大学に来 たんだから,またとない機会だと思ってついてきて欲しい.世界の見え方が変わって くるかもしれないよ.
補足2.1 ゲームを一般的に定義する前に,集合の記号を復習しておく.
集合 (set)とは「きちんと定義された相異なる《もの》のあつまり」と考えてお
けばよい.集合を構成する《もの》を要素 (element)と言い,たとえば集合 N = {香川,徳島,愛媛}は香川,徳島,愛媛の3つの要素を持つことになる.aが集合A の要素であるとき,a ∈ Aと書いて,aはAに属すると言う.aが集合Aの要素で ないとき,a /∈ Aと書く.たとえば,香川∈ Nであり,高知∈ N/ である.
太字のRは慣例的に「すべての実数の集合」を表す.実数とは数直線上の一点で 表せるような数(有理数と無理数をふくむ)を指すが,とりあえず「数」とだけ理解 してくれても問題ない.
n個の集合S1, S2, . . . , Snから1つずつ要素si∈ Siを選んで,i = 1, 2, . . . , n の順に並べた束(s1, s2, . . . , sn)をn-組(n-tuple)という.このようにして作られた すべてのn-組の集合をS1, . . . , Snの直積(direct product)といい,S1× · · · × Sn
と書く.すなわち
S1× · · · × Sn:= {(s1, . . . , sn) : s1∈ S1, . . . , sn∈ Sn} である.1
集合Aから集合B への関数 (function)あるいは写像 (mapping) f : A → B と は,定義域とよばれる集合Aの任意の要素x ∈ Aにたいして,値域と呼ばれる集合 Bの要素を1つ(その要素をf (x)と書く)対応させる関係である.要素に注目して
f : x 7→ f(x)と書くこともある.定義域や値域は明示されないことがある.たとえば
「関数f (x) = 2x」とあれば,通常はf : R → Rなる関数で,x 7→ 2xの対応を持つ ものを意味する.
定義 2.1 戦略形ゲーム (strategic game) とは以下の要素から構成される組 (S1, . . . , Sn; u1, . . . , un) である:
• プレーヤー (players) の集合 {1, . . . , n} (この教材では上記の組には明 示的にふくめないことにする)
• それぞれのプレーヤー i について,i の戦略集合 (the set of strategies) Si
• それぞれのプレーヤー i について,i の利得関数 (payoff function) ある いは効用関数 (utility function)2
ui: S1× · · · × Sn→ R
1記号 := は等号の一種で,左辺を右辺によって定義するという意味.
2定義域と値域を明示しないと関数をきちんと定義したことにならないため,この利得関数の 定義では,あえてそれらの集合を明示した.(利得関数 ui の定義域は後述する S1× · · · × Sn
で,値域はすべての実数の集合 R であることが分かる.) ところが最近のゲーム理論入門テキ ストでは記号化を嫌って,定義域や値域はおろか戦略集合 Siさえ明示的に記号化しないことが 多い.(むかしとちがって最近は小学生に集合の記号を教えないためだろうか.) そのばあい,た とえば「任意の si∈ Siについて」と書くかわりに,「プレーヤー i の任意の戦略 siについて」
と言葉で書く.つまりプレーヤー i の戦略の集合は記号化しないまでも分かっているものとして 扱われている.
プレーヤー i の戦略集合 Si は i がどういう行動を選べるかを記述する.3 各プレーヤーの利得関数の定義域 S1× · · · × Snに属する要素 (s1, . . . , sn) を戦略の組あるいは戦略プロファイル (strategy profile) とよぶ.つまり戦略 プロファイルは「だれがどの戦略を採るか」という,全員の戦略の組合せを 記述している.
プレーヤー i の利得関数とは,任意の戦略プロファイル (s1, . . . , sn) にたい して,そのプロファイルが選ばれたときのプレーヤー i の利得 ui(s1, . . . , sn) を実数で与える関数である.4
例 2.1 上の囚人のジレンマでは,S1 = S2 = {〈黙秘〉,〈自白〉}.利得関数 u1,u2はたとえば u1(〈黙秘〉,〈自白〉) = −9 や u2(〈黙秘〉,〈自白〉) = 0 とい う値をとる.
リマーク2.3 2人のプレーヤーからなる戦略形ゲームは利得行列で表せた.いま利得 行列のそれぞれの枡目に,その枡目に対応する戦略ペアが取られたときの(利得ペア のかわりに)結果(アウトカム)を記入する.こうやって得られる表をゲーム・フォー ム(ゲーム形式, game form)とかメカニズム(mechanism)とよぶ.たとえば2車線 道路のある地点での対向車の運命は以下のゲーム・フォームで与えられる:
ドライバー2 左側 右側 ドライバー1 左側 無事 衝突 右側 衝突 無事
囚人のジレンマの分析に戻る.「2人の囚人は脅しを本気にして,できるだ け自分の刑期を短くしたいと考える」と仮定.つまりこのゲームを信じ,自 分の利得を最大化したいと.すると
• 2人が隔離されている状況では,合理的なプレーヤは自白を選ぶだろ う.相手が黙秘しようが自白しようが,自分は自白したほうが有利 (利 得が高い) だから.(演習: 表でチェックせよ.)
• その結果実現する戦略ペアは〈自白, 自白〉で利得のペアは (−6, −6).
• ところがふたりがともに黙秘する戦略ペア〈黙秘, 黙秘〉にたいする利得 ペアは (−1, −1).この方がどちらのプレーヤにとってもより望ましい. (「〈黙秘, 黙秘〉は〈自白, 自白〉よりも パレート優位 (Pareto-superior) である」という.)
協力しあえばプレーヤー全員に利益があるのに,それぞれのプレーヤーが 相手に「ただ乗り (free riding)」しようとしてしまうため,その利益を実現 できない.現実社会でもこの種のジレンマはいろいろある.国際紛争,ゴミ 収集所の清掃,など.
3具体的なゲームが決まれば戦略を具体的に列挙できるが,ゲーム一般をあつかうときにはそ うはできないために,プレーヤー i の取りうる戦略を集合 Siによって抽象的に表現する.
4利得関数の代わりに,戦略集合 S1× · · · × Sn上で定義された「選好」を考えることもある.
囚人のジレンマでは,囚人 1 にとって〈自白〉が支配戦略 (dominant strat- egy): (囚人 2 の戦略がなんであっても) 囚人 1 は〈自白〉という戦略を選ぶ のがもっとも有利になっている.囚人 2 にとっても〈自白〉が支配戦略になっ ている.
ノーテーション (記号): i 以外のプレーヤーの戦略集合の直積 S1× · · · × Si−1× Si+1× · · · × Snを S−i,その要素を s−iなどと書く.たとえば 4 人の ばあい,s−2= (s1, s3, s4),(s′2, s−2) = (s1, s2′, s3, s4),s∗−4= (s∗1, s∗2, s∗3). 定義 2.2 戦略形ゲーム (S1, . . . , Sn; u1, . . . , un) が与えられているとする. 次の不等式群がみたされるとき,プレーヤー i の戦略 si∈ Siがプレーヤー i の戦略 s′i∈ Siを (強) 支配する ((strictly) dominates) という: 他のプレー ヤーの任意の戦略組 s−i∈ S−iにたいして,5
ui(si, s−i) > ui(s′i, s−i).
次の (i),(ii) の不等式群がみたされるとき,戦略 si ∈ Siが戦略 s′i ∈ Si
を弱支配する (weakly dominates) という [武藤 34 頁]: 6(i) すべての s−i∈ S−iにたいして,ui(si, s−i) ≥ ui(s′i, s−i); (ii) ある s−i ∈ S−iにたいして, ui(si, s−i) > ui(s′i, s−i).
戦略 si∈ Siが個人 i の支配戦略 (dominant strategy) であるとは,siが si
以外のすべての戦略 s′i∈ Siを支配することをいう [武藤 33—34 頁]. 戦略 si ∈ Siが個人 i の弱支配戦略 (weakly dominant strategy) であると は,siが si以外のすべての戦略 s′i∈ Siを弱支配することをいう [武藤 44 頁]. リマーク2.4 「siがs′iを支配する」「siがs′iを弱支配する」という概念は,同一プ レーヤーの戦略を比較するものである.定義2.2でsiとs′iは同一プレーヤーの戦略 になっている(ともにSi の要素である)ことに注意.たとえばプレーヤー1の戦略 s1がプレーヤー2の戦略s2を支配することは,概念上ありえない.
リマーク2.5 戦略si∈ Siが戦略si′ ∈ Siを支配するとき,siはs′iを弱支配すると 当然いえる.(支配が成り立つとき,弱支配を定義するいずれの不等式も>でなりたっ ている.左辺が右辺より大きいということは,左辺が右辺以上であることの特殊ケー スにすぎない.)しかしsiがs′iを弱支配するとき,支配するとはかぎらない.すな わち支配は弱支配より「強い」条件である.
リマーク2.6 2人ゲーム(S1, S2; u1, u2)のばあい,プレーヤー1の戦略s′1∈ S1が プレーヤー1の戦略s′′1 ∈ S1を支配するのはつぎの条件がみたされるとき: プレー ヤー2のすべての戦略s2∈ S2にたいして,
u1(s′1, s2) > u1(s′′1, s2).
5以下の不等式は,i 以外の戦略が s−iで固定されているもとでは,i にとって siを選ぶ方
が s′iを選ぶよりも利得が高いことを意味する.「siが s′iを支配する」と言えるためには,他人 の戦略の任意の組合せ s−iについて,その不等式が成り立つ必要があることに注意.
6文献によっては「弱支配」を「支配」と呼ぶことがある.
たとえば,囚人のジレンマではプレーヤー1の〈自白〉がプレーヤー1の〈黙秘〉を 支配:7
u1〈自白〉( ,〈黙秘〉) > u1(〈黙秘〉,〈黙秘〉) u1〈自白〉( ,〈自白〉) > u1(〈黙秘〉,〈自白〉)
例 2.2 つぎのゲーム (男女の闘い; Battle of the Sexes; Bach or Stravinsky) ではいずれのプレーヤーも支配戦略を持たない (演習: 説明せよ):
ふみ Bach Stravinsky いちろう Bach 2, 1 0, 0
Stravinsky 0, 0 1, 2
• ふみが〈Bach〉という戦略を選んだとき,いちろうの利得を最大にす る戦略は〈Bach〉になっている.このとき「ふみの〈Bach〉という戦 略にたいするいちろうの最適反応 (best response) は〈Bach〉である」 という.
• 逆に,いちろうの〈Bach〉という戦略にたいするふみの最適反応は
〈Bach〉になっている.
• 戦略のペア (s, s′) がたがいに相手の戦略にたいする最適反応からなって いるとき (つまり s は s′にたいする最適反応,s′は s にたいする最適反 応),そのペアをナッシュ均衡 (Nash Equilibrium) とよぶ.「おたがいが ナッシュ均衡を構成する戦略をとっているかぎり,どちらもそのペアを 離れる誘因はない」という意味で,安定したペアである.
• 〈Bach, Bach〉はこのゲームのナッシュ均衡である.
• 〈Stravinsky, Stravinsky〉もナッシュ均衡である.
• これら以外にナッシュ均衡はない.
補足2.2 最適反応を定義する前に,「最大化問題の最適解」という概念を復習してお く.実数値関数f : A → Rの最大化問題(maximization problem)とは
「条件x ∈ Aのもとでf (x)を最大化せよ」
という問題のことをいう.ある特定のx∗∈ Aがこの問題の最適解(optimal solution) であるとは,すべてのx ∈ Aについて,
f (x∗) ≥ f(x)
となることをいう.たとえば[0, 2] = {x ∈ R : 0 ≤ x ≤ 2}を0以上2以下の実数の 集合(区間)とするとき,g(x) = −(x − 1)2 で与えられた関数g: [0, 2] → Rは,任 意のx ∈ [0, 2]についてg(1) ≥ g(x)を満たすので,x = 1は最大化問題の最適解で ある(グラフ参照).
7以下の式では,s′
1 =〈自白〉, s′′1 =〈黙秘〉であり,最初の式で s2=〈黙秘〉,2 番目の式 で s2=〈自白〉となっている.S2= {〈黙秘〉,〈自白〉} だから,これですべての s2∈ S2を考 えたことになる.
定義 2.3 戦略形ゲーム (S1, . . . , Sn; u1, . . . , un) が与えられているとする.プ レーヤー i の戦略 si∈ Siが他のプレーヤーのとる戦略の組
s−i= (s1, . . . , si−1, si+1, . . . , sn) ∈ S−i
にたいする最適反応 (best response) であるとは,以下の条件8 をみたすこと である: すべての s′i∈ Siにたいして,
ui(si, s−i) ≥ ui(s′i, s−i) となる.
リマーク2.7 「戦略siは戦略組s−iにたいする最適反応である」という言い方に注 意.どういうs−iにたいするものかを明示せずに「戦略si は最適反応である」と言 うのは概念上正しくない.
リマーク2.8 2人ゲーム(S1, S2; u1, u2)のばあい,プレーヤー1の戦略s′1∈ S1が プレーヤー2の戦略s2∈ S2にたいする最適反応であるとは,すべてのs′′1 ∈ S1につ いて,
u1(s′1, s2) ≥ u1(s′′1, s2)
となることである.ここでプレーヤー2の戦略s2が両辺に共通である(「固定されて いる」)ことに注意.相手の戦略s2を固定したうえでプレーヤー1が自分の戦略s′′1
を動かして見つけた最適解がs′1になっている.
すべてのs′′1 ∈ S1についてこの不等式が成り立つことの意味を利得表で言えば,あ る特定の列を(s2に対応するものに)固定したうえで行(つまりPlayer 1の戦略s′′1) をいろいろ変えてu1の値がいちばん大きくなる行(戦略s′1に対応)を見つけている ことになる.9
演習 2.1 ふみの〈Bach〉にたいするいちろうの最適反応 (best response) は
〈Bach〉であることをチェックせよ.
定義 2.4 戦略プロファイル s∗= (s∗1, . . . , s∗n) がナッシュ均衡 (Nash Equilib- rium) であるとは,おのおののプレーヤー i について,戦略 s∗i が他のプレー
ヤーのとる戦略 s∗−i= (s∗1, . . . , s∗i−1, s∗i+1, . . . , s∗n) への最適反応となっている こと.10
演習 2.2 (i) 以下の利得表で表わされるゲームを考える. 粕さん
左 右
沙理さん 上 14, 14 7, 17 下 17, 7 10, 10
8以下は s
iが,最大化問題「条件 s′i∈ Siのもとで ui(s′i, s−i) を最大化せよ.ただし s−i
は固定されている」の最適解になることを意味している.
9s′
1 と s′′1 は別変数である.上の定義の中身をたとえば次のように言い換えてもまったく同 じである: 「すべての t1∈ S1について,u1(s′1, s2) ≥ u1(t1, s2) となることである.」
10べつの言い方をしてみよう.いま,プレーヤー i が予想する他のプレーヤーの戦略の組を
˜
s−iとする.s∗がナッシュ均衡であるとは,任意の i にたいして,(i) s∗i が予想 ˜s−iにたいす
る最適反応になっており,かつ (ii) 予想が合理的であること (˜s−i= s∗−i) を意味している.奥 野 4.3.1 節を参照.
沙理さんの支配戦略について正しいものを選べ. シ.沙理さんの支配戦略は上である.
ハ.沙理さんの支配戦略は下である.
イ.沙理さんの支配戦略は(下, 右)である. カ.沙理さんの支配戦略は存在しない.
(ii) 問題 (i) のゲームにかんする記述のうち正しいものを選べ.[パレート 優位,パレート効率が未定義.]
パ.(上, 左) は (下, 左) にたいしてパレート優位である. ユ.(下, 左) は (下, 右) にたいしてパレート優位である. ウ.(下, 右) はパレート効率である.
イ.(下, 左) はパレート効率である.
演習 2.3 囚人のジレンマを考える.囚人 2 の戦略〈黙秘〉にたいする囚人1 の最適反応はなにか? 囚人 2 の戦略〈自白〉にたいする囚人1の最適反応は なにか? このゲームにナッシュ均衡は存在するか? 存在するならすべて列挙 せよ.
演習 2.4 戦略形ゲーム (S1, S2; u1, u2) が与えられている.戦略プロファイル s = (s1, s2) がナッシュ均衡であるとは,以下のどの条件をみたすことか: (1) u1(s1, s2) ≥ u1(s′1, s2) for all s′1∈ S1
and u2(s1, s2) ≥ u2(s′1, s2) for all s′1∈ S1. (2) u1(s1, s2) ≥ u1(s1, s′2) for all s′2∈ S2
and u2(s1, s2) ≥ u2(s1, s′2) for all s′2∈ S2. (3) u1(s1, s2) ≥ u1(s′1, s′2) for all s′1∈ S1, s′2∈ S2
and u2(s1, s2) ≥ u2(s′1, s′2) for all s′1∈ S1, s′2∈ S2. (4) u1(s1, s2) ≥ u1(s′1, s2) for all s′1∈ S1
and u2(s1, s2) ≥ u2(s1, s′2) for all s′2∈ S2.
正解例. (4)が正解.最初の式はs1がs2にたいして最適反応であることを,次の式は
s2がs1にたいして最適反応であることを言っている(リマーク2.8).たとえば最初の 式でs2が両辺に共通である(「固定されている」)ことに注意.プレーヤー1の利得 u1の最大化を考えるときは,相手の戦略s2を固定したうえで,自分の戦略s′1を動
かしてみるわけである.たとえば(2)の最初の不等式はプレーヤー1の利得u1 を最 大化するとき,自分ではないプレーヤー2の戦略s′2 を動かしているのでおかしい.
追加演習 2.1 戦略形ゲーム (S1, S2, S3; u1, u2, u3) が与えられている. (i) いま,s′2 および s′′2 はプレーヤー 2 の戦略 (つまり S2 の要素) である とする.s′2が s′′2を支配するとは,任意の (s1, s3) について,どういう条件が 成立することか?条件を不等式でしめせ.
(ii) 戦略プロファイル (s∗1, s∗2, s∗3) がナッシュ均衡であるとは,以下の条件 (a), (b), (c) がすべて成り立つことである:
(a) s∗1が (s∗2, s∗3) にたいする最適反応である; (b) s∗2が (s∗1, s∗3) にたいする最適反応である; (c) が にたいする最適反応である. 空欄を埋めて (c) を完成させよ.
また,条件 (b) を不等式をもちいて表現せよ.必要におうじて “for all si∈ Si” あるいは「すべての si ∈ Si にたいして」(ただし i は 1, 2, 3 のよ うな具体的な数字に置き換える) といった言葉を添えること.
正解例. (i)不等式は以下のようになる:
u2(s1, s′2, s3) > u2(s1, s′′2, s3).
意味としては,「他のプレーヤーの戦略がなんであろうとも,プレーヤー2にとって は,戦略s′2の方が戦略s′′2 よりも望ましい」となる.定義2.2の表現通りに書けば,
「他のプレーヤーの任意の戦略組s−2にたいして u2(s′2, s−2) > u2(s′′2, s−2)
となる」とすべきところだが, 「任意の(s1, s3)について」と問題文にあり,s−2= (s1, s3)と書けることから,正解のようにするのがよい.(戦略列(s1, s′2, s3)のこと を(s′2, s1, s3)と書くべきではない.(s′2, s−2)のような順番を無視した書き方は,s−2
といった短縮表現をもちいるばあいに留めるべき.)
参考.問題文中の表現「任意の(s1, s3)について」(for all (s1, s3) ∈ S1× S3)と 重複するので,“for all s1∈ S1, for all s3∈ S3”といった記述を添えてはならない.
参考.すでに問題文にs′2およびs′′2 がS2の要素であると記述されているので,“for s′2, s′′2 ∈ S2”といった表現は不要.この表現を用いると,問題文中のs′2, s′′2 と解答の それが異なるという誤解を与える可能性がある.かりに“for all s′2, s′′2 ∈ S2”と書い たら,両者ははっきりと異なるものになってしまう.その際,たとえばs′2= s′′2 とな る場合も不等式が成り立つことを要求することになり,あきらかに条件は満たせない.
(ii)条件(c)は「s∗3が(s∗1, s∗2)にたいする最適反応である」となる. 条件(b)を不等式をもちいて表現すると,以下のように書ける:
u2(s∗1, s∗2, s∗3) ≥ u2(s∗1, s2, s∗3) for all s2∈ S2.
定義2.3を参照.この不等式は,戦略s2を集合S2のなかでいろいろ変えたとき,右 辺の利得が最大化されるのがs2 = s∗2のときであることを言っている.不等号を > と間違わないように注意.
参考.u2(s∗1, s2)といったナンセンスな表記も見られた.利得関数は戦略プロファ イルをインプットとし実数をアウトプットとする関数である.いま問題にしているの は3人ゲームだから戦略プロファイルは3人の戦略を並べたものである.(s∗1, s2)で は2人分の戦略しか書かれていないのでダメ.期末試験ではヒントなしで「戦略プロ ファイル(s1, s2, s3)がナッシュ均衡である」を定義せよと言われても正解を答えられ るようにしておくべき.
演習 2.5 以下のゲームを考える.
Player 2
l m r
Player 1 u 1, −1 1, −1 1, 1 d 100, 0 0, 100 −1, 1
(i) Player 1 の戦略 u にたいする Player 2 の最適反応を以下のリスト [次の設 問と共通] から選べ.
(ii) Player 2 の支配戦略を以下のリストから選べ.
(1) 戦略 u, (2) 戦略 d, (3) 戦略 l, (4) 戦略 m, (5) 戦略 r, (6) 存在しない. (iii) このゲームの (純粋戦略による) ナッシュ均衡は
(1) (u, l) だけである,(2) (u, m) だけである,(3) (u, r) だけである,(4) (d, l) だけである,(5) (d, m) だけである,(6) (d, r) だけである,(7) 存在しない. 演習 2.6 以下のゲームを考える.
Player 2
l m r
Player 1 U 2, 3 3, 2 0, 0 M 1, −1 1, −1 1, 1 D 2, 1 1, 2 −1, 1
(i) Player 1 の戦略 U にたいする Player 2 の最適反応を以下の正解候補 [設 問 (ii) と共通] から選べ.
(ii) Player 2 の支配戦略を以下の正解候補から選べ.
設問 (i), (ii) の正解候補: (1) 戦略 U , (2) 戦略 M , (3) 戦略 D, (4) 戦略 l, (5) 戦略 m, (6) 戦略 r, (7) 存在しない.
(iii) Player 1 の戦略 U は M を支配するか?弱支配するか? Player 1 の戦略 U は D を支配するか?弱支配するか?
(iv) このゲームの (純粋戦略による) ナッシュ均衡を以下の正解候補から選べ. [すべての正解候補を選んだ場合のみ得点]
設問 (iv) の正解候補 (均衡が存在しない場合は (0) を,存在する場合はそれ らすべて (1 つとは限らない) を (1)–(9) から選ぶこと): (1) (U, l),(2) (U, m), (3) (U, r),(4) (M, l),(5) (M, m),(6) (M, r),(7) (D, l),(8) (D, m),(9) (D, r), (0) 存在しない.
正解例. (i) U にたいする最適反応はlである.U に対応する行のPlayer 2の利得は 以下のようになり,Player 2がlを選んだときに最大化される.
u2(U, l) = 3 u2(U, m) = 2 u2(U, r) = 0.
Player 1の戦略U にたいするPlayer 2の最適反応を求めるには,U に対応する行の
なかでPlayer 2の3つの利得を比較し,いちばん高い利得(複数あればすべて)に下
線などでマークすればいい.その利得の列に対応するPlayer 2の戦略(いまのばあい はl)がU にたいする最適反応である.(言葉では分かりにくいが,黒板でやれば一目 瞭然.)
(ii) Player 2は支配戦略を持たない.もし支配戦略が存在してs2であれば,s2は Player 2の(s2を除く)いかなる戦略s′2 も支配するため,Player 1の任意の戦略s1
にたいして,s2がs′2よりも高い利得をもたらす,つまり,u2(s1, s2) > u2(s1, s′2)と
なるはずである.つまりs2は任意のs1にたいする唯一の最適反応になっているはず である.ところが以下で分かるように,つねに最適反応になる戦略はl, m, rのなか には存在しない:
• Uにたいする最適反応はl.
• Mにたいする最適反応はr.
• Dにたいする最適反応はm.
参考.Player 2の支配戦略とは戦略なので,l, m, rのいずれかでしかありえない.
支配戦略自体が(D, l)のような戦略の組(ペア)になることはない.ただし,「支配戦 略の組」といえば,文字通り戦略の組であり,たとえば囚人のジレンマの解がそれに あたる.
(iii) UはM を支配しないし,弱支配しない.弱支配しないことをしめせば十分で
ある.UがMを弱支配するとすれば,以下の不等式がすべて満たされるはずである. しかし実際は最後の式が満たされない:
• u1(U, l) ≥ u1(M, l). これは2 > 1となるため,等号なしで成立.
• u1(U, m) ≥ u1(M, m). これは3 > 1となるため,等号なしで成立.
• u1(U, r) ≥ u1(M, r). これは0 ≥ 1となり,実際は0 < 1であることに反する. U はDを支配しないが,弱支配する.以下から弱支配するための条件を満たすこ とが分かる:
• u1(U, l) ≥ u1(D, l). これは2 ≥ 2となるため,等号で成立.不等号>では成 立しないため,UはDを支配しないことが分かる.
• u1(U, m) ≥ u1(D, m). これは3 > 1となるため,等号なしで成立.
• u1(U, r) ≥ u1(D, r). これは0 > −1となるため,等号なしで成立.
参考.この問では間違えようがないが,ちょっと質問の仕方を変えると,「U がlを 支配する」とか「U がmを支配する」と答える誤解が多いので注意.そういうこと はありえない.一般に「戦略sがtを支配する」という概念は,同一プレーヤーの戦 略sとtを比較するものである.sとtは同一プレーヤーの戦略でなければならな い.(一般的に書くときはプレーヤーiの戦略であることを明示するため,だれの戦略 かはっきりしないsやtを使うよりも添字iのついたsi とかti という記号を使う
のが普通.)ここではU はPlayer 1戦略だから,それが支配できる戦略はPlayer 1 のものであるM かDしかありえない.
(iv) (U, l)と(M, r)がナッシュ均衡である.具体的な求め方を述べる:
• Player 2の各戦略にたいするPlayer 1の最適反応と,Player 1の各戦略にた
いするPlayer 2の最適反応を問(i)の正解例の要領で求める.
• 利得の両方にマークがついた「升目」(利得ペア)をすべてみつける.その升目 に対応する戦略の組がナッシュ均衡である.(理由.Player 1の利得にマーク がついているということは,その升目に対応するPlayer 2の戦略にたいして
Player 1が最適反応をしているということである.同様にPlayer 2の利得に
マークがついているということは,その升目に対応するPlayer 1の戦略にた
いしてPlayer 2が最適反応をしているということである.これらから,互い
に最適反応をしていることが分かる.)
参考.ナッシュ均衡を問われたときに誤って利得の組 (ペア) を答えないように. ナッシュ均衡とは戦略の組であり,だれがどの戦略を取るかを記述したものであるこ とに注意.
演習 2.7 以下のゲームを考える.
Player 2
s2 t2 u2
Player 1 s1 1, −1 1, −1 1, 1 t1 100, 0 0, 100 −1, 1 u1 0, 100 100, 0 −1, 1
Player 2 の戦略 t2にたいする Player 1 の最適反応は である. Player 1 の戦略 t1にたいする Player 2 の最適反応は である.こ のゲームの (純粋戦略による) ナッシュ均衡は
である.(たとえば「(s1, s2), (s1, t2)」のように,すべてのナッシュ均衡を挙 げること.)
次に簡単な真偽問題を載せる.試験では複数の真偽問題を組みあわせて出 題することが多いので注意.また,反例などによって簡単に理由があげられ るばあい,試験では理由を問うかもしれない.
演習 2.8 以下のそれぞれのステートメントの真偽を答えよ.
a. 非協力ゲーム理論は,プレーヤーたちがどのように協力を実現できるかを 分析できない.
b. (強) 支配される戦略がナッシュ均衡にふくまれることはない. c. (強) 支配戦略の組はナッシュ均衡になるとはかぎらない.
d. 戦略 s1が戦略 s′1 を (強) 支配するとき,戦略 s1は戦略 s′1を弱支配する.
e. 弱支配戦略は他のプレーヤーの任意の戦略にたいする最適反応である. f. ある混合戦略が相手のある戦略にたいする最適反応であるとき,その混合 戦略にふくまれる純粋戦略 (その混合戦略が正の確率を与える純粋戦略) はど れも,相手のその戦略にたいする最適反応である.
g. ナッシュ均衡から 1 人のプレーヤーだけが離れる (戦略を変える) ことに よって,そのプレーヤーの利得が改善されることはない.
h. ナッシュ均衡から同時に2人が離れる (戦略を変える) ことによって,そ の 2 人の利得が両方とも改善されることはない.
i. 戦略形ゲームに複数の均衡があるとき,特定のプレーヤーの利得はそれら どの均衡においても等しい.
j. もし (s1, s2) と (s′1, s′2) がナッシュ均衡であるとき,(s′1, s2) または (s1, s′2) もナッシュ均衡である.
正解例. a.偽.協力ゲーム理論は提携を組むひとびとが協力できることを前提として 分析.非協力ゲーム理論は協力できることを前提とせず,競争や協力などさまざまな 行動を個々のプレーヤーの意思決定レベルで分析.
b. 真.武藤44頁参照. c. 偽.武藤44頁参照.
d. 真.武藤33–34頁.逆にある戦略が他の戦略を弱支配するからといって,支配
するとはいえないことに注意.
e. 真.ただし任意の戦略にたいする唯一の最適反応とはかぎらない.
f. 真.たとえばS1 = {U, M, D}, S2 = {L, R}とする.Player 1 の混合戦略 p= (1/3, 2/3, 0) (U , M , D をそれぞれ1/3, 2/3, 0の確率でプレイする混合戦略) がPalyer 2の混合戦略q= (q, 1 − q)にたいする最適反応のとき,U やM 自体も qにたいする最適反応であるという意味.かりにU が最適反応でないばあい,Uに 正の確率を与えるよりは,ほかのMまたはDにすべての確率を与えた方が利得が高 くなるはずである.
g. 真.(s1, s2)がナッシュ均衡ならば,s1はs2にたいする最適反応だから(s2が 固定されているかぎり) s1 から離れてs′1 (ただしs′16= s1)に動くことで利得が増え ることはない.以下の不等式群がしめすところである:
u1(s1, s2) ≥ u1(s′1, s2) for all s′1∈ S1
h. 偽.たとえば囚人のジレンマ(武藤39頁あるいは31頁表2-1)では,均衡から 2人が同時に動くと2人の利得はともに改善する.
i. 偽.たとえばBattle of the Sexes (武藤67頁)では(サッカー,サッカー)と (映画,映画)が均衡.しかしPlayer Aの利得は前者で2,後者で1となって等しく ない.あるいは以下のような簡単なゲームを考えてもいい:
Player 2
L R
Player 1 U 1,1 0,0 D 0,0 2,2
j. 偽.たとえばBattle of the Sexes (武藤67頁)では (サッカー,サッカー)と (映画,映画)が均衡.しかし(映画,サッカー)も(サッカー,映画)も均衡ではない. 問iの正解例の別ゲームでも同様.
以下 2 題はややすすんだ演習問題.学生の答案作成能力や採点の手間など を考えると,試験でこのままの形で出すには厳しいものがある.必要な条件 が抜けているなど,設問に不完全な部分があれば適当に補って答えよ. 演習 2.9 室温が 0 度から 50 度の範囲で自由にコントロールできる,冷暖房 完備の部屋の温度設定を考える.この部屋には 5 人がいて,それぞれが自分 にとって最適な室温をこの範囲に持っており,その温度から離れれば離れる ほど快適さは下がる (単峰型の効用) とする.もちろん各人は自分の快適さを 最大化しようとするものとする.
(i) 各自に自分の最適室温を報告してもらって,室温をそれらの平均値に設定 する決め方を採用したとする.このとき,みんないつも本当の最適室温を報 告しようとする (その決め方が「戦略的操作にたえる」) といえるか? 各自の 戦略集合を [0, 50] = {x ∈ R : 0 ≤ x ≤ 50} とし (戦略は室温を表す),自分の 本当の最適室温を報告するのが弱支配戦略であるかどうかをしめせ. (ii) 各自に自分の最適室温を報告してもらうとし,全員がじっさいに本当の 最適室温を報告すると仮定する.どのような決め方を採用すれば,その決め 方で定まる室温が他の室温に (1 対1の) 単純多数決で負けることがないよう にできるか?
(iii) 問題 (ii) では全員が本当の最適室温を報告すると仮定した.じっさいは どうだろうか? 問題 (ii) で答えた決め方を採用したとき,みんないつも最適
室温を報告しようとするといえるか? 自分の本当の最適気温を報告するのが 弱支配戦略であるかどうかをしめせ.
演習 2.10 2 人以上の入札者が,セカンドプライス・オークションに参加し ている.これは参加者が入札額を他の参加者に分からないように紙に書いて 競り人に渡し,いちばん高い額をつけた参加者が落札する封印入札方式であ る.ただし,落札者が支払うべき価格は,落札者以外の参加者のつけた額で いちばん高いもの (2 番目に高い入札額) となる.もし最高の入札額を提示し た参加者が複数のばあい,その中からくじ引きで落札者を決め,支払うべき 価格はその最高額とする.入札者1の評価額 (当該商品を得るために払って もよいと思っている上限価格) が v1 のとき,どのような入札額 b1 を提示す
るのがいいか? 入札額として,評価額 v1をそのまま提示する戦略が弱支配 戦略であるかどうかをしめせ.ただし落札しなかったときの利得をゼロとし, 落札したときの利得を評価額から支払額を引いた値とする.
3 展開形ゲーム
「武藤」とあるのは,武藤『ゲーム理論入門』[?] のこと.まず武藤章末の 練習問題より易しめの問題を列挙する.
演習 3.1 武藤の事例 3-1(p. 71) と事例 2-1 (p. 25) をそれぞれ展開形ゲーム で表現せよ.[正解はそれぞれ図 3-1 と図 3-2.]
演習 3.2 武藤の図 3-3 (p. 79) の展開形ゲームを戦略形ゲーム表現に直せ.B の戦略をすべて列挙せよ.B の「維持-引き下げ (維下)」という戦略を展開形 ゲーム上に表現せよ.[正解は表 3-1.「維下」という戦略は図 3-3 では点線で 表現されている.演習 5.1の類題.]
演習 3.3 武藤の図 3-4 (p. 83) の展開形ゲームを戦略形ゲーム表現に直せ.純 粋戦略によるナッシュ均衡をすべて列挙せよ.[正解は表 3-2 と p. 83 本文. 演習 5.1の類題.]
演習 3.4 武藤の事例 3-6 (p. 87) のケース 1 とケース 2 のそれぞれを情報集 合に注意しながら展開形ゲームで表現せよ.それぞれのケースについて,全 体ゲーム以外の部分ゲームをすべて特定せよ.それぞれのケースについて, プレーヤー C の純粋戦略の個数を求めよ.[正解: 図 3-9(矢印と枝の数字は無 視) と本文 pp. 88-89.全体ゲーム以外の部分ゲームについてはケース 1 では 6 個,ケース 2 では 2 個を特定すればいい.プレーヤー C の純粋戦略の個数 はケース 1 では 2 × 2 × 2 × 2 = 16 個,ケース 2 では 2 × 2 = 4 個.]
演習 3.5 武藤の図 3-11 (p. 97) の展開形ゲームで,利得が一部欠けていると する.利得を記入してゲームを完成せよ.そして部分ゲーム完全均衡を求め よ.[正解: 利得はその図のとおり.本文の説明を参照.部分ゲーム完全均衡 は p. 98 の本文にある.]
演習 3.6 武藤の事例 3-5 (p. 72) の 2 期間のケースを展開形ゲームで表現せ よ.ただし割引因子を δ とする.このゲームには全体ゲーム以外の部分ゲー ムがいくつあるか.[正解: 図 3-12.全体ゲーム以外の部分ゲームは 4 個.] 演習 3.7 武藤の表 2-1 (p. 31) の戦略形ゲームを無限回繰り返す繰り返しゲー ムを考える.利得は割引因子 δ をもちいて p. 105 で与えられる平均利得で 定義する.
(i) 2人のプレーヤーがトリガー (永久懲罰) 戦略をとるときのプレイは毎期
「維持」をとりつづけることになることを確認せよ.
(ii) トリガー戦略の組がナッシュ均衡であることをしめそう.いま B がトリ ガー戦略をとっているとする.このとき,A がトリガー戦略をとったときの 利得と t 期にトリガー戦略を逸脱したときの利得を比べることにより,トリ ガー戦略が確実に A の最適反応になるための δ の値の範囲をもとめよ.
[正解: p. 106 の下から第 2 パラグラフ.pp. 106-108.] 演習 3.8 以下のそれぞれのステートメントの真偽を答えよ.
a. 囚人のジレンマの有限回繰り返しゲームでは,毎期裏切り (自白) をとり つづける戦略の組は部分ゲーム完全均衡である.
b. 囚人のジレンマの有限回繰り返しゲームで割引因子 δ がじゅうぶん大きけ れば,毎期裏切り (自白) をとりつづける戦略の組以外の部分ゲーム完全均衡 が存在する.
c. 囚人のジレンマの無限回繰り返しゲームでは,毎期裏切り (自白) をとりつ づける戦略の組は部分ゲーム完全均衡である.
d. 囚人のジレンマの無限回繰り返しゲームで割引因子 δ がじゅうぶん大きけ れば,毎期裏切り (自白) をとりつづける戦略の組以外の部分ゲーム完全均衡 が存在する.
[正解: 真,偽,真,真.]
演習 3.9 シュタッケルベルグの複占市場の部分ゲーム完全均衡 (武藤 pp. 111- 114) における先導者である企業 A の利潤は,少なくともクルーノー・ナッ シュ均衡における企業 A の利潤以上である理由をしめそう.シュタッケルベ ルグの複占市場では企業 A はクルーノー・ナッシュ均衡のときと同じ生産量 x = (a − c)/3 を選ぶことができたはずである.そのときの利潤はクルーノー ナッシュ均衡のときの利潤 uA= (a − c)2/9 と同じになっていたはずである (設問: それをしめせ).生産量 x を選べば同じ利潤 uAを得られたのに,企業 A はあえて x とは異なる生産量 x∗= (a − c)/2 を選んでいる.そのことから
シュタッケルベルグの複占市場の部分ゲーム完全均衡における企業 A の利潤 は少なくとも uA以上であることが分かる.
[正解: シュタッケルベルグの複占市場で企業 A が x = (a − c)/3 を選んだ とすれば,企業 B は x にたいする最適反応 y = (a − c)/3 を選んだはずであ る.この y が x にたいする最適反応であることは,戦略のペア (x, y) がナッ シュ均衡であることから分かる (武藤 p. 56).両企業の生産量がクルーノー・ ナッシュ均衡のときと同じだから,企業 A はクルーノー・ナッシュ均衡のと きと同じ利潤 uAを得ることができたはずである.]
演習 3.10 梶井・松井 [?, p. 251] の練習問題 13.1 と 13.2. ホテリングモデル で 3 人あるいは 4 人競争するばあい.なお,消費者が自分の居場所にもっと も近い店を訪れることを前提とすれば,このゲームは 2 軒の店をプレーヤー とする戦略形ゲームとなり,部分ゲーム完全均衡のかわりにナッシュ均衡が 適用できる.
演習 3.11 (議員報酬引き上げ点呼式投票 (Pay raise roll-call voting); Morrow [?], pp. 125-126) 3 人の議員からなる議会で,議員報酬の引き上げについて roll-call 方式 (公開
で順番に投票; 自分より前に投票した議員の投じた票が分かる) で投票を行う. 3 人の議員はいずれも報酬引き上げを望んでいる (引き上げの利益を b > 0 と する).その一方で,もし引き上げに投票すれば,有権者の反感を買うための コスト c (ただし b > c > 0) を被るとする.いま投票する順番にしたがって プレーヤーを 1, 2, 3 と呼び,各プレーヤーは y (yes: 引き上げに賛成) また は n (no: 引き上げに反対) のいずれか一方に投票するとする.
(i) この状況を展開形ゲームで表現せよ.図 1を完成させればよい.
n y 1
n y 2
n y 2
n (0, 0, 0) y (0, 0, −c) 3
n y 3
n y 3
y (b − c, b − c, b − c) 3 n (b − c, b − c, b) 3
図 1: 議員報酬引き上げ点呼式投票
(ii) このゲームを逆向き帰納法 (backwards induction) で解くことにより,部 分ゲーム完全均衡と均衡における利得列を求めよ.その際,おのおのの決定 節 (点) で各プレーヤーが選ぶ選択肢 (行動) に対応する枝に矢印を記入せよ (プレーヤー 3 のいちばん上の決定節から出ている選択肢 n に対応する枝に