第三讲 · 混合策略 Nash 均衡

有些博弈的每个纯策略组合都存在有利偏离。此时“永远选择某个行动”不可能稳定，但“以恰当概率随机选择”却可能让对手无从利用，从而形成混合策略 Nash 均衡。

1. 猜硬币为什么没有纯策略均衡

双方同时选择正面 $O$ 或反面 $R$。两枚硬币相同则玩家 2 赢，不同则玩家 1 赢：

玩家 1 \ 玩家 2	$O$	$R$
$O$	$(-1,1)$	$(1,-1)$
$R$	$(1,-1)$	$(-1,1)$

任何一个格子里，输的一方都愿意改变行动。因此四个格子都不是 Nash 均衡。

问题的本质是：每个人都想猜中对手，又都不想被对手猜中。若行动可预测，对手就能针对；均衡必须让对手无法从改变自己的纯行动中获利。

2. 混合策略是纯策略上的概率分布

若玩家 $i$ 的纯策略集为

$$S_i=\{s_{i1},\dots,s_{ik}\},$$

混合策略 $\sigma_i$ 满足

$$\sigma_i(s_{ij})\ge0, \qquad \sum_{j=1}^{k}\sigma_i(s_{ij})=1.$$

纯策略是混合策略的特例：某个行动的概率为 $1$，其他行动为 $0$。

混合策略不是“玩家不知道自己在做什么”，而是玩家有意保持不可预测。每次实际行动仍然是一个纯行动，概率描述的是行动产生机制。

3. 混合策略下比较期望收益

所有玩家独立随机化时，纯策略组合 $s=(s_1,\dots,s_n)$ 出现的概率为

$$\prod_{j=1}^{n}\sigma_j(s_j).$$

玩家 $i$ 的期望收益为

$$u_i(\sigma) = \sum_{s\in S} \left( \prod_{j=1}^{n}\sigma_j(s_j) \right) u_i(s).$$

两人各有两个策略时，设玩家 1 第一个策略的概率为 $p$，玩家 2 第一个策略的概率为 $q$，四个格子的概率分别是

$$pq,\quad p(1-q),\quad (1-p)q,\quad (1-p)(1-q).$$

4. 支集与无差异原理

混合策略中概率大于零的纯策略集合叫支集：

$$\operatorname{supp}(\sigma_i) = \{s_i:\sigma_i(s_i)>0\}.$$

均衡中，玩家愿意在支集内随机选择，说明这些纯策略给他的期望收益必须相同，而且不能低于支集外策略：

