Nash 均衡 | Codeboy's Blog

形式陈述

设 $p=(p_1,\ldots,p_n)$ 是有限博弈的混合策略剖面， $U_i$ 是独立抽样产生的期望收益。若对每位玩家 $i$ 和每份替代分布 $q_i\in\Delta(S_i)$ 都有

U_i(p_i,p_{-i})\ge U_i(q_i,p_{-i}),

则称 $p$ 为 Nash 均衡。式子右边只允许玩家 $i$ 改变自己的策略，其他人的分布完全固定。等价地，只需对每个纯动作 $a\in S_i$ 检查 $U_i(p)\ge U_i(a,p_{-i})$ ；任意混合偏离的收益是这些纯偏离收益的加权平均。

若每位玩家都以概率 $1$ 选择一个动作，这个均衡称纯策略 Nash 均衡。一般混合均衡中，每人赋正概率的动作必须都是对当前对手分布的最佳回应，而支持集外的动作可以同样好，也可以严格较差。

有限博弈存在定理。 玩家数量有限、每个纯策略集有限非空、收益为实数时，至少存在一个混合策略 Nash 均衡。下面用连续正增益映射和Brouwer 不动点定理给出自足证明。

从偏离增益构造连续映射

所有混合剖面组成 $K=\prod_i\Delta(S_i)$ 。它在有限维实空间中非空、闭且有界，并且凸，所以是非空紧致凸集。对 $p\in K$ 定义

g_{ia}(p)=\max\{0,U_i(a,p_{-i})-U_i(p)\},\qquad G_i(p)=\sum_{a\in S_i}g_{ia}(p).

$g_{ia}$ 是改选纯动作 $a$ 能获得的正增益；没有改进时记为零。把这个增益加到原概率上再归一化，得到

T_{ia}(p)=\frac{p_{ia}+g_{ia}(p)}{1+G_i(p)}.

分母至少为 $1$ ，各坐标非负，且对每位玩家求和恰为 $1$ ，所以 $T$ 将 $K$ 映回自身。有限期望收益是概率坐标的多项式，取最大值与上述除法保持连续，因此 $T$ 连续。Brouwer 定理给出固定点 $p=T(p)$ 。

为什么固定点一定是均衡

在固定点上，整理等式可得 $g_{ia}=p_{ia}G_i$ 。假设某位玩家 $G_i>0$ 。那么每个正支持动作都满足 $g_{ia}>0$ ，从而 $U_i(a,p_{-i})-U_i(p)>0$ 。然而收益的加权平均恒等式给出

\sum_a p_{ia}\bigl(U_i(a,p_{-i})-U_i(p)\bigr)=U_i(p)-U_i(p)=0.

左侧在所有正概率项上严格为正，与等于零矛盾。故每位玩家都满足 $G_i=0$ ，进而每个 $g_{ia}=0$ ，所有纯偏离都不能获利。线性性再排除所有混合偏离，固定点就是 Nash 均衡。

直觉

均衡是相互一致的最佳回应：每个人以其他人的策略为给定条件，再检查自己能否改进。这里没有要求大家满意当前收益，也没有要求共同改变方案后仍不能变好。一个剖面可能同时让所有人愿意联合离开，却没有任何人愿意独自先改。

存在证明没有直接把“选一个最佳回应”当作连续函数。在两动作收益刚好相等的位置，最佳回应可能从一个纯动作突然跳到另一个。正增益映射保留原概率，并随收益差连续地调整权重，因而满足不动点定理的条件。这个证明建立存在性；它没有证明反复迭代 $T$ 必然收敛，也没有给出寻找均衡的效率保证。

例子与边界

求出协调博弈的全部均衡

考虑下表，令 $p=\Pr(U)$ 、 $q=\Pr(L)$ ：

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

逐格比较可见 $(U,L)$ 、 $(D,R)$ 是纯均衡，另外两格都允许获利偏离。若双方都使用两个动作，支持集判据要求行玩家的两收益相等、列玩家的两收益也相等：

3q=2(1-q),\qquad 2p=3(1-p).

因此唯一全支持候选为 $p=3/5,q=2/5$ 。此时行玩家的两个纯收益都为 $6/5$ ，列玩家的两个纯收益也都为 $6/5$ ，所以任何单方混合偏离都不能超过 $6/5$ ，候选确为均衡。

