13* Almost Public Monitoring Games

13章
Almost Public Monitoring Games
Motivation
private monitoring では公的な履歴なし
でゲームを繰り返し行う
 一方，almost public monitoring ではほ
ぼ公的な履歴が，ゲームを繰り返し行
う上で必要となる
 本章では，12.3節で紹介したアイデア
を用いて，almost public monitoring の
繰り返しゲームにおいて均衡を構成す
ることが可能かどうかを調査する

Condition
public monitoring game において均衡を
構成する戦略の組は，almost public
monitoring gameでも均衡になりうる
 また，~を public monitoring game にお
ける利得として使用する

◦ プレイヤ i の realization(y , a) 後の期待利得
*
~
は，ui ( y , ai ) と表現される
◦ private monitoring game の利得として，~
は用いない
アウトライン
1.
2.
3.
4.
5.
6.
When Is Monitoring Almost Public?
Nearby Games with Almost Public
Monitoring
Public Profiles with Bounded Recall
Failure of Coordination under
Unbounded Recall
Patient Players
A Folk Theorem
When Is Monitoring Almost Public?

Definition 13.1.1
1. 自分がシグナル y を受け取った時，他者がシグ
ナル y を受け取る確率が 1- ε 以上
2. private monitoring において全員が y というシグ
ナルを受け取る確率と，public monitoring にお
いて y というシグナルが発せられる確率の差が
ε 以下
Definition 13.1.1を満たす全ての private signal
は，何らかの public signal として表現可能で
ある
 private monitoring distribution に ξ を用いた分
布と public monitoring distribution が ε-close で
あるとき，その private monitoring game は
almost public monitoring game である

関数 ξ について
z1
z1
z2
z2
(1 – ζ) (1 – 2ε)
ε
ε
ζ (1 – 2ε)
minimally private monitoring distribution
を上記の表とする
： Z  Y である関数とする
 ξ (ξ,...,ξ ) をξ
と，ε が十分小さいとき

1
n
i
i
1. ξ1 ( z1 ) ξ2 ( z 2 )  y
2. ξ1 ( z1 ) ξ2 ( z2 )  y
When Is Monitoring Almost Public?

public monitoring distribution
◦ シグナル y の確率 1 - ζ
◦ シグナル y の確率 ζ

minimally private monitoring
distribution
z
z2
z1
z1
2
(1 – ζ) (1 – 2ε)
ε
ε
ζ (1 – 2ε)
◦ シグナル y の確率 (1 – ζ) (1 – 2ε)
◦ シグナル y の確率 ζ (1 – 2ε)
When Is Monitoring Almost Public?

Lemma 13.1.1
◦ minimally private monitoring distribution
は，full-support public monitoring
distribution と ε-close であるとする
アウトライン
1.
2.
3.
4.
5.
6.
When Is Monitoring Almost Public?
Nearby Games with Almost Public
Monitoring
Public Profiles with Bounded Recall
Failure of Coordination under
Unbounded Recall
Patient Players
A Folk Theorem
Nearby Games with Almost Public
Monitoring

本節では，public monitoring game にお
ける行動と，nearby private monitoring
game における行動を結びつける
◦
◦
◦
◦
Payoffs
Continuation Values
Best Responses
Equilibrium
Nearby Games with Almost Public
Monitoring -Payoffs

public monitoring と private monitoring は
signal distribution と利得が近似している
場合，類似した観測であるといえる
Definition 13.2.1
1. private monitoring distribution に ξ を用いた
分布と public monitoring distribution が
ε-close
2. private monitoring game と public monitoring
game の期待利得が ε-close
◦ この時，private monitoring games と public
monitoring games は ξ を用いて ε-close である
Nearby Games with Almost Public
Monitoring -Continuation Values
0
(
W
,
w
, f ,τ) は full-support public
public profile
monitoring game に適応可能であると同時に，
ξ のもとで ε-close private monitoring game にも
適応可能である
◦
◦
◦
◦
W ：set of states
0
w ：initial state
f ：decision function
τ：transition function
public profile は，τi ( wi , zi ) τ( wi ,ξi ( zi ))
のとき private profile に自然に置換可能である
 W が有限であれば，各プレイヤの戦略は有
