合作联盟博弈ppt课件.ppt

1、博弈论 经济与管理学院经济与管理学院 刘洋博士刘洋博士 1合作博弈 （ COOPERATIVE GAMES)2 合作博弈合作博弈COOPERATIVE GAMESn熊、狼、狐狸一起抓了一只兔子，民主协商如何分熊、狼、狐狸一起抓了一只兔子，民主协商如何分配。狐狸对熊说：平均分只能各得配。狐狸对熊说：平均分只能各得1/3，这样吧，我，这样吧，我们俩联合起来，平分如何？熊要答应，狼急了，于们俩联合起来，平分如何？熊要答应，狼急了，于是狐狸对狼说：怎么样，我和熊联合起来可以让你是狐狸对狼说：怎么样，我和熊联合起来可以让你什么也得不到，我可以和你合作，不过我要什么也得不到，我可以和你合作，不过我要3/4

2、。狼。狼感激的点头，熊琢磨过味来，对狼说：别听那个两感激的点头，熊琢磨过味来，对狼说：别听那个两面三刀的，和我合作，我给你面三刀的，和我合作，我给你1/3。狐狸见势不妙，。狐狸见势不妙，对狼说：别，我给你对狼说：别，我给你2/3，我只要，我只要1/3。狼成了抢手。狼成了抢手货，正得意，没留神狐狸和熊又开始嘀咕起来，有货，正得意，没留神狐狸和熊又开始嘀咕起来，有再次把自己晾在一边的不妙趋势，连忙钻去继续讨再次把自己晾在一边的不妙趋势，连忙钻去继续讨价还价。结果呢？价还价。结果呢？3n如果在实际博弈问题中，具有有力的保障使局中人能够进行协商、谈判，联合选择行动，共同分享利益，我们就面对一个合作博弈

3、问题。本章通过合作博弈模型的介绍，讨论在合作博弈中，局中人如何进行协商谈判、结成联盟及分享利益。n1、联盟博弈、联盟博弈n2、联盟博弈的分配、联盟博弈的分配n3、核和稳定集、核和稳定集n4、沙普利值、沙普利值4导论导论先回忆一下囚徒困境的例子：先回忆一下囚徒困境的例子： 在囚徒困境中，还有另外一个策略组合在囚徒困境中，还有另外一个策略组合，该，该组合为参与人带来的支付是组合为参与人带来的支付是。由。由到到，每个参与人的支付都增加了，即得到一个帕累托改进。每个参与人的支付都增加了，即得到一个帕累托改进。 坦白坦白抵抗抵抗坦白坦白-8，-80，-10抵抗抵抗-10，0-1，-15导论 构不成一个均

4、衡是基于参与人的个人理性。在参构不成一个均衡是基于参与人的个人理性。在参与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机行为谋取超额收益通过投机行为谋取超额收益1。如果两个参与人在博弈之前，。如果两个参与人在博弈之前，签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第三方支付价值大于参与人双方向第三方支付价值大于1的保证金；如果谁违背了的保证金；如果谁违背了这个协议，则放弃保证金。有了这样一个协议，这个协议，则放弃保证金。有了这样一个协议，就称为一个均

5、衡，每个人的收益都得到改善。就称为一个均衡，每个人的收益都得到改善。 上述分析表明，通过一个有约束力的协议，原来不能实现上述分析表明，通过一个有约束力的协议，原来不能实现的合作方案现在可以实现。这就是合作博弈与非合作博弈的区的合作方案现在可以实现。这就是合作博弈与非合作博弈的区别。二者的主要区别在于人们的行为相互作用时别。二者的主要区别在于人们的行为相互作用时,当事人是否达当事人是否达成一个具有约束力的协议。如果有成一个具有约束力的协议。如果有,就是就是合作博弈合作博弈；反之；反之,则是则是非合作博弈非合作博弈。6合作博弈的概念及其表示合作博弈的概念及其表示 合作博弈，非合作博弈的对称，一种博

6、弈类合作博弈，非合作博弈的对称，一种博弈类型。参与者能够联合达成一个具有约束力且可强型。参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型。制执行的协议的博弈类型。合作博弈强调的是集合作博弈强调的是集体理性体理性,强调效率、公正、公平。强调效率、公正、公平。 合作博弈最重要的两个概念是合作博弈最重要的两个概念是联盟和分配联盟和分配。每个参与者从联盟中分配的收益正好是各种联盟每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益形式的最大总收益,每个参与者从联盟中分配到的每个参与者从联盟中分配到的收益不小于单独经营所得收益。收益不小于单独经营所得收益。 7合作博弈的概念及其表示合作

