相関均衡

同義語:correlated equilibrium

概要

相関均衡(correlated equilibrium)とは、有限の戦略形ゲームで、手の組を 1 つの同時分布から引いて各参加者に自分の手だけを推奨として伝えるとき、どの参加者も推奨から外れる得がないような分布のことで、R. Aumann が導入した。条件は分布についての有限個の 1 次不等式なので、相関均衡の全体は凸多面体で線形計画で計算でき、積の形の相関均衡はちょうど Nash 均衡であるが、Nash 均衡の凸結合を超えて全員の利得を上げる相関均衡もある。存在は補助のゼロ和ゲームにミニマックス定理を当て、定常分布を使えば不動点定理なしに示せる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ゲーム理論, Nash均衡, von Neumannのミニマックス定理

相関均衡(correlated equilibrium)は、参加者の手の組を 1 つの同時分布から引き、各参加者には自分の手だけを推奨として伝えるとき、誰も推奨から外れる得がないような分布のことである。R. Aumann が 1974 年に導入した(KP17 第 7 章の注、p. 146)。
Nash均衡 では各参加者が独立に乱数を使うので、手の組の分布は各人の分布の積になる。相関均衡は積でない分布も許す。たとえば交差点の信号は、一方に「進め」、他方に「止まれ」を同時に伝える相関した推奨であり、両者が従うことが互いに最適になる。この意味で相関均衡は Nash 均衡を広げたものである。積の形の相関均衡はちょうど Nash 均衡であり、Nash 均衡の凸結合はすべて相関均衡になる。一方で、Nash 均衡の凸結合では届かない利得を実現する相関均衡もある。
相関均衡の条件は分布についての有限個の 1 次不等式なので、相関均衡の全体は凸多面体であり、線形計画で計算できる。この記事では、定義と言い換え、基本的な性質を述べたあと、存在定理を von Neumannのミニマックス定理 と Markov 連鎖の定常分布だけから証明する。不動点定理は使わない。続いて 2 人ゼロ和ゲームでの相関均衡、例、後悔にもとづく学習との関係を述べ、仮定を外した例を挙げる。

定義

記号は Nash均衡 の定義「戦略形ゲーム」に合わせる。$N$ 人の参加者 $i=1,\dots,N$、純粋戦略の空でない有限集合 $S_i$、$S:=S_1\times\cdots\times S_N$、利得 $u_i\colon S\to\mathbb R$ からなるゲームを考える。$s\in S$ の第 $i$ 成分を $b\in S_i$ に替えた組を $(b,s_{-i})$ と書き、$S_{-i}:=\prod_{j\ne i}S_j$ とする。

相関均衡

$S$ の上の確率分布 $p$ が 相関均衡 であるとは、すべての参加者 $i$ と、すべての $a,b\in S_i$ について
$$ \sum_{t\in S_{-i}}p(a,t)\bigl(u_i(a,t)-u_i(b,t)\bigr)\ge0\qquad\text{(1)} $$
が成り立つことをいう。ここで $p(a,t)$ は、第 $i$ 成分が $a$ で残りが $t$ である組の確率である。

  1. は次のように読む。仲介者が分布 $p$ に従って組 $s$ を引き、参加者 $i$ には $s_i$ だけを伝える。$i$ が「$a$ をとれ」と伝えられたとき(その確率 $\sum_tp(a,t)$ が正のとき)、相手の組の条件付き分布は $p(a,\cdot)$ を正規化したものである。(1) を $\sum_tp(a,t)$ で割ると、推奨どおり $a$ をとったときの条件付き期待利得が、$b$ に替えたときの条件付き期待利得以上であるという式になる。$\sum_tp(a,t)=0$ なら (1) は $0\ge0$ で、何も課さない。2 人のゲームの定義は KP17 Definition 7.2.3(p. 143)にあり、(1) の形への書き換えは同 Remark 7.2.4(p. 143)である。
    推奨を各参加者に 私的に 伝えることが本質的である。全員に組 $s$ 全体を知らせると、各人は相手の手を知ったうえで最適反応をとるので、$p$ の台は純粋 Nash 均衡だけに限られてしまう(ex-ce-counterexamples)。
外れ方の関数による言い換え

$S$ の上の確率分布 $p$ について次は同値である。

  1. $p$ は相関均衡である。
  2. すべての $i$ と、すべての写像 $\varphi\colon S_i\to S_i$ について、$s$ が $p$ に従うとき $\mathbb E_p[u_i(s)]\ge\mathbb E_p[u_i(\varphi(s_i),s_{-i})]$ である。
