《博弈论：原理、模型与教程》第章子博弈精炼Nash均衡第节子博弈精炼Nash均衡的求解.docVIP

《博弈论：原理、模型与教程》 第二部分 完全信息动态博弈 第7章 子博弈精炼Nash均衡 7.2 子博弈精炼Nash均衡的求解（重点！） （已精细订正！） 定义7－1虽然给出了子博弈精炼Nash的定义，但没有说明如何求解子博弈精炼均Nash衡。 下面以图6－8 中扩展式博弈为例，介绍一种最常用的求解子博弈精炼Nash均衡的方法—逆向归纳法。 （讲！） 考察图6－8中的博弈。参与人1在博弈开始时（即在信息集上面临两种选择—行动和行动。参与人1此时选择哪种行动呢？对于理性的参与人1来讲，只会选择使自己支付最大化的行动。从图6－8很容易知道参与人1选择行动时所得到的支付为；但是，如果参与人1选择行动，则所得支付就要取决于参与人2在信息集上的选择，以及博弈达到决策结时参与人1在信息集上的选择。也就是说，参与人1选择行动所得支付，取决于子博弈的结果。因此，为了确定参与人1在博弈开始时的选择，就必须确定参与人1选择行动的所得支付，而为了确定参与人1选择行动的所得支付，就必须先求解子博弈。如何求解博弈呢？可以采用同样的方法来求解子博弈，即在求解子博弈的基础上，确定参与人2在信息集上的选择，从而求解子博弈。 由以上分析可以得到图6－8中博弈的求解过程： 首先求解博弈树中最底层的子博弈得到子博弈的结果为（即参与人1选择）； 再求解博弈，容易得到博弈的结果（即参与人2选择）； 最后求解原博弈，即子博弈，得到博弈的结果为（即参与人1选择）。 （讲！） 考察更一般的情形。对于图7－6中的博弈树，参与人在信息集 选择行动还是行动，取决于选择行动和行动所带来的后果。由于参与人选择行动时使博弈进入了子博弈，因此参与人选择行动的后果就是得到子博弈。同样，参与人选择行动的后果就是得到子博弈。所以，参与人在信息集上的最优选择，取决于参与人在信息集上可能采取的行动，所导致的各个子博弈。也就是说，参与人在信息集上的最优选择，一定是使博弈进入能给自己带来最大支付的子博弈。因此，为了确定参与人在信息集上的选择，就必须先求解参与人在信息集上可能采取的行动所导致的各个子博弈。而对于各个子博弈求解又可以采用同样方法进行。 图7－6 一般情形的博弈树 由以上分析可以得到求解有限扩展式博弈的一般步骤： (找出博弈的所有子博弈。 (按照博弈进行的“反方向”逐一求解各个子博弈，即最先求解最底层子博弈，再求解上一层的子博弈，……，直至原博弈。也就是说，在求解每一个子博弈时，该子博弈要么不含有其他任何子博弈，要么所含子博弈都已被求解。 上述求解有限扩展式的方法亦称“逆向归纳法”（backward induction）。由于逆向归纳法对各个子博弈逐一进行求解，因此逆向归纳法所得到的解在各个子博弈上构成均衡。这也意味着逆向归纳法所得的解为子博弈精炼Nash均衡。 （重点，讲！） 【例7-2】 考察如图7－7所以的扩展式博弈。图7－7中，博弈存在5个子博弈，即子博弈 、、、和（即原博弈），其中、和为最底层的子博弈。 下面利用逆向归纳法求解博弈的子博弈精炼Nash均衡。 图7－7 逆向归纳法求解扩展式博弈 (求解最底层的子博弈—子博弈、和。子博弈的结果为（即参与人2选择），子博弈的结果为（即参与人1选择），子博弈的结果为（即参与人选择）。 (求解上一层的子博弈。由于的上一层子博弈含有尚未求解的子博弈,因此此时不能直接求解博弈。和的上一层子博弈为,而所含的子博弈（即和都已求解，所以此时可以求解子博弈。求解，可得博弈的结果。Nash均衡为（即参与人1选择，参与人2选择）。 (由于（即原博弈）所含子博弈都已求解，因此可以求解。求解，可得博弈的结果为，Nash均衡为。 由于在各个子博弈上都构成Nash均衡，因此即为如图7－7所示扩展式博弈的子博弈精炼Nash均衡。 （讲！） 从逆向归纳法求解子博弈精炼Nash均衡的过程可以看到：在求解任一子博弈时，参与人在该子博弈的初始决策结上的选择，对余下的博弈进程而言是最优的。例如，在图7－6中，当求解子博弈时，参与人在信息集上的选择，是使博弈进入能给自己带来最大支付的子博弈。因此，从这个意义上讲，应用逆向归纳法所得到的博弈的解—子博弈精炼Nash 均衡，在一定程度满足动态规划的最优原理。 （讲！） 逆向归纳法对于完美信息（perfert information）的博弈问题尤为适用。所谓完美信息的博弈，是指每个参与人决策时都没有不确定性，也就是说，在博弈树中每个参与人的信息集都是单决策结的。例如，图6－1 图6－5 图6－6 图6－8 图7－3及图7－7所示的扩展使都是完美信息的，而图6－2 图6－3 图6－4中的扩展使