【算法分析与设计】第30篇：博弈论算法入门：纳什均衡与组合博弈

在之前所有篇章中，算法面对的是一个被动的世界：输入给定，约束固定，目标明确，算法只需单向地计算出最优解。但现实中有大量的决策场景并非如此。你在拍卖中出价，对手会根据你的出价调整策略；你选择通勤路线，其他司机也在同时做出同样的决策，所有人的选择共同决定了每条路的拥堵程度；你下棋时，对手的每一步都在主动地破坏你的计划。这些场景的共同本质是：存在多个决策主体，每个主体的最优选择依赖于对其他主体行为的预测，而其他主体也在做同样的推理。博弈论正是分析这种策略互动的数学语言，而算法博弈论则将计算复杂性和算法设计引入这一框架。

一、博弈的基本要素与分类

形式化地，一个博弈由三个要素构成。

第一是参与者，通常记为集合 N={1,2,…,n}N={1,2,…,n}。

第二是策略空间，每个参与者 ii 拥有一个可选策略的集合 SiSi​。

第三是收益函数ui:S1×⋯×Sn→Rui​:S1​×⋯×Sn​→R。给定一个策略组合 (s1,…,sn)(s1​,…,sn​)，其中每个参与者都选定了一个策略，uiui​ 给出参与者 ii 在此组合下的收益数值。所有参与者同时或独立地选择策略，收益由最终的策略组合决定。

按照参与者之间的利益关系，博弈可以分为三类。本文重点讨论第一类和第三类。

零和博弈：两人参与，收益之和恒为零。一方的收益恰好是另一方的损失。这是最纯粹的对抗性博弈，棋类游戏、点球大战、网络安全攻防均可建模为零和博弈。

非零和博弈：参与者的利益既有冲突也有一致。囚徒困境、企业价格竞争、国际气候谈判均属此类。此时“合作还是背叛”成为核心议题。

组合博弈：两人轮流行动，完全信息，无随机因素。象棋、围棋、Nim取石子游戏均属此类。其核心特征是“轮流操作”而非“同时选择”。

二、零和博弈与最小最大定理

考虑最简单的两人零和博弈。参与者1（行玩家）有 mm 个纯策略，参与者2（列玩家）有 nn 个纯策略。收益矩阵 A∈Rm×nA∈Rm×n 定义如下：行玩家选策略 ii、列玩家选策略 jj 时，行玩家获得 AijAij​，列玩家获得 −Aij−Aij​。行玩家希望最大化自己的收益，列玩家希望最小化行玩家的收益。

如果双方都必须选择纯策略，即确定性地选一个策略，行玩家会这样推理：“我选 ii，列玩家必定选 arg⁡min⁡jAijargminj​Aij​ 来最小化我的收益。所以我应该选那个能最大化自身最坏情况收益的策略。”这给出了最大最小值：

vmax⁡min⁡=max⁡imin⁡jAijvmaxmin​=maxi​minj​Aij​

对称地，列玩家的最小最大值为：

vmin⁡max⁡=min⁡jmax⁡iAijvminmax​=minj​maxi​Aij​

不等式 max⁡min⁡≤min⁡max⁡maxmin≤minmax 恒成立。先手选择策略，后手针对性回应，先手确实处于劣势。在某些矩阵中，严格不等式成立，此时“谁先暴露策略”至关重要。

冯·诺依曼在1928年发表的最小最大定理是博弈论的奠基性成果。如果允许混合策略——参与者以概率分布选择纯策略——则上述不等号变为等号。设行玩家的混合策略为概率向量 x∈Δmx∈Δm​，列玩家的混合策略为 y∈Δny∈Δn​，期望收益为 xTAyxTAy。最小最大定理断言：

max⁡x∈Δmmin⁡y∈ΔnxTAy=min⁡y∈Δnmax⁡x∈ΔmxTAymaxx∈Δm​​miny∈Δn​​xTAy=miny∈Δn​​maxx∈Δm​​xTAy