7、博弈的概念及其表示 合作博弈的结果必须是一个帕累托改进，合作博弈的结果必须是一个帕累托改进，博弈双方博弈双方的利益都有所增加，或者至少是一方的利益增加，而另的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害。一方的利益不受损害。 合作博弈采取的是一种合作的方式，合作之所以能合作博弈采取的是一种合作的方式，合作之所以能够增进双方的利益，就是因为合作博弈能够产生一种够增进双方的利益，就是因为合作博弈能够产生一种合合作剩余作剩余。至于合作剩余在博弈各方之间如何分配，取决。至于合作剩余在博弈各方之间如何分配，取决于博弈各方的力量对比和制度设计。于博弈各方的力量对比和制度设计。 合作博弈

8、的核心问题合作博弈的核心问题是参与人如何结盟以及如何重是参与人如何结盟以及如何重新分配结盟的支付。新分配结盟的支付。 8合作博弈的概念及其表示合作博弈的概念及其表示 在在 人博弈中，参与人集用人博弈中，参与人集用 表示，表示， 的任意子集的任意子集 称为一个称为一个（coalition）。）。 空集空集 和全集和全集 也可以看成是一个联盟，当然单点集也可以看成是一个联盟，当然单点集 也是一个联也是一个联盟盟。 给定一个给定一个 人博弈，人博弈， 是一个联盟，是一个联盟， 是指是指 和和 的两人博弈中的两人博弈中 的最大效用，的最大效用， 称为称为联盟联盟 的的（characteristic f

9、unction）。）。 规定规定 。根据定义，。根据定义， 表示参与人表示参与人 与全体其他人博弈时的与全体其他人博弈时的最大效用值，表示为最大效用值，表示为 。 用用 表示参与人集为表示参与人集为 ，特征函数为，特征函数为 的的合作博弈合作博弈，其中，其中 是定是定义在义在 上的实值映射。上的实值映射。 在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的行在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的行动。动。 有时被解释为联盟有时被解释为联盟 独立于联盟独立于联盟 的行动可保证的最的行动可保证的最大支付大支付 。n,2, 1nN NSSSSSSNNin)(Sv)(Sv)

