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

1、博弈论：原理、模型与教程第二部分 完全信息动态博弈第7章 子博弈精炼Nash均衡本章将介绍一种新的博弈的解子博弈精炼Nash均衡，并对子博弈精炼Nash均衡的唯一性、求解方法及存在的不足进行分析。7.1 子博弈精炼Nash均衡（已精细订正！）对于扩展式博弈，同样可以用Nash均衡作为博弈的解，但是，与Nash均衡作为战略式博弈的解一样，面临着Nash均衡的多重性问题，而且在多个Nash均衡中有些是明显不合理的。例如，在图6-1中，博弈存在两个Nash均衡和，其中均衡要求企业2采取战略“企业1开发自己就开发，企业1不开发自己就不开发”。在“新产品开发博弈”中，如果市场需求大，不管对方是否开发，每

2、个企业都应该选择“开发”（因为只要开发即可盈利） 参见图1-1. 。所以“当企业1开发时，企业2开发”是合理的；但是当“当企业1不开发时，企业2不开发”是不合理了。所以，均衡不是一个关于博弈结果的合理预测。在图6-6中博弈存在三个Nash均衡、和，但这三个均衡是否都是合理的呢？在“新产品开发博弈”中，如果市场需求小，那么就只能一个企业开发，另一个企业不开发。问题在于谁选择开发，谁选择不开发。对于先行动的企业1来讲，只要自己选择“开发”，理性的企业2就只会选择“不开发” 否则，企业2就会亏本，还不如选择“不开发”。，所以均衡是不合理的。而对于企业2来讲，企业1开发自己当然不应开发，如果企业1不开

3、发自己显然应该开发，所以均衡也是不合理的。因此 ，对于图6-6中的扩展式博弈，合理的Nash均衡是。（讲！）在图6-8中，博弈存在两个Nash均衡。当参与人1在信息集采取行动时，博弈结束。但是，作为参与人1的战略必须告诉参与人1如果他在信息集上他应如何选择。显然，如果轮到参与人1在信息集上决策，他的最优选择行为。所以，对于图6-8中博弈，均衡是不合理的。博弈论的研究目的就是寻找博弈问题的解。到目前为止，人们主要是将Nash均衡作为博弈的解，但Nash均衡作为博弈的解面临一个很大的问题多重性问题。如何解决Nash均衡的多重性问题，人们已做了很多探讨，如前面讨论过的“焦点效应”相关均衡等，但这些方

4、法都是一些非规范式的方法，需要结合具体的博弈问题，剔除不合理的Nash均衡。如对于图6-1和图6-6中的博弈问题，只有结合“新产品开发博弈”的特点，才能将不合理的均衡剔除。除了非规范式的方法以外，解决Nash均衡多重性问题的一种主要方法就是精炼的方法，即从博弈解的定义入手，在Nash均衡的基础上，通过定义更加精炼的博弈解剔除Nash均衡中不合理的均衡。例如，对于图6-6中扩展式博弈，存在三个Nash均衡、和，但只有均衡是合理的。如果能够构造一种新的（或者说更加精炼的）博弈解，使得均衡满足新的博弈解的要求，而其他两个均衡和却不满足新的博弈解的要求，那么就可以直接根据新的博弈解的定义，将不合理的N

5、ash均衡（即均衡和）剔除掉。Selten在1965年提出的“子博弈精练Nash均衡”（subgame perfect equlibrium）的概念，就是这样一种新的博弈解。子博弈精炼Nash均衡不仅在一定程度上解决了Nash均衡的不足，而且对完全信息的动态博弈问题尤为适用。下面对子博弈精炼Nash均衡的定义及求解方法进行介绍。在给出子博弈精炼Nash均衡的正式定义之前，需要介绍“子博弈”这个概念。所谓“子博弈”，就是原博弈的一部分，它始于原博弈中一个位于单结信息中的决策结，并由决策结及其后续结共同组成 假设为博弈树中的两个结，如果博弈能够从达到，则称为的后续结。例如，在如图6-8所示的博弈数

