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

博弈论：原理、模型与教程第二部分 完全信息动态博弈第7章 子博弈精炼Nash均衡7.2 子博弈精炼Nash均衡的求解（重点！）（已精细订正！）定义71虽然给出了子博弈精炼Nash的定义，但没有说明如何求解子博弈精炼均Nash衡。下面以图68 中扩展式博弈为例，介绍一种最常用的求解子博弈精炼Nash均衡的方法逆向归纳法。（讲！）2，116121，11，213，0图6-8 博弈树 考察图68中的博弈。参与人1在博弈开始时（即在信息集上面临两种选择行动和行动。参与人1此时选择哪种行动呢？对于理性的参与人1来讲，只会选择使自己支付最大化的行动。从图68很容易知道参与人1选择行动时所得到的支付为；但是，如果参与人1选择行动，则所得支付就要取决于参与人2在信息集上的选择，以及博弈达到决策结时参与人1在信息集上的选择。也就是说，参与人1选择行动所得支付，取决于子博弈的结果。因此，为了确定参与人1在博弈开始时的选择，就必须确定参与人1选择行动的所得支付，而为了确定参与人1选择行动的所得支付，就必须先求解子博弈。如何求解博弈呢？可以采用同样的方法来求解子博弈，即在求解子博弈的基础上，确定参与人2在信息集上的选择，从而求解子博弈。由以上分析可以得到图68中博弈的求解过程：首先求解博弈树中最底层的子博弈得到子博弈的结果为（即参与人1选择）；再求解博弈，容易得到博弈的结果（即参与人2选择）；最后求解原博弈，即子博弈，得到博弈的结果为（即参与人1选择）。 （讲！） 考察更一般的情形。对于图76中的博弈树，参与人在信息集 选择行动还是行动，取决于选择行动和行动所带来的后果。由于参与人选择行动时使博弈进入了子博弈，因此参与人选择行动的后果就是得到子博弈。同样，参与人选择行动的后果就是得到子博弈。所以，参与人在信息集上的最优选择，取决于参与人在信息集上可能采取的行动，所导致的各个子博弈。也就是说，参与人在信息集上的最优选择，一定是使博弈进入能给自己带来最大支付的子博弈。因此，为了确定参与人在信息集上的选择，就必须先求解参与人在信息集上可能采取的行动所导致的各个子博弈。而对于各个子博弈求解又可以采用同样方法进行。图76 一般情形的博弈树由以上分析可以得到求解有限扩展式博弈的一般步骤：找出博弈的所有子博弈 由于原博弈为有限扩展式博弈，因此博弈的子博弈有限。按照博弈进行的“反方向”逐一求解各个子博弈，即最先求解最底层子博弈，再求解上一层的子博弈，直至原博弈。也就是说，在求解每一个子博弈时，该子博弈要么不含有其他任何子博弈，要么所含子博弈都已被求解。 上述求解有限扩展式的方法亦称“逆向归纳法”（backward induction）。由于逆向归纳法对各个子博弈逐一进行求解，因此逆向归纳法所得到的解在各个子博弈上构成均衡。这也意味着逆向归纳法所得的解为子博弈精炼Nash均衡。（重点，讲！）【例7-2】 考察如图77所以的扩展式博弈。图77中，博弈存在5个子博弈，即子博弈 、和（即原博弈），其中、和为最底层的子博弈。下面利用逆向归纳法求解博弈的子博弈精炼Nash均衡。5, 1, , , 1,12, 31图77 逆向归纳法求解扩展式博弈求解最底层的子博弈子博弈、和。子博弈的结果为（即参与人2选择），子博弈的结果为（即参与人1选择），子博弈的结果为（即参与人选择）。求解上一层的子博弈。由于的上一层子博弈含有尚未求解的子博弈,因此此时不能直接求解博弈。和的上一层子博弈为,而所含的子博弈（即和都已求解，所以此时可以求解子博弈。求解，可得博弈的结果。Nash均衡为 在子博弈的Nash 均衡中，为参与人1的战略，表示参与人1在信息集选择，在信息集选择;为参与人2的战略。（即参与人1选择，参与人2选择）。由于（即原博弈）所含子博弈都已求解，因此可以求解。求解，可得博弈的结果为，Nash均衡为 在Nash均衡中，为参与人1的战略，表示参与人1在信息集选择，在信息集)选择；在信息集选择；为参与人2的战略，表示参与人2在信息集选择，在信息集选择。由于在各个子博弈上都构成Nash均衡，因此即为如图77所示扩展式博弈的子博弈精炼Nash均衡。（讲！）从逆向归纳法求解子博弈精炼Nash均衡的过程可以看到：在求解任一子博弈时，参与人在该子博弈的初始决策结上的选择，对余下的博弈进程而言是最优的。例如，在图76中，当求解子博弈时，参与人在信息集上的选择，是使博弈进入能给自己带来最大支付的子博弈。因此，从这个意义上讲，应用逆向归纳法所得到的博弈的解子博弈精炼Nash 均衡，在一定程度满足动态规划的最优原理 动态规划的最优性原理是指“作为整个过程的最优战略具有这样的性质：无论过去的状态和决策如何，对前面的状态和决策所形成的状态而言，余下的诸决策必须构成最优策略”。简言之，一个最优战略的子战略总是最优战略。（讲！）逆向归纳法对于完美信息（perfert information）的博弈问题尤为适用。所谓完美信息的博弈，是指每个参与人决策时都没有不确定性，也就是说，在博弈树中每个参与人的信息集都是单决策结的 注意完美信息与完全信息的区别，完全信息只是博弈开始时参与人没有不确定性，相当于博弈树共同知识;而完美信息则是在任一决策点上参与人都没有不确定性，这不仅要求博弈树为共同知识，而且每个参与人决策时博弈的历史也是共同知识。例如，图61 图65 图66 图68 图73及图77所示的扩展使都是完美信息的，而图62 图63 图64中的扩展使博弈却不是完美信息博弈，因为参与人3决策时，不知道参与人1或参与人2的选择。对于完美信息的博弈，子博弈精炼Nash 均衡完全满足动态规划的最优原理，即在博弈的任何决策时点上，子博弈精炼Nash均衡都能给出参与人的最优选择。在如图77所示的扩展式博弈中，为子博弈精炼Nash均衡，容易验证：在博弈树的任一决策结上，该均衡都能给出参与人的最优选择。例如，在决策结上，参与人1选择所导致的博弈结果为即子博弈的结果），选择所导致的博弈结果为（即子博弈的结果），所以参与人1的最优选择为，这与所给出的选择一致；又如，在决策结上，参与人2的最优选择为，与所给出的选择也一致。（讲！）由于子博弈精炼Nash 均衡在任一决策结上都能给出最优决策，这也使得子博弈精炼Nash均衡不仅在均衡路径（即均衡战略组合所对应的路径）上给出参与人的最优选择，而且在非均衡路径（即除均衡路径以外的其他路径）上也能给出参与人的最优选择。所以，子博弈精炼Nash均衡不会含有参与人在博弈进程中不合理的、不可置信的行动（或战略）。这就是子博弈精炼Nash 均衡与Nash均衡的实质性区别。（讲！）例如，在如图66所示的“新产品开发博弈”中，200，0企业2企业2开发0，200不开发不开发不开发企业1开发开发400，4000，0图6-6 博弈树为子博弈精炼Nash均衡，该均衡不仅在均衡路径上而且在任一非均衡路径上，都能给出参与人的最优决策。Nash均衡虽然在均衡路径上上给出了参与人的最优决策，但却包含了参与人在非均衡路径上的不合理选择：当企业1选择“不开发”时，企业2也选择“不开发”。虽然为Nash均衡，但却包含了企业2不可置信的战略：无论企业1如何选择，企业2都将选择“开发”。事实上，当企业1选择“开发”时，理性的企业2只能选择”不开发”。像Nash均衡中，“企业2无论什么情况下都能开发”这种不可置信的战略亦称为“不可置信的威胁”（incredible，threat）。作为求解子博弈精炼Nash均衡的方法，逆向归纳法可以将Nash 均衡中的“不可置信的威胁”剔除掉。 1 2 1,2 , , （a）博弈的扩展式描述 参与人2参与人1 0,02，11，2 1,2(b)博弈的战略式描述图78 逆向归纳法剔除“不可置信威胁”（讲！）例如，对于如图78所示的动态博弈，战略组合 和 都是Nash 均衡（参见78（b）。但是，只有为子博弈精炼Nash 均衡，而却不是，这是因为在中，包含了参与人2不可置信的威胁：当参与人1在决策结选择时，参与人2在决策结选择。事实上，只要博弈达到决策结，参与人2的理性选择就是。（讲！）又如，在图77中，也是博弈的Nash均衡，但该均衡却包含了参与人1在子博弈中的不可置信的威胁：如果参与人2选择，则选择（此时参与人1理性的选择应为）。所以，不是子博弈精炼Nash均衡。5, 1, , , 1,12, 31图77 逆向归纳法求解扩展式博弈由于逆向归纳法可以讲Nash均衡中不合理的、不可置信的行动（或威胁）剔除掉，因此逆向归纳法从本质上讲是一种重复剔除战略的过程。下面以逆向归纳法求解图77中博弈为例，对这一问题进行分析。用表示参与人1的战略集，其中分别表示参与人1在决策结、和上的行动；用表示参与人2的战略集，其中分别参与人2在决策结和上的行动。图7-9给出的是图7-7中博弈的战略式描述。5, 1, , , 1,12, 31图77 逆向归纳法求解扩展式博弈参与人2 2，12，12，32，32，12，14，14，13，23，22，32，33，23，24，14，12，35，12，35，12，35，12，35，12，35，12，35，12，35，12，35，1参与人1图7-9 战略式描述当使用逆向归纳法求解图7-7中博弈时，首先求解最底层的子博弈、和。由于在子博弈中，参与人1的最优行动为，因此参与人1在决策结上选择的战略必为参与人1的劣战略，即中的战略是参与人1的劣战略。基于同样的原因，通过求解子博弈可知：参与人1的劣战略。所以，当求解子博弈和时，实际上已将和中的战略剔除掉，此时参与人1余下的战略集为。同理，通过求解子博弈，可以将中战略剔除掉，此时参与人2余下的战略集为。图7-10给出的是图7-7中扩展式博弈剔除劣战略后的战略式描述。 参与人2参与人13, 24,12, 32, 3图7-10 战略式描述求解子博弈。参与人2在决策结上最优行动，因此参与人2在决策结上选择的战略必为劣战略。所以，通过求解子博弈,可以将中战略剔除掉，此时参与人2余下的战略集为。图7-11给出的是：通过求解子博弈、和，图7-7中扩展式博弈剔除劣战略后的战略式描述。最后求解子博弈，即原博弈。参与人1在决策结上最优行动为，因此参与人1在决策结上选择的战略必为劣战略。所以，通过求解子博弈,可以将中战略剔除掉，此时参与人1余下的战略集为。图7-11 战略式描述参与人1参与人23,22,3综上分析可以看到：当求解完所有的子博弈后，参与人1和参与人2余下的战略集都只含有一个战略，它们所构成的战略组合就是该博弈的子博弈精炼Nash均衡。（讲！）虽然逆向归纳法的本质是一种重复剔除劣战略的过程，但在某种情况下却不能直接应用重复剔除劣战略的思想来求解子博弈精炼Nash均衡。这是因为在重复剔除劣战略的过程中，如果各个劣战略剔除的顺序不同，得到的博弈均衡就有可能不同，除非每次剔除的都是严格劣战略。在图7-12中，图7-12（a）是博弈的扩展式描述，图7-12（b）是相应博弈的战略式描述。在图7-12（a）中，应用逆向归纳法可得到博弈的唯一子博弈精炼Nash均衡。但是，在图7-12（b）中，如果先剔除参与人1的劣战略，再剔除参与人2的弱劣战略，则得到的Nash均衡中就没有博弈唯一的子博弈精炼Nash均衡。参与人13, 30, 21212, 01, 1（a）扩展式描述 参与人22,01,10,21,1(b)战略式描述3，33，33，33，3图7-12 重复剔除劣战略求解子博弈精炼Nash均衡（基本不讲！供扩展阅读）【例7-3】 考察“海盐分金”博弈问题 该博弈源于科学美国人中的一道智力题，原名为凶猛海盗的逻辑，现在人们习惯上称它为“海盗分金”。有个亡命之徒在海上抢到枚金币，他们决定通过一种民主的方式来分配这笔财富。投票规则如下：个海盗通过抽签决定每个人提出分配方案的的顺序，由排序最靠前的海盗提出一个分配方案，如果有半数或半数以上的人赞成，那么就按照这个海盗提出的分配方案分配金币，否则提出的这个方案的海盗就要被扔进海里；再由下一个海盗提出分配方案，如果有半数或半数以上的人赞成，按么就按照他提出的方案进行分配，否则他也会被扔进海里；以此类推。每个海盗都非常聪明并且知道他人的凶残。对于海盗而言，他们希望自己获得尽可能多的金币，但是被丢到海里就意味着喂鱼，因此他们都不愿意丢掉性命。试问：在这种规则下最后的分配结果是什么？从直觉上看，最先提出分配方案的海盗所处的位置最不利，因为其他的海盗可以通过将其扔进海里减少分配金币的人数，从而使自己获得更多的金币。但是，如果将“海盗分金”问题当成一个完全信息的动态博弈来分析，所得的结论将会与我们的直觉完全不同。显然，“海盗分金”问题可以看成是一个有限的完美信息动态博弈 这里假设金币只能按整数进行分配。，所以可以采用逆向归纳法进行求解。不妨将第个提出分配方案的海盗称为海盗,用表示海盗提出的分配方案，其中表示海盗愿意付给海盗的金币数量。显然，。图7-13是“海盗分金”问题的示意图 注意，图7-13仅是“海盗分金”问题的示意图，而不是博弈问题的扩展式描述，即博弈树。提出 集体 提出 集体 提出 集体 提出 集体 提出 集体方案 投票 反对 方案 投票 反对 方案 投票 反对 方案 投票 反对 方案 投票海盗1 海盗2 海盗3 海盗4 海盗5 赞成 赞成 赞成 赞成 赞成 图7-13 海盗分金”博弈示意图 首先考察如果轮到海盗提出分配方案时的情况。轮到海盗提方案时，前个海盗肯定已经被丢进大海喂鱼了，这个时候只有他留在船上，无论他提出怎样的分配方案，最后都会被实施。为了尽可能多地获得金币，海盗会选择。向前递推一步，当轮到第4个海盗提出方案时，前面3个海盗都已经被丢进大海喂鱼了，这个时候船上只留下海盗和海盗。无论海盗赞成与否，集体投票的赞成票数都至少达到半数，海盗提出的分配方案最终被实施，因此海盗会提出分配方案。顺次向前推一步，如果轮到海盗做决定，他会提出怎样的分配方案？当轮到海盗提方案时，前2个海盗肯定已经被丢进大海喂鱼了，这个时候只有海盗、海盗和海盗留在船上。海盗知道如果他的方案被否决，海盗将提出分配方案,那么海盗将什么也得不到。现在只要他给海盗一个单位的金币，海盗将赞同该方案。这样一来，集体投票的赞成票数就会大于半数，因此海盗就会选择分配方案。继续向前递推，轮到海盗做决定的时候，海盗已经被丢进大海，留在船上的还有海盗、海盗、海盗和海盗。海盗知道如果自