博弈树

博弈树 (Game Tree)

博弈树是博弈论中用于表示序贯博弈（动态博弈）的标准图形工具，属于扩展型博弈的核心组成部分。一棵博弈树由根节点出发，通过有向边连接子节点，递归地展开为树状结构，完整刻画了博弈的参与者、行动顺序、可选策略、信息结构以及每个终局的收益分配。与策略型博弈（标准式）使用收益矩阵的静态表达不同，博弈树能够捕获时序维度，使"谁在什么时候知道什么、能做什么"得以显式建模。这一工具广泛应用于经济学中的市场进入威慑、拍卖理论、委托-代理问题、国际关系中的危机谈判以及人工智能的博弈搜索算法（如极小化极大算法）。

博弈树的构成要素

一棵完整的博弈树包含以下基本元素：

• 决策节点 (Decision Node)：表示某个参与者在特定时点需要做出选择的位置。每个决策节点标注该节点的行动者。根节点为博弈的起点，通常对应第一个行动者。
• 边/分支 (Edge/Branch)：从决策节点出发的每条有向边代表该参与者在该时点可选择的一个行动。在完全博弈树中，每个决策节点的分支数量等于该时点的可行行动数。
• 终节点 (Terminal Node)：没有出边的叶节点，博弈到达该点即告结束。每个终节点标注各参与者的收益向量 $(u_1, u_2, \dots, u_n)$，其中 $u_i$ 为参与者 $i$ 的效用（通常以期望效用形式给出）。
• 信息集 (Information Set)：将某个参与者的若干决策节点用虚线连接表示该参与者在这些节点上无法区分博弈的历史——即该参与者不知道博弈究竟走到了信息集中的哪一个具体节点。信息集刻画了不完全信息的核心结构。若每个信息集只包含一个决策节点，则该博弈为完美信息博弈；否则为不完美信息博弈。
• 自然 (Nature)：对于包含随机外生事件的博弈，引入虚拟参与者"自然"（记为 $N$），在相应节点按给定概率分布选择分支。自然的引入使博弈树能建模贝叶斯博弈和随机环境。

以最简单的市场进入博弈为例：根节点标注为"潜在进入者 (Entrant)"，其两条分支为"进入"与"不进入"。若选择"不进入"，博弈直接到达终节点，在位者获得垄断利润，进入者收益为零。若选择"进入"，博弈到达在位者(Incumbent)的决策节点，在位者选择"默许"或"价格战"。两条分支分别抵达两个终节点，对应不同的收益组合。这棵博弈树直观地展示了时序、策略互动与可信承诺问题。

信息集与不完全信息

信息集是博弈树区别于普通决策树的根本特征。当博弈存在同时行动或参与者无法观测到对手先前的具体选择时，多个决策节点被划入同一信息集。例如，在经典的囚徒困境用扩展型表示时，囚徒2的两个决策节点（分别对应囚徒1选择"坦白"或"抵赖"之后）被放入同一个信息集，因为囚徒2在做出决策时不知道囚徒1的选择——这等价于两人同时行动。

信息集的引入使博弈树能够严格区分以下两种不同的信息结构：

• 完美信息 (Perfect Information)：每个信息集均为单节点集。所有参与者始终知道博弈的完整历史。泽尔腾证明：每个有限的完美信息博弈存在一个子博弈精炼纳什均衡，可通过逆向归纳法求出。
• 不完美信息 (Imperfect Information)：至少存在一个多节点信息集。参与者对博弈所处状态存在不确定性。这类博弈需借助贝叶斯纳什均衡或序贯均衡等更强的解概念进行分析。

子博弈与逆向归纳法

博弈树的子树在满足"不割裂任何信息集"的条件下构成一个子博弈。具体而言，从一个决策节点出发沿所有后继路径构成的子结构若满足：该节点自身构成一个单节点信息集，且其后所有信息集完全包含于该子树内或其外（不允许信息集被子树边界割裂），则该子树为一个子博弈。

逆向归纳法是求解有限完美信息博弈的核心算法：从最末端的决策节点开始（即直接前驱为终节点的节点），在每个决策节点选择使该行动者收益最大化的行动，然后将其替换为相应的均衡收益，递归地向上"剪枝"，直至抵达根节点。该方法确保了所得策略组合构成子博弈精炼均衡——在每个子博弈上均诱导出纳什均衡的策略组合，排除了依赖不可信威胁的均衡。

逆向归纳法的经典应用包括：

• 蜈蚣博弈 (Centipede Game)：理论上的逆向归纳解与实验观测之间出现显著偏离，揭示了参与者的有限理性和互惠偏好对理论预测的挑战。
• Stackelberg 双寡头模型：领导者先选择产量，追随者观察到后选择产量。逆向归纳法得出领导者利用先动优势获得高于古诺均衡的利润。
• 有限期重复博弈：若阶段博弈有唯一纳什均衡，则有限次重复的唯一子博弈精炼均衡是每期都玩该纳什均衡——著名的连锁店悖论即源于此，揭示了逆向归纳法在面对长期关系时的逻辑局限。

博弈树与策略型博弈的关系

任何用博弈树表示的扩展型博弈都可以等价地转化为策略型博弈（标准式），但转化通常伴随信息膨胀。在扩展型中，参与者的（纯）策略是一个完整行动方案——为该参与者在每一个信息集上指定一个可行行动。因此，即便一棵中等规模的博弈树也可能对应极其庞大的策略空间。例如，国际象棋的博弈树规模远超宇宙中的原子数，使穷举式逆向归纳法在实际中不可行。这正是博弈树搜索算法（如 $\alpha$-$\beta$ 剪枝和蒙特卡洛树搜索）成为人工智能核心技术的动因。

反过来，策略型博弈也可以扩展型化，但表示方式不唯一——不同的行动时序和信息结构可以在"诱导的策略型"层面上等价，却在均衡精炼的意义上迥异。这正是博弈树相较于标准式的最根本优势：它能捕捉时序和信息的细微差异，为均衡精炼提供结构基础。

经济学应用

博弈树在微观经济分析中的应用极为广泛。在产业组织理论中，博弈树被用于建模企业的进入-威慑、产能承诺、产品差异化与研发竞赛等序贯决策问题。在拍卖理论中，英式拍卖、荷式拍卖、一级密封拍卖和二级密封拍卖对应了不同的博弈树结构——尤其是投标者是否能观察到对手的出价决策决定了信息集的划分方式。在契约理论中，委托人与代理人之间的合同设计、最优激励方案的分析也依赖于博弈树对时序和信息不对称的精确建模。

此外，博弈树还是机制设计理论的基本工作语言。设计者在博弈树中插入规则（即改变可行分支和信息集结构），使参与者的均衡策略自发实现设计者期望的社会目标——这种"反向工程"思维的核心前提正是博弈树所提供的结构化表达框架。从VCG机制到匹配市场设计，博弈树始终是连接理论与应用的基础设施。