相关均衡 | Codeboy's Blog

形式陈述

在有限策略式博弈中，协调者按联合分布 $\mu$ 抽取剖面 $s$ ，只向玩家 $i$ 私下建议 $s_i$ 。玩家知道收益表和分布，可以看见自己的建议后决定是否服从。相关均衡要求，在每一种建议下，单方改换动作都不能提高期望收益。

对建议 $a\in S_i$ 和替代动作 $b\in S_i$ ，定义未归一化偏离增益

D_i(a\to b;\mu)=\sum_{s:s_i=a}\mu(s)\bigl[u_i(b,s_{-i})-u_i(s)\bigr].

若对所有 $i,a,b$ 都有 $D_i(a\to b;\mu)\le0$ ，则称 $\mu$ 为相关均衡（CE）。当 $\mu_i(a)=\Pr(s_i=a)>0$ 时，除以它可写成条件服从约束

\mathbb E[u_i(a,s_{-i})\mid s_i=a]\ge\mathbb E[u_i(b,s_{-i})\mid s_i=a].

若某个建议概率为零，原线性式自动为零，完全不需要定义零概率事件下的条件分布。有限条线性式因此比逐项写条件概率更适合核验和求解。

本页的 $\varepsilon$ -CE 采用每条未归一化约束 $D_i(a\to b;\mu)\le\varepsilon$ 的约定， $\varepsilon\ge0$ 。它允许的条件收益改进是 $\varepsilon/\mu_i(a)$ ，不是统一的 $\varepsilon$ 。对于很少出现的建议，两种近似标准会差很多；精确的零误差定义则没有这一差别。

从条件偏离到遗憾

从单对改换到任意动作映射

一份确定的偏离规则是映射 $\phi:S_i\to S_i$ ：收到 $a$ 时执行 $\phi(a)$ 。它的总期望增益为

\sum_aD_i(a\to\phi(a);\mu).

若所有单对约束都非正，任何映射的总增益也非正。反过来，选一个只把 $a$ 改成 $b$ 、其余动作保持原样的映射，就能恢复该条单对约束。因此，CE 等价于没有任何有利的动作映射。随机偏离规则仍只是确定映射的混合，不会产生额外约束。

粗相关均衡只检查不看建议的固定偏离。固定改选 $b$ 对应常值映射 $\phi(a)=b$ ，其增益为

D_i(b;\mu)=\sum_aD_i(a\to b;\mu).

内部遗憾与交换遗憾

对实际历史 $s^1,\ldots,s^T$ ，单对内部遗憾记录“只重做当初选过 $a$ 的那些轮次”：

I_i(a,b)=\sum_{t:s_i^t=a}\bigl[u_i(b,s_{-i}^t)-u_i(s^t)\bigr].

将出现次数合并，经验分布满足 $D_i(a\to b;\widehat\mu_T)=I_i(a,b)/T$ 。因此所有内部遗憾都不超过 $T\varepsilon$ ，恰好等价于本页约定的经验 $\varepsilon$ -CE。这里比较的是同一段实际历史，并没有重新运行对手。

允许对每个原动作分别选择替代动作，得到交换遗憾（swap regret）：

R_i^{\mathrm{swap}}(T)=\max_{\phi:S_i\to S_i}\sum_t\bigl[u_i(\phi(s_i^t),s_{-i}^t)-u_i(s^t)\bigr] =\sum_{a\in S_i}\max_{b\in S_i}I_i(a,b).

最后一步成立，是因为映射对不同 $a$ 的选择互不约束。又因 $I_i(a,a)=0$ ，每个最大值非负，所以 swap regret 非负，且不小于外部遗憾。 $R_i^{\mathrm{swap}}\le T\varepsilon$ 保证每条 CE 约束不超过 $\varepsilon$ ；反过来，每条内部遗憾不超过 $T\varepsilon$ 只给出 $R_i^{\mathrm{swap}}\le |S_i|T\varepsilon$ 。零误差时两种条件等价，近似常数不能直接互换。

直觉

CE 的每条条件偏离增益都非正，固定偏离增益又是这些量的和，所以 CE 必然是 CCE。反向不成立，因为固定偏离对建议求和时，允许某些建议下的获利被其他建议下的损失抵消。CCE 页的三轮循环博弈已经给出精确反例：六条固定偏离增益全为零，但 $0\to1$ 的增益为 $1/3$ 。

例子与边界

三轮与四轮历史的内部遗憾

例如 CCE 页三轮对角历史中，两位玩家各自的内部遗憾表相同：

原动作 $a$ ／替代 $b$	$0$	$1$	$2$
$0$	$0$	$1$	$-1$
$1$	$-1$	$0$	$1$
$2$	$1$	$-1$	$0$