10、(Sv,|SiNiiSN0)(v)(ivi)(iv),(vNvv2NSN 9合作博弈的概念及其表示合作博弈的概念及其表示 合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。n如果 仅与 的个数有关，则 称作对称博弈对称博弈。n如果 ，则 称作常和博弈常和博弈。n如果 ，则 称作简单博弈简单博弈。例如，例如，在投票博弈中，每个参与人的权重 ， n如果 ，则 称作凸博弈凸博弈。 )(SvS),(vN),(vN),(vN),(vN( )()()v Sv NSv N0( )1Siv SSN(),1iiw wQi n 0( )1ii Sii SwQv SwQ( )(

11、)()()v Sv Tv STv ST10合作博弈的概念及其表示合作博弈的概念及其表示 之所以称为特征函数，是因为这个合作博弈的性质基本由 决定。由此可见 对合作博弈的重要性。 设 是参与人集合上 的特征函数，则有如下的超超可加性可加性：对于联盟 和 ，如果 ，则vvvvN1S2S21SS)()()(2121SvSvSSv上式说明，特征函数只有满足超加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么，其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。11n例：例： 局中人局中人1（卖主）要把一件物品卖掉，局中人（卖主）要把一件物品卖掉，局中人2和和3（买主

12、）分别出（买主）分别出价价9元和元和10元。如果局中人元。如果局中人1将物品卖给局中人将物品卖给局中人2的要价是的要价是 x 元，则局中元，则局中人人2赢利赢利 9-x 元。联盟元。联盟 的总收益为的总收益为9元。类似，联盟元。类似，联盟 的总赢的总赢利为利为10元。于是有元。于是有 。n另一方面，单个局中人或者两个买主在一起都不可能赢利，另一方面，单个局中人或者两个买主在一起都不可能赢利，即即 ， 。n当三个局中人在一起交易时，局中人当三个局中人在一起交易时，局中人1显然要把物品卖给局中人显然要把物品卖给局中人3，从而，从而 v(1,2,3)=10， 显然满足超可加性，于是我们建立了联盟博弈

13、显然满足超可加性，于是我们建立了联盟博弈 。n特征函数特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。题需要仔细分析，甚至需要一些专业知识。2, 13,1103 , 1,92, 1vu03 , 2 viv3,2,1i)(vvN,12由策略型博弈导出特征函数型博弈由策略型博弈导出特征函数型博弈nV()=0nV(1)=0nV(2)=5nV(1,2)=10局中人2LR局中人1U

14、-1，25，5D0，100，10最小最大值法：最小最大值法：联盟外局联盟外局中人将采取行动使该联盟中人将采取行动使该联盟的总和收益最小（极度悲的总和收益最小（极度悲观），联盟选择策略观），联盟选择策略最大化这些最小值。最大化这些最小值。13例：垃圾博弈分析博弈局势例：垃圾博弈分析博弈局势n在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。n记Vn(n=0,1, ,7)表示任意n个局中人组成的特征函数值，在合作博弈条件下，有：V V0 0=V(=V()=0 )=0 V V1 1=-6=-6V V2 2=-5=-5 V V3 3=-4=-

15、4，V V4 4=-3=-3，V V5 5=-2=-2V V6 6=-1=-1， V V7 7=-7=-714合作博弈的概念及其表示合作博弈的概念及其表示例：设有一个例：设有一个3人合作对策，每个参与人各有两个纯策略。人合作对策，每个参与人各有两个纯策略。当三人不合作时，其支付见下表。假设采用最稳妥策略，当三人不合作时，其支付见下表。假设采用最稳妥策略，即即最坏情况下选择最好最坏情况下选择最好，求合作博弈的支付函数，求合作博弈的支付函数 15合作博弈的概念及其表示合作博弈的概念及其表示解：用 表示一个联盟， 表示联盟中参与人的个数。 当 0，自然 ，有 。 当 1， 有3个，以 为例。 当 ，

16、则 。 的策略集合 ， 策略组合 。 与 进行如下矩阵对策： SSSSSSSS ()0v 2S 2S 1,3NS, A BNS( ,),( ,),( ,),( ,)A AA BB AB BNS16合作博弈的概念及其表示合作博弈的概念及其表示 上述矩阵对策没有纯策略， 的混合策略是 ， 的混合策略是 。 的均衡值是 。故 。 同理，可以求出 。 当 2， 有3个，以 为例。 当 ，则 。 的策略集合 , 策略组合 。 与 进行如下矩阵对策： S3 1,4 4NS13, 0 , 0 ,44S14 1( 2 )4v ( 1 )1, ( 3 )1vv SS1,2S 1,2S 3NSS( , ),( ,

17、 ),( , ),( , )AA AB BA BBN S,A BSNS17合作博弈的概念及其表示合作博弈的概念及其表示上述矩阵对策有纯策略， 的均衡值是3 。故 。 同理，可以求出 。 当 3， 有1个， ，最大的联盟。 的策略空间 。 有 。 至此特征函数的值已全部求出。S( 1,2 )3v( 1,3 )1, ( 2,3 )1vvSSSSN,3A B()max 2,0,4,2,2,1,3,24v N?)(Nv18分分 配配 所谓分配就是博弈的一个 维向量集合，之所以 是维向量，是由于每个参与人都要得到相应的分配。 维的分配向量称为博弈的“解”。 对于合作博弈 ，对每个参与人 ，给予一个实值参

18、数 ，形成 维向量 且其满足： 则称 是联盟 的一个分配方案。分配方案。nnnn(, ),1,2,N v NniNix1( ,)nxxx1(),()niiixv ixv NxS19分配分配 分配的定义中， 是基于个人理性个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约束参与约束。如果 ，那么，参与人 是不可能参加联盟的。 是基于集体理性集体理性，每个参与人的分配之和不能超过集体剩余 。另外若 没有全部被分配，显然 不是一个帕累托最优的分配方案，不会参与人所接受。 ()ixv i)(ivxii1()niixv N()v N()v Nx20 在前面的例子分配中，分配显然不是一个，

19、而是无限个，无限个分配形成一个分配集合。 对于实质博弈，其分配总是有无限个。例如，对于实质博弈 ，由于存在无限个正向量 ，满足 。显然如下的 都是分配，其中 。用 表示一个博弈 的所有分配方案组成的集合。 (, )N v()uv N 1()0nivi12( ,)nuu uu12,nuuuu 1( ,)nxxx,1iixviuin )(vEv分配分配21分配中的优超分配中的优超 设 的两个分配 和 ， 是一个联盟。如果分配方案 和 满足 （i） ， ； （ii） 。 则称分配方案 在 上优超于 ，或称分配方案 在 上劣于 ，记为 。 如果分配方案 在 上优超于 ，则联盟 会拒绝分配方案 ， 方案

20、得不到切实执行。因为从 到 ，中的每个参与人的收益都得到改善， 创造的剩余 又足以满足他们在 中的分配。 )(vExxxxyyyyyyyySSSSSSSxxxiiyx Si)(SvxSiiyxS( )v S22分配中的优超分配中的优超在优超关系中，联盟 的特征：1.单人联盟不可能有优超关系。2.全联盟 上也不可能有优超关系。 因此，如果在 上有优超关系，则 。 3.优超关系是集合 上的序关系，这种序关系一般情况下不具有传递性和反身性。4.对于相同的联盟 ，优超关系具有传递性，即 ， ，则有 。 5.对于不同的联盟 ，优超关系不具有传递性。 NSSSS21Sn)(vESxySyzSxz23核心核

21、心 尽管可行分配集合 中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所接受的 。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。 在一个 人合作博弈 中，全体优分配方案形成的集合称为博弈的(core)，记为 。显然有 。)(vEn(, )N v)(vC( )( )C vE v24核心核心说明： 1.核心 是 中的一个闭凸集。 2.若 ，则将 中的向量 作为分配， 既满满足个人理性，又满足集体理性足个人理性，又满足集体理性。 3.用核心作为博弈的解，其最大缺陷是 可能是空集。 )(vC)(vC)(vC( )E v( )C v xx

22、25核心核心 分配方案 在核心 中的充要条件是： （i） ， ， (ii) 。证明 如果 ， 满足（i）、(ii)，则 不可能被优超，即 。反证法，设存在 ，使 。根据优超的定义，有:则有 ，矛盾。如果 ， 不满足 (ii)，则 一定被优超，即 。),(1nxx x)(vC)(SvxSiiNS )(1Nvxnii( )xE vxx( )xC vSSyxiixySi()iiSyv S( )( )iii Si Sv Sxyv S( )xE vxx( )xC v26核心核心对于 ，存在联盟 ，有 ，则定义 ，定义 ，使得 在 中平均分配， 在 中平均分配，从而得到一个新的分配 如下：显然如此定义得向

23、量 是个分配，且有 。 ( )xE vSS( )ii Sxv S( )0ii Sv Sx ()()()0iN Sv Nv SviNS1(,)nyyy ,(),iixiSSyviiSnS 1(,)nyyySyx27n例例2 设有三人联盟对策，其特征函数设有三人联盟对策，其特征函数 n ， n若若 由定理由定理1 易知易知,该博弈的核由下面不等式组确定：该博弈的核由下面不等式组确定：n易知易知 ， ， ， 。n故该博弈的核故该博弈的核 n其图形为单纯形其图形为单纯形 内以内以 n 为顶点的四边形，如图为顶点的四边形，如图1所示。所示。0321vvv53 ,2, 1, 33 , 1, 13 ,2,4

24、2, 1vvvv0,5134321321323121xxxxxxxxxxxx41x22x13x0, 5),(321321321xxxxxxxxxxA) 1 , 2 , 2(),0 , 2 , 3(),0 , 1 , 4(),1 , 0 , 4(10 , 20 , 40 , 5),()(321321321xxxxxxxxxvc)(),(321vcxxxx若28图图 1(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)(4,0,1)29核心核心练习练习1：设3人合作博弈 的特征函数如下： ， ， ， ， 求其核心 。 v0)( iv3,2, 1i32)2 , 1(

25、v127)3 , 1(v21)3 , 2(v1)3,2, 1(v)(vC)(),(321vCxxxx解解 由核心定义，若由核心定义，若 ，则它必满足，则它必满足3 ,2, 1,013212132127313221ixxxxxxxxxxi10003213131252211xxxxxx30解线形不等式组： 该不等式组无解，即 。上面三个例子说明了求解核心的方法。核心核心练习练习2 考虑如下的合作博弈 ，特征函数如下： ， ； 。1213231230,1,2,31111ixixxxxxxxxx ( )C v (, ),1,2,3N v N ()0vi3 ,2, 1i ()1, 23vSS31核心核心

26、 在合作博弈中，用核心代替分配具有明显得优点，即 的稳定性。对于 中的每一个分配，每个联盟都没有反对意见，都没有更好的分配，每个分配都可以得到执行。当然，用 代替 也有致命的缺陷，即 可能是空集，而 。 定理定理 2 对于 人的联盟博弈，核心 非空的充分必要条件是线性规划 有解。 ，( )C v( )C v( )C v( )C v( )C v( )E v( )E v n( )P( )P)(min1Nvxnii1( ).()ii Sniixv Sstxv NNS 32核心核心 定理的直观意义很明显，线性规划（L）若有解，则最优解一定属于 ；若 ，则 中的每个向量都是可行解，自然线性规划（L）有最

27、优解。对于原线性规划（P），写出它的对偶规划（DP）： ，)(vC( )C v ( )C v()DPmax( )()SSNy v Sv N1.0SSNSystyNS 33核心核心 对策 有 的充分必要条件是：对于满足 的向量 ，有 。 设 是个0-1简单对策，若存在一个参与人 ，满足 ，则 称作一个否决人。 简单对策 中， 充分必要条件是 中存在一个否决人。(, )N v(, )N v(, )N v( )C v ( )C v 1.0SSNSystySy( )()SSNy v Sv Ni()0v NiNi34核心核心证明 设 是 中一个否决人，定义 ，1处于第 的位置。 根据定理 2， 是一个分

28、配，且 。用反证法。设 ，且不存在否决人，即 。 ，则 。 故有 ，从而 。也即 ，矛盾。 iN0,0,1,0,0ie i0,0,1,0,0ie ( )ieC v( )C v ()1v Ni( )xC v ()1, ()()1,x Nx Niv NiiN1()()()1,ix Nx Nix ix iN 0,ixiN( )0ii Nv Nx35核仁核仁 为评估 对 满意性，定义如下的被称作超出超出一个指标： 的大小反映了 对 满意性。 越大， 对越不满意，因为 中所有参与人的分配之和远没有达到其所创造的合作剩余 ； 越小， 对 越满意，当 为负值时， 中所有参与人不但分配了其所创造的合作剩余 ，

29、还分配了其他联盟所创造的价值。 SSSSSSxxxx( ,)()iiSe S xv Sx( , )e S x( , )e S x( , )e S x( , )e S x( )v S( )v S36核仁核仁 对于同一个 ， 共有 个，可以表示为 。故可以计算出 个 。联盟对 的满意性取决于 中的最大的 ，故可以对 个 由大到小排列，得到一个 的向量：其中 。 联盟对 的满意性取决于 的大小， 越小，联盟对 越满意。xxS2n,1,2,2njSj 2n(, ),1,2,2nje S x j x(, )je Sx1,2,2nj 2n(, )je S x2n122( )( ),( ),( )nxxxx

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

31、)kkxy( )x( )y( )( )Lxy38核仁核仁 对于合作博弈 ，核仁 是一些分配的集合，即 ，使得任取一个 ， 都是字典序最小的，即 。 对于合作博弈 ，其核仁 ，且 只包含一个元素 。 对于合作博弈 ，如果核心 ，则有 。 (, )N v(, )N v(, )N vNN( )NE vxN( ) :( ),( )( )LNxE vyE vyxxy N xC NC( )x39核仁核仁 例例 5 考虑如下的合作博弈， ，特征函数如下： ； ； 。求该博弈的核仁。 解解 先求出该博弈的核心，再求核仁。先求出该博弈的核心，再求核仁。根据核心的条件，根据核心的条件， 充分必要条件：充分必要条件