推奨ごとに足し合わせる

$1\Rightarrow2$:$\mathbb E_p[u_i(s)]-\mathbb E_p[u_i(\varphi(s_i),s_{-i})]$ を $s_i=a$ の値で分けると
$$ \sum_{a\in S_i}\sum_{t\in S_{-i}}p(a,t)\bigl(u_i(a,t)-u_i(\varphi(a),t)\bigr) $$
であり、各 $a$ の項は (1) で $b=\varphi(a)$ とした左辺なので $0$ 以上である。
$2\Rightarrow1$:$a,b\in S_i$ を与え、$\varphi(a)=b$、$a$ 以外の $c$ では $\varphi(c)=c$ とおく。上の和で $a$ 以外の項は $0$ になるので、2 の不等式はちょうど (1) である。$\square$

2 は、参加者 $i$ が「推奨 $a$ を受けたら $\varphi(a)$ をとる」という規則をあらかじめ決めても得をしないことを述べる。$\varphi$ を定数写像 $c$ に限ると条件は $\mathbb E_p[u_i(s)]\ge\mathbb E_p[u_i(c,s_{-i})]$ となり、推奨を聞く前に外れる場合だけを禁じる弱い条件になる。2 人ゼロ和ゲームの議論(prop-ce-zero-sum)ではこの弱い条件だけを使う。

基本的な性質

相関均衡の集合と Nash 均衡
  1. 相関均衡の全体は、$S$ の上の確率分布の単体の中の、空でない有界な凸多面体である。
  2. 混合戦略の組 $\sigma=(\sigma_1,\dots,\sigma_N)$ について、積の分布 $p_\sigma(s):=\prod_j\sigma_j(s_j)$ が相関均衡であることと、$\sigma$ が Nash 均衡であることは同値である。
  3. Nash 均衡の積の分布の凸結合は相関均衡である。
1 次不等式と台による判定
    1. 式は $p$ についての 1 次不等式で、その個数は $\sum_i|S_i|^2$ 個と有限である。単体も有限個の 1 次の等式・不等式で定まる有界な集合なので、共通部分は有界な凸多面体である。空でないことは (2) と Nash均衡 の定理「Nash の存在定理」から従う(不動点定理によらない証明は thm-ce-existence)。
  1. $p=p_\sigma$ のとき、$U_i$ を Nash均衡 の定義のとおり期待利得とすると、(1) の左辺は
    $$ \sigma_i(a)\sum_{t}\prod_{j\ne i}\sigma_j(t_j)\bigl(u_i(a,t)-u_i(b,t)\bigr)=\sigma_i(a)\bigl(U_i(a,\sigma_{-i})-U_i(b,\sigma_{-i})\bigr) $$
    である。これがすべての $a,b$ で $0$ 以上であることは、$\sigma_i(a)>0$ となる $a$ がすべて $\max_bU_i(b,\sigma_{-i})$ を達成することと同値である。すべての $i$ でこれが成り立つことは、Nash均衡 の命題「台による判定」により $\sigma$ が Nash 均衡であることと同値である。
    1. と (1) の凸性から従う。$\square$
  1. の逆は成り立たない。Nash 均衡の凸結合に入らない相関均衡があり、利得の面でも Nash 均衡の凸結合より全員がよくなることがある(ex-ce-chicken)。

存在定理

有限の戦略形ゲームに相関均衡があることは、Nash 均衡の存在と prop-ce-polytope (2) から直ちに従うが、ここでは不動点定理を使わない証明を与える。KP17 第 7 章の注(p. 146)によれば、S. Hart と D. Schmeidler がミニマックス定理による初等的な直接証明を与えた。以下の証明はその考え方に沿ってこの記事で書き下したものである。
まず補助の事実として、確率行列の定常分布の存在を示す。

釣り合う分布

$A$ を空でない有限集合、$w\colon A\times A\to\mathbb R_{\ge0}$ とする。このとき $A$ の上の確率分布 $\pi$ で、すべての $c\in A$ について
$$ \pi(c)\sum_{b\ne c}w(c,b)=\sum_{a\ne c}\pi(a)\,w(a,c)\qquad\text{(2)} $$
を満たすものがある。

定常分布をとる