限オートマトンで表現できる

Nearby Games with Almost Public
Monitoring -Continuation Values
private strategy が action-free であるとき
◦ ある時点での状態は private signals からなる関
数のみで求まるため，private history から再帰
的に求めることが可能である
◦ つまり，初期値さえ与えれば，各プレイヤの
ある時点での状態は求まる
 最初は全てのプレイヤが同じ状態であるが，private
signal であるので，2回目以降は異なるプレイヤは異
なる状態に遷移していることはある
◦ private profile は，public profile から構成され
る private monitoring game に適応可能
Nearby Games with Almost Public
Monitoring -Continuation Values


private strategy がσi であるとき
◦ ξi は独立したものであるため，全ての戦略はξi
のもとで measurable である
◦ そのため，public monitoring の戦略のオートマト
σi は適応可能である
ンに，
プレイヤ i の時点 t における，自分以外のプ
t
n 1
β

Δ
(
W
) とする
レイヤに対する信念を i
Lemma 13.2.2
◦ all i if the posterior belief implied by the induced
private profile
n 1
t
◦ private history ĥit satisfies βi ( w | hˆi )  1 ε
~ ~
t
ˆ
| U i (σi | hi )  U i (σi | w) |ν , for all ν 0
Nearby Games with Almost Public
Monitoring -Best Responsesstrict PPE (W , w, f ,τ) である public
monitoring game について考える
 i の信念が，他の全てのプレイヤは状態
w であるというものであったとする
 このとき， f i (w) が最適な行動となる

◦ 全員が同じ状態にあるということは，ナッ
シュ均衡を構成する行動を全員がとっている
と予想される
◦ また他の全てのプレイヤも， i が状態 w にい
るという信念を持っていることが予想される
ため
Nearby Games with Almost Public
Monitoring -Best Responses
Lemma 13.2.3
◦ public profile (W , w0 , f ,τ) が，割引率 δ の
public monitoring game における strict PPE
であるとき
t
n 1
t
◦ βi ( w | hi )  1 ε ならば σi ( hi )  f i ( w)
◦ ある履歴から導かれる信念が，全員が同
じ状態 w にいるというものであれば，自
分の最適反応は f i (w) になる
Nearby Games with Almost Public
Monitoring -Equilibrium
７章などから，nearby private monitoring
game においては，strict PPE であれば均
衡を構成すると考えられる
◦ どのような履歴の後でも，全員が同じ状態に
いると考えているから

Proposition 13.2.1
◦ public profile (W , w0 , f ,τ) が，割引率 δ の
public monitoring game における strict PPE で
あり，信念が βi ( wn1 | hit )  1 ε であるとき
◦ 割引率 δ が等しいなら private profile は
sequential equilibrium となる
◦ また，その均衡における期待利得は０より
大きい
Nearby Games with Almost Public
Monitoring -Equilibriumまた，次の proposition が成り立って
いる
 proposition 13.2.3
◦ public profile (W , w, f ,τ) が，割引率 δ の

public monitoring game における uniformly
strict equilibrium であるとき
t
n 1
t
◦ f i ( w)  f i (τi (hi )) で，βi ( w | hi )  1 ε
ならば，private profile は同じ割引率 δ で
ある private monitoring においてナッシュ
均衡にならない
アウトライン
1.
2.
3.
4.
5.
6.
When Is Monitoring Almost Public?
Nearby Games with Almost Public
Monitoring
Public Profiles with Bounded Recall
Failure of Coordination under
Unbounded Recall
Patient Players
A Folk Theorem
Public Profiles with Bounded Recall

grim trigger PPE は almost public monitoring
games において必ずしも均衡を構成しない
◦ ある時点における public state は主に全体の履歴
から決定しているから

一方，section 12.3.1 では，各 profile における
nearby game で，最後のシグナルが行動を決
定するのに十分である場合に，均衡を構成す
ることについて説明した

より一般に，履歴の記憶に制限がある場合，
almost public monitoring games で均衡を構成で
きる
Public Profiles with Bounded Recall

Definition 13.3.1
◦ public profile σ が L bounded recall であるとは，
これまでの履歴 h t と，最新の L 個の履歴 h L に対
して，以下が成り立つことを言う
σ(ht ) σ(h L )

