博弈论是研究多个智能体在竞争或合作环境中如何进行策略性决策的数学理论。传统博弈论与人工智能的深度融合，推动机器学习从“求取最优解”向“求取均衡解”转变。
博弈论的相关概念
博弈论的诞生
现代博弈论思想起源于1944年冯·诺依曼与摩根斯特恩合著的《博弈论与经济行为》，首次用数学形式阐述了博弈论及其应用。
约翰·纳什于1950年在其博士论文中提出非合作博弈及其均衡解一定存在的纳什均衡思想，将博弈论发扬光大，也因此获得1994年诺贝尔经济学奖。
博弈行为是多个带有相互竞争性质的主体，为达到各自目标和利益，采取的带有对抗性质的行为，即 “两害相权取其轻，两利相权取其重”。
博弈论术语与囚徒困境
基本术语
| 术语 | 说明 |
|---|---|
| 玩家（Player） | 博弈的参与者 |
| 策略（Strategy） | 玩家在每种可能情况下采取的行动方案 |
| 收益（Payoff） | 玩家在博弈结束后获得的效用值 |
| 均衡（Equilibrium） | 所有玩家策略达到稳定、无人愿单方面改变的状态 |
囚徒困境
两个共谋罪犯被捕，单独审讯。每人可选择坦白或抵赖。
| 甲\乙 | 乙抵赖 | 乙坦白 |
|---|---|---|
| 甲抵赖 | 各判1年 | 甲判10年，乙释放 |
| 甲坦白 | 甲释放，乙判10年 | 各判5年 |
- 个体理性：无论对方如何选择，坦白对自己更有利（严格占优策略）
- 均衡结果：双方都坦白，各判5年
- 集体最优：双方都抵赖，各判1年
- 困境本质：个体理性导致集体非最优的结果
博弈的分类
| 分类标准 | 类型 | 说明 |
|---|---|---|
| 是否合作 | 合作博弈 / 非合作博弈 | 玩家之间能否达成有约束力的协议 |
| 行动顺序 | 静态博弈 / 动态博弈 | 玩家是同时行动还是先后行动 |
| 信息完备性 | 完全信息 / 非完全信息 | 玩家是否知道其他玩家的收益函数 |
| 收益关系 | 零和博弈 / 非零和博弈 | 玩家收益之和是否恒为零 |
| 博弈次数 | 单次博弈 / 重复博弈 | 博弈是一次性还是多次重复进行 |
纳什均衡
定义：在一个策略组合中，每个玩家的策略都是对其他玩家策略的最优反应。没有任何玩家可以通过单方面改变自己的策略来获得更高的收益。
数学表达： 对于 个玩家的博弈，策略组合 是纳什均衡，当且仅当对每个玩家 ：
- ：玩家 的收益函数
- ：除玩家 外其他玩家的策略
纳什存在定理：任何具有有限玩家的有限策略博弈，至少存在一个纳什均衡（可能包含混合策略）。
| 策略类型 | 说明 |
|---|---|
| 纯策略 | 玩家确定性地选择某个具体动作 |
| 混合策略 | 玩家以一定的概率分布随机选择动作 |
人工智能与博弈论
人工智能与博弈论深度融合的研究方向：
- 博弈策略求解：寻找博弈中的均衡策略（如虚拟遗憾最小化算法）
- 博弈规则设计：设计机制使得个体理性行为导向合意的全局结果
- 多智能体学习：多个AI智能体在博弈环境中学习和进化
博弈策略求解
研究问题
在非完全信息博弈中，玩家不知道其他玩家的私有信息（如手牌），这大大增加了求解难度。核心目标是计算博弈中的纳什均衡策略或近似均衡策略。
挑战：
- 非完全信息博弈的状态空间极大（如德州扑克的博弈树规模约为 ）
- 需要考虑信息的不对称性和对手行为的不可预测性
虚拟遗憾最小化算法（Counterfactual Regret Minimization, CFR）
CFR 是求解大规模非完全信息博弈的里程碑算法，通过迭代自我博弈，使每个信息集上的虚拟遗憾值最小化，最终收敛到纳什均衡。
遗憾值（Regret）
- 遗憾值：实际采取某动作后，与事后知道的最佳动作相比，所遭受的损失
- 虚拟遗憾值（Counterfactual Regret）：在特定信息集上，对“如果采取了某动作”而“实际采取了另一动作”的遗憾进行虚拟计算，同时考虑对手到达该信息集的概率
CFR算法核心流程
CFR 使用反事实遗憾最小化来独立地最小化每个信息集上的遗憾：
计算反事实价值：对每个信息集，计算采取每种动作所能获得的期望价值
计算即时遗憾： ，即采取动作 的价值与信息集平均价值的差值
累积遗憾：
更新策略：使用遗憾匹配算法更新当前策略，使得正遗憾值的动作获得更高的选择概率：
迭代：重复上述过程，最终平均策略收敛到纳什均衡
数学保证：CFR 算法保证在无限次迭代后，平均策略的遗憾上界趋近于零，即策略收敛到近似纳什均衡。
安全子博弈
在实际博弈求解中，常将完整的博弈分解为若干子博弈进行处理：
- 子博弈：从某个决策点开始的博弈子树
- 安全子博弈求解：在求解子博弈时，需要保留父博弈中对手可能策略的全部信息，避免信息丢失导致策略“不安全”
安全子博弈求解技术使 CFR 可以在博弈树的各个局部进行独立优化，同时保证全局策略的质量。
博弈规则设计
研究问题
博弈规则设计（机制设计）研究：如何在给定社会目标的前提下，设计博弈规则（机制），使得自利的个体在追求自身利益最大化的过程中，恰好实现设计者所期望的全局目标。
应用场景：
- 拍卖机制设计
- 匹配市场设计（如学生入学分配、器官移植匹配）
- 交通流量调度
双边匹配算法
问题描述：存在两类参与者（如申请者和接收者），需要在两类之间进行一一匹配，每个参与者对另一类参与者有严格的偏好排序。
延迟接受算法（Gale-Shapley算法）是求解稳定匹配的经典算法。
稳定匹配：不存在这样一对参与者，他们互相认为对方优于自己当前的匹配对象。
算法流程（以申请者主动为例）：
- 每轮，每位未匹配的申请者向其偏好列表中尚未拒绝自己的最靠前接收者发出申请
- 每个接收者保留当前最佳申请者（含上一轮暂留的），拒绝其余的
- 重复直到没有新的申请发出
性质：
- 算法必然终止，且一定能找到稳定匹配
- 对主动方（申请者）是最优的，对被动方（接收者）是最劣的
单边匹配算法
问题描述：只有一类参与者（如室友分配），参与者之间相互匹配，每个参与者对所有其他参与者有偏好排序。
顶部交易循环算法（Top Trading Cycle, TTC）是求解单边匹配的经典方法，用于初始物品分配后的再交换等场景。
算法流程：
- 每个参与者指向自己最喜欢（尚未被占有）的物品
- 必然形成至少一个环路
- 环路中的参与者互相交换物品，并离开市场
- 重复以上步骤直到所有参与者离开
非完全信息博弈的实际应用
人工智能博弈的里程碑成果集中在非完全信息博弈领域：
| AI系统 | 研发机构 | 博弈类型 | 成就 |
|---|---|---|---|
| Libratus | 卡内基梅隆大学 | 两人无限注德州扑克 | 2017年击败世界顶级人类玩家 |
| Pluribus | 卡内基梅隆大学 / Facebook | 六人无限注德州扑克 | 2019年击败人类职业玩家 |
| DeepStack | 阿尔伯塔大学 | 两人无限注德州扑克 | 2017年达到职业玩家水平 |
这些系统综合运用了 CFR 算法、安全子博弈求解、蒙特卡洛采样、深度学习等技术，标志着人工智能在非完全信息博弈领域的重大突破。
小结
本章介绍了人工智能博弈的核心内容：
- 博弈论基础：博弈的要素、分类，以及核心概念纳什均衡
- 囚徒困境：经典的博弈模型，揭示了“个体理性并非总是导致集体最优”的现象
- 博弈策略求解：虚拟遗憾最小化（CFR）算法是求解大规模非完全信息博弈的关键方法，通过最小化累积遗憾使平均策略收敛到纳什均衡
- 博弈规则设计：通过设计匹配算法（如延迟接受算法、顶部交易循环算法），引导自利个体实现全局合意的结果
- 实际应用：在德州扑克等非完全信息博弈中，AI系统已达到甚至超越人类顶级玩家的水平