shin_econ’s diary

今回は相関均衡についてまとめていきたいと思います。(岡田(2011)やMascheler他(2013)を参考に、)自分の理解のままに書いていくので、その理解は間違っているとか、別の説明・解釈の方が分かりやすくて妥当だ等のコメントがありましたら是非コメントお願いします。

1.Introduction
2.シグナル構造における戦略の均衡としての相関均衡
3.行動の助言としての相関戦略
4.相関均衡(1)と(2)の同値性
5.相関均衡の性質について

1.Introduction

私たちは普段交差点で青信号だったら進み、赤信号だったら止まるという行動を取るように、共通に観測できるシグナルに紐づけて行動を決めることがよくあります。それぞれのプレイヤーは「進む」か「止まる」の行動を取れるわけですが、赤⇒止まる、青⇒進むという行動を選びます。ほかのプレイヤーが信号に従っていると仮定すると赤で進むと事故りますし、青で止まる必要もないので、信号に違反するインセンティブがないので、この状況は信号によって導かれた”均衡”になっています。このような信号によって導かれる均衡が相関均衡の直観となります。

混合戦略均衡において、各プレイヤーは”コイントス”に従って純粋戦略を選びますが、この”コイントス”は各プレイヤーで独立です。言い換えると、混合戦略均衡において、各プレイヤーは独立のシグナルに従って行動を決め、どのプレイヤーもそのシグナルからの逸脱インセンティブを持っていない状況と形容することができます。このような説明に変換すると、自然と出てくる混合戦略均衡の拡張概念として、「それぞれのプレイヤーはシグナルに従って行動を選び、どのプレイヤーもそのシグナルからの逸脱インセンティブを持ち合わせていなく、またシグナルはプレイヤー間で相関していてもいい」と言ったものが思い浮かびます。この拡張された均衡概念と先述した信号(シグナル)によって導かれる均衡概念が完全に対応するということを以下で見ていきます。シグナルに関する均衡という側面は第2節で展開され、混合戦略均衡の拡張概念としての相関均衡の側面は第3節で展開され、第4節で両者の同値性が確認されます。

まず、相関均衡の例として以下のチキンゲームを考えましょう。

f:id:shin_econ:20190606174636j:plain

このゲームのナッシュ均衡は1.(よける,よけない),2.(よけない,よける)3. ( (2/3,1/3), (1/3,2/3) )の三つでそれぞれの期待利得ベクトルは(2,7),(7,2),(14/3,14/3)となります。(確認してみてください。)

ここにシグナルを導入するとどのような帰結を均衡として導けるでしょうか。コインを投げて表が出たらプレイヤー1が避ける,プレイヤー2が避けない、裏が出たら逆に1が避けず,2が避けるという戦略の組みを考えてみましょう。この時、各プレイヤーはこの戦略からの逸脱インセンティブを持ちません。プレイヤー1の立場から見ると、表だった場合相手は避けないので避けるのが最適となり、裏だった場合は逆に相手は避けるので避けないのが最適となります。プレイヤー2についても同様の議論が成り立ちます。

このコインに紐づけられた均衡における(事前)期待利得は(9/2,9/2)となり、ナッシュ均衡1,2の利得ベクトルをちょうど二分の一に内分した利得ベクトルになります。表がでる確率がt,裏がでる確率が(1-t)のイカサマコインで同様の議論をすると、ナッシュ均衡1,2の利得ベクトルの任意の凸結合はイカサマコインの元、均衡として実現できることがわかります。

では、純粋戦略ナッシュ均衡の凸結合以外の利得ベクトルを均衡として導くようなシグナルはあるでしょうか。以下のような仲裁者付きのシグナルを考えてみましょう。箱の中には(よける,よける)(よけない,よける)(よける,よけない)と書かれた三つのボールがあり、仲裁者はボールを引きます。それに(A,B)と記載されていたらプレイヤー1にはAをプレイヤー2にはBを伝えます。先ほどのコインのシグナルは、相手のプレイヤーが受け取っているシグナルも分かる”public”なものでしたが、今回のシグナルはそのような”public”なものではありません。

