逆向歸納法

逆向歸納法是博弈論中一個比較古老的概念，它的提出最早可以追溯到澤梅羅（1913） 針對國際象棋有最優策略解的證明，後來人們將其推廣到了更廣泛的博弈中。例如，在有限完美信息擴展型博弈中，就是用逆向歸納法（BI）來證明子博弈完美均衡（SPE）的存在以及求解 SPE，其基本思路是從動態博弈中的最後一個階段開始，局中人都遵循效用最大化原則選擇行動，然後逐步倒推至前一個階段，一直到博弈開始局中人的行動選擇，其邏輯嚴密性毋庸置疑。然而，當從終點往前推到某一決策點時，BI 完全忽略了到達該決策點的以往歷史行動，而這一歷史行動當然會影響處於該決策點的局中人有關其對手將來如何採取行動的信念，例如，一個局中人如果觀察到對手在過去沒有按照 BI 進行行動選擇，那麼他就有理由相信他的對手仍會採取同樣的模式進行下去，但是通過這種信念修正以後所做的選擇就會與 BI矛盾。為了達到均衡解，為了能按 BI進行推理求解，我們需要對局中人的信念或者説知識增加一些限制性條件，也就是説在什麼樣的前提下，BI 是合理的，顯然，僅僅要求每個局中人都理性是不夠的，所有的局中人都必須知道所有的局中人都是理性的，所有的局中人都必須知道所有局中人都知道所有局中人都是理性的……等等以至無窮，在這樣的認知條件基礎下，我們就不會偏離 BI，即“在完美信息擴展型博弈中，理性的公共知識藴含了BI”（Aumann 1995）。 ^[1] 

在完全且完美的動態博弈中，先行為的理性博弈人，在前面階段選擇策略時，必然會考慮後行博弈人在後面階段中將會怎樣選擇策略。因而，只有在博弈的最後一個階段，不再有後續階段牽制的情況下，博弈人才能作出明智的選擇。在後面階段博弈人選擇的策略確定後，前一階段的博弈人在選擇策略時也就相對容易。

逆向歸納法的邏輯基礎：動態博弈中先行動的參與人，在前面階段選擇行為時必然會考慮後行動的參與人在後面階段中的行為選擇，只有在最後一階段的參與人才能不受其他參與人的制約而直接做出選擇。而當後面階段的參與人的選擇確定後，前一階段的參與人的行為也就容易確定了。逆向歸納法排除了不可信的威脅或承諾。 ^[2] 

1.博弈行為是順序發生的，先行動的理性的博弈方，在前面階段選擇行為時必然會考慮後行動博弈方在後面階段中將會怎樣選擇行為，只有在博弈的最後一個階段選擇的，不再有任何後續階段影響的博弈方，才能直接作出明確選擇；

2.後面的行動者在進行行動選擇前，所有以前的行為都可以被觀察到，而當後面階段博弈方的選擇確定以後，前一階段博弈方的行為也就容易確定了。

逆向歸納法是求解動態博弈的重要方法，但逆向歸納法也有明顯的侷限性。

1.首先，逆向歸納法要求博弈的結構，包括次序，規則和得益情況等都是博弈方的共同知識，各個博弈方瞭解博弈結構，相互知道對方瞭解博弈結構。即“博弈 1 知道博弈 2 知道博弈 3 知道得益函數。”顯然，博弈方越多，逆向遞推的鏈條就越長，博弈方共同知識的要求就越難滿足；

2.其次，逆向歸納法不能分析比較複雜的動態博弈。由於逆向歸納法的推理方法是從動態博弈的最後階段開始對每種可能路徑進行比較，這對博弈者的理性提出了很高的要求，博弈者不能有哪怕是絲毫的對理性偏離的行為，博弈者必須有能力比較判斷的選擇路徑數量，包括數量不很大的離散策略，或者有連續得益函數的連續分佈策略，而這往往是不可能的；

3.最後，在遇到不同的路徑有相同利益的情況時逆向歸納法也會發生選擇困難。因為此時博弈方遇到了無差異行為，無法確定唯一的最優路徑，逆向歸納法適用性會在這裏失效。

逆向歸納法的精髓就是“向前展望，向後推理”，即首先仔細思考自己的決策可能引起的所有後續反應，以及後續反應的後續反應，直至博弈結束；然後從最後一步開始，逐步倒推，以此找出自己在每一步的最優選擇。因為博弈是有限的，博弈樹上一定存在一個最後的決策結的集合。（即倒數第二個結，它的直接後續結是終點結），在該決策結上行動的參與人將選擇一個最大化自己的支付的行動；給定這個參與人的選擇，倒數第二個決策結上的參與人將選擇一個可行的行動最大化自己的支付……如此等等，直到初始結。當這個倒推過程完成時，我們得到一個路徑，該路徑為每一個參與人給出一個特定的戰略，所有這些戰略構成一個納什均衡。

總結逆向歸納法實質上是各階段動態規劃的庫恩算法，把一個多階段動態規劃問題“分解”為一個個單階段的優化問題，通過求解每一個單階段的最優化，來得到整體規劃的最優化。同樣，在動態博弈中，逆向歸納法也就是把多階段動態博弈化為一系列的單人博弈，通過對一系列的單人博弈的分析，確認各博弈方在各自選擇階段的選擇，最後對動態博弈結果，包括博弈的路徑和各博弈方的得益做出判斷，歸納各個博弈方各階段的選擇則可得到各個博弈方在整個動態博弈中的策略。