粗相关均衡 | Codeboy's Blog

形式陈述

设有限策略式博弈的联合动作集为 $S=\prod_iS_i$ ，收益 $u_i$ 越大越好。令 $\mu$ 是 $S$ 上任意一份概率分布，不要求它分解成个人边际的乘积。想象协调者先按 $\mu$ 抽取联合动作，再让各人执行自己的分量。玩家可以在得知本轮分量之前决定退出，始终改选一个固定动作 $b\in S_i$ 。

这个偏离相对于服从的期望增益是

D_i(b;\mu)=\sum_{s\in S}\mu(s)\bigl[u_i(b,s_{-i})-u_i(s)\bigr].

若对所有玩家 $i$ 、所有固定动作 $b$ 都有 $D_i(b;\mu)\le0$ ，则 $\mu$ 是粗相关均衡（CCE）。给定 $\varepsilon\ge0$ ，将右边改为 $\varepsilon$ ，得到 $\varepsilon$ -CCE。固定偏离可以是随机的，但其增益只是上述纯偏离增益的加权平均，因此检查有限个纯动作已经足够。

从动作历史到均衡约束

一条精确恒等式

给定实际历史 $s^1,\ldots,s^T$ ， $T\ge1$ ，其经验联合分布记录各个完整剖面出现的频率：

\widehat\mu_T(s)=\frac1T\sum_{t=1}^T\mathbf1\{s^t=s\}.

玩家 $i$ 的收益形式外部遗憾为

R_i^{\mathrm{ext}}(T)=\max_{b\in S_i}\sum_{t=1}^T\bigl[u_i(b,s_{-i}^t)-u_i(s^t)\bigr].

把同一剖面的出现次数合并，对每个固定 $b$ 都有

D_i(b;\widehat\mu_T)=\frac1T\sum_{t=1}^T\bigl[u_i(b,s_{-i}^t)-u_i(s^t)\bigr],\qquad \max_bD_i(b;\widehat\mu_T)=\frac{R_i^{\mathrm{ext}}(T)}T.

因此，全体玩家满足 $R_i^{\mathrm{ext}}(T)\le T\varepsilon$ ，当且仅当这段历史的经验联合分布是 $\varepsilon$ -CCE。这是逐条历史成立的代数恒等式，既不要求历史独立同分布，也不要求它由某个特定学习算法产生。

外部遗憾可以为负：按局面变化行动的人可能胜过所有固定动作。所以满足约束的最小非负误差是

\varepsilon_T^*=\max\left\{0,\max_i\frac{R_i^{\mathrm{ext}}(T)}T\right\}.

若用损失 $\ell_i^t(b)=c_i-u_i(b,s_{-i}^t)$ 表示，同一历史的“实际累计损失减最佳固定动作累计损失”恰等于上面的收益遗憾，平移常数会抵消。改用损失并不会再把遗憾符号翻一次。

无遗憾保证哪一种收敛

若每位玩家都有统一次线性上界 $R_i^{\mathrm{ext}}(T)\le r_i(T)$ 、 $r_i(T)/T\to0$ ，则 $\varepsilon_T^*\to0$ 。有限单纯形是紧的，每条 $D_i(b;\mu)$ 又是连续线性函数，所以任何经验分布的聚点都满足全部 CCE 约束。进一步，经验分布到 CCE 集的距离趋零：否则存在一条与该集合保持正距离的子列，取其收敛子列便与刚才的聚点结论矛盾。

这个结论允许经验分布在均衡集合附近移动，并不要求它收敛到唯一的一点。若学习算法只给期望或高概率遗憾界，均衡结论也必须保留同样的概率限定。乘法权重更新详细区分平均乘积分布的确定性保证与随机动作历史的抽样误差。

直觉

这里的“粗”指偏离者使用的信息较少。它必须在知道自己的建议之前选定替代方案。相关均衡允许玩家看到私人建议后决定怎样改换动作，因而要求更多约束。两者都保持其他玩家的动作分布不变；不分析“我今天改变行为后，其他人明天会怎样反应”。

例子与边界

四轮得到恰好四分之一的误差

双方动作均为 $0,1,2$ ，行收益矩阵为

A=\begin{pmatrix}0&-1&1\\1&0&-1\\-1&1&0\end{pmatrix},

列收益为同一格的 $-A$ 。于是双方都在自己的动作比对手大 $1\pmod3$ 时获胜，在对角格收益为零。考虑历史

H_4=((0,0),(0,0),(1,1),(2,2)).