f:id:shin_econ:20190606180225j:plain

実はこのシグナルの元、仲裁者に勧められた通りの行動をとることが均衡になります。

プレイヤー1の立場にたちます。

(i)「よける」と言われた場合

この時相手が「よける」と言われた条件付き確率は1/2,「よけない」も1/2です。この時の「よける」の期待利得は(6+2)/2=4であり、「よけない」の期待利得は(7+0)/2=7/2なので、言われた通りよけることが最適になります。

(ii)「よけない」と言われた場合

この時、相手が「よける」と言われた条件付き確率は1であることが分かる。となれば、自分は言われた通りよけないことが最適となります。

プレイヤー2にとっても同様のことが成り立ちます。この均衡における(事前)期待利得ベクトルを考えてみましょう。これは計算してみると(5,5)になります。この利得ベクトルは三つのナッシュ均衡における利得の凸結合ではないものです。

この議論から”public”でないシグナル構造を用いればナッシュ均衡における利得の凸結合以外の利得ベクトルを均衡として導けることがわかりました。ここでミソとなるのはシグナル下の均衡行動分布が混合戦略の結果では成立し得ないものになっている点です。この均衡下では最悪の結果である(よけない,よけない)が実現する確率が0になっていますが、混合戦略の組みの場合、これが成立するためにはどちらかのプレイヤーが「よけない」に0の確率を振ることが必要であるため、(よける,よけない)か(よけない,よける)の確率が0になることに注意してください。このようにシグナル下での戦略を考えると混合戦略では均衡として導けない帰結が均衡として導けることがわかりました。以下の節ではこの議論を厳密に定式化していきます。

1.Introduction
2.シグナル構造における戦略の均衡としての相関均衡
3.行動の助言としての相関戦略
4.相関均衡(1)と(2)の同値性
5.相関均衡の性質について

2.シグナル構造における戦略の均衡としての相関均衡

$G = (N, (S_i,u_i)_{i \in N})$ を戦略型ゲームとする。(以下、有限ゲームを仮定する。)

今、ここにシグナル構造が存在して、プレイヤーは受け取ったシグナル $\omega \in \Omega$ に従って戦略を決めるものとする。

定義(シグナル構造)

$\gamma = (\Omega , (P_i)_{i \in N}, p)$ をシグナル構造と呼ぶ。ただし、 $\Omega$ をシグナルの全体集合、 $P_i$ をプレイヤーiの情報分割、すなわち $P_i$ は $\Omega$ の分割であり同じ同値類に入るシグナル同士をプレイヤーiは区別できない(同一のシグナルとして認識する)、pはすべてのプレイヤーが共通して持っている $\Omega$ の上の事前分布である。

イントロで具体例で出した道路の信号の例だと

$\Omega =$ {(青赤)(赤青)},

$P_1 = P_2 =$ {{(青赤)}{(赤青)}},

pは(例えば)共に1/2

のようにかける。このシグナルこうぞうでは全てのプレイヤーがすべてのシグナルを区別できる。(“public”なシグナル)

道路の信号とは異なるが、別のシグナル構造の例として、(赤赤)(赤青)(青赤)(青青)の4通りがあってそれぞれのプレイヤーは自分の色しか知らされないというシグナル構造を考えてみよう。この時は

$\Omega =$ {(赤赤)(青赤)(赤青)(青青)},

$P_1 =$ {{(赤赤),(赤青)},{(青赤)(青青)}},

$P_2 =$ {{(赤赤),(青赤)},{(赤青)(青青)}},

pは(例えば)すべて1/4

のようにかける。それぞれのプレイヤーの情報分割の各同地類が複数の要素を持っている、すなわちそれぞれのプレイヤーはすべてのシグナルを区別できるわけではない(“public”なシグナルではない)点に注意されたい。

また、簡単のため以下を仮定する。

・ $\Omega, S_i$ は有限集合

・ $p(\omega) \gt 0 (\forall \omega \in \Omega)$

このシグナル構造 $\gamma$ をもつゲームGにおいて各プレイヤーの戦略は $\pi_i : \Omega \to S_i$ ただし、 $P_i(\omega_1) = P_i(\omega_2)$

