均衡概念

纳什均衡、相关均衡、粗相关均衡的定义与计算复杂度；在两人零和博弈中最小最大等于纳什，可利用性（exploitability）是评估策略的标准。本章给出全书博弈部分需要的概念。

博弈的标准式

$n$ 个参与者、每个有策略空间与效用函数。与单智能体 RL 的本质区别：效用来自强者的行为，没有单一的"最优策略"——好不好取决于别人怎么做。均衡概念由此而来：一个"谁都不想单方面偏离"的状态。

纳什均衡

纳什均衡（Nash Equilibrium, NE）：策略组合 $\sigma^* = (\sigma_1^*, \dots, \sigma_n^*)$，每个参与者在其对手固定的前提下无偏离动机：

$\forall i,\ \forall \sigma_i:\quad u_i(\sigma_i^*, \sigma_{-i}^*) \ge u_i(\sigma_i, \sigma_{-i}^*).$

两个关键事实：

• 存在性：有限博弈必有（混合策略）纳什均衡（Nash 定理）；
• 计算复杂度：一般和博弈中计算纳什均衡是 PPAD-hard——不仅难算，而且不唯一（均衡选择问题：多个均衡选哪个，本身没有公认答案）。

零和博弈：最小最大 = 纳什

两人零和博弈（我的收益是你的损失）有清晰得多的结构：最小最大值与纳什均衡重合，

$\max_{\sigma_1} \min_{\sigma_2}\ u_1(\sigma_1, \sigma_2) = v^*,$

且任何纳什均衡达到同一个值 $v^*$。这意味着零和博弈没有均衡选择问题——最优解唯一（在价值意义上），可以用最小最大化直接定义。可利用性（exploitability）由此成为标准评估指标：

$\mathrm{Expl}(\sigma) = \max_{\sigma'}\ u_1(\sigma', \sigma) - v^*,$

即"对手采取最优响应时能从你这里多赚多少"。可利用性越低，策略离均衡越近；它是可计算的（一次最优响应求解），这是零和博弈中评估策略的标准（→ 自博弈与 PSRO用它监控训练）。

相关均衡与粗相关均衡

放松"独立随机化"得到更弱也更容易计算的均衡：

• 相关均衡（Correlated Equilibrium, CE）：允许一个公开的推荐装置——所有人观察到同一随机信号（"今天都别先手"），约定都服从推荐后无偏离动机。计算：线性规划多项式可解。
• 粗相关均衡（Coarse Correlated Equilibrium, CCE）：更弱——参与者事先承诺服从推荐（不是看到信号后决定）。计算更简单。

无悔学习收敛到 CCE：多人重复博弈中，每个参与者用无悔算法（regret matching、multiplicative weights）调整策略，联合分布收敛到粗相关均衡（CE 用 swap regret）。这是多智能体 RL 的一个理论支点：无悔学习者的系统不需要求解均衡，就自动走到（粗）相关均衡。

对多智能体 RL 的启示

• 一般和博弈（利益部分一致部分冲突）中，纳什难计算且不唯一，"逼近纳什"常常不是正确的目标——逼近哪个均衡？与人类协作的应用里，"自然的"均衡比"任意"的均衡重要（→ 通信与协作的零样本协作问题）。
• 零和博弈有清晰的目标（可利用性趋零），这是自博弈 + 搜索（AlphaZero）与 CFR 系方法成功的原因之一。
• 无悔收敛到 CCE：训练多智能体时不必强制收敛到纳什，收敛到相关均衡可能已经足够（甚至更符合"大家都不亏"的直觉）。

本章要点

• 一般和博弈中纳什均衡难计算且不唯一
• 零和博弈有清晰的最优解概念
• 无悔学习收敛到粗相关均衡

相关阅读

• 自博弈与 PSRO