这个公共值 v∗v∗ 称为博弈的值。达到该值的策略对 (x∗,y∗)(x∗,y∗) 构成一个纳什均衡。在零和博弈中，任何一方单方面偏离均衡策略都不会改善自身收益。

更精妙的是，这个均衡可以通过求解一对互为对偶的线性规划得到。

原问题（P）：

max⁡vs.t.xTA≥v1T,∑ixi=1,xi≥0maxvs.t.xTA≥v1T,∑i​xi​=1,xi​≥0

对偶问题（D）：

min⁡ws.t.Ay≤w1,∑jyj=1,yj≥0minws.t.Ay≤w1,∑j​yj​=1,yj​≥0

这意味着零和博弈的最优策略可以在多项式时间内精确计算，只需调用一次线性规划求解器。在多臂赌博机问题、在线学习的对抗性分析、安全博弈的资源分配中，这一结果构成了算法基础。

三、纳什均衡：存在性、计算复杂性与意义

当博弈不再是零和时，最小最大定理不再成立。参与者的利益不完全对立，无法用单一数值刻画博弈的“值”。核心概念转为纳什均衡：一组策略，可以是混合策略，使得没有任何参与者可以通过单方面改变自己的策略而获得更高收益。

形式化地，设参与者 ii 的策略为 sisi​，其他参与者的策略组合为 s−is−i​。若对任意 ii 和 ii 的任意可选策略 si′si′​，有：

ui(si,s−i)≥ui(si′,s−i)ui​(si​,s−i​)≥ui​(si′​,s−i​)

则策略组合 (s1,…,sn)(s1​,…,sn​) 是一个纳什均衡。每个人都在给定他人选择的前提下做出了最优回应，系统处于某种“稳定态”。

Nash在1951年证明了一个存在性定理：任何有限博弈（参与者有限、策略有限）至少存在一个混合策略纳什均衡。证明基于角谷静夫不动点定理，其核心构造是“最优回应映射”——将参与者的策略组合映射到自身，其不动点恰为纳什均衡。这一定理的确立使纳什获得了1994年诺贝尔经济学奖。

然而，存在性不等于可计算性。Daskalakis、Goldberg和Papadimitriou在2009年证明了一个令人震惊的结果：计算一般非零和博弈的纳什均衡属于PPAD完全问题。PPAD是一个介于P与NP之间的复杂度类，一般认为其中的完全问题不具备多项式时间算法。

这一结果对经济学理论提出了深刻挑战。如果连计算机都无法在合理时间内找到均衡，人类市场如何通过自发交互收敛到均衡？传统经济学的“均衡总是会达到”的信念，在计算复杂性的审视下需要更精细的论证。算法视角的引入不仅为博弈论提供了新的计算方法，更从根本上重塑了我们对“理性”与“均衡”的认识。

四、公平组合博弈：从Nim到Sprague-Grundy定理

从连续策略和混合策略的博弈论，我们转向另一类结构完全不同的博弈——组合博弈。与“同时选择策略”不同，组合博弈是“轮流操作”的。

组合博弈理论的研究对象是公平组合博弈，满足三个条件。第一，两人轮流行动。第二，双方在任何游戏状态下的合法移动集合完全相同，这与象棋中红方只能动红子、黑方只能动黑子截然不同。第三，无法移动的玩家输，这称为正常规则。

Nim是最经典的公平组合博弈。有若干堆石子，每轮玩家选择一堆并从中取走任意正整数颗石子。取走最后一颗石子的玩家获胜。

分析Nim的第一个关键步骤是将“胜负”转化为数值。定义博弈状态 GG 的Grundy数，也称nimber，记为 g(G)g(G)。递归定义如下：终态，即无法移动的状态，Grundy数为 00。对于非终态 GG，设其一次合法移动可达的状态集合为 {G1,G2,…,Gk}{G1​,G2​,…,Gk​}，则：