$\Rightarrow$ $\pi_i (\omega_1) = \pi_i (\omega_2)$ を満たすとかける。それぞれのプレイヤーは自分の受け取るシグナルに対して一つの純粋戦略を選ぶような状況を考えれば良い。このような戦略の組 $\pi = ( \pi_1 , ... , \pi_n)$ を相関戦略と呼ぶ。

プレイヤーiの情報 $P_i(\omega)$ における相関戦略 $\pi$ の期待利得は以下のように書ける。

$Eu_i(\pi \mid P_i(\omega) ) = \Sigma_{t \in P_i(\omega)} u_i(\pi(t))p(t \mid P_i(\omega))$ ただし、 $p(t \mid P_i(\omega)) = \frac{p(t)}{\Sigma_{s \in P_i(\omega)}p(s)}$

また、相関戦略 $\pi$ が一つ定まるとその戦略が導く行動分布が定まる。これを $F_{\pi (s)} = \Sigma_{\pi (\omega) = s} p(\omega)$ と書く。

この時、相関戦略における均衡概念、すなわち相関均衡は以下のように自然に定まる。

定義(相関均衡)

戦略型ゲームG,シグナル構造 $\gamma$ において相関戦略 $\pi^\ast$ が相関均衡であるとは全てのプレイヤーi,任意のの戦略 $\pi_i$ に対して以下が成立することである。

$Eu_i(\pi^\ast \mid P_i(\omega)) \geq Eu_i( (\pi_i, \pi_{-i}^\ast) \mid P_i(\omega))$

相関均衡においては、どのプレイヤーもどのシグナルを受け取ったとしても逸脱インセンティブを持たないことが分かる。

第3節の意味での相関均衡と区別する際には本節での相関均衡を特に相関均衡(1)と呼ぶことにする。

1.Introduction
2.シグナル構造における戦略の均衡としての相関均衡
3.行動の助言としての相関戦略
4.相関均衡(1)と(2)の同値性
5.相関均衡の性質について

3.行動の助言としての相関戦略

ここでは、上の節とはまた別の混合戦略均衡の拡張としての相関均衡の定義をあたえる。

戦略型ゲームGにおいて純粋戦略の直積集合S上の確率分布dを考える。混合戦略の組みから導かれるような確率分布は各 $S_i$ に関して独立である必要があるが、このdは独立でなくても良い。このdの実現値 $s = (s_1, ... , s_n)$ に従って仲裁者がプレイヤーiに $s_i$ を勧めるような状況を考えよう。(自分以外のプレイヤーへの助言を知ることはできない。)誰もその提案から逸脱するインセンティブを持たないのであれば、この戦略の分布dが均衡における行動分布として実現する。

定義(相関均衡)

戦略型ゲームGにおいてS上の確率分布dが相関均衡であるとは以下が成立することである。

すべてのプレイヤーi、任意の純粋戦略 $t_i \in S_i$ に対して

$\Sigma_{s_{-i}} u_i(s_i,s_{-i}) d(s_{-i} \mid s_i) \geq \Sigma_{s_{-i}} u_i(t_i,s_{-i}) d(s_{-i} \mid s_i)$

ちなみに、これは $d(s_{-i} \mid s_i)$ を $d(s_i, s_{-i})$ としても両辺定数倍するだけなので同値となるので簡単のためこちらを定義として書いてしまう場合もある。

第3節の議論と対応させると、この相関均衡は相関均衡(1)において特に $\Omega = S, P_i(s) = P_i(s^\prime) \iff s_i = s_i^\prime$ としたものとみなすことができる。

本節での相関均衡を区別のため相関均衡(2)とする。

1.Introduction
2.シグナル構造における戦略の均衡としての相関均衡
3.行動の助言としての相関戦略
4.相関均衡(1)と(2)の同値性
5.相関均衡の性質について

4.相関均衡(1)と(2)の同値性

定理

