公的観測の「繰り返しゲーム理論」

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) ：プレーヤーたちは過去に採られた全員の行 動をすべて正確に観測できる． → 今までの章で置かれていた仮定 I cf—不完全記憶 (imperfect/bounded recall) ：過去に観測した情報を忘れる． 不完全観測 (imperfect monitoring) ：過去のプレイヤーたちの行動を直接観 測することができない代わりに，前期の行動に依存したシグナルを観測する． I 公的観測 (public monitoring) → 7-11 章 ：プレーヤーたちが各期ごとに 共通のシグナルを観測する． I 私的観測 (private monitoring) → 12-14 章 ：プレーヤーたちが個別のシ グナルを受け取る．

不完全公的観測 (imperfect public monitoring) の難しさ “裏切り”( = 均衡外行動) と “おしおき”( = punishment ）の関係が間接的に I 相手の行動を直接見ることができないので，観測したシグナルに応じてお しおきすることしかできない． I きちんと均衡行動を採っていても正の確率で (悪いシグナルが出てしまうた め) おしおきすることになる． ⇒ 完全観測と比べて、おしおき方法の決め方が格段に難しい… しかしその一方で，実は再帰的 (recursive) な構造は保たれる！ I 完全公的均衡 (Perfect Public Equilibrium) は再帰的構造を持つ． I PPE に均衡解を限定すれば (2 章で学んだ self-generation の考え方を拡張 して) 完全観測と同じように問題を分析することができる． I 私的観測のもとでは再帰的構造が保たれない → 分析が質的に異なる．

例：囚人のジレンマ—第 2 節 次のような囚人のジレンマを考える．ただし，プレーヤーたちは相手の行動を 直接観測することができないとする． Table: 事前の 利得表 1\2 C D C 2, 2 -1, 3 D 3, -1 0, 0   素朴な疑問  実現した自分の利得 (および自分の選んだ行動) から，相手の行 動を見破ることができるのではないだろうか？ ⇒ これが可能であればそもそも “不完全” 観測ではないことになってしまうが…

不完全公的観測のモデル化 ステージ・ゲームにおける個々のプレーヤー i の利得は，i の行動 ai ∈ {C, D} と公的シグナル y ∈ {g, b} のみに依存すると仮定する． I 公的シグナルの実現値から相手の行動 a−i を割り出すことはできない． I 実際にプレイヤーが (事後的に) 受けとる利得は以下の形となる． Table: 事後の 利得表 i\y C D g 3 − p − 2q p−q 3(1 − r) q−r b p + 2q − p−q 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}.

トリガー戦略の罠 完全観測とのアナロジーで次のようなトリガー戦略を考えよう： I 第 0 期は (C, C) をプレーする． I シグナル g が出続ける限り (C, C) をプレーする． I 過去に 1 度でも b が出たら，それ以降は (D, D) をずっとプレーする． このトリガー戦略は，p と q の大きさが十分に異なり，かつ割引因子 δ が十分に 大きいときに，均衡となることを示すことができる．具体的には δ(3p − 2q) ≥ 1 ⇐⇒ δ ≥ 1 3p − 2q (7.2.4) がトリガー戦略が均衡になるための必要十分条件となる． 2(1 − δ) となり，割引因子 δ が 1 に近づくと 0 に収束． 1 − δp → 均衡利得が効率点 (= 2) から変わらない完全観測の場合とは大きく異なる． このとき均衡利得は

均衡利得はなぜ低くなってしまったのか？ 悪いシグナル b が実現すると，その期以降の利得が最低 (= 0) になってしまう． I トリガーはいつかは (長期的には確率 1 で) 引かれてしまう． I δ が大きくなるにつれ，将来トリガーによって発生する利得のマイナス分 のインパクトが相対的に大きくなるため，均衡利得が低下してしまった． おしおきの仕方を工夫することで利得を上げることができる！たとえば… I 「ずっと (D, D) 」ではなく，途中で (C, C) に戻れるようにする． I b が実現した時に，1 より厳密に小さい確率でトリガーを引くようにする． I 対称行動である (D, D) をおしおきにつかうのでなく，非対称な (C, D) お よび (D, C) を用いる． → 第 8・9 章を参照．フォーク定理証明の肝！   疑問 場当たり的に特定の戦略を調べるのではなく，もっと一般的に均衡利得   を求める方法は無いのだろうか？ → DP の考え方を使う！

不完全公的観測の一般モデル n 人の長期 (long-lived) プレーヤーたちが無限回繰り返しゲームを行う．各期プ レーされるステージ・ゲームは以下によって定義される． I ai ∈ Ai ：各プレーヤー i の行動 (Ai は有限と仮定) I y ∈ Y ：各期の終わりに受けとる公的シグナル (Y は有限と仮定) I ρ(y|a)：シグナルの実現確率を指定した確率関数 (フル・サポートを仮定) I u∗i (y, ai )：プレーヤー i の事後利得 I ui (a)：プレーヤー i の事前利得．次のように書くことができる： X ∗ ui (a) = ui (y, ai )ρ(y|a) (7.1.1) y∈Y I V (δ)：割引因子 δ のもとでの均衡 (完全公的均衡) 利得の集合