$K>\max_a\sum_{b\ne a}w(a,b)$ をとり、$a\ne b$ では $P(a,b):=w(a,b)/K$、$P(a,a):=1-\sum_{b\ne a}w(a,b)/K$ とおく。$P$ の成分は $0$ 以上で各行の和は $1$ なので、$P$ は確率行列であり、行ベクトルの確率分布 $\rho$ に対して $\rho P$ も確率分布である。
$\rho_0$ を任意の確率分布とし、$\bar\rho_T:=\frac1T\sum_{k=0}^{T-1}\rho_0P^k$ とおく。$\bar\rho_T$ は確率分布で、
$$ \bar\rho_TP-\bar\rho_T=\frac1T\bigl(\rho_0P^T-\rho_0\bigr) $$
の各成分の絶対値は $1/T$ 以下である。確率分布の全体はコンパクトなので、$\bar\rho_T$ の部分列は確率分布 $\pi$ に収束し、極限で $\pi P=\pi$ を得る。
$\pi P=\pi$ の第 $c$ 成分は $\pi(c)=\pi(c)P(c,c)+\sum_{a\ne c}\pi(a)w(a,c)/K$ である。$P(c,c)$ を代入して $K$ 倍すると (2) になる。$\square$

$\pi$ は確率行列 $P$ の 定常分布 であり、(2) は各状態 $c$ について「$c$ から出る流れ」と「$c$ に入る流れ」が釣り合うことを述べる。

相関均衡の存在

有限の戦略形ゲームには相関均衡がある。

補助のゼロ和ゲームとミニマックス定理

補助のゲーム:参加者 I は組 $s\in S$ を選び、参加者 II は 3 つ組 $\tau=(i,a,b)$($i$ は参加者、$a,b\in S_i$、$a\ne b$)を選び、II が I に
$$ h(s,\tau):=\mathbf 1[s_i=a]\bigl(u_i(s)-u_i(b,s_{-i})\bigr) $$
を支払う有限のゼロ和ゲームを考える。どの $S_i$ も 1 点のときは、どの分布も (1) を自明に満たすので、$\lvert S_i\rvert\ge2$ となる $i$ があるとしてよい。このとき II の手は少なくとも 1 つある。I の混合戦略は $S$ の上の確率分布 $p$ であり、$\mathbb E_{s\sim p}[h(s,(i,a,b))]$ はちょうど (1) の左辺である($a=b$ では (1) は自明)。したがって
$$ p\ \text{が相関均衡}\iff \min_\tau\mathbb E_{s\sim p}[h(s,\tau)]\ge0 $$
であり、補助のゲームの値 $V$ が $0$ 以上なら、I の最適戦略が相関均衡である。
値が $0$ 以上であること:von Neumannのミニマックス定理 により、$V$ は II の混合戦略 $\mu$ についての $\max_p\mathbb E_{p,\mu}[h]$ の最小値に等しい。よって、どの $\mu$ に対しても $\mathbb E_{p,\mu}[h]\ge0$ となる $p$ があることを示せばよい。
$\mu$ を与え、$w_i(a,b):=\mu(i,a,b)$($a\ne b$)、$w_i(a,a):=0$ とおく。lem-ce-balance を $A=S_i$、$w=w_i$ に当てて $\pi_i$ をとり、積の分布 $p(s):=\prod_j\pi_j(s_j)$ を使う。$t\in S_{-i}$ を固定し、$\pi_{-i}(t):=\prod_{j\ne i}\pi_j(t_j)$ と書くと
$$ \mathbb E_{p,\mu}[h]=\sum_i\sum_{t\in S_{-i}}\pi_{-i}(t)\,D_i(t),\qquad D_i(t):=\sum_{a\ne b}w_i(a,b)\,\pi_i(a)\bigl(u_i(a,t)-u_i(b,t)\bigr) $$
である。$D_i(t)$ の第 1 項は $\sum_c\pi_i(c)u_i(c,t)\sum_{b\ne c}w_i(c,b)$、第 2 項は $\sum_cu_i(c,t)\sum_{a\ne c}\pi_i(a)w_i(a,c)$ で、(2) によりこの 2 つは等しい。よって $D_i(t)=0$、$\mathbb E_{p,\mu}[h]=0$ である。
したがって $V\ge0$ であり、I の最適戦略は相関均衡である。$\square$