戦略型ゲームGにおいて、あるシグナル構造 $\gamma$ とそれにおける相関均衡(1) $\pi$ が存在してその行動分布 $F_\pi$ がdになることと、dが相関均衡(2)であることは同値。

証明

[(2)ならば(1)]

上記の対応関係の議論より明らか。

実際、 $\Omega = S, P_i(s) = P_i(s^\prime) \iff s_i = s_i^\prime, p = d$ として、相関均衡(2)の定義を変形していくと、これは上のシグナル構造の元でシグナルの示す行動通りの行動をとるという戦略が相関均衡(1)の定義を満たすことがわかり、これは均衡行動分布としてdを導くことが分かる。(もし分からなければコメント頂ければ加筆するかもしれません。)

[(1)ならば(2)]

f:id:shin_econ:20190606203512j:plain

シグナル構造の入れ方というのは無数にあるが、均衡としてどのような行動分布を導けるのかという点のみに焦点を絞れば、シグナルとして直接個々人に行動のを送るというタイプの直接的なシグナル構造のみを考えれば十分であるということをこの定理は教えてくれる。この定理と同種の定理がインフォメーションデザインの文脈で重要な意味を持ってくるという点でも重要な定理だ。また、この議論はメカニズムデザインにおける顕示原理に対応するものだという点にも注意されたい。

1.Introduction
2.シグナル構造における戦略の均衡としての相関均衡
3.行動の助言としての相関戦略
4.相関均衡(1)と(2)の同値性
5.相関均衡の性質について

5.相関均衡の性質について

今までの議論からすぐに分かる相関均衡の性質や重要な相関均衡の性質を挙げていく。

・純粋戦略均衡の導く行動分布の凸結合は相関均衡となる。

相関均衡(1)においてシグナル構造をどの純粋戦略均衡を選ぶかを各プレイヤーに完全情報(“public”なシグナルとして)として指定するものとして構成すればよい。

・相関均衡全体は凸かつコンパクト

相関均衡(2)の定義より、相関均衡全体の空間はイコール付きの線形不等式の解として与えられる。すなわち、有限個の半空間の積集合で表される。半空間は閉かつ凸であり、閉と凸は有限個の積について閉じているので相関均衡全体の空間は閉かつ凸である。また、行動分布全体の空間は(Sの位数-1)単体であるためコンパクト。よってコンパクトの閉部分集合はコンパクトより示された。

→シグナル機構を変数として持っていて、行動分布の上に目的関数を持っているというような最適化問題を考えると、シグナルによって導ける行動分布全体は相関均衡全体なので、この結果(凸かつコンパクト)はかなり嬉しい結果になるように感じる。

・混合戦略均衡の行動分布の凸結合は相関均衡

相関均衡(2)の定義より任意の混合戦略均衡の行動分布は相関均衡。(ちなみに、ここから相関均衡は必ず存在することが分かる)また、相関均衡全体は凸集合をなすことから成立する。

【参考文献】

・岡田章(2011) 「ゲーム理論新版」有斐閣

・Maschler, M., E. Solan, S. Zamir, (2013) “Game Theory,” Cambridge University Press.

最近読んでるLuenberger “Optimization by Vector Space Methods”を参考に関数解析の枠組みでみた最適化理論についての議論をまとめていこうと思います。どうやら、関数解析の知識を整備していくと、複雑な空間(e.g. 連続関数の空間などと言った無限次元のヒルベルト空間)における最適化問題を幾何的な直感の元扱えるようになるみたいです。

章立てはこんな感じ。

Introduction
Linear Space
Hilbert Space
Least Squares Estimation
Dual Spaces
Linear Operators and Adjoints
Optimization of Functionals
Grobal Theory of Constrained Optimization
Local Thoery of Constrained Optimization
Iterative Methods of Optimization

(4章以外は)6章まで前提知識を整えて7章から最適化理論をみていく感じですね。ざっとみた感じ有名どころだと8章でラグランジュの未定乗数法、9章でKKT条件、ポントリャーギンの最大原理などに触れるみたいです。

イントロダクション曰く、本書の中で一貫して展開される最適化の幾何学的直感において重要となる原理は・射影定理・ハーン-バナッハの定理・双対性・微分法の4つだそうなので、この辺を意識しながら進めていきたいです。