$$u_i(s_i,\sigma_{-i}) = u_i(s_i',\sigma_{-i}) \ge u_i(s_i'',\sigma_{-i}),$$

其中 $s_i,s_i'$ 位于支集内，$s_i''$ 位于支集外。

如果支集内某个行动收益更低，玩家就会把它的概率全部移走，它便不可能以正概率出现。

5. 最容易写反的逻辑

设玩家 1 用概率 $p$ 随机化，玩家 2 用概率 $q$ 随机化：

• 玩家 1 是否无差异，由玩家 2 的概率 $q$ 决定；
• 玩家 2 是否无差异，由玩家 1 的概率 $p$ 决定。

因此：

用玩家 1 的无差异方程解 $q$，用玩家 2 的无差异方程解 $p$。

自己的均衡概率不是为了让自己无差异，而是为了让对手无法通过改行动获利。

6. 猜硬币的完整推导

设玩家 1 选择 $O$ 的概率为 $p$，玩家 2 选择 $O$ 的概率为 $q$。

玩家 1 选择两个纯策略的期望收益分别为

$$u_1(O)=q(-1)+(1-q)(1)=1-2q,$$ $$u_1(R)=q(1)+(1-q)(-1)=2q-1.$$

令玩家 1 无差异：

$$1-2q=2q-1,$$

得到

$$q=\frac12.$$

同理，玩家 2 无差异要求

$$p=\frac12.$$

所以唯一的 Nash 均衡是双方都以 $1/2$ 概率选择正面、以 $1/2$ 概率选择反面，均衡期望收益都是 $0$。

7. 性别战：纯策略和混合策略可以同时存在

玩家 1 \ 玩家 2	足球 $F$	芭蕾 $B$
足球 $F$	$(2,1)$	$(0,0)$
芭蕾 $B$	$(0,0)$	$(1,2)$

先用划线法可得两个纯策略 Nash 均衡：$(F,F)$ 与 $(B,B)$。

再求混合均衡。设玩家 1 选择 $F$ 的概率为 $p$，玩家 2 选择 $F$ 的概率为 $q$。

让玩家 2 在 $F$、$B$ 之间无差异：

$$p=2(1-p),$$

所以

$$p=\frac23.$$

让玩家 1 无差异：

$$2q=1-q,$$

所以

$$q=\frac13.$$

因此该博弈一共有三个 Nash 均衡：两个纯策略均衡，以及

$$\sigma_1=\left(\frac23,\frac13\right), \qquad \sigma_2=\left(\frac13,\frac23\right).$$

8. 一般博弈的支集枚举

两人不止两个策略时，可以按下面步骤系统求解：

1. 猜测双方均衡策略的支集；
2. 令对手在其支集中的所有纯策略期望收益相等；
3. 加上所有概率之和为 $1$；
4. 解方程并检查概率全部非负；
5. 检查支集外策略的期望收益没有更高。

出现以下任一情况，都说明猜错了支集：

• 方程无解；
• 某个概率为负；
• 支集外行动的期望收益更高。

策略数量增加后，可能的支集组合指数增长，这也是一般 Nash 均衡计算困难的来源。

9. 存在性与 Wilson 奇数定理

Nash 存在性定理保证：每个有限博弈至少存在一个 Nash 均衡，允许它是混合策略均衡。

课件还给出了 Wilson 奇数定理：对“几乎所有”的有限标准式博弈，Nash 均衡的数量是有限的奇数。这里的“几乎所有”排除了支付参数恰好落在退化情形上的博弈；在这些例外里，均衡数仍可能是偶数，甚至出现连续多个均衡。

这个结论也解释了一个常见现象：如果一个非退化博弈已经找到了两个纯策略均衡，通常还应继续找第三个均衡，它往往是混合策略均衡。但奇数定理不是机械的数数规则，遇到无差异区间或其他退化结构时不能直接套用。

这并不表示每个玩家一定在现实中真的掷硬币。混合策略还可以理解为：

• 玩家群体中不同个体选择不同纯策略；
• 同一玩家在重复环境中按长期频率行动；
• 很小的私人收益扰动使不同类型选择不同纯策略，整体上呈现随机比例。

10. 规划求解法

支集法需要枚举可能的支集。课件还介绍了另一种思路：把两人有限博弈的 Nash 条件写成一个规划问题。

设玩家 1、2 的收益矩阵分别为 $A\in\mathbb R^{m\times n}$、$B\in\mathbb R^{m\times n}$，混合策略分别为列向量 $x$、$y$，均衡收益记为 $\alpha$、$\beta$。考虑

$$\begin{aligned} \max_{x,y,\alpha,\beta}\quad &x^\mathsf T(A+B)y-\alpha-\beta\\ \text{s.t.}\quad &Ay\le \alpha\mathbf 1_m,\\ &x^\mathsf TB\le \beta\mathbf 1_n^\mathsf T,\\ &\mathbf 1_m^\mathsf Tx=1,\quad \mathbf 1_n^\mathsf Ty=1,\\ &x\ge0,\quad y\ge0. \end{aligned}$$

前两组约束表示：任何纯策略带来的期望收益都不能超过均衡收益。由这些约束可得

$$x^\mathsf TAy\le\alpha, \qquad x^\mathsf TBy\le\beta,$$

所以目标函数永远不大于 $0$。当最优值恰好为 $0$ 时，两个不等式都取等号，$x$、$y$ 就互为最优反应，因而构成 Nash 均衡。

这个写法避免了手工列出全部支集，但目标函数含有双线性项，并不是普通线性规划。参与人或策略增多后，支集法和规划法都仍会遇到计算复杂性。

11. 混合策略题的解题步骤

1. 先用划线法找完所有纯策略 Nash 均衡；
2. 设玩家 1、2 的混合概率为 $p$、$q$；
3. 写出玩家 1 各纯策略收益并令其相等，解 $q$；
4. 写出玩家 2 各纯策略收益并令其相等，解 $p$；
5. 检查概率在 $[0,1]$ 内；
6. 多策略题还要检查支集外策略；
7. 最后写出完整概率向量和均衡期望收益。

这里的无差异条件可以这样理解：一方的均衡随机化概率，恰好使对手在支集中的各个纯策略之间无差异。