逆向归纳法

逆向归纳法是求解动态博弈均衡的方法

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

逆向归纳法是求解动态博弈均衡的方法。所谓动态博弈是指博弈参与人的行动存在着先后次序，并且后行动的参与人能够观察到前面的行动。逆向归纳法在逻辑上是严密的，然而它存在着“困境”。所谓逆向归纳法是从动态博弈的最后一步往回推，以求解动态博弈的均衡结果。逆向归纳法又称逆推法。它是完全归纳推理，其推理是演绎的，即结论是必然的。 在完全且完美的动态博弈中，先行为的理性博弈人，在前面阶段选择策略时，必然会考虑后行博弈人在后面阶段中将会怎样选择策略。因而，只有在博弈的最后一个阶段，不再有后续阶段牵制的情况下，博弈人才能作出明智的选择。在后面阶段博弈人选择的策略确定后，前一阶段的博弈人在选择策略时也就相对容易。

逆向归纳法就是从动态博弈的最后一个阶段开始分析，逐步向前归纳出各阶段博弈人的选择策略。

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

逆向归纳法：它的精髓就是“向前展望，向后推理”，即首先仔细思考自己的决策可能引起的所有后续反应，以及后续反应的后续反应，直至博弈结束；然后从最后一步开始，逐步倒推，以此找出自己在每一步的最优选择。

图1的求解过程如下：

若2在右，2将选择进；∵＞
若2在左，2将选择退；∵＞
在2的选择中1的最大收益是选择进；∵＞
∴纳什均衡为）均衡解为，均衡收益为

逆向归纳法仅适合有限步动态博弈，而且要求决策者犯的可能性很小。

如果使用逆向归纳法得到的结果是A选择右边的行动，双方各得3。

如果A在第一步选择下边的行动，B该做何想？只有当A在第二步犯错误的可能性小于1/11时，B才有胆量选择让游戏继续玩下去。于是A极有可能获得10这个最大回报。