逆向归纳法

逆向归纳法(backward induction)，是求解动态博弈均衡的方法，是博弈论中一个比较古老的概念，是指博弈参与人的行动存在着先后次序，并且后行动的参与人能够观察到前面的行动。

历史逆向归纳法是博弈论中一个比较古老的概念，它的提出最早可以追溯到泽梅罗（1913） 针对国际象棋有最优策略解的证明，后来人们将其推广到了更广泛的博弈中。例如，在有限完美信息扩展型博弈中，就是用逆向归纳法（BI）来证明子博弈完美均衡（SPE）的存在以及求解 SPE，其基本思路是从动态博弈中的最后一个阶段开始，局中人都遵循效用最大化原则选择行动，然后逐步倒推至前一个阶段，一直到博弈开始局中人的行动选择，其逻辑严密性毋庸置疑。然而，当从终点往前推到某一决策点时，BI 完全忽略了到达该决策点的以往历史行动，而这一历史行动当然会影响处于该决策点的局中人有关其对手将来如何采取行动的信念，例如，一个局中人如果观察到对手在过去没有按照 BI 进行行动选择，那么他就有理由相信他的对手仍会采取同样的模式进行下去，但是通过这种信念修正以后所做的选择就会与 BI矛盾。为了达到均衡解，为了能按 BI进行推理求解，我们需要对局中人的信念或者说知识增加一些限制性条件，也就是说在什么样的前提下，BI 是合理的，显然，仅仅要求每个局中人都理性是不够的，所有的局中人都必须知道所有的局中人都是理性的，所有的局中人都必须知道所有局中人都知道所有局中人都是理性的……等等以至无穷，在这样的认知条件基础下，我们就不会偏离 BI，即“在完美信息扩展型博弈中，理性的公共知识蕴含了BI”（Aumann 1995）。1

认知基础在完全且完美的动态博弈中，先行为的理性博弈人，在前面阶段选择策略时，必然会考虑后行博弈人在后面阶段中将会怎样选择策略。因而，只有在博弈的最后一个阶段，不再有后续阶段牵制的情况下，博弈人才能作出明智的选择。在后面阶段博弈人选择的策略确定后，前一阶段的博弈人在选择策略时也就相对容易。

逆向归纳法的逻辑基础：动态博弈中先行动的参与人，在前面阶段选择行为时必然会考虑后行动的参与人在后面阶段中的行为选择，只有在最后一阶段的参与人才能不受其他参与人的制约而直接做出选择。而当后面阶段的参与人的选择确定后，前一阶段的参与人的行为也就容易确定了。逆向归纳法排除了不可信的威胁或承诺。2

特征博弈行为是顺序发生的，先行动的理性的博弈方，在前面阶段选择行为时必然会考虑后行动博弈方在后面阶段中将会怎样选择行为，只有在博弈的最后一个阶段选择的，不再有任何后续阶段影响的博弈方，才能直接作出明确选择；

后面的行动者在进行行动选择前，所有以前的行为都可以被观察到，而当后面阶段博弈方的选择确定以后，前一阶段博弈方的行为也就容易确定了。2

局限逆向归纳法是求解动态博弈的重要方法，但逆向归纳法也有明显的局限性。

首先，逆向归纳法要求博弈的结构，包括次序，规则和得益情况等都是博弈方的共同知识，各个博弈方了解博弈结构，相互知道对方了解博弈结构。即“博弈 1 知道博弈 2 知道博弈 3 知道得益函数。”显然，博弈方越多，逆向递推的链条就越长，博弈方共同知识的要求就越难满足；

其次，逆向归纳法不能分析比较复杂的动态博弈。由于逆向归纳法的推理方法是从动态博弈的最后阶段开始对每种可能路径进行比较，这对博弈者的理性提出了很高的要求，博弈者不能有哪怕是丝毫的对理性偏离的行为，博弈者必须有能力比较判断的选择路径数量，包括数量不很大的离散策略，或者有连续得益函数的连续分布策略，而这往往是不可能的；

最后，在遇到不同的路径有相同利益的情况时逆向归纳法也会发生选择困难。因为此时博弈方遇到了无差异行为，无法确定唯一的最优路径，逆向归纳法适用性会在这里失效。3

运用逆向归纳法的精髓就是“向前展望，向后推理”，即首先仔细思考自己的决策可能引起的所有后续反应，以及后续反应的后续反应，直至博弈结束；然后从最后一步开始，逐步倒推，以此找出自己在每一步的最优选择。因为博弈是有限的，博弈树上一定存在一个最后的决策结的集合。(即倒数第二个结，它的直接后续结是终点结)，在该决策结上行动的参与人将选择一个最大化自己的支付的行动；给定这个参与人的选择，倒数第二个决策结上的参与人将选择一个可行的行动最大化自己的支付……如此等等，直到初始结。当这个倒推过程完成时，我们得到一个路径，该路径为每一个参与人给出一个特定的战略，所有这些战略构成一个纳什均衡。

总结逆向归纳法实质上是各阶段动态规划的库恩算法，把一个多阶段动态规划问题“分解”为一个个单阶段的优化问题，通过求解每一个单阶段的最优化，来得到整体规划的最优化。同样，在动态博弈中，逆向归纳法也就是把多阶段动态博弈化为一系列的单人博弈，通过对一系列的单人博弈的分析，确认各博弈方在各自选择阶段的选择，最后对动态博弈结果，包括博弈的路径和各博弈方的得益做出判断，归纳各个博弈方各阶段的选择则可得到各个博弈方在整个动态博弈中的策略。1

本词条内容贡献者为:

孙和军 - 副教授 - 南京理工大学