game tree

博弈树 (Game Tree)

博弈树（Game Tree）是展开型博弈（Extensive Form Game）的图形与数学表示，以有根树（Rooted Tree）结构刻画序贯决策中参与人的行动顺序、可选行动以及最终结果。在博弈论中，博弈树是展开型博弈的直观载体——一切关于信息集、策略、均衡的分析均在树结构上展开。博弈树的概念由冯·诺依曼与摩根斯坦在《博弈论与经济行为》（1944）中系统引入，后经Kuhn（1953）关于展开型博弈的严格形式化而成为标准工具。

博弈树的数学结构

博弈树由以下要素构成：

1. 节点（Nodes）：分为决策节点（Decision Nodes）与终节点（Terminal Nodes）。决策节点标注当前行动的参与人；终节点标注支付向量 $(u_1, u_2, \dots, u_n)$。树的根节点（Root）对应博弈的初始历史——空历史 $\emptyset$。
2. 边（Edges/Branches）：每条有向边从一个决策节点出发，对应该参与人在该时点的一个可行行动。
3. 路径（Path）：从根到任一终节点的行动序列构成一条博弈路径（Play），每条路径唯一确定一个博弈结果。
4. 信息集（Information Sets）：将属于同一参与人且该参与人无法区分的决策节点划分在同一信息集内。在博弈树图示中，同一信息集的节点以虚线连接（或圆圈框出）。

博弈树是有限的当且仅当节点数有限，是有限深度的当且仅当最长路径长度有限。大多数经济应用中的博弈树同时满足两者。

完美回忆与博弈树

博弈树的一个重要性质是完美回忆（Perfect Recall）：参与人永不遗忘自己过去知道的信息或采取过的行动。在博弈树上，完美回忆等价于：若两个决策节点属于同一信息集，则它们到各自根节点的路径上，该参与人的行动序列必须一致。具有完美回忆的博弈树保证了Kuhn定理的成立——混合策略与行为策略等价，极大地简化了均衡分析。

反向归纳法与树搜索

博弈树最为经典的分析方法是反向归纳法（Backward Induction）：从终节点出发，自底向上逐层求解最优行动。算法如下：(1) 选取一个所有后继均为终节点的决策节点；(2) 比较各行动对应的支付，选择最大化当前参与人支付者；(3) 将该节点的支付替换为最优行动的支付向量，删除其子树；(4) 重复直至到达根节点。对于完美信息博弈（所有信息集均为单点），反向归纳法产生唯一的子博弈完美纳什均衡（SPNE）。Zermelo定理（1913）是反向归纳法的先驱：任何有限完美信息零和博弈中，要么一方有必胜策略，要么双方均能保证平局——该定理本质上断言了博弈树的可决定性（Decidability）。

反向归纳实际上是对博弈树的深度优先搜索（DFS）与极小极大算法（Minimax）的特例：在零和博弈中，一参与人最大化支付而对手最小化该支付，博弈树搜索退化为经典的极小极大回溯。更深层地，博弈树的复杂度随深度呈指数增长——若每个节点有 $b$ 个分支、树深为 $d$，则终节点数为 $O(b^d)$，这直接导致了棋类博弈中剪枝算法的需求。Alpha-Beta剪枝利用已搜索子树的信息排除不可能成为最优的分支，将有效分支因子降至约 $\sqrt{b}$，在最优情况下搜索节点数减至 $O(b^{d/2})$，是博弈树计算的核心突破。

反向归纳法的一个深刻困难在于其对共同知识（Common Knowledge）的强依赖：每个参与人必须相信所有参与人在每一个后续节点上均采取理性行动。在长博弈中，这一假设链极其脆弱——蜈蚣博弈（Centipede Game）以实验证据揭示了实际行为系统性地偏离反向归纳预测，推动了行为博弈论对有限理性与社会偏好的研究。

博弈树与决策树的区别

博弈树与决策树（Decision Tree）虽结构相似，但存在本质区别。决策树中仅存在单一决策者面对自然环境（以概率分布刻画），分支代表随机结果而非对手策略选择。博弈树则包含多个策略性互动的参与人，每个参与人的最优决策依赖于对其他参与人行为的信念。这一区别使博弈树的均衡分析——而非单纯的期望值最大化——成为核心议题。

信息集对树结构的影响

信息集在博弈树上形成划分（Partition）：每个参与人的决策节点被分割为若干信息集，同一信息集内的节点必须具有相同的可选行动集（否则参与人可通过行动集区分节点）。信息集切断了博弈树的局部可分解性：若存在非单点信息集，则无法从该信息集开始定义子博弈（子博弈要求起始节点为单点信息集），从而限制了反向归纳法的直接适用。这正是不完美信息博弈需要更复杂的解概念（如序贯均衡、完美贝叶斯均衡）的原因。

子博弈与子树结构

博弈树上的子博弈（Subgame）在结构上对应于树的子树，但附加了严格条件：子博弈的起始节点必须是单点信息集，且子博弈不得切割任何信息集。这一要求保证了子博弈自身构成一个良定义的独立博弈——参与人在子博弈中的推理不受外部信息干扰。从树结构角度看，子博弈完美纳什均衡要求均衡策略在每个这样的子博弈子树中均构成纳什均衡，从而修剪掉依赖不可信威胁的非均衡路径。

对于不完美信息博弈，非单点信息集的存在意味着博弈树上并非每个节点都能作为子博弈的起点。这催生了更精细的解概念：序贯均衡（Sequential Equilibrium）要求在每个信息集上——即便该信息集不在任何子博弈中——参与人的策略也必须相对于某个信念（Belief）系统是序贯理性的。

计算与应用

博弈树广泛存在于经济学、计算机科学和运筹学中。在产业组织中，企业进入-威慑博弈的博弈树刻画先动者优势——斯塔克尔伯格模型的领导者-跟随者结构直接对应两层博弈树。在拍卖理论中，英式拍卖的升价过程、荷式拍卖的降价过程以及多轮密封拍卖均自然形成博弈树。在政治经济学中，议程设置模型将立法博弈建模为投票者依次对修正案表决的博弈树，最终通过者成为政策结果。

在人工智能领域，围棋、国际象棋等完全信息博弈的状态空间即为巨大的博弈树。围棋的博弈树分支因子约 $250$、深度约 $150$，全树节点数远超宇宙原子数。蒙特卡洛树搜索（MCTS）是应对这一复杂度的方法论突破：MCTS不尝试穷举搜索，而是通过四个步骤——选择（Selection）、扩展（Expansion）、模拟（Simulation）、回溯（Backpropagation）——在博弈树上进行非对称的智能探索。AlphaGo将MCTS与深度神经网络结合，以策略网络指导搜索方向、以价值网络评估叶节点，在围棋博弈树上实现了超越人类顶尖水平的决策。

博弈树亦是机制设计中的基本语言：设计者通过调整博弈树的规则——可行行动集、信息结构与支付函数——来诱导参与人如实报告私人信息。显示原理（Revelation Principle）保证任何均衡结果均可由一个直接机制实现，其博弈树简化为参与人同时报告类型、设计者执行分配规则的二阶段结构，极大地压缩了博弈树的分析空间。