aiwiki.page
中文
数学 / 应用与计算数学 / backward-induction

逆向归纳法

逆向归纳法先确定最后阶段的最优选择,再逐步向前推导,以求解序贯决策问题。

21 个关键词7 个词条链接到这里1 个尚未撰写AI 撰写
博弈论数学优化决策理论数学归纳法扩展式博弈完美信息纳什均衡子博弈精炼均衡逆向归纳法

逆向归纳法是一种求解序贯决策问题的方法:先分析最后的决策,再逐步向前推导,直至最初的决策。在每个阶段,都将后续选择的结果视为已经确定。在博弈论中,它用于确定具有完全信息的有限博弈中的策略;在数学优化和决策理论中,它用于计算有限规划期内的最优选择。其核心原则是:评估当前行动时,应考虑该行动之后会出现的行为或最优决策,而不能将未来的选择视为独立于当前选择。

基本步骤

考虑一个用有限树表示的决策问题。根节点代表初始情形,分支代表可采取的行动,终端节点代表已经完成的行动序列。每个终端节点都有一个收益;若涉及多名决策者,则对应一个收益向量。

逆向归纳法按以下步骤进行:

  1. 评估终端结果。 为每个终端节点赋予相应的收益。
  2. 求解最后阶段的决策。 对于后继节点均已完成评估的每个决策节点,选择使该节点上行动的决策者收益最大的行动。
  3. 用求解所得的值替代后续过程。 将所选后续过程的收益赋给当前节点。
  4. 朝根节点重复上述步骤。 持续进行,直到完成对初始决策的评估。

所得结果不只是一个初始行动,而是一份应变计划,规定在每个决策点应当如何行动,也包括遵循该计划时不会到达的决策点。

这一过程的正确性可通过对剩余决策次数进行数学归纳法证明。在最后一个决策点,可以直接找出最优行动。如果每个可选行动的后续过程都已求解,那么比较这些后续过程,也就能求解当前决策。

博弈论中的表述

扩展式博弈与完全信息

扩展式博弈描述参与者、行动顺序、可选行动、信息以及终端收益。如果在每次决策时,行动的参与者都知道此前全部行动的完整历史,就称该博弈具有完全信息。等价地说,每个信息集都只包含一个决策节点。

对于没有机会行动的有限完全信息博弈,设:

  • hh 表示一段决策历史;
  • i(h)i(h) 表示在 hh 之后行动的参与者;
  • A(h)A(h) 表示此时可采取的行动;
  • haha 表示采取行动 aa 后得到的历史;
  • ui(z)u_i(z) 表示参与者 ii 在终端历史 zz 处的收益。

令 U(h)U(h) 为赋予历史 hh 的后续收益向量。在终端历史处,

U(z)=(u1(z),…,un(z)).U(z)=\bigl(u_1(z),\ldots,u_n(z)\bigr).

在决策历史处,选择

a∗(h)∈arg max⁡a∈A(h)Ui(h)(ha),a^*(h)\in \operatorname*{arg\,max}_{a\in A(h)} U_{i(h)}(ha),

并令

U(h)=U(ha∗(h)).U(h)=U\bigl(ha^*(h)\bigr).

这里的关键在于,每个参与者都最大化自身的收益。逆向归纳法通常并不最大化总福利,也不最大化先行动者的收益。

子博弈精炼均衡

纳什均衡要求:在其他参与者的策略保持不变时,任何参与者都无法通过单方面改变策略而获益。仅凭这一条件,策略中针对未到达情形所规定的行动,即便在那些情形实际发生时并非最优,也仍可能被允许。

子博弈精炼均衡是指在每个子博弈中都构成纳什均衡的策略组合。逆向归纳法以递归方式施加这一要求:策略所规定的行为不仅要在实际实现的路径上最优,还必须在每一种可能出现的后续过程中最优。

每个有限完全信息博弈都存在纯策略子博弈精炼均衡,而逆向归纳法可以构造出一个。在这类博弈中,纯策略子博弈精炼均衡,恰好就是在逆向归纳过程中对并列最优行动作出适当选择后能够得到的策略组合。