証明の要点は、II の混合戦略 $\mu$ が「どの推奨をどの手に替えるか」の重みを与え、それに釣り合う分布を各参加者ごとに独立に選べば、外れて得る分と失う分がちょうど打ち消し合うところにある。$\mu$ ごとに I が選ぶ $p$ は積の分布だが、ミニマックス定理が保証する I の最適戦略は一般に積ではない。積の分布ひとつで全部の $\mu$ に同時に対抗できれば、それは積の形の相関均衡、つまり prop-ce-polytope (2) により Nash 均衡である。$\mu$ ごとに対抗の分布を取り替えてよいことが、証明を初等的にしている。

2 人ゼロ和ゲームの場合

2 人のゲームで、参加者 1 の利得を $m\times n$ 行列 $A$、参加者 2 の利得を $-A$ とする。分布 $p=(p_{ij})$ の 周辺分布 を $x_i:=\sum_jp_{ij}$、$y_j:=\sum_ip_{ij}$ とする。

ゼロ和ゲームの相関均衡

$p$ が相関均衡なら、参加者 1 の期待利得 $\sum_{i,j}p_{ij}a_{ij}$ はゲームの値 $V(A)$ に等しく、周辺分布 $x,y$ はそれぞれの参加者の最適戦略である。

定数の外れ方だけを使う

$E:=\sum_{i,j}p_{ij}a_{ij}$ とする。prop-ce-deviation で参加者 1 の $\varphi$ を定数 $k$ にとると、$E\ge\sum_{i,j}p_{ij}a_{kj}=(Ay)_k$ である。$k$ は任意なので
$$ E\ge\max_k(Ay)_k\ge\min_{y'}\max_k(Ay')_k=V(A) $$
である。参加者 2 の $\varphi$ を定数 $l$ にとると、$-E\ge-\sum_{i,j}p_{ij}a_{il}=-(A^{\mathsf T}x)_l$、すなわち $E\le\min_l(A^{\mathsf T}x)_l\le V(A)$ である。
よって $E=V(A)$ で、途中の不等式はすべて等号である。$\max_k(Ay)_k=V(A)$ は $y$ が参加者 2 の最適戦略であることを、$\min_l(A^{\mathsf T}x)_l=V(A)$ は $x$ が参加者 1 の最適戦略であることを意味する(von Neumannのミニマックス定理 の (1) 式)。$\square$

ゼロ和ゲームでは、相関させても利得は値から動かず、相関均衡の考えは新しいものを生まない。相関均衡が Nash 均衡と違う答えを出すのは、協調の余地があるゲームである。

例

弱虫ゲーム

2 人が向かい合って車を走らせ、それぞれ「よける(S)」か「突っ込む(D)」かを選ぶ。利得の表は次のとおりである(KP17 Example 7.2.5、p. 144)。

参加者 2 が S参加者 2 が D
参加者 1 が S$(6,6)$$(2,7)$
参加者 1 が D$(7,2)$$(0,0)$

Nash 均衡は (S, D)、(D, S) と、各人が S を確率 $\frac23$ で選ぶ混合の均衡で、利得はそれぞれ $(2,7)$、$(7,2)$、$(\frac{14}3,\frac{14}3)$ である。2 人の利得の和は最大で $\frac{28}3$ なので、Nash 均衡の凸結合で得られる利得の和も $\frac{28}3$ 以下である。
分布を $p_{\mathrm{SS}},p_{\mathrm{SD}},p_{\mathrm{DS}},p_{\mathrm{DD}}$ と書くと、(1) は 4 本の不等式
$$ 2p_{\mathrm{SD}}\ge p_{\mathrm{SS}},\quad p_{\mathrm{DS}}\ge2p_{\mathrm{DD}},\quad 2p_{\mathrm{DS}}\ge p_{\mathrm{SS}},\quad p_{\mathrm{SD}}\ge2p_{\mathrm{DD}} $$
になる。前の 2 本は参加者 1 が S、D を推奨された場合、後の 2 本は参加者 2 の場合である。たとえば参加者 1 が S を推奨されたときの (1) は $p_{\mathrm{SS}}(6-7)+p_{\mathrm{SD}}(2-0)\ge0$ である。
(a) (S, S)、(S, D)、(D, S) に $\frac13$ ずつ置く分布は 4 本を満たし、利得は 2 人とも $5$ である(KP17 p. 144)。
(b) 利得の和 $12p_{\mathrm{SS}}+9(p_{\mathrm{SD}}+p_{\mathrm{DS}})$ を相関均衡の中で最大にする。$r:=p_{\mathrm{SD}}+p_{\mathrm{DS}}$ とおくと、第 1・3 式を足して $p_{\mathrm{SS}}\le r$、また $p_{\mathrm{SS}}\le1-r$ なので、和は $12\min(r,1-r)+9r$ 以下で、これは $r=\frac12$ で最大値 $\frac{21}2$ をとる。等号は $p_{\mathrm{SS}}=\frac12$、$p_{\mathrm{DD}}=0$ で、第 1・3 式から $p_{\mathrm{SD}}=p_{\mathrm{DS}}=\frac14$ のときに限る。この分布では 2 人とも利得 $\frac{21}4$ で、利得の和 $\frac{21}2$ は Nash 均衡の凸結合の上限 $\frac{28}3$ を超える。