2章：Linear Spaceは、線型空間やノルム空間の確認の章です。ベクトル空間の定義→部分空間、アファイン空間→凸、錐→線型独立、次元という流れで線型空間についての知識が整備されていきます。(ここは標準的な議論) 次にノルム→開集合→収束→連続性→バナッハ空間→完備集合といった流れでノルム空間についての知識が整備されていきます。

開集合の議論でちょっと面白いのが、まず集合の内部や閉包を定義し、開集合を内部と自身が一致する集合、閉集合を閉包と自身が一致する集合と定義する。そして、定理として開集合の補集合が閉集合を導いてるという所です。同値なのでどちらを定義としてどちらを定理としても齟齬はないのですが、慣れた構成と違った展開をされると少しハッとして面白いですね。

閉集合については収束との重要な関係があります。

定理1

点列 $(a_n) \subset A$ がxに収束する時、xはAの閉包に属する。

証明

xがAの閉包に属さない、すなわちAの補集合の内部に属すると仮定する。

この時、ある正の $\epsilon$ が存在し、 $B(x, \epsilon) \subset A^c$ が成立。(ただし、 $B(x, \epsilon)$ は中心x半径 $\epsilon$ を中心とする開球とする。)

$a_n \to x$ よりある $a_N$ が存在して $a_N \in B(x, \epsilon) \subset A^c$ だが、これは $(a_n) \subset A$ に矛盾。

閉集合は自身と閉包が一致するので定理1から収束操作について閉じていることが分かる。また、以下で示すように逆も成立する。

定理2

$(a_n) \subset A$ and $a_n  \to \alpha$ ⇒ $\alpha \in A$ が成立する(i.e.Aが収束操作について閉じている)ならば、Aは閉集合。

証明

Aが閉集合でない、すなわちAの閉包に属すがAには属さないような元xが存在すると仮定する。

このとき、任意の自然数nに対し、 $B(x,1/n) \cap A \not= \phi$ が成立。

$a_n \in B(x,1/n) \cap A$ となるように点列 $(a_n) \subset A$ を構成できる。

このとき $a_n$ はxに収束するが、仮定よりxはAに属する。これは矛盾である。

以上より閉集合が収束操作について閉じるという性質によって特徴付けられた。

これを使うとバナッハ空間において完備集合であることと閉集合であることが同値であることが直ちにわかる。

ある集合が閉だと仮定する。その集合内でコーシー列を取るとこれは収束列となり全体集合のどこかに収束先を持つが、閉集合は収束操作について閉じているので収束先はその集合に属する。よって閉集合は完備集合である。逆にある集合が完備だと仮定する。この集合に含まれるような収束列を任意にとる。収束列はコーシー列なので完備性からこの点列はその集合内に収束先をもつことになり、この集合は収束操作について閉じていることがわかった。よってこの集合は閉である。

3章での議論を追っていると、射影原理の議論をするときなどある部分空間が閉集合であるかどうかが重要になるようだ。となると、「ノルム空間において、任意の有限次元部分空間は完備である。」という定理が重要になってくるはずだ。これを示せば、バナッハ空間、ヒルベルト空間の有限次元部分空間は閉集合になるということが(上の議論と合わせて)分かる。

ヒルベルト空間の無限次元部分空間と閉集合(閉包)についての議論が気になるけど全然知らないので詳しい人教えてください......

本当は今回この定理を示して2章のまとめ終わり！ってしたかったんだけど、既にいい分量になっちゃったし、いい時間にもなっちゃったので今回はここまでにします。

経済学と数学のまとめをそれぞれ週1位のペースで投稿できればいいな(目標)と思ってます〜

shin_econ’s diary

相関均衡(Correlated Equilibrium)について

1.Introduction

2.シグナル構造における戦略の均衡としての相関均衡

3.行動の助言としての相関戦略

4.相関均衡(1)と(2)の同値性

5.相関均衡の性質について

【関数解析と最適化1】あらすじ・閉集合と収束の関係

ブログはじめました