9.1 算法与复杂度

9.1 算法与复杂度

本节摘要：本节回答"均衡到底好不好算"。答案分两层：两人零和博弈有线性规划级的稳定算法；一般和博弈的纳什均衡求解在复杂性理论上与"找不动点"同级，是 PPAD 完全问题——除非 P 等于 NP 一类的根基假设被推翻，不存在对一切博弈都高效的确切算法。本节还拆解确定性学习规则为何会陷入循环，这正是复杂性结论在微观层面的投影。

一、复杂度地形：一张能定位的地图

先建立坐标系。复杂度类 P 收纳有多项式时间算法的问题——线性规划属于它（多面体算法的胜利）；NP 收纳解可以快速验证的问题；PPAD（有向论证的不动点类）则收纳"解保证存在，但存在性证明依赖非构造性论证"的问题——纳什均衡的存在性靠不动点定理保证，而不动点定理本身不给寻找的路径。2006 年达斯古普塔与戈德堡证明了两人博弈纳什均衡的 PPAD 完全性，2009 年陈鑫与邓小铁把难度进一步收紧到两策略博弈：即便每个参与者只有两个可选动作，找均衡也是同类问题里最难的。这个结论不是"暂时没找到好算法"，而是"好算法的存在将动摇整个复杂性理论的根基"——工程上应当把它当作地质稳定层来规划。

对照面同样重要。两人零和博弈的求解是多项式可解的——极小极大定理直接把它变成线性规划，工业级的求解器毫秒内处理上万策略；完美信息的序贯博弈用回推，规模随树的节点线性增长（存储才是瓶颈）。所以复杂度地图上的落点取决于博弈的结构：结构越对称（零和、完美信息），越好算；结构越一般（非零和、不完美信息），越接近不可及的地带。

图 9-1：均衡求解的复杂度地形

二、确切算法的两种形态与它们的天花板

支撑枚举是教科书式的确切算法：均衡里概率为正的策略集合叫支撑，枚举双方支撑的全部组合，每个组合解一组线性条件（概率非负、支撑内无差异、支撑外不更优）。二乘二矩阵两个支撑组合，瞬间完成；十乘十矩阵支撑组合数以万计，尚可容忍；一百乘一百的组合数是天文数字——指数天花板明确可见。勒姆克-豪森算法聪明一些：把均衡存在性证明里的路径追踪变成算法，在两人博弈上从"多出来的虚拟策略"出发沿互补松驰路径走，端点即均衡。它的平均表现好，但最坏步数仍是指数级，且一次只输出一个均衡——均衡选型问题它帮不上忙。

一般和之外的常见形态各有专门解法：完美信息序贯博弈的回推是线性扫描；两人零和写成线性规划；多人在零和附近的结构可用间接方法。工程结论是：确切算法适用于"结构好或规模小"，两者都不占时，就该转入 9.2 的近似路线。

三、确定性规则的循环宿命

复杂性结论在微观层面有一个生动的投影：确定性学习规则会转圈。石头剪刀布是最小的漩涡：任何"上次对方出什么我就换成克制它的"式的确定性最佳应对，都会陷入三方追逐的死循环——出拳序列永不收敛，均衡（各三分之一）在经验频率意义上可达，在逐期策略意义上永不可达。沙普利 1964 年给出的著名例子证明：最佳应对动态在一般和博弈里甚至不保证收敛到任何地方。这个循环不是实现瑕疵，而是 PPAD 难度的微观成因——均衡的存在靠不动点保证，不动点恰恰是确定性的迭代规则绕不出来的那种点。

出路有两条，都以放弃一点什么为代价。注入随机性：按当前信念的概率混合出招（虚拟对弈的思路），把死循环化成平均行为的收敛——收敛的不是策略，是策略的时间平均。放宽均衡概念：接受"接近均衡"的近似解，允许 ε 大于零的偏离空间——复杂性理论同时证明了近似也有自己的悬崖（多项式时间只能逼近较粗糙的精度），但工程精度通常够用。两条思路的落地形态在下一节展开。

四、把复杂度读成工程承诺

复杂度结论要翻译成工程语言才有用。第一份翻译是规模表：二乘三的矩阵，支撑枚举组合个位数，纸面可解；双方各十策略，支撑组合两的二十次方量级，代码一晚；双方各五十策略，枚举在数学上仍在，物理上不再。第二份翻译是承诺等级：零和博弈可以承诺"精确均衡"；一般和大博弈只能承诺"误差不超过 ε 的近似均衡"且 ε 有下界；行为混合的场景再降一档，只能承诺"模型在样本内的拟合优度"。写结论时对号入座，别把第三档写成第一档。第三份翻译是预算分配：既然一般求解不可行，工程的自由度转向"挑结构"——把谈判设计成序贯披露（让博弈变成可回推的完美信息树），把多边机制拆成双边机制串联，或给博弈加约束让均衡唯一化。复杂性不可绕开，但问题可以被重新表述——这是复杂性结论最实用的一面。

五、结构与对称性：两项合法的捷径

峭壁并非处处等高，两类结构自带下坡路。图博弈（graphical games）假设每个参与者的收益只依赖少数邻居——网络互动的常态——均衡存在性的刻画与计算都随图的稀疏程度降级，社交网络与交通网络的博弈因此可解得多。对称博弈则更彻底：所有参与者角色相同、收益对称时，只需在对称均衡里找，高维问题塌缩成单种群问题——6.2 的演化框架本质上正是对称博弈的单种群动力学，公共品与拥堵场景的多数应用都在这一档。识别捷径的口诀：先看收益矩阵能不能被"少数邻居"或"人人相同"两刀切开，能切开的问题，峭壁上其实修了盘山路。

走完这一章，复杂性结论在工程里就完成了身份转换：它不再是"这道题解不动"的判决书，而是选型时的地形图——PPAD 完全性划出不可硬闯的峭壁，零和与完美信息标出坦途，图结构与对称性指出盘山路。下一章把这些地形判断接进具体算法：什么时候直接调求解器、什么时候改走近似、什么时候干脆重述问题，都会给出可操作的分工。

一条实用的收尾判据：遇到大规模博弈时，先花半小时判定它落在地形图的哪一层、有没有对称或稀疏的捷径可走，再决定投入多少算力——多数工程惨案不是算力不够，是把峭壁问题硬塞进了平原预算，或者反过来，在平原上浪费了数月的近似代码。

把本节与第 6 章连起来还能多看一层：复杂性给"均衡预测"划了红线，而演化与学习动态给"长期走向"留了后门——即便均衡算不出来，"系统此刻正在朝哪个方向漂"往往可估。金融监管、平台治理里的大量实战判断，用的正是方向感而非点位：不需要解出明天的均衡，只需要知道今天的规则把系统推向哪边。这也是为什么复杂度结论不是悲观的丧钟，而是研究议程的重新分配——从"解出均衡"转向"理解动态"。

本节要点回顾

• 要点一：两人零和与完美信息是多项式平原，一般和纳什均衡是 PPAD 峭壁，两策略博弈已完全。
• 要点二：支撑枚举的天花板是支撑组合的指数增长，勒姆克-豪森走路径但最坏仍指数且只给一个均衡。
• 要点三：石头剪刀布的确定性最佳应对循环与沙普利例，是复杂性结论在迭代规则上的微观投影。
• 要点四：出路的代价清单——随机化收敛到时间平均，近似解标注精度承诺，两者都要写进分析结论的口径。