コイン合わせ

参加者 1 は 2 人の手(表 H か裏 T)がそろえば $1$ を得て、そろわなければ $1$ を払う。参加者 2 の利得はその符号を変えたものである。(1) の 4 本の不等式は
$$ p_{\mathrm{HH}}\ge p_{\mathrm{HT}},\qquad p_{\mathrm{TT}}\ge p_{\mathrm{TH}},\qquad p_{\mathrm{TH}}\ge p_{\mathrm{HH}},\qquad p_{\mathrm{HT}}\ge p_{\mathrm{TT}} $$
で、つなぐと $p_{\mathrm{HH}}\ge p_{\mathrm{HT}}\ge p_{\mathrm{TT}}\ge p_{\mathrm{TH}}\ge p_{\mathrm{HH}}$ となる。よって相関均衡は 4 つの組に $\frac14$ ずつ置く分布だけで、これは唯一の Nash 均衡(両者が $\frac12$ ずつ)の積である。prop-ce-zero-sum のとおり、利得は値 $0$ である。

公開の合図で調整する

Nash均衡 の例「男女の争い」では、(A, A) と (B, B) が純粋 Nash 均衡で、利得は $(2,1)$ と $(1,2)$ である。公平な硬貨を投げて表なら (A, A)、裏なら (B, B) とする分布は、prop-ce-polytope (3) により相関均衡で、利得は $(\frac32,\frac32)$ である。この場合は合図を 2 人に公開しても構わない。合図の後の組がそれぞれ Nash 均衡だからである。混合の Nash 均衡の利得 $(\frac23,\frac23)$ と比べて、2 人ともよくなる。

計算と学習

相関均衡の条件 (1) は 1 次不等式なので、利得の和などの 1 次関数を最大にする相関均衡は線形計画で求まる(KP17 第 7 章の注、p. 146)。ex-ce-chicken (b) は小さい場合を手で解いたものである。Nash 均衡を求める問題は一般に 1 次の問題にならない。
相関均衡は、ゲームを繰り返すときの単純な学習とも結びつく。時刻 $1,\dots,T$ に組 $s^1,\dots,s^T$ が出たとし、経験分布 $z_T(s):=\frac1T\#\{\tau\le T\mid s^\tau=s\}$ と、参加者 $i$ の 後悔
$$ R^T_i(a,b):=\frac1T\sum_{\tau\le T,\ s^\tau_i=a}\bigl(u_i(b,s^\tau_{-i})-u_i(s^\tau)\bigr) $$
を考える。$R^T_i(a,b)$ は、「$a$ をとった時刻にすべて $b$ をとっていたら平均でどれだけ得をしたか」である。$\varepsilon\ge0$ について、(1) の右辺の $0$ を $-\varepsilon$ に替えた条件を満たす分布を $\varepsilon$-相関均衡 という。

後悔と経験分布
  1. $z_T$ が $\varepsilon$-相関均衡であることは、すべての $i,a,b$ で $R^T_i(a,b)\le\varepsilon$ であることと同値である。
  2. すべての $i,a,b$ で $\limsup_{T\to\infty}R^T_i(a,b)\le0$ なら、$z_T$ と相関均衡の集合との距離は $0$ に近づく。
経験分布で書き直す
  1. $z_T$ の定義から、$z_T$ についての (1) の左辺は
    $$ \sum_tz_T(a,t)\bigl(u_i(a,t)-u_i(b,t)\bigr)=\frac1T\sum_{\tau:\,s_i^\tau=a}\bigl(u_i(s^\tau)-u_i(b,s^\tau_{-i})\bigr)=-R^T_i(a,b) $$
    である。
  2. そうでないとすると、$\delta>0$ と部分列 $T_k$ があって、$z_{T_k}$ と相関均衡の集合との距離が $\delta$ 以上である。確率分布の全体はコンパクトなので、さらに部分列をとって $z_{T_k}\to z$ としてよい。前半により $z_{T_k}$ についての (1) 式の左辺は $-R^{T_k}_i(a,b)$ で、その下極限は $0$ 以上である。左辺は分布について連続なので $z$ は相関均衡であり、距離が $\delta$ 以上であることに反する。$\square$