Lemma 13.3.1
◦ The public
profile induced by the minimal automaton
0
(W , w , f ,τ) has L bounded recall if and only if for all
w, w'W reachable in the same period and for all h Y 

τ( w, h L ) τ( w' , h L )
Proposition 13.3.1
◦ strict PPE である public monitoring game を ξ で変
換した ε-close private monitoring game は，同じ割
引率 δ に応じてsequential equilibrium になる
アウトライン
1.
2.
3.
4.
5.
6.
When Is Monitoring Almost Public?
Nearby Games with Almost Public
Monitoring
Public Profiles with Bounded Recall
Failure of Coordination under
Unbounded Recall
Patient Players
A Folk Theorem
Failure of Coordination under
Unbounded Recall
本節では，記憶に限定がない戦略では，
極めて一般に行動の coordinate が出来
ないということを示す
 ３つの繰り返し囚人のジレンマの例を
用いて説明する

Failure of Coordination under
Unbounded Recall -Example
Example 13.4.1
◦ proposition 12.3.1 より，grim trigger による
implied private profile は q<r のときに限り，
minimally private almost public monitoring games
においてナッシュ均衡を形成する
◦ しかし，次の例のような場合は，例え q<r で
あっても，implied profile は nearby games with
almost public monitoring においてナッシュ均
衡を形成しない場合がある
 p, if a  EE,

 ( y | a)  q, if a  ES or SE ,
r , if a  SS ,

Failure of Coordination under
Unbounded Recall -Example
Example 13.4.1
z1
z '1
z "1
z2
z2
(1 – ζ) (1 – 3ε)
ε
ε
ζ’ (1 – 3ε)
ε
(ζ – ζ’) (1 – 3ε)
◦ 0 < r’ < q’ < q < r と仮定する
◦ S の後に z "1 を観測したときは，プレイヤ
２も S である可能性が高い
 i.e., πi ( z 1"| SS ) ε (r  r ' )(1  3ε)
ε (q  q' )(1  3ε) πi ( z 1"| SE)
Failure of Coordination under
Unbounded Recall -Example
Example 13.4.1
z1
z '1
z "1
z2
z2
(1 – ζ) (1 – 3ε)
ε
ε
ζ’ (1 – 3ε)
ε
(ζ – ζ’) (1 – 3ε)
◦ 0 < r’ < q’ < q < r と仮定する
◦ S の後に z '1 を観測した時は，
プレイヤ２は E である可能性が高い
 i.e., ε + r’(1 – 3ε) < ε + q’(1 – 3ε)
◦ 同じ状態にいないと思っているため，
ナッシュ均衡を形成しない
Failure of Coordination under
Unbounded Recall -Example
Example 13.4.2
◦ 下図の forgiving profile を考える
◦ forgiving profile は割引率 δ が十分に大きく，
3p – 2q > 1 のとき，strict PPE (7.2.5)
◦ grim trigger としては，q > r の時どんな
nearby minimally private monitoring game と
もナッシュ均衡を形成しない（12.3）
y
y
WEE
w0
y, y
y
y
ŴEE
WSS
Failure of Coordination under
Unbounded Recall -Example
Example 13.4.2
◦ q < r の時，このような戦略に対しては，協力と
非協力を交互に取るという戦略への deviation が
考えられる
◦ p(1-p) < q(1-q) の時に単独な z を受け取ると，相
手はまだ協力している状態にあると考える
◦ そのため，協力と非協力を交互に取る戦略への
deviation は有益になり，この時ナッシュ均衡と
ならない
◦ q < r でかつ p(1-p) > q(1-q) の時，ナッシュ均衡
になる
y
y
y, y
y
WEE
WSS
ŴEE
y
w0
Failure of Coordination under
Unbounded Recall -Example
Example 13.4.3
◦ 下図の forgiving profile を考える
◦ 例えば，割引率 δ が小さいとき最初に
一回裏切るという要因がある
◦ この例では決してナッシュ均衡を形成し
ない
y
y
WEE
w0
y
ŴEE
y, y
y
WSS
Failure of Coordination under
Unbounded Recall -Incentives to Deviate先ほどの例のように，戦略を変更した
い（裏切りたい）という衝動が発生す
ると，belief manipulation が妨害される
 その結果，ナッシュ均衡を構成しなく
なる

Failure of Coordination under
Unbounded Recall -Incentives to DeviatePPE を public monitoring game と nearby
almost public monitoring game に適応す
るときを考える
 grim triggerの例の考え方を発展

◦ プレイヤ i は private state ŵ
ˆ
◦ 他のプレイヤは全員 private state w  w
にいるという強い信念を i が持つとする
~  ( f ( wˆ ), f ( w )) とすると
◦ このとき， a
i
i
πi ( zi | a~) πi ( zi | ( fi ( wˆ ), a'i ))a'i  f i( w )
ˆ )  f i ( w ) の時，その private
◦ つまり，fi ( w
profile は均衡を構成しない
アウトライン
1.
2.
3.
4.
5.
6.
When Is Monitoring Almost Public?
Nearby Games with Almost Public
Monitoring
Public Profiles with Bounded Recall
Failure of Coordination under
Unbounded Recall
Patient Players
A Folk Theorem
Patient Players





almost public monitoring games におけるフォーク
定理を考察
これまでの話から，any strict (bounded recall) PPE
of a public monitoring game は，ε-close private
monitoring game においてsequential equilibriumを
構成することが分かった
しかし，フォーク定理を考察するにおいて，プ
レイヤが辛抱強くなっていく（δが１に近づく）
ということを扱うことが難しい
同時に，プレイヤが辛抱強くなっていくと，戦
略を逸れるプレイヤは存在しなくなっていく
また，記憶が限定された戦略の profile の value が
equalized across state を引き起こすから難しい
(remark 7.2.1 の例より)
Patient Players -Patient Strictness
Definition 13.5.1
◦ A public profile is connected if for all w, w'W
there exists h m  Y m for some m and
w W such that
τ( w, hm )  w τ( w' , hm )
◦ ある同じ履歴を違う状態から再生した時，
至った状態が同じであるならば，その二
つの状態は connected である
Patient Players -Patient Strictness
connected finite public profile が strict
equilibrium ならば，割引率 δ が十分大
きいとき，次の式が満たされる
~
ˆ
ˆ
Σw ' (θww ' θww ' (ai ))Δw 'wVi
 (ui (ai , f i ( w))  ui ( f ( w)))
◦ Θ：denote the matrix of transition
probabilities on the finite state space W
induced by the public profile
ˆ ww ' ( f ( w)) θ
ˆ ww '
◦ The ww’th element is θ
Patient Players
-Equilibria in Nearby Gamesbounded recall と connected finite public
profile より，お互いのプレイヤが共に
ある望ましい state profile にいる確率
が高くなる
 monitoring が minimal private ならば，

◦ ある履歴の後の信念は，strategy profile に
対して整合である
◦ その strategy profile は private monitoring で
もナッシュ均衡である
アウトライン
1.
2.
3.
4.
5.
6.
When Is Monitoring Almost Public?
Nearby Games with Almost Public
Monitoring
Public Profiles with Bounded Recall
Failure of Coordination under
Unbounded Recall
Patient Players
A Folk Theorem
A Folk Theorem
almost perfect almost public monitoring
games における mutual minmax pureaction folk theorem について証明
 public monitoring distribution (Y , ρ) is
η-perfect if Y = A and ρ(a|a) > 1 – η
 η-perfect public monitoring distribution
に ε-close であるどんな private
monitoring distribution(Z , π) も
(η+ε)-perfect になる(definition12.2.1)

A Folk Theorem

Proposition 13.6.1：A private monitoring folk
theorem
~  A ( a~  ( f ( wˆ ), f ( w )) ).
◦ Suppose A is finite. Fix a
i
i
If there exists a  A
max ui (ai , a i )  ui (a~),
ai Ai
for all i ,
◦ then for all κ<1, there exists δ <1, and η > 0 ,
◦ such that for all η-perfect public monitoring
distributions (Y, ρ),
◦ there exists ε>0, such that for all private monitoring
distributions(Z , π), ε-close to (Y, ρ),for all δ (δ ,1)
◦ there is a sequential equilibrium of repeated game
~)
with private monitoring with payoffs within κ of u (a

Download Report