32、：解此不等式组，得到解此不等式组，得到 。(, ),1,2,3N v N ( 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 xx40核仁核仁 ，故有，故有 。下面开始求。下面开始求 。对于核心对于核心 ，开始，开始求求 ， 。 ，有，有 440； ，有，有 0 ； ，有，有 0 ； ，有，有 5 ； ，有，有 7 ； ，有，有 6 0； ，有，有 10100； 当当 ，

33、。上式在。上式在 达到，故有达到，故有 。该结果验证。该结果验证了了 ， 。 ( )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,) :4(4, 2, 4)x xxN

34、N 1N3x41Shapley值值 分配是合作博弈最重要的概念，分配是合作博弈最重要的概念，但遗憾的是在一个博弈中，但遗憾的是在一个博弈中，分配有无限个，且许多根本就得不到执行。利用优超的概分配有无限个，且许多根本就得不到执行。利用优超的概念，对分配进行了分类，形成了核心的概念，但遗憾的是，念，对分配进行了分类，形成了核心的概念，但遗憾的是，许多博弈中核心可能是空集。为此，引入了超出这一指标，许多博弈中核心可能是空集。为此，引入了超出这一指标，寻求最大超出最小化的分配，即核仁。核仁这一解的优势寻求最大超出最小化的分配，即核仁。核仁这一解的优势体现在核仁总存在，且是唯一的，这一解的缺陷就是计算体

