2.2 均衡求解技术

2.2 均衡求解技术

本节摘要：上一节认识了均衡的两副面孔，本节把"找均衡"升级为一套可复用的技术栈：反复剔除、最优反应函数、支撑枚举、零和线性规划与虚拟对弈。每个技术都标明适用规模与失效场景，并用一场攻防突袭博弈做完整的数值演算。读完本节，三乘三以内的矩阵你应当能在纸面上系统清剿，更大的矩阵知道交给哪类算法。

一、技术栈总览：按矩阵规模选工具

求解纳什均衡没有万能流水线，但有清晰的选型顺序。矩阵还大时，先做减法：反复剔除严格劣策略，能砍掉大量行与列，且计算便宜。减到二乘二，用无差异条件配平即可闭式求解。非零和的一般矩阵、策略数较多时，用支撑枚举：均衡中概率为正的策略集合叫支撑，枚举双方支撑的所有组合，在每个组合上解一组线性方程，检验概率非负且为最优反应——小矩阵上这是精确算法。两人零和博弈有特殊通道：冯·诺依曼在 1928 年就证明极小极大定理，其线性规划形式让求解变成标准运筹问题，且对偶关系自动给出双方的均衡策略。更大的非零和矩阵没有已知的多项式精确算法（9.1 节会解释这是复杂性意义上的困难，而非暂时没人聪明），工程上退而求其次用迭代法逼近，虚拟对弈是其中最直观的一种：让双方各自把对手的历史出招频率当作今日的类型，反复最佳应对，平均策略被证明收敛于零和博弈的均衡。

二、手算示范：突袭博弈的完整清剿

背景。防御方只有一支机动守备队，可驻东线或西线；进攻方选择主攻一个方向。攻下东线对进攻方价值 6，西线价值 4；守备队驻守的方向使进攻失败，进攻方收益记 0。双方同时决策、互相不知情，进攻方最大化期望价值，防御方使其最小化——标准的两人零和博弈。

操作。收益矩阵（进攻方视角）：攻东对守东得 0、对守西得 6；攻西对守东得 4、对守西得 0。先查纯策略：固定守方守东，攻方改攻西得 4 大于 0；固定守方守西，攻方改攻东得 6 大于 0；固定攻方攻东，守方改守东从 6 降到 0；固定攻方攻西，守方改守西从 4 降到 0——谁都不想留在一个确定选择上，纯策略均衡不存在，转混合配平。

设守方以概率 q 守东。攻方攻东的期望 = 0·q + 6(1 − q)；攻西的期望 = 4q + 0(1 − q)。无差异条件：6(1 − q) = 4q，解得 q = 0.6。设攻方以概率 p 攻东。守方守东的期望损失 = 0·p + 4(1 − p)；守西 = 6p。无差异：4(1 − p) = 6p，解得 p = 0.4。博弈价值 = 6 × 0.4 = 2.4，也等于 4 × 0.6，两条路线互验通过。

结果。均衡为：守方以 0.6 的概率守东、0.4 守西；攻方以 0.4 攻东、0.6 攻西；进攻的均衡期望收获 2.4。

解读。结果反直觉但逻辑硬：价值更高的东线，进攻方押它的概率反而更低。原因在于守方对高价值目标的防备更敏感——攻东一旦被守到，损失的价值也大，攻方必须压低攻东频率，恰好让守方觉得守两线无差别；反过来守方把六成概率押在东线，正好抵消东线的价值诱惑。直觉只能指出"高价值目标更常被守"，定量结论（0.6 对 0.4，价值 2.4）必须由联立方程给出——这正是需要技术栈的原因。

变式。若守方多到可以分兵两线，博弈立刻退化：分兵让攻方两个方向都归零，守方一路纯策略分兵即可，混合配平失去意义——这个退化案例反过来提醒我们，混合均衡的配平依赖于"任何纯策略都会被反制"这一前提。若攻方可先派佯攻部队干扰守方观察，博弈获得时间与信息结构，那是第 3 章信号博弈的领地。

三、代码实现：支撑枚举与虚拟对弈

import itertools, random

# 通用二乘二混合均衡：枚举双方支撑，无差异配平
def solve_2x2(U1, U2):
    """U1[i][j] = 参与者1在策略i,j下的收益，参与者2同理"""
    best = None
    for s1 in range(2):
        for s2 in range(2):
            # 纯策略组合是否互为最优反应
            if U1[s1][s2] >= max(U1[i][s2] for i in range(2)) and \
               U2[s1][s2] >= max(U2[s1][j] for j in range(2)):
                best = (("纯", s1), ("纯", s2))
    # 无差异配平：参与者1选 s1 的概率 p 使参与者2无差异
    # p*U2[0][0]+(1-p)*U2[1][0] = p*U2[0][1]+(1-p)*U2[1][1]
    denom = (U2[0][0] - U2[1][0]) - (U2[0][1] - U2[1][1])
    p = (U2[1][1] - U2[1][0]) / denom if denom else 0.5
    denom2 = (U1[0][0] - U1[0][1]) - (U1[1][0] - U1[1][1])
    q = (U1[1][1] - U1[0][1]) / denom2 if denom2 else 0.5
    return best, (round(p, 4), round(q, 4))

# 虚拟对弈：把对手历史频率当类型，反复最佳应对
def fictitious_play(U1, U2, rounds=20000):
    c1 = [1, 1]; c2 = [1, 1]          # 计数从 1 起避免除零
    for _ in range(rounds):
        e1 = [U1[i][0]*c2[0]/sum(c2) + U1[i][1]*c2[1]/sum(c2) for i in (0, 1)]
        e2 = [U2[0][j]*c1[0]/sum(c1) + U2[1][j]*c1[1]/sum(c1) for j in (0, 1)]
        a1 = e1.index(max(e1)); a2 = e2.index(max(e2))
        c1[a1] += 1; c2[a2] += 1
    return [x/sum(c1) for x in c1], [x/sum(c2) for x in c2]

# 猜硬币：甲正=1 反=-1，乙相反
U1 = [[ 1, -1], [-1,  1]]
U2 = [[-1,  1], [ 1, -1]]
print(solve_2x2(U1, U2))             # 混合均衡各 0.5
print(fictitious_play(U1, U2))       # 收敛到约 0.5 0.5
​

两段代码在猜硬币上都输出各 0.5，与手算一致。虚拟对弈的价值在零和之外：虽然一般非零和博弈上不保证收敛，但大量场景（含 7.2 节的拍卖出价学习）里它给出的平均策略是很好的近似起点。把上面突袭博弈的矩阵代入 solve_2x2 的四行数据，可以核对第二节的配平结果。

四、易错点与要点回顾

三个高频错误。其一，弱劣策略当严格劣策略剔除，会把某些均衡剔丢——只剔严格的。其二，支撑枚举时漏检"概率为负"的解：无差异方程组可能给出负概率，那是支撑选错的信号，不是均衡。其三，零和博弈误用"最大化自己列均值"这类启发式——极小极大要求的是保证值最大化，二者在对手随机化时完全不同。

• 要点一：选型顺序是剔除减法、闭式配平、支撑枚举、零和线性规划、迭代近似，规模越大越靠后。
• 要点二：突袭博弈演示了零和配平的完整流程，也演示了"直觉定向、公式定量"的分工。
• 要点三：虚拟对弈用平均策略逼近均衡，是零和场景下简单可靠的数值通道。
• 要点四：混合均衡方程组可能给出负概率，那是支撑选错的信号，要换支撑重解而不是硬圆。