其联合频率表为 $\widehat\mu_4=\operatorname{diag}(1/2,1/4,1/4)$ 。双方实际累计收益都是零。行玩家固定选 $0$ 的收益为 $0+0-1+1=0$ ；固定选 $1$ 为 $1+1+0-1=1$ ；固定选 $2$ 为 $-1-1+1+0=-1$ 。列玩家读取自己的收益矩阵后得到相同三个和。全部六条固定偏离约束如下。

玩家	固定选 $0$	固定选 $1$	固定选 $2$
行玩家 $D_1(b;\widehat\mu_4)$	$0$	$1/4$	$-1/4$
列玩家 $D_2(b;\widehat\mu_4)$	$0$	$1/4$	$-1/4$

所以双方外部遗憾均为 $1$ ，最小非负误差为 $1/4$ 。它是 $1/4$ -CCE，却不是任何 $\varepsilon<1/4$ 的 CCE。这一步既能从频率表算，也能从四轮累计值除以 $4$ 得到。

三轮已经是 CCE，仍然不是 CE

删去一次 $(0,0)$ ，得到

H_3=((0,0),(1,1),(2,2)),\qquad \widehat\mu_3=\operatorname{diag}(1/3,1/3,1/3).

对任何固定动作，面对对方三个动作时恰好一胜、一负、一平，累计偏离增益都是零。因此两位玩家的六条 CCE 约束全部取零， $\widehat\mu_3$ 是精确 CCE。

但是，收到建议 $0$ 的玩家知道对方也是 $0$ ，改成 $1$ 就把收益从 $0$ 提高到 $1$ 。这一事件概率为 $1/3$ ，所以“只在建议为 $0$ 时改成 $1$ ”的平均增益为 $1/3>0$ ，违反 CE。固定改选 $1$ 还会在建议为 $2$ 时吃亏，正负抵消才使 CCE 检验通过；条件偏离可以只保留有利的部分。

三轮对角历史通过固定偏离检验，但只在建议为零时改成一可获得三分之一的平均增益 — 固定偏离与条件偏离检验

图中同一份对角联合分布通过全部固定动作检验，却允许“只在建议为 $0$ 时改成 $1$ ”获得平均增益 $1/3$ 。进一步计算，完整循环映射 $0\mapsto1,1\mapsto2,2\mapsto0$ 每轮都能改进，平均增益为 $1$ 。CCE 与 CE 的差别来自偏离规则能否依赖建议，不来自收益表或抽样分布的更换。

历史平均不能代替最后一轮

周期重复 $H_3$ 。当 $T=3m$ 时双方外部遗憾均为零，其余时刻遗憾也有常数上界。但每个最后实际剖面都是某个 $(a,a)$ ；一位玩家改成 $a+1\pmod3$ 就能提高收益 $1$ 。最后动作的点质量始终不是误差小于 $1$ 的 CCE，更不是纯 Nash 均衡。

这个例子证明“这条历史有次线性外部遗憾”不足以推出最后实际动作稳定。它没有证明产生该周期的规则对所有对手都无遗憾，也没有证明某个指定乘法权重算法的最后混合分布必然循环；后两者需要另行分析算法。

推论与应用

与独立混合的接口

CCE 的对象是完整联合分布。将各玩家历史频率分别平均再相乘，会丢掉同一轮动作之间的相关性，通常不保留偏离约束。相关均衡用一个协调博弈完整计算了这种改变：原联合分布是精确 CE，边际乘积却连精确 CCE 都不是。

只有在 $\mu=\prod_ip_i$ 本来就是乘积分布时，CCE 条件才直接成为 $U_i(p)\ge U_i(b,p_{-i})$ ，即混合 Nash 均衡的纯偏离判据。一般联合分布上的 CCE 允许比独立混合更丰富的长期行为。

从稳定性到社会成本

CCE 还可与逐剖面的成本比较结合。无政府价格证明：有限无权原子拥塞博弈若具有非负仿射资源成本，任何 CCE 的期望总成本都不超过社会最优的 $5/2$ 倍；每位玩家容许加性误差 $\varepsilon$ 时，再加 $3n\varepsilon/2$ 。同一证明把历史平均成本与各人的外部遗憾直接连接，无需假定最后一轮已成为均衡。

参考资料

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–3，pp. 1129–1134；经验联合分布、遗憾与到均衡集合的收敛。

形式陈述 ​

从动作历史到均衡约束 ​

一条精确恒等式 ​

无遗憾保证哪一种收敛 ​

四轮得到恰好四分之一的误差 ​

三轮已经是 CCE，仍然不是 CE ​

历史平均不能代替最后一轮 ​

与独立混合的接口 ​

从稳定性到社会成本 ​

反向链接