6、中，博弈能够从达到终点结，（通过参与人2采取行动）和（通过参与人2采取行动），博弈也能够从达到终点结（通过参与人2采取行动之后，参与人1采取行动）和（通过参与人2采取行动之后，参与人1采取行动）。所以博弈树中的都是的后续结。 。子博弈可以作为一个独立的博弈进行分析，并且与原博弈具有相同的信息结构。例如：对于图6-2和图6-8中的扩展式博弈，除原博弈外还分别存在两个子博弈（如图7-1和图7-2所示）；33 1L2R图6-2 博弈树：知道1的选择；不知道2的选择2原博弈图7-1 子博弈2（b）32（a）32，116121，11，213，0图6-8 博弈树原博弈2 （a） 3，0 1，21, 11（

7、b） 3，0 1，21图7-2 子博弈对于图6-5中的扩展式博弈，则存在包括原博弈在内的7个子博弈；33331L22R图6-5 博弈树：既知道1的选择；也知道2的选择而对于图6-4和图6-12中的扩展式博弈，都只有1个子博弈，即原博弈本身 与某些而文献或教材中的定义不同，本书将原博弈也看成是一个子博弈。3331L22R图6-4 博弈树：既不知道1的选择；也不知道2的选择图6-12 “囚徒困境的扩展式描述”坦白抵赖抵赖小偷小偷坦白抵赖坦白-4, -40,-6-6, 0-1,-1坦白抵赖抵赖小偷2小偷1坦白抵赖坦白-4, -40,-6-6, 0-1,-1（讲！） 需要说明的是，对于图6-4中的扩展

8、式博弈，虽然决策结都是位于单决策结信息集中的决策结，但及其后续结并不能构成一个子博弈，这是因为子博弈必须与原博弈具有相同的信息结构。 在原博弈中，参与人3并不知道参与人1的选择，也就是说，参与人3并不知道参与人2是在上进行选择。及其续结如能作为“一个独立的博弈”（即子博弈）进行分析，则必须要求参与人3知道这个“一个独立的博弈”是始于在，而这与原博弈中“参与人3并不知道参与人2是在上进行选择”是矛盾的。基于同样的原因，图6-3中的扩展式博弈也只存在一个子博弈，即原博弈。（讲！）子博弈的表示在以后的讨论中，为了叙述方便，用表示博弈树中开始于决策结的子博弈。例如，对于图6-8中的博弈树，比表示开始于

9、决策结的子博弈，如图7-2(a)所示；表示开始于决策结的子博弈，如图7-2（b）所示；而表示开始于决策结的子博弈，即原博弈，如图6-8所示。下面给出 子博弈精炼Nash均衡 的定义。定义7-1 扩展式博弈的战略组合是一个子博弈精炼Nash均衡，当且仅当满足以下条件：(1)它是原博弈的Nash均衡；(2)它在每一个子博弈上给出（或构成）Nash均衡.上述定义意味着：一个战略组合是子博弈精炼Nash均衡当且仅当它对所有的子博弈（包括原博弈）构成Nash均衡，同时也意味着原博弈的Nash均衡并不一定是子博弈精炼Nash均衡，除非它还对所有子博弈构成Nash均衡。 开发 不开发 企业2 企业2 开发

10、不开发 开发 不开发 (300,300) (800,0) (0, 800) (0,0) 图6-1 博弈树企业1例如，对于图6-1中的扩展式博弈，子博弈和的Nash的均衡为企业2选择“开发” 注意，始于的子博弈实际上是一个单人博弈问题（决策问题）。，所以原博弈的Nash对所有的子博弈（包括原博弈）构成Nash均衡，因此是子博弈精炼Nash均衡。由于对子博弈没有给出Nash均衡，因此虽然是Nash均衡，但并不是子博弈精炼Nash均衡。再例如，对于图66中的扩展式博弈，子博弈的Nash 均衡为企业2选择“不开发”，子博弈的Nash均衡为企业2的选择“开发”，所以原博弈的Nash均衡是子博弈精炼Nas