35、现在核仁总存在，且是唯一的，这一解的缺陷就是计算太复杂，因为共有太复杂，因为共有 个。个。 本节引入了一个很直观的解的概念，即本节引入了一个很直观的解的概念，即。参与人按照参与人按照Shapley值进行分配。值进行分配。 2n42Shapley值值 对每个博弈 ，存在唯一的Shapley值 ，其中 （8.5.1）下面对这一计算公式给出非数学化的解释：1、 ， 就是按照参与人的平均贡献来安排的分配设计。2、在一个博弈中，每个人的所得应该与其贡献成正比。对于联盟 ，其合作剩余 。如 加入 ，则新联盟的合作剩余是 。因此 的贡献是 。 (, )N v12( )( ),( ),( )nvvvv /!(

36、1)!( )( ()( )!iSNiSnSvv Siv Sn12( )( ),( ),( )nvvvv( )iixvS( )v SiS()v Sii ()( )v Siv S43Shapley值值3、在博弈 中，不包含 的 有 个，对每个 都有一个贡献值 ，因此，Shapley值的计算公式中有 项。4、即使对于一个固定的 ， 与 中参与人的排列顺序无关，与 中参与人的顺序无关。因此 的系数中存在 。为什么系数中有 ？主要是为了计算 的平均值。(, )N viSSS12n ()( )v Siv S()( )v Siv SSNSi ()( )v Siv S!(1)!SnS!n()( )v Siv

37、S44Shapley值值 5、对于 也可以作出这样解释： 加入 ，其贡献是 。 加入 的概率是多少？如果 个局中人以次参加博弈，当 加入该博弈时，其前面已有一些参与人 ， 加入后，后继的参与人集合 。 和 中参与人的顺序与 无关。 加入 的概率是 ， 的数学期望（或者平均值）就是Shapley值。 6、Shapley值不一定是个分配，即理性约束 可能不满足。 !(1)!SnSniiiiSSSS ()()v Siv Sin NSiS NSi ()( )v Siv S!(1)!SnSn()( )v Siv S( )ivvi45Shapley值值例例1 假设联合国安理会进行投票，部分国家可以形成联盟

38、。该博弈的特征函数为： 而对所有其他 ， 。为了求 ，对所有包含参与人1的联盟按Shapley值求和。 与 有差异的联盟 只有 、 、 、 、 、 和 ，对于其他的 ， 0。所以有 类似地， 。 于是， ， 。这样，参与人1、2比参与人3、4、5重要得多。 1) 5 , 4 , 3 , 2 , 1 () 5 , 4 , 2 , 1 () 5 , 3 , 2 , 1 () 4 , 3 , 2 , 1 () 5 , 2 , 1 () 4 , 2 , 1 () 3 , 2 , 1 (vvvvvvv(2)S S 0)(Sv)(1v(1 )v S( )v SSS3,2, 14, 2, 15, 2, 15

39、, 3, 2, 15,4,2, 14, 3, 2, 15, 4, 3, 2, 1 ()( )v Siv S209)01 (! 5! 0! 4)01 (! 5! 1 ! 33)01 (! 5! 2! 23)(1v301)01 (! 5!2!2)(3v45. 0)()(21vv0333. 0)()()(543vvv46Shapley值若博弈 满足超加性，即 , ,则Shapley向量 ，即Shapley值是分配。证明 满足超加性，则 。12( )( ),( ),( )( )nvvvvE v /!(1)!( )( ()()!(1)!()()!iSNiSNiSnSvv Siv SnSnSvivin。 ()( )()v Siv Sv i( , )N v( , )N v)()()(2121SvSvSSv21SS 4748