每行最大值为 $1$ ，所以交换遗憾为 $3$ ，最优映射为 $(1,2,0)$ ，平均增益为 $1$ 。每条 CE 线性约束则是表项除以 $3$ ，最小非负 $\varepsilon$ 为 $1/3$ 。四轮历史中 $0\to1$ 的累计增益为 $2$ 、未归一化增益为 $1/2$ ，而条件于建议 $0$ 的收益改进仍为 $1$ ；这具体展示了近似定义中的概率因子。

协调建议与边际乘积

先核验所有服从约束

考虑下面的非零和协调博弈。

行玩家／列玩家	$L$	$R$
$U$	$(3,2)$	$(0,0)$
$D$	$(0,0)$	$(2,3)$

令协调者以各 $1/2$ 概率选择 $UL$ 和 $DR$ ，即

\mu=\begin{pmatrix}1/2&0\\0&1/2\end{pmatrix}.

双方服从时的平均收益均为 $5/2$ 。收到 $U$ 的行玩家知道对方是 $L$ ，改成 $D$ 会从 $3$ 降到 $0$ ；收到 $D$ 时改成 $U$ 则从 $2$ 降到 $0$ 。列玩家同理。乘上相应建议概率，四条非平凡 CE 约束为

玩家及改换	概率 × 条件收益差	未归一化增益
行： $U\to D$	$(1/2)(0-3)$	$-3/2$
行： $D\to U$	$(1/2)(0-2)$	$-1$
列： $L\to R$	$(1/2)(0-2)$	$-1$
列： $R\to L$	$(1/2)(0-3)$	$-3/2$

保持原动作的约束均为零，这就检查完全部八条约束。故 $\mu$ 是精确 CE，自然也是精确 CCE。

还能直接检查 CCE：行玩家固定选 $U,D$ 的收益为 $3/2,1$ ，减去服从收益 $5/2$ ，增益为 $-1,-3/2$ ；列玩家固定选 $L,R$ 的增益为 $-3/2,-1$ 。如果把分布实现为两轮历史 $UL,DR$ ，双方最大累计固定偏离增益均为 $-2$ 。负外部遗憾与精确均衡并不冲突。

相同边际为何失去稳定性

两人的边际都是 $(1/2,1/2)$ 。若改成各自独立抽样，混合策略所产生的乘积分布为

\nu=\begin{pmatrix}1/4&1/4\\1/4&1/4\end{pmatrix}.

两个失配格现在各有 $1/4$ 概率，双方平均收益降到 $5/4$ 。固定纯动作面对的对方边际没有变化，但服从基线已经下降：

玩家	第一纯动作的固定偏离增益	第二纯动作的固定偏离增益
行： $U,D$	$3/2-5/4=1/4$	$1-5/4=-1/4$
列： $L,R$	$1-5/4=-1/4$	$3/2-5/4=1/4$

所以 $\nu$ 不是精确 CCE，也不是 CE 或 Nash 均衡，其最小 CCE 误差为 $1/4$ 。相关性原先让双方总能协调；保留个人频率却拆散共同出现的关系，会改变服从的收益。

对于乘积分布，CE 的每条约束进一步分解为

D_i(a\to b;\nu)=p_i(a)\bigl[U_i(b,p_{-i})-U_i(a,p_{-i})\bigr].

若 $p$ 是 Nash 均衡，正支持动作全是最佳回应，上式非正；反过来，乘积 CE 是乘积 CCE，后者恰是 Nash 的纯偏离判据。故在乘积分布这一限定下，CE、CCE 与Nash 均衡等价。一般联合分布没有这一限制，不能仅凭边际分布就判断稳定性。

推论与应用

CE 约束加上 $\mu(s)\ge0$ 、 $\sum_s\mu(s)=1$ ，组成关于联合概率的有限线性系统。给定一个候选分布时，逐项代入即可核验；收益表很大时，联合动作数仍可能随玩家数迅速增长，线性形式本身不等于输入规模总是小。

在重复博弈中，外部无遗憾控制事先固定偏离，得到 CCE；内部或交换无遗憾控制建议相关的改换，得到 CE。上面的恒等式解释了目标为何不同，但没有给出实现交换无遗憾的算法。普通指数权重的固定动作界不能直接充当交换遗憾界。

参考资料

Tim Roughgarden，CS364A Lecture 13: Equilibrium Concepts，§3.1–3.5，pp. 4–7，尤其 Definitions 3.3–3.4 的建议与事前偏离接口。
Sergiu Hart and Andreu Mas-Colell，A Simple Adaptive Procedure Leading to Correlated Equilibrium，Econometrica 68(5)，2000，§2，p. 1129 的未归一化 CE 与近似 CE 定义；§3，pp. 1133–1134 的遗憾与经验分布关系。

形式陈述 ​

从条件偏离到遗憾 ​

从单对改换到任意动作映射 ​

内部遗憾与交换遗憾 ​

三轮与四轮历史的内部遗憾 ​

协调建议与边际乘积 ​

先核验所有服从约束 ​

相同边际为何失去稳定性 ​

反向链接