相関均衡(correlated equilibrium)とは、有限の戦略形ゲームで、手の組を 1 つの同時分布から引いて各参加者に自分の手だけを推奨として伝えるとき、どの参加者も推奨から外れる得がないような分布のことで、R. Aumann が導入した。条件は分布についての有限個の 1 次不等式なので、相関均衡の全体は凸多面体で線形計画で計算でき、積の形の相関均衡はちょうど Nash 均衡であるが、Nash 均衡の凸結合を超えて全員の利得を上げる相関均衡もある。存在は補助のゼロ和ゲームにミニマックス定理を当て、定常分布を使えば不動点定理なしに示せる。
前提知識: ゲーム理論, 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$ である組の確率である。
$S$ の上の確率分布 $p$ について次は同値である。
$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 均衡の存在と 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 人のゲームで、参加者 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$-相関均衡 という。
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)$ であり、どれも相関均衡である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する