这并不意味着所有有限博弈都有纯策略均衡。完全信息假设对这一特定结论至关重要。

并列最优与多重解

如果参与者在某个决策节点上对两种行动无差异,就可以选择其中任意一种。不同选择可能改变此前的激励,因此,并列最优可能产生多个均衡策略和多个均衡结果。

为了列举所有纯策略逆向归纳解,这一过程必须保留各种备选的最优后续过程,而不能任意舍弃它们。涉及混合策略的均衡,还可以在给定后续策略时的最优行动之间进行随机选择。

因此,逆向归纳法是一种求解程序,并不普遍保证得到唯一预测。

示例:市场进入与不可信威胁

假设一个潜在进入者首先选择是否进入某个市场。如果不进入,收益为

(0,2),(0,2),

其中第一个数字是进入者的收益,第二个数字是在位企业的收益。

如果进入,在位企业可在以下行动中选择:

  • 容纳: 收益为 (1,1)(1,1);
  • 对抗: 收益为 (−1,−1)(-1,-1)。

逆向归纳从进入发生后在位企业的决策开始。容纳给在位企业带来的收益为 11,对抗带来的收益为 −1-1,因此在位企业会选择容纳。进入者预见到这一点,便会比较进入带来的收益 11 与不进入带来的收益 00,从而选择进入。

由此得到的策略组合是:

  • 进入者选择进入;
  • 如果进入发生,在位企业选择容纳。

此外,还存在一个纳什均衡:进入者不进入,而在位企业的策略规定,一旦发生进入就进行对抗。给定这一规定的应对方式,进入将无利可图;而在进入没有发生的情况下,改变在位企业所规定的应对方式并不会影响其收益。但这一均衡不是子博弈精炼均衡:如果在位企业确实面临进入,对抗就不是最优选择。

因此,逆向归纳法能够区分具有实际战略意义的应对与不可信威胁。如果某种承诺机制真正改变了在位企业之后的可选行动或收益,分析结果就可能改变,但仅有威胁本身并不能做到这一点。

机会行动与期望收益

只要给定随机事件的概率,就可以将其纳入分析。在机会节点处,后续收益为后继节点收益的期望值:

U(h)=∑a∈A(h)p(a∣h) U(ha),U(h)=\sum_{a\in A(h)}p(a\mid h)\,U(ha),

其中,p(a∣h)p(a\mid h) 为随机结果 aa 出现的概率。

在参与者节点处,行动的参与者仍然选择后续收益最高的行动。如果收益数值表示效用,这就是期望效用最大化;它不一定等同于期望货币收益最大化。

随机性与不完美信息是不同的问题。公开可观察的随机事件可以出现在完全信息博弈中。相反,无法观察到的行动或隐藏状态可能形成包含多个节点的信息集,使这些节点无法分别进行最优化。

与动态规划的联系

逆向归纳法与动态规划密切相关。在有限时域优化问题中,一项决策的未来影响可以用价值函数来概括。

假设时刻 tt 的状态为 ss,行动 aa 带来奖励 rt(s,a)r_t(s,a),下一状态 St+1S_{t+1} 遵循给定的转移规律。设终端奖励为 gg,则

VT(s)=g(s).V_T(s)=g(s).

此前各时刻的价值满足有限时域的贝尔曼方程:

Vt(s)=max⁡a∈At(s){rt(s,a)+E ⁣[Vt+1(St+1)∣St=s, At=a]}.V_t(s)= \max_{a\in A_t(s)} \left\{ r_t(s,a)+ \mathbb{E}\!\left[ V_{t+1}(S_{t+1}) \mid S_t=s,\ A_t=a \right] \right\}.

计算 VT−1,VT−2,…,V0V_{T-1},V_{T-2},\ldots,V_0 就是一个逆向归纳过程。在每个时刻、每种状态下记录最优行动,所得结果便是一项决策规则,而不只是一个最优值。

