Chapter 7: The Basic Structure of Repeated Games with
Imperfect Public Monitoring
安田 洋祐
Mailath and Samuelson (2006) —第 7 章のまとめ
2012年 3 月
この章のポイント
✞
✝
☎
目的1✆プレーヤーたちが過去の行動を完全には観測できない場合に，今まで の章の分析とどのような違いが生じるかをきちんと理解する．
✞
✝
☎
目的2 Abreu, Pearce and Stacchetti (1986, 1990)✆ によって提唱された，繰 り返しゲームの再帰的(recursive)な構造を生かして均衡利得の集合を特徴付け る手法(decomposabilityやself-generation)をマスターする．
再帰的な構造とは何か？
(無限回)繰り返しゲームでは，各期から始まるその期以降のゲームが元の(時点 0から始まる)繰り返しゲームと全く同じ構造をしている．
⇒ 1人エージェントによる動学的最適化問題を解く際のダイナミック・プログラ ミング(DP)の複数エージェント版と考えることができる．APSの本質はDP！
観測 (monitoring) 精度の違い
完全観測(perfect monitoring) ：プレーヤーたちは過去に採られた全員の行 動をすべて正確に観測できる．→今までの章で置かれていた仮定
◮ cf—不完全記憶(imperfect/bounded recall)：過去に観測した情報を忘れる．
不完全観測(imperfect monitoring) ：過去のプレイヤーたちの行動を直接観 測することができない代わりに，前期の行動に依存したシグナルを観測する．
◮ 公的観測(public monitoring) → 7-11章 ：プレーヤーたちが各期ごとに 共通のシグナルを観測する．
◮ 私的観測(private monitoring) → 12-14章 ：プレーヤーたちが個別のシ グナルを受け取る．
不完全公的観測 (imperfect public monitoring) の難しさ
“裏切り”( =均衡外行動)と“おしおき”( = punishment）の関係が間接的に
◮ 相手の行動を直接見ることができないので，観測したシグナルに応じてお しおきすることしかできない．
◮ きちんと均衡行動を採っていても正の確率で(悪いシグナルが出てしまうた め)おしおきすることになる．
⇒完全観測と比べて、おしおき方法の決め方が格段に難しい… しかしその一方で，実は再帰的(recursive)な構造は保たれる！
◮ 完全公的均衡(Perfect Public Equilibrium)は再帰的構造を持つ．
◮ PPEに均衡解を限定すれば(2章で学んだself-generationの考え方を拡張 して)完全観測と同じように問題を分析することができる．
◮ 私的観測のもとでは再帰的構造が保たれない→分析が質的に異なる．
例：囚人のジレンマ — 第 2 節
次のような囚人のジレンマを考える．ただし，プレーヤーたちは相手の行動を 直接観測することができないとする．
Table: 事前の 利得表
1 \ 2 C D
C 2, 2 -1, 3 D 3, -1 0, 0
✞
✝
☎
素朴な疑問 実現した自分の利得✆ (および自分の選んだ行動)から，相手の行 動を見破ることができるのではないだろうか？
⇒これが可能であればそもそも“不完全”観測ではないことになってしまうが…
不完全公的観測のモデル化
ステージ・ゲームにおける個々のプレーヤーiの利得は，iの行動ai∈ {C, D} と公的シグナルy∈ {g, b}のみに依存すると仮定する．
◮ 公的シグナルの実現値から相手の行動a−iを割り出すことはできない．
◮ 実際にプレイヤーが(事後的に)受けとる利得は以下の形となる． Table: 事後の 利得表
i\ y g b
C 3 − p − 2q
p− q −
p+ 2q p− q D 3(1 − r)
q− r −
3r q− r
ここでp, q, r(ただし0 < q, r < p < 1)はシグナルgが出る条件付き確率： p= Pr{g|CC}, q = Pr{g|DC} = Pr{g|CD}, r = Pr{g|DD}.
トリガー戦略の罠
完全観測とのアナロジーで次のようなトリガー戦略を考えよう：
◮ 第0期は(C, C)をプレーする．
◮ シグナルgが出続ける限り(C, C)をプレーする．
◮ 過去に1度でもbが出たら，それ以降は(D, D)をずっとプレーする．
このトリガー戦略は，pとqの大きさが十分に異なり，かつ割引因子δが十分に 大きいときに，均衡となることを示すことができる．具体的には
δ(3p − 2q) ≥ 1 ⇐⇒ δ ≥ 1
3p − 2q (7.2.4)
がトリガー戦略が均衡になるための必要十分条件となる． このとき均衡利得は2(1 − δ)
1 − δp となり，割引因子δが1に近づくと0に収束．
→均衡利得が効率点(= 2)から変わらない完全観測の場合とは大きく異なる．
均衡利得はなぜ低くなってしまったのか？
悪いシグナルbが実現すると，その期以降の利得が最低(= 0)になってしまう．
◮ トリガーはいつかは(長期的には確率1で)引かれてしまう．
◮ δが大きくなるにつれ，将来トリガーによって発生する利得のマイナス分 のインパクトが相対的に大きくなるため，均衡利得が低下してしまった． おしおきの仕方を工夫することで利得を上げることができる！たとえば…
◮ 「ずっと(D, D)」ではなく，途中で(C, C)に戻れるようにする．
◮ bが実現した時に，1より厳密に小さい確率でトリガーを引くようにする．
◮ 対称行動である(D, D)をおしおきにつかうのでなく，非対称な(C, D)お よび(D, C)を用いる．→第8・9章を参照．フォーク定理証明の肝！
✞
✝
☎
疑問 場当たり的に特定の戦略を調べるのではなく，もっと一般的に均衡利得✆ を求める方法は無いのだろうか？→ DPの考え方を使う！
不完全公的観測の一般モデル
n人の長期(long-lived)プレーヤーたちが無限回繰り返しゲームを行う．各期プ
レーされるステージ・ゲームは以下によって定義される．
◮ ai∈ Ai：各プレーヤーiの行動(Aiは有限と仮定)
◮ y∈ Y：各期の終わりに受けとる公的シグナル(Y は有限と仮定)
◮ ρ(y|a)：シグナルの実現確率を指定した確率関数(フル・サポートを仮定)
◮ u∗
i(y, ai)：プレーヤーiの事後利得
◮ u
i(a)：プレーヤーiの事前利得．次のように書くことができる： ui(a) =X
y∈Y
u∗i(y, ai)ρ(y|a) (7.1.1)
◮ V(δ)：割引因子δのもとでの均衡(完全公的均衡)利得の集合
完全公的均衡 (PPE)
定義7.1.1 プレーヤーの戦略のうち，各期の行動がその期以前の公的シグナ
ルの歴史のみに依存するものを，公的戦略(public strategy)と呼ぶ．
定義7.1.2 公的戦略の組のうち，すべての起こりうる公的シグナルの歴史に
対して，その期以降の戦略がすべてのプレーヤーで同一のものを，強対称 (strongly symmetric)であると言う．
定義7.1.3 公的戦略の組のうち，すべての起こりうる公的シグナルの歴史に
対して，その期以降の戦略の組がナッシュ均衡となっているようなものを，完 全公的均衡(perfect public equilibrium)と呼ぶ．
◮ 純粋戦略のみを考える場合には，公的戦略への限定は制約とはならない．
◮ 自分以外のすべてのプレーヤーが公的戦略をとっているとき，最適反応は 同じく公的戦略となる．(→すべてのPPEは逐次均衡 になっている．)
繰り返しゲームにおける DP アプローチ
1. Decomposition
◮ 本来は複雑な動学的意思決定の問題を，あたかも静学的な問題へと変換．
◮ 鍵を握るのは，繰り返しゲームの再帰的構造と，第2章で学んだ一回逸脱 の原理(one-shot deviation principle)．→後者は定理2.2.1を参照
2. Self-generation
◮ Decompositionを生かした，均衡利得(の集合)に関する便利な性質．
◮ ゲームを直接解かずに均衡利得集合を完全に特定化することができる．
DP の考え方その 1 ： Decomposition— 完全観測の場合
今期以降の将来利得(Continuation Payoff，DPのValueに相当) viを今期のス テージ・ゲームの利得と，来期から始まる繰り返しゲームの将来利得に分解：
vi= (1 − δ)ui(a) + δγi(a) (1)
◮ ここで，γ: A → V (δ) (⊂ Rn)は，今期の行動の組に応じて来期以降の将 来利得ベクトルを割り当てる写像．γiはその第i要素．
◮
✞
✝
☎
注意 来期以降の将来利得が均衡利得にならなければならない．✆ (再帰性)
◮ 潜在的には非常に複雑な動学的なインセンティブの問題を劇的に単純化．
vが部分ゲーム完全均衡(の平均利得)で達成可能な条件は，以下と同値：
∀i ∀a′i (1 − δ)ui(a) + δγi(a) ≥ (1 − δ)ui(ai′, a−i) + δγi(a′i, a−i) (2) を満たすような戦略の組aと写像γ: A → V (δ)が存在する．
DP の考え方その 1 ： Decomposition— 不完全観測の場合
完全観測の場合と同様に，今期以降の期待将来利得を今期のステージ・ゲーム の利得と，来期から始まる繰り返しゲームの期待将来利得に分解：
vi= (1 − δ)ui(a) + δX
y∈Y
γi(y)ρ(y|a) (3)
◮ ここで，γ: Y → V (δ) (⊂ R)は，今期末に実現するシグナルyに応じて 来期以降の期待将来利得ベクトルを割り当てる写像．γiはその第i要素．
◮
✞
✝
☎
注意 来期以降の将来利得が完全公的均衡利得にならなければならない．✆ vが完全公的均衡で達成可能な条件は，以下と同値：
∀i ∀a′i (1 − δ)ui(a) + δX
y∈Y
γi(y)ρ(y|a) ≥
(1 − δ)ui(a′i, a−i) + δX
y∈Y
γi(y)ρ(y|a′i, a−i) (4)
を満たすような戦略の組aと写像γ: Y → V (δ)が存在する．
DP の考え方その 2 ： Self-Generation— 準備段階
✞
✝
☎
（高度な）疑問 ✆(4)式のdecompositionにおいて，γの値域を均衡利得では なく任意の集合W ⊂ Rnとしたときに何が起こるだろうか？
定義 すべてのプレイヤーiについて以下を満たすベクトルwの集合をB(W ) と定義する．(4)を満たすような戦略の組aと写像γ: Y → W が存在して，
wi:= (1 − δ)ui(a) + δX
y∈Y
γi(y)ρ(y|a) (5)
定義 非空かつ有界な集合W∈ RnがW ⊆ B(W )を満たすとき，「Wは self-generatingである」という．
定理 完全公的均衡利得V(δ)は写像Bの不動点V(δ) = B(V (δ))である． 定理 W ⊆ W′ ならばつねにB(W ) ⊆ B(W′)が成り立つ．
DP の考え方その 2 ： Self-Generation— 主要な性質 (1)
Self-generation もしもW がself-generatingであれば以下が成り立つ： W ⊆
∞
[
t=1
Bt(W ) ⊆ V (δ) (6)
◮ 均衡“戦略”について何も知らなくても均衡“利得”を判定できる．
◮ 均衡利得を具体的にどうやって達成するかについては何も教えてくれない．
アルゴリズム もしもW が有界でV ⊂ W であれば以下が成り立つ：
∞
\
t=1
Bt(W ) = V (δ) (7)
◮ 機械的に均衡利得の集合を完全に計算することができる．
DP の考え方その 2 ： Self-Generation— 主要な性質 (2)
単調性 任意の0 < δ1< δ2<1について，δ1のもとでの均衡利得集合 V(δ1)が凸となるとき，V(δ1) ⊆ V (δ2)が成り立つ．
◮ プレーヤーが我慢強くなると，より多様な利得が均衡で維持される．
◮ Public Randomizationが使える場合には均衡利得はかならず凸集合．
→単調性はつねに成り立つ．
Bang-bang 均衡利得集合V(δ)はコンパクトになる．すべてのv∈ V につ いて，値域としてV(δ)のextreme pointをとるγのみを選ぶことができる．
◮ 一般性を失うことなく，extreme pointに焦点をあてることができる．
◮ (追加的な条件のもとで)効率的な均衡利得を達成するためにはextreme
pointをとるγのみを使わなければならない，という必要性も成り立つ．