11、h 均衡。由于和分别对子博弈和没有给出Nash均衡 ，因此虽然和是Nash均衡，但并不是子博弈精炼Nash均衡。（讲！）又例如，对于图68中的均衡扩展式博弈，子博弈的 Nash均衡为参与人1选择，子博弈的Nash均衡为：参与人2选择，参与人1选择，所以原博弈的Nash均衡对所有的子博弈（包括原博弈）构成Nash均衡，因此，是子博弈精炼Nash均衡。由于对子博弈和都没有给出Nash 均衡，因此虽然是Nash均衡，但并不是子博弈精炼Nash均衡。 由以上分析可以看到：虽然图61 、图66和图68中的扩展式博弈都存在多个Nash均衡，但合理的Nash均衡都是子博弈精炼Nash均衡。所以，对于诸如图6

12、1、图66和图68所示的扩展式博弈，尤其是完全信息的动态博弈，一般都用子博弈精炼Nash均衡作为博弈的解。例7-1】 两个使用下列过程分配两个不相同的不可分割的物品：他们中的某一个人提出一种分配方式，另一个人可能接受也可能拒绝；如果拒绝，两个人都得不到任何东西。假设每个人仅关心所得的物品数量。图73是上述分配博弈的扩展式描述，其中表示“参与人1得件物品，参与人2得件物品”的分配方案，表示“两个人与人各得件物品”的分配方案，表示“参与人1得件物品，参与人2得件物品”的分配方案；表示参与人2接受参与人1的分配方案，表示参与人2拒绝参与人1的分配方案。所以，在分配博弈中，参与人1有三个战略战略、和，

13、参与人2有8个战略战略、 、 、 、和 在战略（其中）中 ，表示参与人1的分配方案为时，参与人2的选择； 表示参与人1的分配方案为时，参与人2的选择； 表示参与人1的分配方案为时,参与人2的选择。图74是分配博弈的战略式描述。从图74中可以看到，博弈的Nash均衡为、(、 、。在这9个均衡中，前四个导致的分配结果为（，），随后两个导致的分配结果为（，），最后一个导致的分配结果为（,），其他两个导致的分配结果为(,) 。除了均衡和外，在其余的均衡中都涉及：在轮到参与人2选择时，参与人2的一个不合理的选择拒绝至少给他一件物品的分配方案。所以，合理的Nash均衡只有和。而根据子博弈精炼Nash均衡的

14、定义，容易验证和为子博弈精炼Nash均衡。 , , , , , 图73 分配博弈的扩展式描述 图7-4 分配博弈的战略式博弈 参与人10, 00, 00, 00, 00, 00, 01, 0, 01, 0, 01, 10, 00, 20, 00, 00, 20, 20, 02, 00, 21, 02，02，02，02，00，00，01，11，10，2参与人2以上分析说明，用子博弈精炼Nash均衡作为博弈的解，可以在一定程度上克服Nash均衡的不足，剔除一些不合理的Nash均衡。同时，著名的Kuhn也为应用这种新的解概念分析一类博弈问题奠定了基础。定理71（Kuhn定理） 每个有限的扩扩展式博弈

15、都存在子博弈精练Nash均衡 所谓有限的扩展式博弈，是指参与人和参与人行动时的行动空间都有限的扩展式博弈。除非特别说明，本书所讨论的扩展式 博弈都是指有限的扩展式博弈。虽然Kuhn定理保证了子博弈精练Nash均衡的存在性，但Kuhn定理不能确保所讨论的有限的扩展式博弈精练Nash均衡都只存在唯一的子博弈精练Nash均衡。例如，例中所讨论的分配博弈，就存在两个子博弈精练Nash均衡。由于子博弈精练Nash均衡并不是在任何情况下都是唯一的，使用子博弈精练均衡仍可能面临解的多重性问题，特别是在某些情况下（如退化了的动态博弈），博弈的子博弈精练Nash均衡与Nash均衡是一样的。图75中，图75（b）是图75(a)中扩展式描述的战略式描述，从图75(b)中容易看出，博弈存在两个Nash均衡。但由于图75(b)中博弈只存在一个子博弈，即原博弈，因此这两个Nash均衡都是子博弈精炼Nash均衡 关于图75中博弈解的合理性讨论，参见本书第四部分。, , , , ,（a）博弈的扩展式描述参与人2 0，00，1 参与人1 （b）博弈的扩展式描述 1，32，11，3 0，2图75存在多个子博弈精炼Nash均衡的扩展式博弈17