还需排除只有一方随机化的边界情形。如果 $0<p<1$ ，行玩家的支持集包含两个动作，迫使 $q=2/5$ ，于是列玩家也完全混合，并迫使 $p=3/5$ 。如果 $p=1$ ，列玩家唯一最佳回应是 $q=1$ ；如果 $p=0$ ，列玩家唯一最佳回应是 $q=0$ 。这覆盖了 $p$ 的所有可能值，故全部均衡恰为

(p,q)=(1,1),\quad(0,0),\quad(3/5,2/5).

对应收益分别为 $(3,2)$ 、 $(2,3)$ 、 $(6/5,6/5)$ 。两个纯均衡都让双方比混合均衡收益更高，但在混合均衡处只改变自己并不能改善。联合改进与单方稳定由此可以同时存在；一般博弈的均衡也不具有共同收益值。

纯均衡可能不存在

让双方各选正面或反面；相同时行玩家得 $1$ 、列玩家得 $-1$ ，不同时收益反过来。在任一纯格子，输家翻转自己的动作就能变成赢家，所以没有纯均衡。双方各自独立以概率 $1/2$ 选择两面时，每个纯动作期望收益都是 $0$ ，任何单方偏离都无利可图。这是混合存在而纯存在失败的最小例子之一。

定理中的有限性负责给出有限维紧致单纯形和连续收益。若玩家可以选择任意实数并以所选数本身为收益，即使只有一个玩家，也永远能选更大的数，没有最佳回应或均衡。要研究无限策略博弈，需要另行检查策略空间和收益函数的条件。

把独立性与服从条件分开

混合 Nash 均衡通过独立抽样形成联合分布。若允许联合分布相关，并只检查事先固定的偏离，就得到粗相关均衡；若还允许根据私人建议改换动作，则得到相关均衡。对乘积分布，这两种条件都等价于本页的 Nash 条件：CCE 的固定偏离正是纯最佳回应检验，Nash 的支持集判据又保证每条 CE 条件偏离都不获利。

对一般联合分布，相关建议能提供独立混合没有的协调。本页博弈中，以各 $1/2$ 概率选择两个纯均衡 $UL,DR$ ，得到相关均衡；但把双方边际 $(1/2,1/2)$ 独立相乘，行玩家改选 $U$ 、列玩家改选 $R$ 都可获利 $1/4$ ，因此并不是 Nash 均衡。无遗憾学习保证经验联合分布趋近某类均衡集合时，也不能据此宣称个人频率的乘积或最后一轮动作成为 Nash 均衡。

推论与应用

矩阵博弈极小极大定理刻画二人零和情况下的均衡：双方各自保证同一个价值，任意最优行策略与最优列策略配对都形成均衡。这个共同价值来自零和结构；本页协调博弈的三个均衡已经展示它不能推广到一般收益表。

实际核验一份有限博弈均衡时，可以先检查各人的概率非负且和为一，再计算当前期望收益与每个纯偏离收益，最后逐项比较。存在定理保证有可通过检查的剖面，寻找过程则是另一个算法问题。

有限无权拥塞博弈提供了纯均衡必然存在的结构性情形：Rosenthal 势函数与每次单方成本变化完全一致，因此严格改进序列有限终止。这里的保证来自资源成本结构；一般有限博弈仍只能保证混合均衡存在。

参考资料

John F. Nash，Equilibrium Points in n-Person Games，PNAS 36(1)，1950，pp. 48–49；原刊扫描。该短文用 Kakutani 不动点定理证明存在性。
Éva Tardos and Vijay V. Vazirani，Basic Solution Concepts and Computational Issues，载 Algorithmic Game Theory，2007，§1.3.4，Theorem 1.8；教学全文。
Tim Roughgarden，CS364A Lecture 20，2013-12-04，§7，Brouwer 到 Nash 的存在性证明；讲义采用带二次惩罚的回应映射，与本页正增益映射的构造不同。

形式陈述 ​

从偏离增益构造连续映射 ​

为什么固定点一定是均衡 ​

求出协调博弈的全部均衡 ​

纯均衡可能不存在 ​

把独立性与服从条件分开 ​

反向链接