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

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