complexity of coalition structure generation

10.Private Strategies
in Games with
Imperfect Public Monitoring
北木真
1
アウトライン
Sequential Equilibrium
 A Reduced-Form Example
 Two-Period Examples
 An Infinitely Repeated Prisoners’ Dilemma

2
公的戦略と私的戦略
行動：E（Effort），S（Shirk）
 {y,y}：公的シグナル
～
＾
 Public strategies：σ，σ



公的シグナルによってのみ定まる
Private strategies：σ
 シグナルyに続く2期の行動は，1期の行動に依存
3
Sequential Equilibrium

定義
任意の行動aに対するシグナルyの観測確率ρ（y|a）は
正であると仮定
 任意の自分の履歴
に対して，
が
に対して最適反応
⇒戦略プロファイルσはsequential equilibrium
（但し，
）

4
アウトライン
Sequential Equilibrium
 A Reduced-Form Example
 Two-Period Examples
 An Infinitely Repeated Prisoners’ Dilemma

5
A Reduced-Form Example


1期目は左，2期目は右のゲームを行う
シグナルyの観測確率ρ
 a：行動，y,y：シグナル


p=9/10，q=4/5，r=1/5と仮定
2回のゲームにおける利得：(1-δ)u1+δu2

δ=25/27と仮定
6
各戦略の期待利得

Pure Strategies

1期はEE，2期ではyのときはRR，それ以外はPP



左辺の式より期待利得は1.4815
Public Correlation
 1期はE，次はyの観測後はR，yの観測後は確率ΦでRを
選択


Φ=0.5かつ期待利得は1.5556
7
各戦略の期待利得

Mixed Public Strategies
 1期は確率αでE，2期はyの観測後はR，yの観測後は確
率ΦでRを選択



Φ=0.567）
より，期待利得は1.5566（α＝0.969，
8
各戦略の期待利得

Private Strategies


1期は確率αでEを選択
2期は1期でSが選ばれ，yを観測した後は確率ξでRを選
択，それ以外の場合は必ずRを選択



より，期待利得は1.5864（α＝0.916，ξ＝0）
9
アウトライン
Sequential Equilibrium
 A Reduced-Form Example
 Two-Period Examples
 An Infinitely Repeated Prisoners’ Dilemma

10
Two-Period Examples
ただ一つのナッシュ均衡を持つゲーム
 右のナッシュ均衡



プレイヤ１：r1かr2を等確率
プレイヤ２：c1かc2を等確率
 公的シグナルY={y,y}のうち，
-- i j
yが観測される確率ρ(y|r c ):
11
PPEと重複しない均衡

1期の各プレイヤーの行動：

2期のプレイヤ１の行動：

2期のプレイヤ２の行動：
12
PPEと重複しない均衡

何故，1期でプレイヤ１はr3を選択？



均衡戦略がpublic


r2を選択すると，2期でプレイヤ２は確率0.1でc1，0.9で
c2を選択
プレイヤ１の期待利得は，r3の選択より減少
1期の行動は2期の行動に影響を与えないため，最適反
応から外れた戦略を取る誘因が発生しない⇒PPE
一方，プレイヤ２のprivate strategyは2期のゲー
ムにおいてcorrelated equilibriumを構成

2期においてナッシュ均衡を構成する必要はない
13
Correlationによる利得

右のゲームにおける均衡



Nash：(1,1)
Correlation：(3/2,3/2)
各シグナルy1,y2,y3の観測確率：
14
Correlationによる利得
1期は3つの行動を等確率で1つ選択
 各プレイヤの2期の行動：



r4=r1，c4=c1，r0=r3，c0=c3とする
2期の戦略はcorrelated equilibirumを構成
15
複数のナッシュ均衡があるゲーム

プレイヤ１は縦，２は横，３は左か右の表から行動を
選択


プレイヤ３にとってRはLを支配
ナッシュ均衡


LRRかRLRを選択：利得（1,1,12）
プレイヤー１と２が1/3でLを選択：利得（1/3,1/3,74/9)16
さらに大きな利得を得る

シグナルY={y0,y1,y2,y3}を考える



l：1期でLを選択したプレイヤの人数
ylの観測確率は1-3ε（ym（m≠l）の観測確率はε）
各プレイヤの1期の行動：

1期では比較的LLLが選択される
17
さらに大きな利得を得る

各プレイヤの2期の行動

εが十分に小さければ，2期はほぼナッシュ均衡となる
18
さらに大きな利得を得る
プレイヤ１と２の
2期の期待利得：


プレイヤ３の2期の期待利得



1期でLを選択：高確率でy3が観測され，利得は12
Rを選択：高確率でy2が観測され，利得は0
ε→0のとき，利得は(6,6,26.22）に近づく

ナッシュ均衡による利得より大きい
19
アウトライン
Sequential Equilibrium
 A Reduced-Form Example
 Two-Period Examples
 An Infinitely Repeated Prisoners’ Dilemma

20
Public Transitions
右の囚人のジレンマを
無限回繰り返す
 2つの公的シグナルy,yの
うち，yの観測確率ρ：



ここではp>0，q=0と仮定
戦略のオートマトン表現



wR：確率αでEを選択
wP：Sを選択
各プレイヤは常に
同じ状態
21
Public Transitions

wRにおける期待利得V(wR)




Eを選択した場合：
Sを選択した場合：
wPにおける期待利得は0
wRにおける行動が無差別⇒

このとき，

各プレイヤが辛抱強い（δが1に近い）とき，αは1に近づき，
V(wR)は2に近づく
この場合，PPEによって達成可能な利得2-(1-p)/pより
大きい
22

q>0のとき
q=0のときと同じ戦略は均衡ではない
 プレイヤ１の履歴Ey，(Ey)kを考える
 Ey観測後，プレイヤ２が
状態wRである確率β0(q)


β0(0)=1
同様にして次の確率βk(q)
を考える：



k→∞のとき，βk(q)は0に近づく
プレイヤ１はプレイヤ２がほぼ確実にwPの状態であると
考え，Eの選択をやめる
23
Belief-free Equilibrium
右の囚人のジレンマにおける
Belief-free equilibrium
（14章で述べられる）を示す
 2つの公的シグナルy,yのうち，
yの観測確率ρ：

24
Belief-free Equilibrium

戦略のオートマトン表現
wR：確率αRでE
を選択
 WP：Sを選択


Vxi(ai)：プレイヤjの状態がwxで，プレイヤiがai選
択をした場合のプレイヤiの利得

VRi(E)=Vri(S)≡VR，VPi(E)=Vpi(S)≡VP
25
Belief-free Equilibrium

VRについて：

VPについて：

これらの等式を解くことにより，確率βが求められる
26
Belief-free Equilibrium

βによって，次の等式が導かれる



δ＝1，αR=1は等式を満たす
p=1/2，q=1/2-ε，r=ε，bは2に近い場合を考える
このとき，1に近いδ<1について，1に近いαR<1が存在
し，それは上の等式を満たす
27

Download Report