第10讲合作博弈论ppt课件.ppt

《第10讲合作博弈论ppt课件.ppt》由会员分享，可在线阅读，更多相关《第10讲合作博弈论ppt课件.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 静态合作博弈静态合作博弈合作博弈的含义合作博弈的含义 前面介绍的各种博弈模型，都是非合作博弈模型; 这些（非合作博弈）模型的一个共同特点是强调“个体理性 (individual rationality)”; 合作博弈则强调群体理性 (group rationality); 群体理性的含义是：从一个群体整体角度，研究策略的选择，使得整体效用最大. 与非合作博弈相比，需要一个描述集体理性的效用函数;合作博弈合作博弈 一般来说，博弈论可以分为合作博弈（cooperative games）与非合作博弈（non-cooperative games），现代大多经济学家谈到的博弈论往往指的是非合作博弈论，

2、很少提到合作博弈论，甚至很多博弈论教材也未曾提到合作博弈。实际上，合作博弈的出现和研究比非合作博弈要早，早在1881年，Edgeworth在他的数学心理学一书中就已经体现了合作博弈的思想。 合作博弈的运用研究主要涉及企业、城市、区域经济以及国家之间的合作等多个方面问题。 虽然这些分析所针对的合作问题类型不同，研究重点或在于阐明合作的内在逻辑，或在于揭示合作的动因，但是研究结果则有助于加强企业的相互联系、完善城市的合作模式、推动区域经济合作实践、促进国家之间的经济交往。这里，我们首先介绍静态合作的基本概念，然后再介绍各种静态合作博弈的不同解法，包括核心（core）与稳定集（stable sets

3、）、夏普利值（Shapley value）、谈判集（negotiation sets）、内核（kernel）与核仁（nucleolus），最后再举出静态合作在现实的经济方面的各种解法的应用例子。导论导论先回忆一下囚徒困境的例子： 在囚徒困境中，还有另外一个策略组合，该组合为参与人带来的支付是。由到，每个参与人的支付都增加了，即得到一个帕累托改进。 坦白抵抗坦白-8，-80，-10抵抗-10，0-1，-1 构不成一个均衡是基于参与人的个人理性。在参与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机行为谋取超额收益1。 如果两个参与人在博弈之前，签署了一个协议如果两个参与人在博弈之前，

4、签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第三方支付价值大于1的保证金；如果谁违背了这个协议，则放弃保证金。有了这样一个协议，就称为一个均衡，每个人的收益都得到改善。 上述分析表明，通过一个有约束力的协议，原来不能实现通过一个有约束力的协议，原来不能实现的合作方案现在可以实现。这就是合作博弈与非合作博弈的区的合作方案现在可以实现。这就是合作博弈与非合作博弈的区别。别。二者的主要区别在于人们的行为相互作用时,当事人是否达成一个具有约束力的协议。如果有,就是合作博弈；反之,则是非合作博弈。 因此，博弈可以划分为合作博弈与非合作博弈。 第一节第一节 合作博弈的基本概念合作博

5、弈的基本概念 合作博弈是指参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型。合作博弈强调的是集体理合作博弈强调的是集体理性性,强调效率、公正、公平。强调效率、公正、公平。 合作博弈最重要的两个概念是联盟和分配联盟和分配。每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益。每个参与者从联盟中分配到的收益不小于单独经营所得收益。 合作博弈的基本形式是联盟博弈联盟博弈,它隐含的假设是存在一个在参与者之间可以自由流动的交换媒介(如货币),每个参与者的效用与它是线性相关的。这些博弈被称为“单边支付”博弈,或可转移效用(Transferable Utility ,TU)博弈。 例子：自

6、行车交易博弈例子：自行车交易博弈 非合作博弈解非合作博弈解100，80200，010，170110，90乔伊乔伊米奇米奇 出让出让 保留保留出让出让保留保留合作博弈解合作博弈解 两人达成一致，结成联盟，从而实现双赢。 每人都比非合作博弈时增加10单位的收益。100，80200，010，170110，90乔伊乔伊米奇米奇 出让出让 保留保留出让出让保留保留（1）旁支付旁支付 在合作博弈中，买卖双方的转让支付是与协议联系在一起的，联盟成员用支付货币的方式弥补联盟成员用支付货币的方式弥补参与者放弃单人联盟或其他联盟形式的损失，此参与者放弃单人联盟或其他联盟形式的损失，此种货币支付叫做种货币支付叫做旁