S. Hart と A. Mas-Colell は、各参加者が後悔の大きさに比例する確率で手を替える単純な手続きをとると、確率 $1$ で経験分布が相関均衡の集合に近づくことを示した(HM00 の要旨)。各参加者は自分の利得と過去の手の組だけを見て手を選び、ほかの参加者の利得も均衡も知る必要がない。prop-ce-regret (2) により、この結論は「どの参加者の後悔も長い目で見て $0$ 以下になる」ことに帰着する。後悔を小さく保つ手続きは 多腕バンディット や オンラインアルゴリズム でも中心的な主題である。

反例:仮定を外すと成り立たないこと

次の表の各行は、上の命題の仮定を 1 つ外すと結論が成り立たなくなる反例である。

外す仮定例成り立たなくなる結論
戦略の集合が有限(thm-ce-existence)自然数を言い合い、大きい方が $1$ を得て小さい方が $1$ を払う(同じなら $0$)相関均衡が存在する
推奨を各参加者に私的に伝える(def-ce-main の解釈)ex-ce-chicken (a) の分布で、引いた組を 2 人に公開する推奨に従うことが各参加者に最適である
ゼロ和(prop-ce-zero-sum)ex-ce-chicken相関均衡の利得がただ 1 つに定まる
表の例の確かめ

大きい数:$S_1=S_2=\mathbb N$、$u_1(a,b)=\mathrm{sgn}(a-b)=-u_2(a,b)$ とする。$\mathbb N^2$ の上の確率分布 $p$ が (1) をすべての $a,b$ で満たすと仮定する。$a$ を固定して $b\to\infty$ とすると、各 $t$ で $u_1(b,t)\to1$ であり、$\sum_tp(a,t)<\infty$ なので有界収束定理から $\sum_tp(a,t)u_1(a,t)\ge\sum_tp(a,t)$ を得る。$a$ について足すと $\mathbb E_p[u_1]\ge1$ である。同様に $\mathbb E_p[u_2]\ge1$ だが、$u_2=-u_1$ なので $\mathbb E_p[u_1]\le-1$ となり矛盾する。よって相関均衡はない。
公開の推奨:ex-ce-chicken (a) で組 (S, S) が引かれたことを 2 人が知ると、参加者 1 は相手が S をとると知っているので、D に替えれば利得が $6$ から $7$ に増える。推奨が私的なら、S を推奨された参加者 1 にとって相手は S と D が $\frac12$ ずつで、S の期待利得 $4$ は D の期待利得 $\frac72$ より大きい(KP17 p. 145)。
ゼロ和でない場合:ex-ce-chicken では、(a) の分布で利得は $(5,5)$、(b) の分布で $(\frac{21}4,\frac{21}4)$、純粋 Nash 均衡 (S, D) の積の分布で $(2,7)$ であり、どれも相関均衡である。

補足

名前と歴史

相関均衡は R. Aumann が Aum74 で導入した。KP17 第 7 章の注(p. 146)は、導入の文献として Aum74 と Aumann の 1987 年の論文を挙げ、存在の初等的な直接証明として HS89 を挙げている。また、大きな問題では相関均衡を求めるほうが Nash 均衡を求めるより計算の上でやさしいと注意している(同所)。KP17 は 2 人のゲームについてだけ定義し、$N$ 人への拡張は自然であると注意している(同所)。この記事の (1) はその拡張を書いたものである。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, Definition 7.2.2–7.2.3、Remark 7.2.4(p. 143)、Example 7.2.5(pp. 144–145)、第 7 章の注(p. 146)(頁は著者公開版 2016-12-13 による)
[2]
Robert J. Aumann, Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics 1 (1974), no. 1, 67–96, 1974
[3]
Sergiu Hart, David Schmeidler, Existence of correlated equilibria, Mathematics of Operations Research 14 (1989), no. 1, 18–25, 1989
[4]
Sergiu Hart, Andreu Mas-Colell, A simple adaptive procedure leading to correlated equilibrium, Econometrica 68 (2000), no. 5, 1127–1150, 2000

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する