第7章子博弈精炼Nash均衡.ppt

《第7章子博弈精炼Nash均衡.ppt》由会员分享，可在线阅读，更多相关《第7章子博弈精炼Nash均衡.ppt（207页珍藏版）》请在三一文库上搜索。

1、第二部分： 完全信息动态博弈,第七章 子博弈精炼Nash均衡,主要内容： 一、子博弈精炼Nash均衡 二、子博弈精炼Nash均衡的求解 三、承诺行动与要挟诉讼 四、子博弈精炼Nash均衡的合理性讨论 五、子博弈精炼Nash均衡的惟一性讨论,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,主要内容： 一、子博弈精炼Nash均衡 二、子博弈精炼Nash均衡的求解 三、承诺行动与要挟诉讼 四、子博弈精炼Nash均衡的合理性讨论 五、子博弈精炼Nash均衡的惟一性讨论,第七章 子博弈精炼Nash均

2、衡,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,一、子博弈精炼Nash均衡,我们知道Nash均衡是一个静态均衡，将Nash均衡作为扩展式博弈的解同样会遇到Nash均衡的多重性问题，而且在多个Nash均衡中有些是明显不合理的。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例1：新产品开发博弈,市场需求大时的情况,Control Science and Engineering, H

3、UST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,博弈存在两个Nash均衡(开发，(开发，开发)和(开发，(开发，不开发)，其中均衡(开发，(开发，不开发)要求企业2采取战略“企业1开发自己就开发，企业1不开发自己也不开发”。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,我们知道，“新产品开发博弈”

4、中，如果市场需求大的话，不管对方是否开发，每个企业都应选择“开发”(因为只要开发即可盈利)，所以，“当企业1开发时，企业2开发”是合理的，但是，“当企业1不开发时，企业2不开发”就不合理了。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,所以，均衡(开发，(开发，不开发)不是一个关于博弈结果的合理预测。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例2：新产品开发博弈,市场需求小

5、时的情况,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,该博弈存在三个Nash均衡： (开发，(不开发，开发)； (开发，(不开发，不开发)； (不开发，(开发，开发)， 但这三个均衡是否都是合理的呢？,Control Science and Engineering, HUST All Rights Reserved, 2007, Lu

6、o Yunfeng,在“新产品开发博弈”中，如果市场需求小，那么就只能一个企业开发，另一个企业不开发，问题在于谁选择开发，谁选择不开发。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,但是，对于先行动的企业1来讲，只要自己选择“开发”，理性的企业2就只会选择“不开发” ，所以，均衡(不开发，(开发，开发)是不合理的。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,而对于企业2来讲，

7、企业1开发自己当然不能开发，如果企业1不开发自己显然应该开发。所以，均衡(开发，(不开发，不开发)也是不合理的。因此，合理的Nash均衡是(开发，(不开发，开发)。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例3：,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved,

8、2007, Luo Yunfeng,该博弈存在两个Nash均衡(B,E),D)和(B,F),D)。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,当参与人1在信息集 采取行动B时，博弈结束。但是，作为参与人1的战略必须告诉参与人1，如果他在信息集 上他应如何选择？ 显然，如果轮到参与人1在信息集 上决策，他的最优选择为行动E。所以，均衡是不合理的(B,F),D) 。,Control Science and Engineering, HUST All Rights Reserved, 20

9、07, Luo Yunfeng,博弈论的研究目的就是寻找博弈问题的解。到目前为止人们主要是将Nash均衡作为博弈的解，但Nash均衡作为博弈的解面临一个很大的问题多重性问题。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,如何解决Nash均衡的多重性问题，人们已做了很多探讨，如前面我们讨论过的“焦点效应”、相关均衡等等，但这些方法都是一些非规范式的方法，需要结合具体的博弈问题，剔除不合理的Nash均衡。,Control Science and Engineering, HUST All

10、Rights Reserved, 2007, Luo Yunfeng,除了非规范式的方法以外，解决Nash均衡的多重性问题的一种主要方法就是精炼的方法，即从博弈解的定义入手，在Nash均衡的基础上，通过定义更加精炼的博弈解剔除Nash均衡中不合理的均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Selten在1965年提出的“子博弈精炼Nash均衡”(subgame perfect Nash equlibrium)的概念，就是这样一种新的博弈解。子博弈精炼Nash均衡不仅在一定程度

11、上解决了Nash均衡的不足，而且对完全信息的动态博弈问题尤为适用。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,子博弈的概念,在给出子博弈精炼Nash均衡的正式定义之前，我们需要介绍“子博弈”这个概念。所谓“子博弈”就是原博弈的一部分，它始于原博弈中一个位于单结信息集中的决策结x，并由决策结x及其后续结共同组成。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,子博弈可以作为一个独

12、立的博弈进行分析，并且与原博弈具有相同的信息结构。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,为了叙述方便，用 表示博弈树中开始于决策结的子博弈。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例子：找出下列博弈的子博弈。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,该

13、博弈存在3个子博弈：除了原博弈自己以外，还存在下面两个子博弈。,(1)子博弈,(2)子博弈,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例子：找出下列博弈的子博弈,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,该博弈存在3个子博弈：除了原博弈自己以外，还存在下面两个子博弈。,(1)子博弈,(2)子博弈,Control Science and Engineering, HUST A

14、ll Rights Reserved, 2007, Luo Yunfeng,子博弈精炼Nash均衡的定义,扩展式博弈的战略组合 是一个子博弈精炼Nash均衡，当且仅当满足以下条件： 它是原博弈的Nash均衡； 它在每一个子博弈上给出(或构成)Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,一个战略组合是子博弈精炼Nash均衡当且仅当它对所有的子博弈(包括原博弈)构成Nash均衡，同时也意味着原博弈的Nash均衡并不一定是子博弈精炼Nash均衡，除非它还对所有子博弈构成Nas

15、h均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例子：,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,虽然(开发，(开发，不开发)是Nash均衡，但并不是子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例子：新产品开发博弈,Control Sc

16、ience and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,虽然(不开发，(开发，开发)和(开发，(不开发，不开发)是Nash均衡，但并不是子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,考察下面的分配博弈问题：,两人使用下列过程去分配两个相同的不可分割的物品：他们中的某一个人提出一种分配方式，另一个人可能接受也可能拒绝。如果拒绝，两人都得不到任何东西。假设每个人仅关心所得的物品数量。,Co

17、ntrol Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,分配博弈的扩展式描述 为：,A表示“参与人1得2件物品，参与人2得0件物品”分配方案， B表示“两个参与人各得1件物品”分配方案， C表示“参与人1得0件物品，参与人2得2件物品”分配方案 ； Y表示参与人2接受参与人1的分配方案， N表示参与人2拒绝参与人1的分配方案 。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,在分配博弈中，参与人

18、1有三个战略战略A、B和C，参与人2有8个战略战略(Y,Y,Y)、(Y,Y,N)、(Y,N,Y)、(N,Y,Y)、(Y,N,N)、(N,Y,N)、(N,N,Y)和(N,N,N)。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,博弈的Nash均衡为：(A,(Y,Y,Y)、(A,(Y,Y,N)、(A,(Y,N,Y)、(A,(Y,N,N)、(A,(N,N,Y)、(A,(N,N,N)、(B,(N,Y,Y)、(B,(N,Y,N)、(C,(N,N,Y)。,Control Science and En

19、gineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,根据子博弈精炼Nash均衡的定义，容易验证只有(A,(Y,Y,Y)和(B,(N,Y,Y)为子博弈精炼Nash均衡。,Control Science and Engineering,

20、HUST All Rights Reserved, 2007, Luo Yunfeng,因此，扩展式博弈，尤其是完全信息的动态博弈，一般都用子博弈精炼Nash均衡作为博弈的解。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Kuhn定理,每个有限的扩展式博弈都存在子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,虽然Kuhn定理保证了子博弈精炼Nash均衡的存

21、在性，但Kuhn定理并不能确保我们所讨论的有限的扩展式博弈都只存在惟一的子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,存在多个子博弈精炼Nash均衡的例子：,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,由于子博弈精炼Nash均衡并不是在任何情况下都是惟一的，使用子博弈精炼Nash均衡仍可能面临解的多重性问题，特别是在某些情况下(如退化了的动态博弈)，博弈

22、的子博弈精炼Nash均衡与Nash均衡是一样的。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,主要内容： 一、子博弈精炼Nash均衡 二、子博弈精炼Nash均衡的求解 三、承诺行动与要挟诉讼 四、子博弈精炼Nash均衡的合理性讨论 五、子博弈精炼Nash均衡的惟一性讨论,第七章 子博弈精炼Nash均衡,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例子：,Control Scie

23、nce and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,虽然(B,F),D)是Nash均衡，但并不是子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,由以上分析可以得到博弈的求解过程： 首先求解博弈树中最底层的子博弈(x3)，得到子博弈(x3)的结果为(3,0) (即参与人1选择E)； 再求解子博弈(x2) ，容易得到博弈的结果为(1,1)(即参与人2选择D)； 最后求解原博弈即子博弈(x1)

24、 ，得到博弈的结果为(2,1) (即参与人1选择B)。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,考察更一般的情形。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,参与人i在信息集Ii (xi)选择行动L还是行动R，取决于选择行动L和行动R所带来的后果。 由于参与人i选择行动L时使博弈进入了子博弈(xi+1) ，因此，参与人i选择行动L的后果就是得到子博弈(xi+1) 。 同样

25、，参与人i选择行动R的后果就是得到子博弈(xi+2) 。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,所以，参与人i在信息集Ii (xi)上的最优选择，取决于参与人i在信息集Ii (xi)上可能采取的行动所导致的各个子博弈。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,也就是说，参与人i在信息集Ii (xi)上的最优选择，一定是使博弈进入能给自己带来最大支付的子博弈。,Cont

26、rol Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,因此，为了确定参与人i在信息集Ii (xi)上的选择，就必须先求解参与人i在信息集Ii (xi)上可能采取的行动所导致的各个子博弈。而对于各个子博弈的求解又可以采用同样的方法进行。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,由以上分析可得求解有限扩展式博弈的一般步骤： 1) 找出博弈的所有子博弈； 2) 按照博弈进程的“反方向”逐一求解各个

27、子博弈，即最先求解最底层的子博弈，再求解上一层的子博弈，直至原博弈。也就是说，在求解每一个子博弈时，该子博弈要么不含有其它任何子博弈，要么所含子博弈都已被求解。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,上述求解有限扩展式博弈的方法亦称“逆向归纳法”(backward induction)。由于逆向归纳法对各个子博弈逐一进行求解，因此，逆向归纳法所得到的解在各个子博弈上构成Nash均衡。这也就意味着逆向归纳法所得的解为子博弈精炼Nash均衡。,Control Science and

28、Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例子：利用逆向归纳法求解下列博弈的子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,由于 在各个子博弈上都构成Nash均衡，因此， 即为上述扩展式博弈的子博弈精炼Nash均衡。,Control Scie

29、nce and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,从逆向归纳法求解子博弈精炼Nash均衡的过程可以看到：在求解任一子博弈时，参与人在该子博弈的初始决策结上的选择，对余下的博弈进程而言是最优的。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,应用逆向归纳法所得到的博弈的解子博弈精炼Nash均衡，在一定程度上满足动态规划的最优性原理。,Control Science and Engineering, HUST A

30、ll Rights Reserved, 2007, Luo Yunfeng,逆向归纳法对于完美信息(perfect information)的博弈问题尤为适用。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,所谓完美信息的博弈是指每个参与人决策时都没有不确定性，也就是说，在博弈树中每个参与人的信息集都是单决策结的。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,完美信息与完全信息的

31、区别：,完全信息只是博弈开始时参与人没有不确定性，相当于博弈树为共同知识； 而完美信息则是在任一决策时点上参与人都没有不确定性，这不仅要求博弈树为共同知识，而且每个参与人决策时博弈的历史也是共同知识。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,对于完美信息的博弈，子博弈精炼Nash均衡完全满足动态规划的最优性原理，即在博弈的任何决策时点上，子博弈精炼Nash均衡都能给出参与人的最优选择。,Control Science and Engineering, HUST All Rights

32、 Reserved, 2007, Luo Yunfeng,由于子博弈精炼Nash均衡在任一决策结上都能给出最优决策，这也使得子博弈精炼Nash均衡不仅在均衡路径(即均衡战略组合所对应的路径)上给出参与人的最优选择，而且在非均衡路径(即除均衡路径以外的其它路径)上也能给出参与人的最优选择。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,所以，子博弈精炼Nash均衡不会含有参与人在博弈进程中不合理的、不可置信的行动(或战略)。这就是子博弈精炼Nash均衡与Nash均衡的实质性区别。,Cont

33、rol Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,在“新产品开发博弈”中，(开发，(不开发，开发)为子博弈精炼Nash均衡，该均衡不仅在均衡路径 上而且在任一非均衡路径上，都能给出参与人的最优决策。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Nash均衡(开发，(不开发，不开发)虽然在均衡路径 上给出了参与人的最优决策，但却包含了参与人在非均衡路径上的不合理选择：当企业1选择“不开发”时，

34、企业2也选择“不开发”。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,(不开发，(开发，开发)虽然为Nash均衡，但却包含了企业2不可置信的战略：无论企业1如何选择，企业2都将选择“开发”。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,像Nash均衡(不开发，(开发，开发)中，“企业2无论什么情况下都开发”这种不可置信的战略亦称为“不可置信的威胁”(incredible thr

35、eat)。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,作为求解子博弈精炼Nash均衡的方法，逆向归纳法可以将Nash均衡中的“不可置信的威胁”剔除掉。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例如：,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,战略组合(A,D)和

36、(B,C)都是Nash均衡，但是，只有(A,D)为子博弈精炼Nash均衡。 因为在(B,C)中，包含了参与人2不可置信的威胁：当参与人1在决策结x1选择A时，参与人2在决策结选择C。事实上，只要博弈达到决策结x2，参与人2的理性选择就是D。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,由于逆向归纳法可以将Nash均衡中不合理的、不可置信的行动(或威胁)剔除掉，因此，逆向归纳法从本质上讲是一种重复剔除劣战略的过程。,Control Science and Engineering, HUS

37、T All Rights Reserved, 2007, Luo Yunfeng,例子,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,用 表示参与人1的战略集，其中x、y和z分别表示参与人1在决策结x1、x4和x5上的行动； 用 表示参与人2的战略集，其中x和y分别表示参与人2决策结和上的行动。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and

38、Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,首先求解最底层的子博弈(x3)、 (x4)和(x5)。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,劣战略,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,由于在子博弈(x4)中，参与人1的最优行动为 ，因此，参与人1在决策结x4上选择的战略 必为参与人1的劣战略，即

39、中的战略是参与人1的劣战略。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,劣战略,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,基于同样的原因，通过求解子博弈(x5)可知： 中的战略也是参与人1的劣战略。所以，当我们求解子博弈(

40、x4)和(x5)时，实际上已将 和 中战略剔除掉。 此时，参与人1余下的战略集为,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,劣战略,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,通过求解子博弈(x3)可知： 中的战略也是参与人

41、2的劣战略。所以，当我们求解子博弈(x3) 时，实际上已将 中战略剔除掉。 此时，参与人2余下战略集为,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,于是，扩展式博弈剔除劣战略后的战略式描述为,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yun

42、feng,劣战略,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,求解子博弈(x2)。参与人2在决策结x2上最优行动为 ，因此，参与人2在决策结x2上选择的战略 必为劣战略。所以，通过求解子博弈(x2)，可以将中战略 剔除掉。 此时，参与人2余下战略集为,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,Control Science and Engineering, HUST All

43、Rights Reserved, 2007, Luo Yunfeng,劣战略,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,最后求解子博弈(x1)即原博弈。参与人1在决策结x1上最优行动为L，因此，参与人1在决策结x1上选择的战略R必为劣战略。 所以，通过求解子博弈(x1) ，可以将 中战略剔除掉。 此时，参与人1余下的战略集为,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,综上分

44、析可以看到：当我们求解完所有的子博弈后，参与人1和2余下的战略集都只含有一个战略，它们所构成的战略组合就是博弈的子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,虽然逆向归纳法的本质是一种重复剔除劣战略的过程，但在某些情况下我们却不能直接应用重复剔除劣战略的思想来求解子博弈精炼Nash均衡。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,这是因为在重复剔除劣战略的过程中，如果各个劣战略剔除的顺序不同，得到的博弈均衡就有可能不同，除非每次剔除的都是严格劣战略。,Control Science and Engineering, HUST All Rights Reserved, 2007, Luo Yunfeng,例如：,如果先剔除参与人1的劣战略(A,E)，再剔除参与人2的弱劣战略D，则所得到的Nash均衡中就没有博弈惟一的子博弈精炼Nash均衡(B,E),D)。,Control Science and Eng