《合作博弈四川大学》PPT课件.ppt

2010-3-3,博弈论及其应用（汪贤裕）,#,博弈论及其应用,第5章合作博弈,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,2,第5章合作博弈,主要内容：5.1基本概念5.2占优方法：合作博弈一类解概念5.3估值方法：合作博弈的一类解概念5.4合作博弈的应用范例,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,3,5.1基本概念,5.1.1纳什谈判解与联盟5.1.2联盟与特征函数5.1.3特征函数的性质5.1.4合作博弈中的解概念,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,4,5.1.1纳什谈判解与联盟,2人纳什谈判解的决定n人纳什谈判解的决定纳什谈判的例子合作博弈与非合作博弈区分的两个假设条件,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,5,2人纳什谈判解的决定,在2人纳什谈判解讨论中，是二人经过谈判后可能达到的结果集。是谈判的初始参考点，经过纳什公理化体系，通过求解，可以得到一对谈判解。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,6,n人纳什谈判解的决定,设是局中人的集合，是n人经过谈判进行合作的可达结果集。当允许采用抽彩方法对结果分配时，结果集是一个凸集。令是谈判达不成协议的支付分配（或n个局中人的保守收益），作为谈判的初始参考点。将纳什公理化体系扩大到n人，则有n人纳什谈判解的唯一结果。一般情况下，它由下式决定：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,7,纳什谈判的例子,例5.1.1设有三个人参与分配300元，若第个人分得，则它的效用为，三个人提出的分配方案分别为，则当三个人方案一致时有收益，否则收益为零，用收益函数表达为：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,8,纳什谈判的例子,很显然，这时可达结果集为：而三个人所得的最低水平为0，即：初始参考点是应用（5.1.1）式，容易得：在这一博弈中，三人都采用了同样的策略显然，作为理性的局中人，它的策略中不会使自己的收益小于100元，而他若使自己的收益高于100元，则不会使其他人得到认同。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,9,纳什谈判的例子,例5.1.2类同例5.1.1，但规定只有当局中人1和局中人2提出的分配策略不同时，各局中人的收益所得为0；若局中人1和局中人2提出的分配策略相同时，即，则按这一分配向各局中人支付，其收益函数可表达为：这时的可达结果结仍为：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,10,纳什谈判的例子,在例5.1.2博弈中，局中人1和局中人2可以联合起来对支付的分配策略进行选择，而局中人3的任何策略都无法干预分配方案。因而，可以合理地认为该博弈仅在局中人1和局中人2两人之间进行分配讨论。若局中人1和局中人2采用二人合作博弈的纳什谈判解。则其结果将是（150，150，0）。在人谈判问题中，若出现联盟，则可能发生实质性的变化。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,11,纳什谈判的例子,例5.1.3类同例5.1.1。但该博弈规定，如果有两个局中人提出相同的分配策略时，则每人按这一策略进行支付，否则每个局中人的支付都为0。其收益函数可以表达为：这时的可达结果集仍为：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,12,纳什谈判的例子,在例5.1.3的博弈中，情况就非常复杂了。若局中人1和局中人2谈判分配方案为，局中人3可以和其中一个局中人再谈判.如与局中人1再谈判,提出分配方案此后局中人2又可以和1，3中一个局中人，如局中人3谈判，提出分配方案，这种过程可以一直进行下去。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,13,纳什谈判的例子,对这一谈判过程的终止可以有两种规定：一是规定局中人通过一轮谈判后形成一个协议，按照协议规定，每个局中人进行再谈判不能与以前的谈判相违背。可以看到，在三人博弈中，先行谈判的局中人具有先动优势。二是规定谈判的次数的顺序。如规定谈判的顺序是先由1，2谈判,其次由2，3谈判。第3由1，3谈判，最后1，2，3谈判,这时局中人1和局中人3，即1，3谈判具有后动的优势。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,14,合作博弈与非合作博弈区分的两个假设条件,作为合作博弈与非合作博弈的相区分的主要两个假设条件如下：合作博弈中允许局中人在博弈前进行谈判；而非合作博弈不允许。合作博弈中一旦达成协议，形成一个联盟，则协议有了强制约束力，因而联盟的一系列行动被局中人所承认；在非合作博弈中也有一定的博弈前沟通，如“相关均衡”，但它不具有强制的约束力，只能用利益进行诱导或激励。在多人合作博弈中，联盟具有核心重要的作用。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,15,5.1.2联盟与特征函数,联盟的定义可转移效用（TU）特征函数的定义特征函数的确定,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,16,联盟的定义,定义5.1.1设博弈的局中人集合为，则任意，称S为N的一个联盟（coalition）。特殊情况，允许取和，后一种情况称为一个大联盟。若，则中联盟个数为。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,17,可转移效用（TU）,若联盟S中局中人的收益可以自由地分配，且任何局中人的收益变化1个单位，它的效用也变化1个单位，我们称为可转移效用（TU）（transformableutility），也称有旁支付的（withside-payments）。本章仅对可转移效用情况进行讨论。可在转移效用（TU）的合作博弈中，联盟S的一个收益表示它加入大联盟进行博弈的机会收益，或联盟S独立活动可获得的最大收益。这是进行合作博弈首先应确立的。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,18,特征函数的定义,定义5.1.2设博弈的局中人集合为，是定义在N的一切子集（即联盟）上的实值函数，其满足：（1）（5.1.4）（2）（5.1.5）称为一个特征函数(characteristicfunction)，或联盟函数(coalitionalfunction)。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,19,给定局中人集合和特征函数，所进行的合作博弈称为可转移效用下合作博弈，记为。它称为特征函数式博弈（characteristicfunctionform）或联盟式博弈（coalitionalform）。在可转移效用下合作博弈，我们着重研究联盟中的收益分配问题。由于本章不涉及到不可转移效用，因此下面简称合作博弈。,特征函数的定义,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,20,特征函数的确定,方法一若联盟S的成立可以获得独立于联盟S之外成交行为的收益，值表示此时联盟可获得的最大机会收益。在例5.1.1中在例5.1.2中在例5.1.3中,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,21,特征函数的确定,方法二联盟S的成立可以获得受到独立于联盟S之外局中人的影响和阻扰下的最好收益。下面我们从策略式博弈到特征函数式博弈的转换加以说明。若给定一个策略形的非合作博弈，其中局中人的混合策略集合为，收益函数为，可以由多种方法从策略式博弈推导出特征函数。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,22,特征函数的确定,第一种方法：-特征函数和-特征函数。在中（给定的子集，即联）,特征函数定义为：其中为在混合策略情况下，局中人的期望收益。-特征函数是把局中人集合划分为两个联盟和这两个联盟进行一种二人零和博弈。联盟将联盟看成利益完全冲突的对立面，以保证自己的保守收益。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,23,特征函数的确定,例5.1.4设有一个非合作博弈其中每个局中人的纯策略均为，其收益函数如右表所示：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,24,特征函数的确定,设局中人1，2组成联盟则和进行的二人零和博弈支付矩阵如右所示：可得矩阵博弈的值，即联盟S的所得为,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,25,特征函数的确定,若局中人3组成一个联盟，则和进行的二人零和博弈支付矩阵为：可得矩阵博弈的值，即联盟的解为：类似计算可得：,联盟,联盟,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,26,在中，给定的的子集，即联盟,-特征函数定义为：-特征函数，仍是假定局中人集合分为联盟和联盟，两个联盟进行二人零和博弈。联盟是联盟形成利益冲突的对立面。定义-特征函数确定过程中，联盟是先行动，对任何策略选择，联盟之外的成员将选择策略使联盟的收益最小。在-特征函数确定过程中，联盟是后行动，对联盟之外的选择的任何策略，联盟将选择策略使自己的收益最大。,特征函数的确定,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,27,第二种方法，防御均衡特征函数（defensive-equilibriumcharacteristicfunction）。在中，给定局中人集合的一个子集，即联盟防御均衡特征函数定义为：其中，由如下方法确定：考虑一个二人非零和博弈，是博弈的纳什均衡。,特征函数的确定,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,28,例5.1.5有一个可转移效用的三人博弈其中局中人的纯策略为，这里可解释为一个“慷慨”策略，是一个“自私”策略其收益函数如下表所示：,特征函数的确定,（5,2,2）,（5,2,2）,（5,2,2）,（5,2,2）,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,29,特征函数的确定,设局中人1组成联盟，和进行下面的非零和双矩阵博弈：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,30,由第二章介绍的双矩阵博弈求解法，上表给出的博弈有唯一的重复剔除占优策略，是纳什均衡。对应均衡结果为（5，4），则有防御均衡特征函数：同理有：从防御均衡特征函数的规定可以看到，用联盟和联盟作为二人非合作博弈（非零和）的均衡结果作为特征函数，从而冠以防御均衡的名称。,特征函数的确定,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,31,第三种方法，理性威胁特征函数（rational-threatscharacteristicfunction）。在中，给定局中人集合的一个子集，即联盟，基于理性威胁的特征函数定义如下：其中，由下面方法确定。考虑一个二人零和博弈是纳什均衡点。很明显，当局中人的策略合集是有限时，类似例5.1.5，和组成一个双矩阵博弈。设联盟和的收益分别为A和B。则为矩阵博弈的均衡点。因为纳什仲裁值唯一的（见定理4.5.2），则理性威胁特征函数值唯一。,特征函数的确定,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,32,再考虑例5.1.5：设局中人1组成联盟为和。从例5.1.5中可以得到：显然，构成的矩阵博弈有唯一纯策略纳什均衡则同理，我们有：,特征函数的确定,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,33,特征函数的确定,小结上面三种方法对应于最简单的二人矩阵博弈中的最小最大值、非合作博弈（非零和）中的纳什均衡和谈判问题中的理性威胁。在实际应用中，特征函数的确定可以根据特征函数的经济含义来得到。用表示联盟加入大联盟的机会收益，或联盟独立活动可获得最大的收益来确定。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,34,5.1.3特征函数的性质,特征函数的性质定义5.1.3超可加性的定义定义5.1.4博弈的凸性和凸博弈定义5.1.5弱超可加性的定义定义5.1.6实质性博弈与非实质性博弈定义5.1.70,1规范化博弈定义5.1.8简单（simple）博弈定义5.1.9赋权多数博弈定义5.1.10策略等价定理5.1.1两个博弈等价,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,35,特征函数的性质,在合作博弈中，若参与博弈的局中人集合N相同，则合作博弈的差异就是特征函数的差异。换句话说，不同的特征函数决定了不同的合作博弈。本小节对特征函数所具有的不同特征进行讨论。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,36,超可加性的定义,定义5.1.3在合作博弈中，若对任意都有：则称特征函数是具有超可加性（supperadditivity）。相对应的博弈称为具有超可加性的合作博弈。超可加性表示两个不相交的联盟分别独立行动，其分别单干的结果不如组成两个联盟的联合而共同行动。这也是大联盟形成的基本动因之一。若在（5.1.10）式中，只有等式恒成立，则称特征函数具有可加性。比超可加性更强的要求是特征函数具有凸性。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,37,特征函数的凸性和凸博弈,定义5.1.4在合作博弈中，若对任意的，都有：（5.1.11）则称特征函数具有凸性，相对应的博弈称为凸博弈。显然，特征函数满足凸性的一定满足超可加性。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,38,特征函数的凸性和凸博弈,特征函数的凸性表示联盟增大，新成员的实际贡献就越大。设对任意，有某一成员被称为新加入的成员，记。由（5.11）式有则有：即新成员加入到联盟后边际贡献要大于（或等于）新成员与联盟的任何子联盟K所组合产生的边际贡献大，即新成员的边际贡献越来越大。（凸性的名称也由此而来。）,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,39,弱超可加性的定义,定义5.1.5一个合作博弈中，若满足对任意的，则一定有，称特征函数具有弱超可加性。显然，特征函数具有弱可加性的条件比超可加性要弱，满足超可加性的特征函数一定满足弱超可加性。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,40,实质性博弈与非实质性博弈,定义5.1.6一个合作博弈，若有（5.1.12）则称该博弈为非实质性（inessential）的博弈，否则称为实质性（essential）博弈。非实质性博弈与特征函数具有可加性具有等同意义，非实质性博弈没有值得研究的内容。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,41,(0,1)规范化博弈,定义5.1.7一个合作博弈，若特征函数满足下面的两个条件：（5.1.13）（5.1.14）则称该博弈为（0，1）规范化（zero-onenormalization）博弈。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,42,简单（simple）博弈,定义5.1.8一个合作博弈，若对任意联盟都有：或，则称博弈为简单（simple）博弈。（0，1）规范化博弈和简单博弈是两个完全不同的概念：在简单博弈中，若联盟S使得，则称为取胜联盟或赢得联盟（winningcoalition）；若则称为失败联盟（losingcoalition）。简单博弈是一个特征函数取值为0，1的博弈，在一些决策中经常使用，例如投票博弈。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,43,赋权多数博弈,定义5.1.9设是一个非负维向量，是一个常数，且满足：（5.1.15）若合作博弈的特征函数满足为：（5.1.16）则该博弈称为一个赋权多数博弈（weightedmajoritygame）.赋权多数博弈是一个简单博弈。它出现的背景是投票博弈。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,44,策略等价,定义5.1.10设有两个合作博弈和，若存在一个正常数和个常数数，使得对的任意联盟都有：（5.1.17）则称合作博弈和是等价的（S-equivalent），又称策略等价的。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,45,两个博弈等价,定理5.1.1设合作博弈是实质性的，则与唯一的一个（0，1）规范化博弈策略等价。证明：设是一个（0，1）规范化博弈，若与是S-等价的，应证明存在唯一高的一个确定的正常数c和唯一的一组数，满足：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,46,两个博弈等价,现在将（5.1.18）中的n个等式相加，得到：代入到（5.1.19）中，有：由定理条件，G是实质性的，则因此，有下面的唯一的c：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,47,两个博弈等价,再代入（5.1.18）式，有唯一的a：G与（0，1）规范化博弈是S-等价的，且后者的特征函数是唯一确定的。利用定理5.1.1可以看到，对实质性的合作博弈都可以看作是同一类的（0，1）规范化博弈，进而我们可以将中心都放在（0，1）规范化博弈上。谈判集，Shapley值的讨论，都可以研究其对应的（0，1）规范化中的结果，再从等价关系使用线性变换的反演，得出原博弈所需求的结果。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,48,两个博弈等价,利用定理5.1.1可以看到，对实质性的合作博弈都可看作是同一类（0，1）规范化博弈，进而可以将我们分析的重点放在（0，1）规范化博弈上。谈判集，Shapley值的讨论，都可以研究其对应（0，1）规范化博弈中的结果，再从等价关系使用线性变换的反演，得出原博弈所需求的结果。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,49,5.1.4合作博弈中的解概念,占优估值,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,50,占优,核心（Core）和稳定集（StableSets）是“占优”准则的主要代表。它们使联盟及个体的合理分配处于一种“占优”状态，以致联盟和个体无法偏离该分配，达到合作博弈的稳定性。谈判集（BargainingSet）、内核（Kernel）和核仁（Nucleolus）是“异议”准则的主要代表。它们使联盟或个体对分配的“异议”出发，将“异议”看成为一种“可置信的威胁”，以保障分配的合理性。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,51,估值法,估值法，它通过规范道德要求的公理化体系，而赋予一种“合理”的分配值，并且这种估值是唯一的。沙普列值（Shapleyvalue）和班切夫势指标（Banzhafindexofpower）是主要代表。它们又都被称为合作博弈的势指标（Indexofpower）.,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,52,5.2占优方法：合作博弈一类解概念,5.2.1转归与占优原则5.2.2核心和-核心5.2.3稳定集5.2.4谈判解5.2.5内核5.2.6核仁,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,53,5.2.1转归与占优原则,转归集的定义个体合理性条件群体合理性条件转归之间的占优关系,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,54,转归集的定义,在合作博弈中，要进行合理地分配，首先应该找出一些可行的预分配方案，称为转归集。定义5.2.1在人合作博弈中，设是一个n维向量，满足下面两个条件：（1）（5.2.1）（2）（5.2.2）则称为一个转归（Imputation），或称分配。全体转归称为转归集，记为。对一个非实质性的合作博弈，转归集只有一个元素。对于一个实质性的合作博弈，有无穷多个转归。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,55,个体合理性条件,条件（5.2.1）式称为个体合理性条件（individualrationality）。这个条件可以理解为：任何一个个体参加到合作博弈中，他分配所得到的至少应该比单干好，否则他不会同意这种分配。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,56,群体合理性条件,条件（5.2.2）式称为群体合理性条件（grouprationality），或帕雷托最优性条件（Paretooptimility），这个条件可以理解为：若，则大联盟所得未分配完，每一个局中人（或联盟）会考虑剩余部分到何处去了，从而不会同意这个分配方案；而当，则它是分配总额超过了大联盟所得的收入，这是不可行的。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,57,转归之间的占优关系,定义5.2.2若有是合作博弈两个转归，即，是博弈的一个非空联盟，。如果（5.2.3）（5.2.4）则称转归关于联盟占优转归（dominateswithrecpectto）,或称转归关于联盟被y占优。记为：（5.2.5）,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,58,转归之间的占优关系,条件（5.2.3）称为可行性或有效性（effectiveness）条件。当y关于S占优x时，即S中的成员可以用分配方案y来反对分配方案x，那么联盟S就应该有所得，使其内部成员能得到分配方案y中应得的份额。而当（5.2.3）式不成立，即时，联盟S不能保证其成员能得到分配方案y中的支付，也就无力去反对分配方案x。条件（5.2.4）表明联盟S中的每一个成员来说，转归y比x好，S中的所有成员都将选择y而不选择x，即实现占优。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,59,转归之间的占优关系,上述定义的联盟不含单人联盟和大联盟。如果有则由定义5.2.2中（5.2.3）和（5.2.4），有，这与转归的定义5.2.1矛盾。如果有则由定义5.2.1中（5.2.3）和（5.2.4），有这也与转归定义5.2.1矛盾。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,60,转归之间的占优关系,定义5.2.3在合作博弈中，若有非空联盟，使得，则称转归占优转归，记为：（5.2.6）该定义表明：对一个分配方案，若存在另一个分配方案，使得，则一定存在至少一个联盟“反对”或“阻止”分配方案。往往称这种联盟为的“阻塞”联盟。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,61,5.2.2核心和-核心,定义5.2.4核心的定义定理5.2.1充分必要条件一个关于合作博弈收益分配的例子定义5.2.5预转归定义5.2.6强-核心定义5.2.7最小核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,62,核心的定义,定义5.2.4设是一个人合作博弈，存在一个转归，使得对所有，满足:（5.2.7）则这种转归组成的集合称为的核心（Core）,并记为。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,63,充分必要条件,定理5.2.1设人合作博弈是一个实质性博弈，且满足弱超可加性，其核心为,则转归，的充分必要条件是不被其它任何转归占优。证明：必要性。我们要证明，当时，则不被优超。假设，被某个转归，占优，即，则由占优的定义，存在某个，使得：这与相矛盾。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,64,充分必要条件,充分性：我们要证明若不被占优，则必有：下面证明其逆否命题。由定理条件，博弈G是一个实质性博弈，因而可以认为已被转为（0，1）规范化形式。假设，由定义5.2.3，存在某个联盟S，使得上式中的S显然不可能是大联盟N，也不是单人联盟，我们现在构造一个转归y，使得。为此，令满足下面条件的实数：（5.2.10）令：（5.2.11）,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,65,充分必要条件,显然有：当时，由于其中，前一个不等号来自（5.2.10）式；后一个不等号来自定理假设，具有弱超可加性。因此，当时，仍有。又因为由（5.2.11）式有：可知。很明显：所以，。因而所需证明的逆否命题成立。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,66,合作收益如何分配的例子,例5.2.1有三个人准备合作办一企业，局中人1仅有核心技术，若他将技术转让可得20万元；局中人2有资金，若他将投入企业的资金用于其他项目投资，可获得共30万元；局中人3有很强的组织管理和营销能力，若他参与其他企业服务，可获得15万元收益。若局中人1和2合作，将企业承包给第三方，可获得60万元；若局中人1和局中人3合作，由于融资的不畅，但仍可获得40万元；若局中人2和局中人3合作，进行其他项目开发，考虑到技术原因造成的项目风险，因而年均可获得65万元。若三人合作，可获得100万元。现三人合作后应该对所得如何分配？,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,67,合作收益如何分配的例子,这是一个三人合作博弈问题，特征函数为：由核心的定义，转归的充分必要条件为：,化简：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,68,合作收益如何分配的例子,画出平面上的重心三角形（即高为的等边三角形），以及各不等式要求，可作图如下可知，在上图中转归集为三角形MNQ内的点集，而阴影六边形ABDEFG为核心，其中6个顶点的坐标分别为A（20，60，20），B（20，40，40），D（30，30，40），E（35，30，35），F（35，50，15），G（25，60，15）。,核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,69,合作收益如何分配的例子,例5.2.2有3人合作博弈，其中，特征函数的值如下：容易验证，该博弈的核心。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,70,核心存在的问题,从以上例题可以看出，在合作博弈中，核心是一个非常合理的解概念，但是它存在两个问题：（1）核心可能是空集。（2）核心中可能有无穷多的元素。对一个人合作博弈，其核心是否为空集，可以用下面线性规划求解进行判断：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,71,核心存在的问题,以上线性规划的由来，包括对核心的基本要求以及转归中的个体合理条件。若设线性规划的最优值，则该博弈的核心非空。反之，当，则该博弈的核心为空集。在用（5.2.12）求解可以判定核心为非空集时，如何在核心中去确定一个唯一的分配方案，可以借用（5.1.1）式，用n人纳什谈判解的方法去确定。此时，可选择求解下面的数学规划：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,72,核心存在的问题,由定理4.3.1可知，上面数学规划有唯一解。并且由约束条件可知，该唯一解。对核心存在的两个问题解决的另一有效方法是引入强核心的概念。强-核心的引入，需对核心的部分条件减弱，其中主要是对转归中条件的减弱。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,73,预转归,定义5.2.5设有人合作博弈，是一个维向量，满足（5.2.14）则称为G的一个预转归（preimputation）。预转归的全体称为预转归集，记为。在预转归中，保留了转归中的群体合理条件，而舍去了个体合理条件。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,74,强-核心,定义5.2.6设有人合作博弈，是一个实数。非空的预转归子集称为的强-核心（Strong-core），记为：（5.2.15）,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,75,强-核心,当，则放松了对的要求，到达某一正数时，可以使合作博弈的原核心由空集变为非空的强-核心；当当时，则加强了对的要求，可以使合作博弈的核心集合变小。实质上起到一个对核心的调节作用。若时才有，可以看到这时的预转归不一定满足一般转归中的个体合理条件。很容易证明，若有和，若和都非空，有：若，则,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,76,最小核心,定义5.2.7设是一个人合作博弈，是使得强-核心的最小，称为的最小核心（Leastcore），记为LC。值得一提的是一个合作博弈的最小-核心LC一定存在，但不一定是单点集。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,77,最小核心,一般情况下，对合作博弈的最小-核心LC，可用下面线性规划求解：该线性规划的第一个约束是强-核心的要求，第二个约束是属于预转归的要求，与判断核心的线性规划相比，其约束多了一个等式约束，变量为个。该线性规划的解即为所求最小-核心对要求，而其余解则是最小-核心在C中所含的分配方案。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,78,例5.2.3设有一个三人合作博弈，其中，特征函数的取值如下：由核心的定义，的条件，可类似于例5.2.1应该满足下列要求：,最小核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,79,作重心三角形（高度为1的等边三角形），可得的转归集即为三角形123内的点组成的集合，的核心为四边形ABCD所围成的区域。,最小核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,80,图5.2.2三人合作博弈的核心及最小,核心,最小核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,81,取，由强-核心的定义，应满足下列条件要求：在上面重心三角形中，可得的为六边形EFGHIJ所围成的区域。,最小核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,82,取，由强-核心定义，应满足下列条件要求：在上面重心三角形中，可得的为线段KM，该线段是的最小-核心LC。其中K点向量为M点的向量为,最小核心,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,83,5.2.3稳定集,定义5.2.8稳定集的概念定理5.2.2核心与稳定集的关系稳定集存在性的证明,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,84,稳定集的概念,定义5.2.8在人合作博弈中，为其转归集，若转归集有子集，且中的转归满足下列条件：（1）对任意转归和，转归和之间不存在占优关系。（2）若，但，则必有，使得占优，即我们称为合作博弈的一个稳定集（StableSet），或称的解。简记为。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,85,稳定集的概念,第一个条件表明，中任意两个转归是不可比较的，它们之间没有占优和被占优的关系。这一性质被称为稳定集的内部稳定性（innerstability）。第二个条件表明，不在中的每一个转归，至少被中的一个转归所占优，即一定存在一个联盟要反对分配方案。联盟会提出分配方案，使得。这一性质称为稳定集的外部稳定性（externalstability）。一个合作博弈的稳定集一般并不唯一，可以有多个稳定集。但是特殊情况下，一个合作博弈也可能没有稳定集。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,86,核心与稳定集的关系,定理5.3.1设人合作博弈是一个实质性博弈。，且满足弱超可加性。若其核心且稳定集存在，则必有。,证明：此定理条件与定理5.2.1相同。当时，任取则不被任何转归所占优，即之间满足内部稳定性若，则必然存在，使得与，即不被占优相矛盾。由于的任意性，则有：。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,87,核心与稳定集的关系,例5.2.4设有三人合作博弈，其中特征函数取值如下：由于这是一个（0，1）规范化的三人博弈。（5.2.20）则该博弈的核心为空集。,，,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,88,核心与稳定集的关系,下面考查其稳定集。作一重心三角形（即高为的等边三角形），作直线，得到平行于23的线段ab，如下图5.2.3，ab线段上所代表的转归集有如下特征：若是ab上任意两点，则和之间互不占优，即有内部稳定性。若在ab线段上变动，则中ab线段以上的任何点都全被占优，ab线段以下的任何点也会被占优，即有外部稳定性。因此线段ab上的全体点所代表的转归组成一个稳定集。这一类稳定集称为差别待遇的解（discriminatorysolution）。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,89,核心与稳定集的关系,同样，作重心三角形（即高为的等边三角形），取三角形的三条边的中点a,b,c,则转归集的子集a,b,c也是一个稳定集，对该稳定集也称为对称解。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,90,核心与稳定集的关系,例5.2.5设有三人合作博弈，其中特征函数取值如下：正如前面提到，该博弈的核心的充分必要条件为：在（5.2.19）的条件下，我们很容易求出其核心。,，,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,91,核心与稳定集的关系,核心,作一重心三角形（即高为的等边三角形）。由和所围成的三角形，即为核心。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,92,核心与稳定集的关系,下面讨论该博弈的稳定集。以核心为一个三角形为例，设直线交三角形的两条边为d和e，直线交三角形的两边为f和g，直线交三角形的两条边为j和h。任取线段jf中一点，连接；任取线段eh中一点，连接；任取线段dg中一点，连接。可以证明是一个稳定集，由于和的任意性，则这样的稳定集也有无穷多。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,93,核心与稳定集的关系,对该例题同样可以讨论在时的稳定集，同样也有无穷多个稳定集。从上面例题可以看到，一个博弈中可能有无穷多个稳定集，而每一个稳定集中又有无穷多个转归，那么我们取什么样的转归作为合理的分配方案呢？这种“指示”很难有一个统一的标准。这也限制了稳定集的实际应用。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,94,5.2.4谈判解,定义5.2.9异议和反异议定义5.2.10博弈谈判解的定义一个关于求谈判解的例子,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,95,异议和反异议,谈判解，又称讨价还价解，它是奥曼（Aumann，2005年诺贝尔经济学奖获得者）等人提出的，也是合作博弈的一种解概念。与核心和稳定集不同，它不是从正面从转归集中寻求合理的分配方案，而是从反面，从局中人对分配结果的“异议”或不满意的角度来确定分配结果。而这种“异议”或不满意的出现是一种“可置信的威胁”。从而局中人将进行谈判，并通过谈判来获得一种合理的分配结果。这种思想也体现在下面两小节讨论的另外两个解概念：内核和核仁。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,96,异议和反异议,若某个分配方案合理，则一旦有人提出一种异议，必然会产生另一种反异议。而当分配方案不合理时，在出现了某种异议后，无反异议足以应对。在这个合作博弈中，若无外界环境的影响，三个局中人的地位作用是对称的，因而可以想象，其分配方案中每一个局中人的分配额应是相同的。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,97,异议和反异议,考虑其平均分配方案（100，100，100）。若有某个局中人想多得，譬如局中人1，他将联合局中人2对该分配方案表示异议而提出新的分配方案（150，150，0），这使得他的收益和伙伴局中人2的收益都有所提高。针对局中人1提出的这种新的分配方案，局中人3会提出反对，局中人3也会去联合局中人2提出一种反异议的分配方案（0，160，140）。因此可以看到一个合理的分配方案，若出现局中人的异议，必然会产生一个反异议。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,98,异议和反异议,考虑另一个分配方案（80，120，100），该方案是局中人2提出的。这个分配方案不是一个平均分配方案，有利于局中人2，而不利于局中人1。此时局中人1认为局中人2多得了，因而反对它。这时局中人1可以联合局中人3，提出一种反异议的分配方案（110，0，190）。此时局中人2则无法提出反异议了。因为它最初提出的方案自己价值是120，而要再拉拢局中人3，则要让局中人3得到190以上。因此，可以看出，局中人2提出的原分配方案（80，120，100）是不合理的。局中人2知道提出不合理的分配方案会遭到其它局中人的异议，而自己又无能为力提出反异议，因此一个理性局中人2不会提出不合理的分配方案。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,99,异议和反异议,对分配方案的合理性的讨论中，异议是一种威胁。若出现反异议，即是存在反威胁。若不出现反异议，即是不存在反威胁。在有威胁而无反威胁的情况下，威胁就成为可置信了，同时也表明该分配方案的不合理。下面，就合作博弈中，局中人个体之间对分配方案的异议（反对，威胁）和反异议（再反对，再威胁），给出一种规范的定义。,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,100,异议和反异议,定义5.2.9在合作博弈中。和是两个独立的参与人，在转归上对的异议（objection）是满足下面条件的二元组：在转归上对提出异议的反异议（counter-objection）是指满足下面条件的二元组：且满足：,2010-3-3,博弈论及其应用（汪贤裕）,#,2010-3-3,博弈论及其应用（汪贤裕）,101,异议和反异议,若在上对有异议存在两个条件。在第一个条件中，可以组成一个不含的联盟来否定分配方案。由于是针对，所以所组成联盟中不含。在第二个条件中，提出了一个新的分配方案，应该满足条件条：一是保证提出的分配方案使得组成联盟的成员收益都比原分配方案好；二是这种分配方案要可行，即联盟