第九章：计算博弈论

第九章 · 计算博弈论

章节摘要：手算时代到本章为止。真实博弈动辄亿万个策略组合：围棋的状态数超过可观测宇宙的原子数，扑克的信息集以十亿计，网络拍卖的参与人以百万计。计算博弈论研究两件事：均衡到底难不算得动（复杂性理论给出的答案近乎冷酷地干脆——难，且可证明地难），以及面对困难有哪些可靠与不可靠的逼近手段。本章还覆盖实验与行为偏离：真实人类与教科书理性人的系统差异。读完本章，你会知道什么时候该信模型、什么时候该测行为、什么时候该让算法上场。

学习目标

读完本章，你应当能够：

1. 区分最坏情况复杂性与实际可解性，说明纳什均衡求解的 PPAD 完全地位；
2. 描述支撑枚举与勒姆克-豪森算法的适用规模与输出性质；
3. 解释虚拟对弈与反事实遗憾最小化的收敛条件与适用场景；
4. 搭建一个重复囚徒困境锦标赛，评估策略的稳健性；
5. 复述最后通牒实验的典型数字，并解释公平偏好如何改写收益函数；
6. 在"模型预测"与"行为预测"之间做出有依据的选择。

核心概念速览

计算博弈论的地图上有三块地形。复杂性理论的结论冷峻：找纳什均衡与找不动点同源，PPAD 完全意味着除非数学根基动摇，不存在对一切博弈都高效的确切算法——这与线性规划的可解性形成鲜明对照。逼近算法因此成为主力：零和场景有收敛保证（虚拟对弈、遗憾最小化），一般场景则只有启发式与希望。行为实验是第三块地形：人类不是误差很小的理性机器，量化响应、层级思维与公平偏好给出"带参数的人"，让模型的预测口径与误差范围首次可以被校准。

一句金句：计算的边界告诉我们模型的可信半径——零和场景敢下断言，一般场景只敢给区间，行为场景先跑实验。

子章节导航

• 9.1 算法与复杂度：求解问题的复杂度地形、纳什均衡的 PPAD 完全性、确定性算法的循环陷阱，配复杂度地图。
• 9.2 求解工具与模拟：锦标赛方法论、虚拟对弈与遗憾最小化、Kuhn 扑克的简化演算与主流软件生态，配工具栈分层图与代码。
• 9.3 实验与行为洞见：最后通牒与信任实验的数字、量化响应与层级思维模型、如何把行为参数装回模型，附行为修正对照表。

子章节之间的逻辑关系

本章按"多难、怎么办、人真的这么干吗"三问推进：9.1 给出难度的数学定位，9.2 给出工程上的逼近手段，9.3 用实验校准人这个参数源。三节合起来的作用是把全书理论标注上"可信区间"——知道每个结论在什么规模与什么人性假设下仍然成立。

  9.1 复杂度（多难）
        │
        ├── 9.2 算法与工具（怎么办）
        │
        └── 9.3 行为实验（人真的这么干吗）
​

本章知识点清单

• PPAD 类的含义、纳什均衡求解的完全性结论及其对工程的影响；
• 支撑枚举的规模上限与勒姆克-豪森算法的适用条件；
• 零和博弈收敛保证的来源与一般场景的失效方式；
• 反事实遗憾最小化的核心思想：按"当初换一招的遗憾"加权调整；
• 最后通牒实验的典型分配区间与拒绝率的稳健性；
• 量化响应函数的参数含义，及层级思维对"猜猜他人怎么想"的解释力。

前置知识与后续延伸

需要第 2 章的均衡概念与第 6 章的重复结构；能读懂简单的循环与表格即可，不要求算法复杂度理论的先修。学完本章，第 10 章把镜头拉远看前沿；想深挖算法的读者，可在 9.2 的代码基础上改造参数做自己的锦标赛。

离章自测三题。其一，为什么两人零和博弈可以精确求解，而一般和只能近似？把答案落在复杂度类上。其二，以牙还牙在哪种锦标赛设置下会从冠军跌出前列，为什么？其三，最后通牒实验里提议者出价四到五成，用不公平厌恶改写收益函数后，理性预言如何变化？三题能答，说明你已获得给理论结论标注可信半径的能力——这正是本章的真正交付物。