7、支付（旁支付（side paymentside payment）。 以是否与货币联系在一起为标准，分为转移效用与不存在转移效用两类。 旁支付的概念来自于赌博。上例中的合作博弈解依靠协议达成，因此各自的旁支付为110和90。（2）解集解集 即允许旁支付的情况下，在保证每个参与者至少获得非合作博弈收益的基础上，使总收益达到最大值的所有合作博弈联盟。1501005001501005080乔伊的收益乔伊的收益米奇的收益米奇的收益解集解集 解集：在存在两种或两种以上有效配置方案时，所有的有效解的集合。 可行解范围的影响因素： (1)来自其他潜在交易者的竞争压力； (2)公平性； (3)讨价还价能力。（3

8、）可信的承诺可信的承诺 承诺不可信协议不能达成非合作博弈解; 承诺可信协议能达成联盟合作博弈解. 合作博弈的结果必须是一个帕累托改进，博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害。合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，合作之所以能够增进双方的利益，就是因为合作博弈能够产生一种合作剩余。至于合作剩余在博弈各方之间如何分配，取决于博弈各方的力量对比和制度设计。因此，合作剩余的分配既是合作的结果，又是达成合作的条件。 合作博弈的核心问题是参与人如何结盟以及核心问题是参与人如何结盟以及如何重新分配结盟的得益如何重

9、新分配结盟的得益。 下面首先分析联盟联盟的概念，与联盟相关联的是特征函数特征函数。 在1950年到1953年间，纳什发表了四篇有关博弈论的重要文献（纳什，1950a，1950b，1951，1953），文献中很清楚地对合作博弈与非合作博弈进行了界定，他所用的界定条件就是博弈者之间是否具有约束力的协议界定条件就是博弈者之间是否具有约束力的协议。他认为如果一个博弈当中的博弈者能够作出具有约束力的协议，那么此博弈便是一个合作博弈，反之，则称为一个非合作博弈。 根据纳什的这一界定条件，由于合作博弈中存在具有约束力的协议，因此，每位博弈者都能够按自己的利益与其他部分的博弈者组成一个小集团，彼此合作以谋求更

10、大的总支付。我们称这些小集团为联盟（coalition），而由所有博弈者组成的联盟则称为总联盟总联盟（grand coalition）。因此，对有n个局中人参与的博弈，即 ，我们称集合 N 的任何一个子集 S 为一个联盟。, 2 , 1 nN定义定义1.1 设博弈的局中人集合为 ，则对于任意 ，我们称 为 的一个联盟（coalition）。这里，允许取 和 两种特殊情况，我们把 称为一个大联盟。若 ，则 中联盟个数为 。正式的合作博弈的定义是以特征函数特征函数（characteristic function form） 的 形式给出的，简称博弈的特征性，也称联盟型。NNS, 2 , 1 nNS

11、NSnN nnnnnCCC221vN,SNSN定义定义1.2 给定一个有限的参与人集合 ，合作博弈的特征型是有序数对 ,其中特征函数特征函数 是从 到实数集 的映射，即 ，且 。 是 中的联盟 和 博弈时S的最大效用，称为联盟S的特征函数特征函数（characteristic function), 表示联盟中参与人相互合作所能获得的得益（支付）。 之所以称为特征函数，是因为这个合作博弈的性质基本之所以称为特征函数，是因为这个合作博弈的性质基本由由 决定。由此可见决定。由此可见 对合作博弈的重要性对合作博弈的重要性。 特征函数是研究联盟博弈的基础，确定特征函数的过程实际上就是一个建立合作博弈的过