g(G)=mex{g(G1),g(G2),…,g(Gk)}g(G)=mex{g(G1​),g(G2​),…,g(Gk​)}

其中 mexmex（minimum excludant）表示不出现在集合中的最小非负整数。例如，若可达状态的Grundy数为 {0,1,3}{0,1,3}，则 g(G)=2g(G)=2。

Sprague-Grundy定理是组合博弈理论的最高成果，包含两个核心结论。

第一，等价性。任意公平组合博弈的任意状态，等价于一局具有相同Grundy数的单堆Nim游戏。Grundy数为零的状态是后手必胜态，非零状态是先手必胜态。

第二，可分解性。多个不相交的公平组合博弈的和，即每轮玩家任选一个子博弈操作，其Grundy数等于各子博弈Grundy数的按位异或（XOR），称为Nim和。

以Nim为例验证。单堆 nn 颗石子的博弈，可达状态为 {0,1,…,n−1}{0,1,…,n−1} 颗石子，由定义可归纳得 g(n)=ng(n)=n。对于多堆Nim，状态为 (n1,n2,…,nk)(n1​,n2​,…,nk​)，Sprague-Grundy定理直接给出其Grundy数为：

g(n1,n2,…,nk)=n1⊕n2⊕⋯⊕nkg(n1​,n2​,…,nk​)=n1​⊕n2​⊕⋯⊕nk​

因此Nim的胜负判定仅有一步异或运算。Nim和非零则先手必胜，为零则后手必胜。Bouton在1901年仅用一行数学公式便彻底解决了Nim游戏，这可能是整个算法博弈论中最简洁而优美的结果。

更深刻的是，Sprague-Grundy定理将这种简洁性推广到了所有公平组合博弈。无论博弈规则多么复杂——多堆不同规则的取石子变体、图上棋子移动博弈、删除边博弈——只要你能分别计算出各分量的Grundy数，整个复合博弈的胜负判定就仅需一次异或运算。这一结论将指数级规模的博弈树分析压缩为Grundy数的计算与异或，是组合数学在博弈问题上最成功的应用之一。

五、从博弈论到算法设计：延伸与展望

博弈论与算法设计的交叉已成为理论计算机科学最活跃的前沿领域之一。以下几个方向是本专栏后续篇章将涉及的。

机制设计，也称逆博弈论。给定一个社会目标，设计博弈规则，包括分配规则和支付函数，使得理性参与者在追求自身利益最大化时，其均衡结果正好实现该社会目标。VCG拍卖、关键词竞价排名、双边匹配市场均属此列。

自私路由与无政府代价。大量用户独立选择路径以最小化自身出行时间时，系统达到的均衡的总出行时间，与全局最优分配之间的比值称为“无政府代价”。这一概念量化了“缺乏中央协调”的效率损失上限。

在线学习与遗憾界。当博弈重复多轮，参与者根据历史反馈调整策略。乘法权重更新算法保证“遗憾”——相对于事后最优固定策略的累计损失——以 O(Tlog⁡n)O(Tlogn​) 的速率增长。这一方法在博弈求解、对冲策略、在线广告投放中广泛应用。

六、总结

从零和博弈的线性规划求解，到纳什均衡的PPAD完全性，再到Nim游戏的异或判定，博弈论为多主体策略交互提供了从存在性到可计算性的完整分析框架。零和博弈的最优策略可高效计算，公平组合博弈的胜负判定归约为异或运算。这些正面结果展示了数学结构如何将策略推理转化为算法。而纳什均衡的计算困难性则警示我们：并非所有经济学概念都具有良好的计算性质，“均衡可达”这一信念需要在算法视角下重新审视。

下一篇，我们将从博弈论转向另一个算法设计的支柱领域——数论算法。扩展欧几里得算法、模运算与同余方程，这些看似初等的工具构成了现代密码学和安全通信的数学基石。从RSA到椭圆曲线，从素数测试到大整数分解，数论算法的精巧与威力将在下一篇中展开。