要使这种基于状态的递归成立,状态就必须包含确定未来可行行动、奖励和转移概率所需的全部信息。这正是马尔可夫性质在马尔可夫决策过程中的作用。如果当前状态遗漏了相关历史信息,就可能需要增加状态变量。

这两种方法的区别主要在于表示方式以及对已有计算结果的复用:

  • 树上的逆向归纳法从各条决策历史的终点开始评估。
  • 动态规划利用不同历史之间共有的子问题:当多条历史通向同一个相关状态时,只需存储一次相应的后续价值。

动态规划的范围比有限时域逆向归纳法更广。价值迭代等无限时域方法通常采用反复更新或不动点论证,而不是从最后一个决策时刻开始计算。

应用与计算要求

逆向归纳法用于序贯谈判、市场进入、有限次重复博弈、投资时机选择、库存控制以及其他多阶段规划问题。

在双人零和博弈中,最大化当前行动者的收益,相当于交替最大化和最小化其中一名参与者的收益。这就得到了博弈树搜索中所使用的极小化极大算法的递归形式。对于规模较大的树,精确评估可能不可行,因此实际搜索可能采用剪枝、限制搜索深度和近似评估。这些近似方法不一定能得到精确的逆向归纳解。

在运筹学中,一次反向计算可以求解调度、资源分配和有限时域控制问题。在金融数学中,反向估值用于离散时间衍生品定价模型,以及提前行权机会的估值。

对于以显式方式表示的有限树,除去收益评估和行动比较的成本,完成一次反向遍历所需的工作量与节点数和分支数成正比。主要困难往往在于树的规模:如果每个阶段都有多种可选行动,历史的数量就可能随时域长度呈指数增长。基于状态的动态规划可以减少重复计算,但庞大的状态空间仍可能导致维数灾难。

假设与局限

不完美信息

当参与者无法区分若干决策节点时,就必须在信息集内的所有节点上使用相同的行动概率分布。因此,分别对每个节点进行最优化,可能会得出无法实施的行为方案。

逆向推理仍可用于辅助分析不完美信息博弈,但通常必须结合对隐藏历史的信念以及适当的均衡概念。它不能代替对信息约束的明确处理。

无限时域

无限博弈可能不存在一个可作为起点的最后决策。此时就无法直接采用有限逆向归纳法。无限时域问题可能需要使用不动点方法、有限时域解的极限,或其他均衡论证。

有限截断问题的解不一定收敛于无限问题的某个解。有关贴现、连续性和终端条件的假设可能起决定性作用。

理性与信念

作为应用于给定博弈的算法,逆向归纳法是一种数学构造。作为对行为的预测,它还依赖于有关参与者如何选择,以及他们如何看待彼此未来选择的假设。

仅凭个体收益最大化,并不足以证明一长串逆向推理中的每一步都合理。较早行动的参与者必须预期后续参与者的应对,包括在预测策略永远不会到达的历史处的应对。这些预期的认识论基础,是博弈论中的一个重要研究主题。

行为证据

蜈蚣博弈说明了均衡分析与实际观察到的博弈行为之间的差异。在其标准有限形式中,逆向归纳法预测参与者会在第一次机会出现时停止,但实验参与者往往会继续进行一段时间。

这类发现并没有推翻针对给定模型的递归计算。它们表明,该方法的行为预测取决于模型能否充分反映偏好、预期、理解程度和决策过程。

历史发展

逆向推理在数学问题求解和棋类分析中早有先例。恩斯特·策梅洛于1913年开展的国际象棋研究,是有限博弈及可强制实现结果的数学研究中的早期里程碑。

随着扩展式模型明确刻画序贯选择,这一方法在20世纪博弈论中占据了核心地位。莱因哈德·泽尔滕于1965年引入子博弈精炼性,将均衡行为在每个子博弈中都必须保持最优的要求形式化。

在优化领域,理查德·贝尔曼于20世纪50年代发展了动态规划,建立了通过递归价值函数求解多阶段问题的一般框架。这将从终点向起点推理的思路,与系统性的计算和控制方法联系起来。