12、程。NvN,v|2NSSNNRNNRvN2:,0)(vNS)(Sv,|SiNiiSN)(Sv)(Sv)(Sv合作博弈的特征函数合作博弈的特征函数例例1 . 设有一个3人合作对策，每个参与人各有两个纯策略。当三人不合作时，其支付见下表。假设采用最稳妥策略，即最坏情况下选择最好，求合作博弈的支付函数. 解：用 表示一个联盟， 表示联盟中参与人的个数。 当 0，自然 ，有 。 当 1， 有3个，以 为例。 当 ，则 。 的策略集合 ， 策略组合 。 与 进行如下矩阵对策： SSSSSSSS ()0v 2S 2S 1,3NS, A BNS( ,),( ,),( ,),( ,)A AA BB AB BN

13、S 上述矩阵对策没有纯策略， 的混合策略是 ， 的混合策略是 。 的均衡值是 。故 。 同理，可以求出 。 当 2， 有3个，以 为例。 当 ，则 。 的策略集合 , 策略组合 。 与 进行如下矩阵对策： S3 1,4 4NS13, 0 , 0 ,44S14 1( 2 )4v ( 1 )1, ( 3 )1vv SS1,2S 1,2S 3NSS( , ),( , ),( , ),( , )AA AB BA BBN S,A BSNS上述矩阵对策有纯策略， 的均衡值是 。故 。 同理，可以求出 。 当 3， 有1个， ，最大的联盟。 的策略空间 。 有 。 至此特征函数的值已全部求出。S3( 1,2

14、 )3v( 1,3 )1, ( 2,3 )1vvSSSSN,3A B()max 2,0,4,2,2,1,3,24v N 显然，合作博弈的特征函数 (characteristic function)是指，对于每一个联盟 (coalition)S (S为N的任意一个子集)，指定一个函数v (S)，用以描述联盟S无需求助于S之外的参与人(NS)所能得到的可传递效用的总量。 在合作博弈中，支付可能是收益，也可能是成本（负效应）。如果这总得益是可以被瓜分的，我们则称它为可转移的（transferable）；反之，则称为不可转移的（non-transferable）。合作博弈的特征函数合作博弈的特征函数

15、合作对策的分类主要是根据合作对策的分类主要是根据特征函数特征函数的性质。的性质。 下面根据特征函数的性质介绍几类特殊的合作对策。1.如果 仅与 的个数有关，则 称作对称博弈。2.如果 ，则 称作常和博弈。3.如果 ， 则 称作简单博弈。例如,在投票博弈中，每个参与人的权重 ， 如果 ，则 称作凸博弈。 )(SvS),(vN),(vN),(vN),(vN( )()()v Sv NSv N0( )1Siv SSN(),1iiw w Qi n 0( )1ii Sii SwQv SwQ( )( )()()v Sv Tv STv ST可传递效用可传递效用 (transferable utility) 为

16、描述n人合作博弈，通常假设合作博弈具有可传递效用; 简单地说，该效用就像货币一样，可以在各参与人之间自由转让. 定义定义1.3 一个支付可转移的联盟型博弈是由一个有限的博弈者集合 和一个定义在集合 的函数 所组成的，而这函数 对集合 当中的每一个可能的非空子集 都会进行赋值，其值为一个实数，我们用 来表示合作博弈，而函数为每一个集合所赋的值则称为S的联盟值。vNSvN,NNv 为了确保每位博弈者都愿意组成总联盟，合作博弈论一般要求支付可转移的联盟型博弈为有结合力的有结合力的：定义定义1.4 一个支付可以转移的联盟型博弈 是有结合力的，当且仅当，对于集合 的每个分割物，即 ，且 ，以下的关系式都

17、成立： vN,N,21mSSSjmjS1mjjSvNv1)()( 根据上述定义，我们可以得知，在一个具有结合力的支付可转移的联盟型博弈中，如果我们把总联盟 分成 m个不相交的小联盟，那么，这m个小联盟的得益的总数是绝不会大于总联盟的得益。由于这些博弈中的支付都是可转移的，因此，总联盟型的情况必定是帕累托最优的。N 在很多情况下，为了使得每位博弈者有更大的愿望组成总联盟，合作博弈论更会要求博弈具有可超加性或是超可加的： 定义定义1.5 在一个支付可转移的联盟型博弈 中，如果对于任意的 ，且 ，有 ，那么，我们称该合作博弈 是超可加的超可加的；如果对于任意的 ，且 ，有 ，那么，我们称该合作博弈

18、是次可加的次可加的；如果对于任意的 ，且 ， 有 ，vN,NTS2,TS)()()(TSvTvSvvN,NTS2,TS)()()(TSvTvSvvN,)()()(TSvTvSvNTS2,TS 那么，我们称该合作博弈 是可加的可加的。 定义定义1.6 在合作博弈 中，若对于任意的 ，满足以下条件： 则称特征函数 具有凸性，相对应的博弈称为凸博弈凸博弈。 从上述定义中可以看出，参与人对某个联盟的边际贡参与人对某个联盟的边际贡献随着联盟规模的扩大而增加献随着联盟规模的扩大而增加。也就是说，在凸博弈中，合作是规模报酬递增的。 显然，特征函数满足凸性的一定满足超可加性。特征特征函数的凸性表示联盟越大，新

19、成员的实际贡献就越大。函数的凸性表示联盟越大，新成员的实际贡献就越大。vN,vN,NTS2,)()()()(TSvTSvTvSvv 上式说明，特征函数只有满足超可加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么，其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。 上式定义的逆命题也是正确的，即： 是一个集合， 是定义在 上的一个非负实值函数。 满足： ，如果 则存在一个 上的合作博弈，使 成为该合作博弈的特征函数。Nvv2N()0v )()()(2121SvSvSSv21SS Nv 对于合作博弈 ，特征函数 满足超加性，自然有： 根据上述不等式，特征函数

20、 分成两种类型： ， 满足 。即大联盟的效用是每个参与人的效用之和。这说明通过联盟并没有创造新的合作剩余，联盟没有价值，这种联盟也不可能维持。这种对策称为非实质性对策，没有研究价值，不是这不是这里研究的范畴。里研究的范畴。 对于非实质性对策，有 ，如果。( , ),1,2,N v Nnvvv ( )(1)( 2, , )(1)( 2)( 3, , )v Nvvnvvvn1()niv i 1()nivi( )v N1212()( )( )v SSv Sv S21SS ， 满足 。即大联盟的效用大于每个参与人的效用之和。这说明通过联盟创造了新的合作剩余，联盟有意义，这种联盟能否维持，取决于如何分配

21、合作剩余，使每个参与人的支付都有改善。这种对策称为实质性对策。 v( )v N1()niv i定义定义1.7 一个合作博弈 ，若特征函数满足下面的两个条件： 则称该博弈为 标准化博弈。 标准化博弈主要是为了简化相关证明过程而假设的，他们要求单个参与人不会产生任何得益，而大联盟所产生的得益标准化为1。vN,niiv,2 , 1, 0)(1)(Nv)1 ,0()1 ,0(分配分配 所谓分配就是博弈的一个 维向量集合，之所以 是 维向量，是由于每个参与人都要得到相应的分配。 维的分配向量称为博弈的“解”。定义定义1.8 对于合作博弈 ，对每个参与人 ，给予一个实值参数 ，形成 维向量 且其满足： 则

22、称 是联盟 的一个分配方案分配方案。nnnn(, ),1,2,N v NniNix1( ,)nxxx1(),()niiixv ixv NxS 分配的定义中， 是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约束。如果 ，那么，参与人 是不可能参加联盟的。 是基于集体理性，每个参与人的分配之和不能超过集体剩余 。另外，若 没有全部被分配，显然 x 不是一个帕类托最优的分配方案，不会被参与人所接受。 ()ixv i)(ivxii1()niixv N()v N()v N在例1分配中，分配显然不是一个，而是无限个，无限个分配形成一个分配集合。 对于实质博弈，其分配总是有无限个。例

23、如，对于实质博弈 ，由于存在无限个正向量 ，满足 。显然如下的 都是分配，其中 。用 表示一个博弈 的所有分配方案组成的集合。 (, )N v()uv N 1()0nivi12( ,)nuu uu12,nuuuu 1( ,)nxxx,1iixviuin )(vEv9 设 的两个分配 和 ， 是一个联盟。如果分配方案 和 满足 （i） ， ； （ii） 。 则称分配方案 在 上优超于 ，或称分配方案 在 上劣于 ，记为 。 如果分配方案 在 上优超于 ，则联盟 会拒绝分配方案 ， 方案得不到切实执行。因为从 到 ，中的每个参与人的收益都得到改善， 创造的剩余 又足以满足他们在 中的分配。 )(v

24、ExxxxyyyyyyyySSSSSSSxxxiiyx Si)(SvxSiiyxS( )v S在优超关系中，联盟 具有以下的特征：1.单人联盟不可能有优超关系。2.全联盟 上也不可能有优超关系。 因此，如果在 上有优超关系，则 。 3.优超关系是集合 上的序关系，这种序关系一般情况下不具有传递性和反身性。4.对于相同的联盟 ，优超关系具有传递性，即 ， ，则有 。 5.对于不同的联盟 ，优超关系不具有传递性。 NSSSS21Sn)(vESxySyzSxz 例例. 假设有五个人A、B、C、D、E，决定合资建厂。每个人或是以人力资本投资，或是以资金投资。经过认真的可行性研究，建成后的合资公司年利润

25、为100单位（单位：10000美元）。现在的问题是如何将这100单位的利润在五个人中合理地分摊？ 对于这个问题，从表面上来看将总利润进行平均分配（即每人20单位）似乎是一个合理的分配方案。但通过进一步的分析表明，如果D和和E单独单独组建联盟进行合作建厂，其年利润为45单位，大于D和E在大联盟（即五个人合作建厂）所分配到的40单位。同样，A、B、C发现发现，如果他们三人单独建厂，只能实现年利润25单位。这样，A、B、C自然希望D和E留在大联盟中。因此，他们决定分给D和E 46单位，而把剩下的54单位在A、B、C三人中平衡。显然，这样还是不行，因为C、D、E发现他们三人单独建厂的年利润为70单位，

26、大于在大联盟中得到的64单位（46+18），而A、B没有足够的资金自行建厂。因此，A和B不得不分给C、D、E 71单位，而把剩下的29单位在A和B中平分。如果C、D、E将71单位利润平分的话，又会产生另一个问题。由于B、D、E三人合作建厂的年利润为65单位，就使得刚才那个分配又变得不可行。那么，它们该怎么办呢？为了简单起见，我们将此博弈的特征函数形式列在表1中。该表列出了每个可能的联盟可能获得的总利润。S)(SVSS101,5201,2,4353,4,570202,3151,2,5401,2,3,460302,4251,3,4401,2,3,565452,5301,3,5451,2,4,575

27、5103,4301,4,5551,3,4,5801,203,5352,3,4502,3,4,5901,354,5452,3,5551,2,3,4,51001,4151,2,3252,4,5650表表1 ： 各合作方案下联盟获得的总利润各合作方案下联盟获得的总利润 通过观察表1，我们就会发现，当任意两个联盟的交集为空集的时候，这两个联盟中的所有参与人组成的新联盟的总利润总是不小于原先的两个联盟的利润之和。因此，这种博弈就是前面我们所讨论的超可加博弈。 第二节第二节 核心与稳定集核心与稳定集 下面，我们将首先介绍个体理性和整体理性，然后再分别介绍合作博弈的两个解概念-核心核心(core)和稳定集和

28、稳定集。 一、个体理性和整体理性一、个体理性和整体理性 当一个博弈具有超可加性，那么便只有组成总联盟才能最优化所有博弈者的总得益。在一个支付可转移的联盟型博弈中，我们可以用一个支付向量 来代表瓜分这总得益的方案，而这向量当中的 则是博弈者 组成联盟后所分得的支付(分配）。我们用 表示在这个支付向量中，每位博弈者所能获得的支付的总和。),(21nixxxxx)(Nxixi 一个能为所有博弈者接受的支付向量必定既符合联盟的整体理性，又符合每位参与联盟的博弈者的个体理性. 同时符合整体理性和个体理性的支付向量同时符合整体理性和个体理性的支付向量则称为一个分配分配或有效的分配有效的分配。 下面我们对整

29、体理性和个体理性给出如下定义： 定义定义2.1 在一个支付可转移的联盟型博弈中，支付向量是 符合整体理性的，当且仅当，每位博弈者所分得的支付的总和等于总联盟的价值，即: 由于所有博弈者的总支付实现了最优化，因此，我们称之为整体理性或整体最优整体理性或整体最优。),(21nxxxxniiNiiNvxxNx1)()( 定义定义2.2 在一个支付可转移的联盟型博弈 中，支付向量 是符合个体理性的，当且仅当，每位博弈者所分得的支付都比各自为政时高，即在一个支付可转移的联盟型博弈 中，支付向量 称为一个分配或有效的分配，当且仅当，它是符合个体理性和整体理性的。 定义定义2.3 一个支付可转移的联盟型博弈

30、的分配集 定义为： 且对于 ，都有 。),(21nixxxxxvN,Niivxi),(),(21nixxxxx( )I v( )()()nI vxR x Nv NiN )( ivxivN,二、核心二、核心 （Core）与稳定集）与稳定集 尽管可行分配集合 中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所接受的 。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。 在一个 人合作博弈 中，全体优分配优分配方案方案形成的集合称为博弈的(core)，记为 。显然有 。)(vEn(, )N v)(vC( )( )C vE v 1. 核心的

31、概念核心的概念 定义定义2.4 一个支付可转移联盟型博弈的核心 是一个集合，当中包含所有能满足以下两个条件的支付向量：（1）（2）根据上述定义，核心不仅要满足整体理性，还要满足集合N中每个小联盟S的“理性”。否则，联盟S的成员的整体支付便没有进行最优化。也就是说，只要通过脱离总联盟，然后成立新的联盟S，那么新联盟S的成员便能够瓜分一个比他们的分配的总和大的联盟价值。 核心是一个不仅能满足个体和整体理性，而且能满足核心是一个不仅能满足个体和整体理性，而且能满足每个联盟的每个联盟的“理性理性”的集合。的集合。)(vC)()(NvNxNSSvSx),()( 一般来说，核心是一个集合。可能结果是：无穷

32、集，唯一集，空集。 核心的理解是核心的理解是，如果合作博弈的一个可行分配 x 不在核心中，那就存在一个联盟S, 该联盟中的参与人可通过更好地合作，并在他们之间分配价值v ( S)，使得该分配结果严格优于x。 (1)通常说来，合作博弈的核包括所有能使联盟保持稳定的结盟方式，在这种结盟状态下，任何参与者都不会因脱离现有联盟组成新的联盟（包括单人联盟）而获益; (2)合作博弈的核包含所有使团体中的任何成员都不能从联盟重组中获益的配置方案，囊括了所有不被占有的配置方式; (3)合作博弈的核的数量是任意的; (4)空核博弈：不存在核的联盟结构的博弈问题叫做的空核博弈。 在合作博弈中，用核心代替分配具有明

33、显的优点，即 的稳定性。稳定性。对于 中的每一个分配，每个联盟都没有反对意见，都没有更好的分配，每个分配都可以得到执行。不过，用 代替 也有致命的缺陷，即 可能是空集，而 。 ( )C v( )C v( )C v( )C v( )E v( )E v 设 是个0-1简单对策，若存在一个参与人 ，满足 ，则 称作一个否决人。 简单对策 中， 充分必要条件是 中存在一个否决人。(, )N v(, )N v( )C v i()0v NiNi2分配方案 在核心 中的充要条件是： （i） ， ， (ii) 。证明 如果 ， 满足（i）、(ii)，则 不可能被优超，即 。反证法，设存在 ，使 。根据优超的定

34、义，有:则有 ，矛盾。如果 ， 不满足 (ii)，则 一定被优超，即 。),(1nxx x)(vC)(SvxSiiNS )(1Nvxnii( )xE vxx( )xC vSSyxiixySi()iiSyv S( )( )iii Si Sv Sxyv S( )xE vxx( )xC v说明： 1.核心 是 中的一个闭凸集。 2.若 ，则将 中的向量 作为分配， 既满足个人理性，又满足集体理性。 3.用核心作为博弈的解，其最大缺陷是 可能是空集。 )(vC)(vC)(vC( )E v( )C v xx例子例子：房地产联盟的收益 乔伊要把两块以上的地聚集起来开发，诺琳N、皮特P、昆西Q各有一块地，可

35、能有下面的联盟：联盟联盟收益收益1（NPQ）（11）2（NP）（）（Q）（8）（）（3）3（NQ）（）（P）（4）（）（3）4（PQ）（）（N）（4）（）（3）5（N）（）（P）（）（Q）（3）（）（3） （3）核核2. 核心的应用核心的应用核心作为合作博弈其中一个最基本的解法，其应用范围也非常广泛。 例例1：三人社会合作：三人社会合作我们用 代表这三人的集合，如果三人同心协力地合作，并组成一个单一联盟，那么，他们便能把这个社会的总利益最优化，并通过协同效应创造出30个单位的总得益。而如果只有其中二人合作并组成联盟，而剩下的一人独自为政，那么这二人也能创造出 个单位的利益。但 个单位的利益只供

36、那二人分享，而3 , 2 , 1N)30,12(, 剩下的一位在独自为政的情况下只能创造出6个单位的得益。现在把以上的三人社会转换为一个支付可转移的联盟型博弈： ；当 其中， 则代表联盟S的成员数目。由于这个博弈中共有三位博弈者，因而核心是一个由非负的支付向量 所组成的集合。在博弈中，核核心心要满足整体理性，故此 ，同时，核心又要满足由一位或两位博弈者所组成的小联盟S的“理性”，故此： ， 当 ；以及 ，当 。)(2;, 6)(; 0)(SvSNiivv时，当30)(,3NvS时S),(321xxx30)(Nx)(Sx2S6)(Sx1S当 ，核心便是由无数个支付向量所组成，即 也就是说，每位博

37、弈者至少也可以获得独自为政时的支付，但最多只可以得到整体合作下和其中二人合作下的利益的差。当 ，核心便只包含一个支付向量（10,10,10），就是三人平分整体合作下的利益。 当 ，核心便是空的，也就是说，这个社会并不存在属于核心的合作方案。20NiiiaNiaaaa12,24,0),6,6,6(3212020例例2: 假想的联合国安全理事会投票，超过两票算通过。该博弈的特征函数为:而对所有其他的 ， 。 应用定理3，有 ，对各个联盟有 由 ， ， ， 推得 ， ， ，而用 ， ，又得到 和 ，所以，核心是1) 5 , 4 , 3 , 2 , 1 () 5 , 4 , 2 , 1 () 5 ,

38、3 , 2 , 1 ()4 , 3 , 2 , 1 () 5 , 2 , 1 ()4 , 2 , 1 () 3 , 2 , 1 (vvvvvvvS0)(Sv151iix5 , 4 , 3 , 2 , 1,0ixi1321xxx1421xxx1521xxx151iix1321xxx04x05x1321xxx04x05x1421xxx03x05x03x121 xx( )( ,1,0,0,0):01C vaaa例例3: 设3人合作博弈 的特征函数如下： ， ， ， ， 求其核心 。解解 由核心定义，若 ，则它必满足 解此不等式组，得v0)( iv3,2, 1i32)2 , 1(v127)3 , 1(

39、v21)3 , 2(v1)3,2, 1(v)(vC)(),(321vCxxxx3 , 2 , 1,013212132127313221ixxxxxxxxxxi10003213131252211xxxxxx例例4: 考虑如下的合作博弈， ，特征函数如下： ， ； 。解线形不等式组： 。该不等式组无解，即 上面三个例子说明了求解核心的方法。1213231230,1,2,31111ixixxxxxxxxx ( )C v (, ),1,2,3N v N ()0vi3 ,2, 1i ()1, 23vSS定理定理3:对于 人的联盟博弈，核心 非空的充分必要条件是线性规划 有解。 ，( )C vn( )P(

40、 )P)(min1Nvxnii1( ).()ii Sniixv Sstxv NNS 定理的直观意义很明显，线性规划（p）若有解，则最优解一定属于 ；若 ，则 中的每个向量都是可行解，线性规划（ P ）有最优解。)(vC( )C v ( )C v核仁核仁 为评估 对 满意性，定义一个如下被称作超出或盈超出或盈余余的概念： 的大小反映了 对 满意性。 越大， 对越不满意，因为 中所有参与人的分配之和远没有达到其所创造的合作剩余 ； 越小， 对 越满意，当 为负值时， 中所有参与人不但分配了其所创造的合作剩余 ，还分配了其他联盟所创造的价值。 SSSSSSxxxx( ,)()iiSe S xv Sx

41、( , )e S x( , )e S x( , )e S x( , )e S x( )v S( )v S 对于同一个 ， 共有 个，可以表示为 。故可以计算出 个 。联盟对 的满意性取决于 中的最大最大的 ，故可以对 个 由大到小排列，得到一个 的向量：其中 。 联盟对 的满意性取决于 的大小， 越小，联盟对 越满意。xxS2n,1,2,2njSj 2n(, ),1,2,2nje S x j x(, )je Sx1,2,2nj 2n(, )je S x2n122( )( ),( ),( )nxxxx122( )(, ),1,2,2 ,( )( )( )nnjjxe Sxjxxx( )x( )x

42、x 对于两个不同的分配 ，分别计算出 。如果是 小的，则联盟对 的满意性大于联盟对 的满意性，自然 优于 。当然这种向量大小的比较不同于数字的比较，是采用字典序的比较方法采用字典序的比较方法。 字典序的比较方法的比较方法如下：字典序的比较方法的比较方法如下： 对于向量 和 ，存在一个下标 ，使得 ， ，则称 字典序小于 ，用符号表示 。 有了上述的定义，就可以给出核仁核仁(Nucleolus）的定义了。xy、( )xy、 ( )xxyyx122( )( ),( ),( )nxxxx122( )( ),( ),( )nyyyyk( )( ),11jjxyjk( )( )kkxy( )x( )y(

43、 )( )Lxy 对于合作博弈 ，核仁核仁 是一些分配的集合，即 ，使得任取一个 ， 都是字典序最小的，即 。 对于合作博弈 ，其核仁 ，且 只包含一个元素 。 对于合作博弈 ，如果核心 ，则有 证明 用反证法。设存在一个分配 。根据核心的性质，由 可知：必存在一个联盟 ，满足 ，由此可知 。 设 。 是所有 中最大的，故有 。 (, )N v(, )N v(, )N vNN( )NE vxN( ) :( ),( )( )LNxE vyE vyxxy N xC NC,xN xCxCS( )ii Sxv S( , )( )0ii Se S xv Sx122()(),(),()nxxxx1( )

44、x(,),1, 2, 2nje Sxj 1()(,)()0iiSxe Sxv Sx( )x 由 可知，存在分配 。根据分配的性质，任取一个 ，有 ，由此可知 满足 。 ， ， ； ， ， 。这与 矛盾。定理得证。C yC,1, 2 , 2njSj (,)()0jjjii Se Syv Sy122( )( ),( ),( )nyyyy( )0,1,2,2njyjxN122( )( ),( ),( )nxxxx1( )0 xyC122( )( ),( ),( )nyyyy1( )0y( )( )Lxy 合作博弈存在多种解算方法,包括核心法、核仁法、夏普里法等，定理4及定理5表明，只有核仁法是一定有

45、解且存在唯一的解。 例例5 考虑如下的合作博弈， ，特征函数如下： ； ； 。求该博弈的核仁。 解 先求出该博弈的核心，再求核仁。根据核心的条件， 充分必要条件：解此不等式组，得到 。(, ),1,2,3N vN ( 1 )4, ( 2 )( 3 )0vvv( 1,2 )5, ( 1,3 )7, ( 2,3 )6vvv( 1,2,3 )10v123( ,)( )xx x xC v11213231234,0 ,2,357610ixxixxxxxxxxx( )(4,6, ):35C vx xx ，故有 。下面开始求 。对于核心 ，开始求 ， 。 ，有 440； ，有 0 ； ，有 0 ； ，有 5

46、 ； ，有 7 ； ，有 6 0； ，有 10100； 当 ， 。上式在 达到，故有 。该结果验证了 ， 。 ( )C v NCN( )(4,6,) : 35C vx xx( , )( )ii Se S xv Sx( )xC v 11S 1(, )e S x 22S 2(, )e Sx(6) x6x 33S3(, )e S x41,2S 51,3S 62,3S 71,2,3S 7(, )e Sx6(, )e Sx5(, )e Sx4(, )e Sx( ) xx4(6)x5x4x(6) xx35x71135( )minmax (, )minmax5,3jjxxe S xxx 4x (4,6,)

47、:4(4, 2, 4)x xxNN 1N3x 3、稳定集、稳定集（Stable Sets）的定义）的定义在一个 人博弈中，联盟 对于一个任意的分配 是有效的，当且仅当，这个联盟的价值高于他们在 分配下的支付的总和，即 。也就是说，如果联盟 对于 分配是有效果的，那么分配 便是不稳定的。有了 “ 有效有效果果”的概念，我们便可以介绍占优分配的概念：定义定义2.5 在一个支付可转移的联盟性合作博弈中，分配x通过联盟S 占优分配y，当且仅当： 且 ， 当严格不等式成立时称分配x通过联盟S严格占优于分配y。 nNS xxSiixSv)(Sxx()()x Nv Niixv 定义定义2.6 支付可转移的联

48、盟性合作博弈的解集符合内内部稳定性部稳定性，如果该集合内的任何分配都不会通过联盟S 占优于该集合内的其他分配。也就是说内部稳定性要求联盟内部的任意两个分配不存在占优关系。 定义定义2.7 支付可转移的联盟性合作博弈的解集符合外外部稳定性部稳定性，如果对于集合外的任意分配，联盟S都存在某配置占优于该集合外的分配。 定义定义2.8 在支付可转移的联盟性合作博弈中，集合X称为稳定集稳定集，当且仅当该集合既符合内部稳定性内部稳定性，也符合外部稳定性外部稳定性。 第三节第三节 夏普利值及其应用夏普利值及其应用 分配分配是合作博弈最重要的概念，但遗憾的是在一个博弈中，分配有无限个，且许多根本就得不到执行。

49、 合作博弈最困难也最有挑战性之处在于建立一个统一的“解”的概念，即从各种各样不具有良好性质的解中挑选唯一的分配或分配方案。不难看出，这几乎是不可能也没有必要的事情。 合作博弈与非合作博弈很大的不同之处在于合作博弈合作博弈与非合作博弈很大的不同之处在于合作博弈没有一个统一的解的概念，因为没有哪个解能够符合所有没有一个统一的解的概念，因为没有哪个解能够符合所有人对人对“公平公平”的理解。的理解。 根据前面的分析，我们知道博弈的核心可能是空集，而且如果不是空集，核心分配也很可能不唯一。合作博弈的核心可能结果可能是空的或非常之大，这限制了核心作为合作博弈的解的应用 我们希望导出一个具有普遍意义的解概念

50、,Shapley 值是其中重要的解概念之一. 随着合作博弈论的发展，现在已经有很多具有唯一解的概念，称为值称为值（Values）,其中最重要的就是夏(沙)普利值。合作博弈在理论上的重要突破及其以后的发展在很大程度起源于夏普利(Shapley)提出的夏普利值的解的概念及其公理化刻画。 Shapley值是一个很直观的解解的概念，参与人按照Shapley值进行分配。 一、夏普利值一、夏普利值(Shapley Values)夏普利值是由夏普利提出的，最初只是应用在支付可转移的情况下，其后由夏普利扩展到支付不可转移的情况，这里我们只介绍支付可转移的沙普利值。由于夏普利是建立在几个公理上，因此，在介绍夏普