完全公的均衡 (PPE) 定義 7.1.1 プレーヤーの戦略のうち，各期の行動がその期以前の公的シグナ ルの歴史のみに依存するものを，公的戦略 (public strategy) と呼ぶ． 定義 7.1.2 公的戦略の組のうち，すべての起こりうる公的シグナルの歴史に 対して，その期以降の戦略がすべてのプレーヤーで同一のものを，強対称 (strongly symmetric) であると言う． 定義 7.1.3 公的戦略の組のうち，すべての起こりうる公的シグナルの歴史に 対して，その期以降の戦略の組がナッシュ均衡となっているようなものを，完 全公的均衡 (perfect public equilibrium) と呼ぶ． I 純粋戦略のみを考える場合には，公的戦略への限定は制約とはならない． I 自分以外のすべてのプレーヤーが公的戦略をとっているとき，最適反応は 同じく公的戦略となる． (→ すべての PPE は逐次均衡 になっている．)

繰り返しゲームにおける DP アプローチ 1. Decomposition I 本来は複雑な動学的意思決定の問題を，あたかも静学的な問題へと変換． I 鍵を握るのは，繰り返しゲームの再帰的構造と，第 2 章で学んだ一回逸脱 の原理 (one-shot deviation principle)． → 後者は定理 2.2.1 を参照 2. Self-generation I Decomposition を生かした，均衡利得 (の集合) に関する便利な性質． I ゲームを直接解かずに均衡利得集合を完全に特定化することができる．

DP の考え方その 1：Decomposition—完全観測の場合 今期以降の将来利得 (Continuation Payoff，DP の Value に相当) vi を今期のス テージ・ゲームの利得と，来期から始まる繰り返しゲームの将来利得に分解： vi = (1 − δ)ui (a) + δγi (a) I (1) ここで，γ : A → V (δ) (⊂ Rn ) は，今期の行動の組に応じて来期以降の将 来利得ベクトルを割り当てる写像．γi はその第 i 要素． I   注意 来期以降の将来利得が均衡利得にならなければならない．(再帰性)   I 潜在的には非常に複雑な動学的なインセンティブの問題を劇的に単純化． v が部分ゲーム完全均衡 (の平均利得) で達成可能な条件は，以下と同値： ∀i ∀a0i (1 − δ)ui (a) + δγi (a) ≥ (1 − δ)ui (a0i , a−i ) + δγi (a0i , a−i ) を満たすような戦略の組 a と写像 γ : A → V (δ) が存在する． (2)

DP の考え方その 1：Decomposition—不完全観測の場合 完全観測の場合と同様に，今期以降の期待将来利得を今期のステージ・ゲーム の利得と，来期から始まる繰り返しゲームの期待将来利得に分解： vi = (1 − δ)ui (a) + δ X γi (y)ρ(y|a) (3) y∈Y I ここで，γ : Y → V (δ) (⊂ R) は，今期末に実現するシグナル y に応じて 来期以降の期待将来利得ベクトルを割り当てる写像．γi はその第 i 要素． I   注意 来期以降の将来利得が完全公的均衡利得にならなければならない．   v が完全公的均衡で達成可能な条件は，以下と同値： X ∀i ∀a0i (1 − δ)ui (a) + δ γi (y)ρ(y|a) ≥ y∈Y (1 − δ)ui (a0i , a−i ) +δ X γi (y)ρ(y|a0i , a−i ) y∈Y を満たすような戦略の組 a と写像 γ : Y → V (δ) が存在する． (4)

DP の考え方その 2：Self-Generation—準備段階   （高度な）疑問   (4) 式の decomposition において，γ の値域を均衡利得では なく任意の集合 W ⊂ Rn としたときに何が起こるだろうか？ 定義 すべてのプレイヤー i について以下を満たすベクトル w の集合を B(W ) と定義する．(4) を満たすような戦略の組 a と写像 γ : Y → W が存在して， wi := (1 − δ)ui (a) + δ X γi (y)ρ(y|a) (5) y∈Y 定義 非空かつ有界な集合 W ∈ Rn が W ⊆ B(W ) を満たすとき， 「W は self-generating である」という． 定理 完全公的均衡利得 V (δ) は写像 B の不動点 V (δ) = B(V (δ)) である． 定理 W ⊆ W 0 ならばつねに B(W ) ⊆ B(W 0 ) が成り立つ．

DP の考え方その 2：Self-Generation—主要な性質 (1) Self-generation W ⊆ ∞ [ もしも W が self-generating であれば以下が成り立つ： B t (W ) ⊆ V (δ) (6) t=1 I 均衡 “戦略” について何も知らなくても均衡 “利得” を判定できる． I 均衡利得を具体的にどうやって達成するかについては何も教えてくれない． アルゴリズム ∞ \ もしも W が有界で V ⊂ W であれば以下が成り立つ： B t (W ) = V (δ) t=1 I 機械的に均衡利得の集合を完全に計算することができる． (7)

DP の考え方その 2：Self-Generation—主要な性質 (2) 単調性 任意の 0 < δ1 < δ2 < 1 について，δ1 のもとでの均衡利得集合 V (δ1 ) が凸となるとき，V (δ1 ) ⊆ V (δ2 ) が成り立つ． I プレーヤーが我慢強くなると，より多様な利得が均衡で維持される． I Public Randomization が使える場合には均衡利得はかならず凸集合． → 単調性はつねに成り立つ． Bang-bang 均衡利得集合 V (δ) はコンパクトになる．すべての v ∈ V につ いて，値域として V (δ) の extreme point をとる γ のみを選ぶことができる． I 一般性を失うことなく，extreme point に焦点をあてることができる． I (追加的な条件のもとで) 効率的な均衡利得を達成するためには extreme point をとる γ のみを使わなければならない，という必要性も成り立つ．