夏普利值 夏普利值是合作博弈论中的一个流行解概念，它为联盟博弈的参与人提供了唯一配 置。与纳什议价解类似，夏普利值也是基于一组公理之上，这些公理确定了如何对参与 人进行分配。夏普利值如实描述了参与人的边际贡献。在工程领域，夏普利值有广泛的 应用。本章介绍夏普利公理，并且证明了夏普利值的存在性与唯一性。我们用一些例子 进行说明，也证明了一些重要结果。 给定联盟博弈，核可能是空的，也可能非常大，甚至是不可数无穷的。这当然对博 弈结果的预测带来了挑战。夏普利值（Shapleyvalue）是一个解概念，它基于下列思 想：对于任何给定的联盟博弈，什么解能给出唯一期望收益配置。劳埃德·夏普利 （LloydShapley）于1953年使用公理化方法提出了夏普利值的概念，这也是他在普林斯 顿大学博士论文的一部分。给定联盟型博弈（N，v），我们将夏普利值记为（N，v)= （pi（N，)，，p（N，）），其中（N，v）是参与人i的期望收益。在不至于混淆 的情形下，我们分别把（N，）与（N，）简记为（）与（)。另外，注意， u∈R²-1，在这里我们去掉了u（），因为它显然等于零。 夏普利值试图描述联盟竞争力量如何影响博弈的可能结果。给定特征函数刻画的策 略现实，夏普利值描述了一种分配联盟价值的合理或公平方法。这种方法的分配依据在 于参与人的边际贡献。 注释在本章，与以前类似，我们稍微滥用一下符号：为方便起见，我们将集合 {1}，{2}，{3}，{1，2}，{1，2，3}分别简记为1，2，3，12，123。

劳埃德·夏普利（LloydShapley）是有史以来最有影响 力的博弈论学家之一。特别地，他对合作博弈论做出的贡献 比任何其他人都多。夏普利做出了很多原创工作，开启了博 弈论的新纪元。夏普利与埃尔文·罗斯（AlvinRoth）一起 获得了2012年诺贝尔经济学奖。博弈论中的很多概念、引 理和定理都以夏普利命名，其中最为重要的是夏普利值，这 是合作博弈论中的一个流行解概念。 夏普利的开创性贡献包括： ·邦德伊瓦-夏普利定理（Bondareva-Shapleytheorem），它为联盟博弈的核的非空 性提供了必要充分条件，这个定理也意味着凸博弈有非空的核；我们在上一章已讨论了 该定理。 ·盖尔-夏普利算法[1]（Gale-Shapleyalgorithm），它为稳定的婚姻问题提供了第 一个而且也许是最常用的解。 ·奥曼-夏普利定价法（Aumann-Shapleypricing），它开创性地指出了如何对使用 共享资源的产品定价。 ·夏普利一福克曼引理（Shapley-Folkmannlemma），它解决了集合加法的凸性 问题。 ·夏普利-舒比克权力指数[2]（Shapley-Shubikpowerindex），它被用于确定投票 权力。 第 29章 ·另外，夏普利早在1953年首先提出了随机博弈的概念。[3]1996年，夏普利与孟 德尔（Monderer）提出了潜在博弈（potentialgames）的概念，现在这种博弈已被研究 夏普利值 者广泛使用。4]夏普利与马希勒（Maschler）、皮莱格（Peleg）一起在内核（kernel） 以及核仁（nucleolus）等概念上做出了开创性的贡献；夏普利与奥曼一起在非原子博 弈、长期竞争方面的贡献也是开创性的。 夏普利于1923年出生于马萨诸塞州剑桥市，从小他就是一个数学天才。1948年大学 毕业后，夏普利进入哈佛大学。1943一1945年，他效力于美国陆军，1943年成为教官， 当时他破译了苏联天气密码，在20岁时被授予青铜勋章。1949年，他开始在普林斯顿大 学追随阿尔伯特·塔克（AlbertTucker）教授攻读博士，1953年获得博士学位。大名鼎鼎 的夏普利值就是在这一时期完成的。夏普利博士的论文题目为《可加与不可加的集合函 数》（AdditiveandNonadditiveSetFunction）。那时，约翰·纳什与夏普利都是塔克教授的 博士生。1954—1981年，夏普利作为数学家效力于兰德公司，在这个时期他取得了很多开 创性的结果。自1981年起，他任教于加利福尼亚大学（洛杉矶）经济系和数学系。 29.1夏普利公理 令（N，u）为联盟型博弈。令π为集合N上的一个排列（permutation）。令

（N，πv）为伴随排列值函数 πU（{π（i):iEC})=v（CCCN 的联盟博弈。这意味着任何参与人iEN在博弈（N，v）中的作用，与参与人π（i）在 博弈（N，πv）中的作用是相同的。 例29.1假设N={1，2，3}。考虑集合N上的下列排列π： π（1）=3；π（2）=1;π（3）=2 于是博弈（N，πu）为 π（1）=v（2）；π（2)=v（3）；π（3）=v（1);π（12)=u（23）; （23）=v（13）；π（13）=v（12）；π（123）=v（123） 夏普利认为好的解概念应该满足一些合意性质，他将其凝练为三个公理：（1）公理 1：对称性；（2）公理2：线性；（3）公理3：载体。 口公理1：对称性 对于任何vER2"-1、N上的任意排列以及任意iEN，对称公理表明 x（i(πU)=i() 大致地说，这个公理表明，给定任一参与人，利用排列值函数对其重新标号，此时他的 夏普利值等于他在原来值函数下的夏普利值。这个公理意味着真正重要的是参与人在博 弈中的作用。他在N中的标号或名字不重要。 口公理2：线性 令（N，）与（N，w）为任意两个联盟博弈。假设pE[0，1]。定义一个新的联 盟博弈（N，pu十(1-p)w）如下： (pu+(1-p)w)(C)=pu（C)+(1-p）w（C)VC≤N 公理2表明，给定任意两个联盟博弈（N，v）与（N，w）、任何数pE[0，1]以及任 意参与人iEN， pi(pu+(1-p)w)=pp:(u)+(1-p）pi（w) 换句话说，对给定的两个联盟博弈取凸组合，形成一个新的博弈，参与人在该新博弈中 的夏普利值等于他在上述原联盟博弈中夏普利值的凸组合。这个公理断言，每个参与人 在不确定性消失之前与消失之后的期望收益是相等的。 口公理3：载体 定义29.1（载体）给定联盟博弈（N，v）以及联盟D，如果 u（CND)=u(C）CCN 那么我们说联盟D是博弈（N，v）的一个载体（carrier）。

如果联盟D是博弈（N，v）的一个载体而且iD，那么 0=（)=（aU{}）=（{}） 如果D是博弈（N，v）的一个载体，那么所有参与人iEN\D称为哑巴或傀儡 （dummies），这是因为他们加人任何联盟后，联盟的价值不会发生变化；也就是说，他 们对联盟的价值没有影响。另外，对于任何CCN以及i&D， u（(CU{i})=u(（CU{i})∩D)=v（C∩D)=v（C） 在直觉上，D包含所有有影响力的参与人［它也可能包括傀儡（即没有影响力的参与 人），但它不会将任何有影响力的参与人排除在外]。如果D是一个载体而且i∈N，那 么对于任何C二N， （C)=u（C∩D)=u（C∩（DU{i})) 因此，对于任何N，DU（i}也是一个载体。事实上，集合N总是一个载体。这意 味着u（D)=v（N）。这也可以从下式看出 (D)=u（D∩N)=u(N) 然而，下列情形也是有可能的：N的任何真子集都不是载体。 载体公理（carrieraxiom，公理3）表明，对于任意uER2"-1以及对于作为博弈 （N，v）载体的任意联盟D， ∑（u）=u（D)=u(N) 第 iED 章 载体公理立即意味着 夏普利 pi(u)=0ViD ∑:(u)=u(N) 值 iEN 这个公理断言载体集内的参与人应该瓜分他们的联合价值（这等于大联盟N的价值）。 这意味着愧什么也没分到。上面的表达式也说明了一个重要事实：夏普利值总将大联 盟的价值在博弈参与人之间分配。这意味着夏普利值隐含地假设参与人构成了大联盟 （然而，一些参与人可以为愧，傀儡什么也分不到）。 注释在本章剩下的内容中，为简单起见，我们将集合N{i}记为N一i。 29.2夏普利定理与例子 有了上面三个公理之后，我们现在可以阐述著名的夏普利定理了。[5] 定理29.1恰好存在一个满足公理1、2和3的映射：R2-1→R”。这个映射满 足：ViEN，VuER2"-1, OEN-i ju

ju i之前的概率；v（CU{i}）一v（C）项是参与人i对联盟C价值的边际贡献。因此，上面关 于（v）的表达式给出了参与人i对任意联盟的价值的期望贡献。 我们用下列情形解释（）。 假设有一组n个资源，每个资源都对某种服务有自已的贡献。假设v（N）是所有这 些资源用于生产该服务时所产生的总价值。我们来关注某个特定资源，比如资源i。现 在，当这个资源被包含在集合C中时，它对集合（N一i）的每个子集C都会做出边际 贡献。我们选择集合C的方法一共有C！（n一|C一1）！种；用|C！（n一|C|一1）！ 除以n!，我们就得到了某个特定子集C被选中的概率。因此，资源i的夏普利值是资源 i对任何作为集合（N一i）的子集（即联盟）的平均边际贡献。 或者，设想某个会议室正在开重要会议，每次只允许一人进人会议室。假设当前正 在开会的人都是某个联盟C的成员；非成员在会议室外等候。进人会议室的个人i任C， 将以某种方式对会议做出贡献。个人i的贡献主要取决于他的影响力和表达能力。如果 集合（N一i）的任何子集（联盟）在会议室的概率相等，那么个人i对任何这种联盟的 平均贡献就是他的夏普利值：（）。 例29.2（分钱博弈）我们首先考察分钱博弈（版本3）（例27.3）。在这个博弈中， N={1，2，3}；v（1）=v（2）=v（3）=v（23）=0，（12）=v（13）=v（123）=300。参与 人1的夏普利值（）的表达式为： +2 （（123）-v（23）) 类似地， p(u)=(v(2)-u(0))+(u(12)-u(1)+- +(u(123)-u(12)) 容易看出 p1（v）=200；p2（)=50；3（u）=50 由此可以验证 p（）+2（)+3（)=v（123) 类似地，对于分钱博弈（版本1）（例27.1）以及对于分钱博弈（版本4）（例27.4），容 易得到=（100，100，100)；对于分钱博弈（版本2）（例27.2)，=(150，150，0)。

例29.3（最小生成树博弈）考虑例27.7中的最小生成树博弈。在这个博弈中， N={1，2，3}； v（）=0，v（1）=5，v（2）=9，v（3）=7 v（12）=15，v（13）=12，v（23）=17,v（123）=23 根据例29.2中的表达式，可知 （)=5.5;p2（v)=10;3（）=7.5 注意，分给参与人2的收益是最高的，这显然合理。另外，分给参与人1的收益最小， 分给参与人3的收益大于参与人1的，这些显然也都符合逻辑。另外，注意，这个配置 属于博弈的核。口 例29.4（手套市场）考虑例28.4中的手套市场博弈，这个博弈有2000001个参 与人，其中1000000个为左手套供应商，1000001个为右手套供应商。我们已经看到， 这个博弈的核为单点集。在这里，任何右手套供应商的夏普利值是他发现任何联盟中左 557，每个左手套供应商的夏普利值为0.500443。注意，夏普利值比核能更好地描述联 盟力量的效应。另外，也要注意到，夏普利值不属于核。口 例29.5[顶峰（apex）博弈]在这个博弈中，有五个参与人：N={1，2，3，4，5}。 参与人1是大参与人，其余四个为小参与人。大参与人若与一个或多个小参与人组成联 盟，则该联盟的价值为1。四个小参与人组成联盟，联盟价值也为1。 v(C)=1若1EC且|C|≥2 =1若|C|≥4 =0其他 夏普利值 夏普利值为 (D)() 注意，这个博弈的核是空的。口 例29.6（物流博弈）图29—1画出了一个物流网络，它将两个重要城市S和T连 接在一起。该物流网络中有五个物流中转站A、B、C、D和E，它们是S和T之间的 中间点。运输服务商有四个，1、2、3和4。 3,50 3,15 1,10 2,15 4,0 E 1,10 2,15 3,10 1,40 图29-1物流网络

我们已在第27章讨论过这个例子，在那里，我们将其形式化为一个伴随可转移效 用的博弈，其中：N={1，2，3，4}；特征函数为 u（1）=u（2）=v（3）=v（4）=0 v（12）=v（13）=v（14）=v（23）=v（24）=v（34）=（234）=v（123）=0 u（134）=40，v（124）=45，v（1234）=65 可以证明，夏普利值为（v)=（20，20，5，20）。可以证明，夏普利值属于这个博弈的 核。口 29.3夏普利定理的证明 证明分两部分。在第一部分，我们证明：（v）的表达式满足所有三个公理。在第二 部分，我们证明存在满足所有三个公理的唯一映射。 口第一部分的证明 对称性 注意，在：（v）的表达式中，对任何联盟来说，真正重要的是它是否包含参与人i 以及它包含的参与人数量。因此，对参与人重新标号对夏普利值没有任何影响。这显然 表明对称性（公理1）成立。 线性 为了证明线性成立，我们必须证明 i（pu+(1-p)w)=pp;(u)+(1-p)p;(e) 现在我们就证明此事。根据定义可知，对于任何p∈[0，1]，我们有 (pu+(1-p)w)(C)=pu（C)+(1-p)w（C)VC≤N (29.1) 注意，p:（pu+（1-p)w)等于 OENHi n! 展开上面的式子并且利用式（29.1），可知线性成立。 载体公理 假设D是博弈（N，v）的一个载体。于是，根据定义 u（CND)=u（C）CCN 我们还可以看到 v({i})=0Vi∈M\D u(D)=u（N)

考察夏普利值表达式，容易看到 p(u)=OVi∈M\D 原因是 u（CU{i})=u（（CU{i})∩D)=u（C∩D)=u（C） 因此，我们必须证明：对于所有载体D， ∑:(u)=u(D) iED 这事不难证明。将夏普利定理中的（v）表达式代人，化简，可得 ∑:(u)=u(N) iEN 由于D是一个载体，所以v（D）=v（N)，因此，载体公理成立。 口第二部分的证明 我们必须证明存在满足所有三个公理的唯一映射。我们首先证明映射是一个线 性变换（lineartransformation）。为此，我们注意到： ·令（N，z）是一个联盟博弈，而且该博弈对每个联盟的赋值为零，即z（C)=0， VC二N。于是，载体公理（公理3）意味着 第 p;(z)=0ViEN (29.2) 章 ●根据线性公理（公理2），我们有 夏普利值 (m)²(d-）+(a)²d=(m(4-[)+ad)² 在上式中令w=，可得 pi(pu)=pp:（u)Vi∈N (29.3) 式（29.2）、式（29.3）与线性公理一起意味着是一个线性变换。 假设L（N）是由N的所有非空子集组成的集合。显然，|L（N)|=2"一1，因此 R|L(NI是一个2"一1维向量空间。令D≤N为任一联盟。对这个D定义一个联盟博弈 (N,wD): Wp(C)=1若D≤C =0其他 这意味着如果联盟C包含D的所有成员，那么C的价值wD（C）为1；否则，等于零。 博弈（N，WD）称为简单的D载体博弈。为了感受一下这种博弈，我们先讨论一个例 子，然后再继续我们的证明过程。 例29.7（D载体博弈）令N={1，2，3}。令1，W2，W3，W12，W13，W23，W123 分别表示D载体博弈的特征函数，它们分别对应着联盟（1），{2>，{3}，（1，2}， {1，3}，{2，3}，{1，2，3}。例如，W2为

w12（1）=0，w2（2）=0,W12（3）=0 w2（12）=1,w12（13）=0，W2（23）=0，W2（123）=1 我们可以将所有w值如下写出。注意，每个w值都是一个7元组。 w=(1,0,0,1,1,0,1) w2=(0,1,0,1,0,1,1) W=(0,0,1,0,1,1,1) w12=(0,0,0,1,0,0,1) w13=(0,0,0,0,1,0,1) w23=(0,0,0,0,0,1,1) W123=(0,0,0,0,0,0,1) 稍后我们将证明这7个向量是R”的一个基（basis）。口 现在，我们继续第二部分的证明工作。注意，D是博弈（N，Wp）的一个载体， 这是因为 Wp（C)=WD(CnD)C≤N 事实上，对于ViEN，DU{j}也是一个载体。另外， wD（N)=1，这是因为DCN WD（D)=1，这是因为DCD 博奔论与机制设计 利用载体公理，可得 ∑:(wD)=1 =wp(D)=wD(N) iED 以及 p;(wD)=OViD 上式成立的原因在于D与DU{j}都是wD的载体。 现在，根据对称性公理可知，D中的每个参与人都应该得到相同的收益。这是因为 D中的每个参与人对特征函数wD的贡献是相同的。因此，不存在将这些参与人区分开 的方法，因此，我们可以对他们任意重新标号。这意味着 pi(w）=TT p;(wD)=OViD 对于每个联盟D二N，都存在着一个博弈（N，wD），因此，我们有2”一1个这样的博 弈。每个博弈都可用一个特征函数表示，而每个特征函数都是一个含有2”一1个元素的 向量。因此，我们有2”一1个向量，每个向量都有2”一1个元素。我们现在证明在 R²一空间中，这些向量彼此线性无关。为了证明线性无关性，我们必须证明 ∑ADWD=(O,0,,0)入D=0D∈L(N) DEL(N)

反证法。假设上面的蕴含关系不成立。现在 ∑ADwD=(O,0,,0)>ADwD(C)=0C≤N DEL(N) DEL(N) 令C二N为任何满足入c≠O的最小联盟。由于D要么是C的子集要么不是，因此，我 们有： ∑DWD(C)+∑DwD(C)=O>∑ADwD(C)=0 C≤N DC DEL(N) 我们知道wD（C)=1，VD≤C以及wD（C)=O，VDC。因此，上面的式子意味着 ∑AD=0 DCC 由于C≤N是满足入c≠O的最小子集，因此对于所有子集DCC，我们有入D=O。因此， 上面的加和等于入c。这意味着入c=O。矛盾！因此，集合{wp：D∈L（N）}是空间 R²"一1的一个基。由于线性变换完全取决于向量空间的基，因此，映射是唯一的。■ 29.4 夏普利值的其他发展方法 我们现在描述夏普利值的其他几种发展方法。每种方法都对夏普利值这个解概念提 供了有趣的解释。 口方法1 夏普利值 给定伴随可转移效用的博弈（N，v），夏普利值可以写为 CSN-i n! 这是因为{（N\C）一（C）}与{（CU{i}）一u（C））相同。因此，上面这个式子与定理 29.1中的表达式相同。这个式子表明，每个参与人的价值仅取决于互补联盟 （N\C）与C的价值之差。对于每一对互补联盟（N\C）与C，（N\C）的成员价值 随着（v（N\C)一v（C)）的增大而增大，而C的成员的价值随着（v（C)一u（N\C)）的增 大而增大。 口方法2 夏普利值的另外一个表达式为 CEN n! iEC 注意， (|C|-1)!(n-∣C|)! n!

是指在随机排列中，联盟C以{i}与所有排在i前的参与人组成的集合的并（union）的 形式出现的概率。 口方法3 令C≤N以及iC。参与人i对C的边际贡献记为m（C，i），由下式给出： m（C,i)=u（CU{i})-u(C) 给定任何排列π∈ⅡI（N），在排列π中排在参与人i之前的那些参与人组成的集 合P（π，i）为： P(π,i)={j:π（j)<π（i)} 我们已经看到，p（）是在假设所有排序的概率都相等的情形下参与人i对N的任何联 盟的平均边际贡献。另外一种解释为，：（u）是参与人i对排在他前面的参与人组成的 集合所做的平均边际贡献，其中均值是对排列而取的（这里假设每个排列出现的概率相 同）。因此，我们有 (29.4) 类似地，如果 S(（π,i)={j:π（i）<π（j)} 博奔论与机制设计 表示在排列π中排在参与人i之后的所有参与人组成的集合，那么我们也可得到 (29.5) 读者可以验证，式（29.4）与式（29.5）都满足夏普利值表达式。 29.5凸博弈的夏普利值 我们在第27章定义了凸博弈，在第28章证明了任何凸博弈的核都非空。我们现在 证明凸博弈的夏普利值属于该博弈的核。注意，一般来说，即使核非空，夏普利值也未 必属于核。 定理29.2令博弈（N，）是一个凸博弈，那么（v）EC（N，v)。 证明：与以前一样，令II（N）表示由集合N的所有排列组成的集合。假设πEⅡI（N） 是任一排列。定义配置y"ER”如下。 y=（m（π，1）,m（π,2),,m（π，n）) 我们已在第28章命题28.2看到 yEC(N,)πEII(N) 而且，我们已经看到（参见式（29.4））

ju (N)II 因此，（）是所有向量y的一个凸组合；πEII（N)。由于核C（N，u）是一个凸集， 因此我们立即可知（)∈C（N，v)。 上面的结果比较有用。如果我们能用凸博弈描述我们所要研究的现实情形，那么夏 普利值有额外特征：它也是一个稳定配置，因为它属于核。因此，对于凸博弈，夏普利 值是一个很好的解概念。 例29.8（最小生成树利润博弈的夏普利值）考虑例27.7中的最小生成树利润 博弈： N={1,2,3} v（1）=5，v（2）=9，v（3）=7 （12）=15，v（13）=12，v（23）=17,v（123）=23 这是一个凸博弈，我们已经证明它的核为 {（x1x2，x）:5<x<6;9<x2<11；7<x<8；x+x2+x=23} 经过计算，可知夏普利值为（5.5，10，7.5），它显然属于核。可以看到，在夏普利值 中，参与人2得到的收益最大，参与人1得到的收益最小。这样的分配是合理的。口 29.6夏普利-舒比克权力指数 第 章 夏普利-舒比克权力指数（Shapley-Shubikpowerindex）是一个解概念，主要用于 夏普利值 确定每个参与人在决策过程中的权力。参与人集N={1，，n）的决策过程可用简单 且单调的TU博弈模拟。回忆单调博弈与简单博弈的定义：给定伴随可转移效用的博弈 值 （TU博弈）（N，)，如果 NA（>（) 那么这个TU博弈是单调的。如果对于任何联盟C二N，v（C）要么为O要么为1，那么 这个TU博弈是简单的（simple)。简单且单调的TU博弈的夏普利-舒比克权力指数， 就是这个博弈的夏普利值。给定参与人证N，定义集合 Q（N，v)={C≤N:v（CU{i}）=1与u（C)=0} 也就是说，Q（N，v）中的每个联盟都具有下列特征：当参与人i加人联盟后，这个联 盟从落败联盟变为获胜联盟。可以证明，简单且单调博弈的夏普利值（即夏普利一舒比 克权力指数）为 p:(v) =≥ ICl!(n-[C|-1)! CEQ,(N,U) n! 例29.9（夏普利-舒比克权力指数）考虑下列三人TU博弈： （1）=1，（2）=v（3）=0，（12）=v（13）=v（23）=v（123）=1

容易看到这个博弈是简单且单调的。 注意，对于这个博弈，我们有 Q（N,v)={，{2}，{3}}；Q2（N,)={{3}}；Q3（N，v)={{2}} 3’6.6 上，这就是这个博弈的夏普利值。注意，由于对称性，参与人2和3有相同的指数。参 与人1的权力是参与人2（或参与人3）的4倍。口 29.7班茨哈夫指数 与夏普利-舒比克权力指数类似，班茨哈夫（Banzhaf）指数（通常称为班茨哈夫权 力指数）也衡量参与人在联盟博弈中的权力。假设博弈（N，）是一个TU博弈，并 且回顾夏普利值的计算式[式（29.4）]： n！ π∈II(N) 在上式中，均值是对所有排列而取（这里假设所有排列发生的概率相同）。另一方面， 考虑下式 4(N,u)= OCN-i 在上式中，均值是对所有排列而取（这里假设所有联盟发生的概率相同）。指数（N， v）称为参与人i的班茨哈夫指数（BanzhafIndex）。它给出了在所有联盟发生概率相同 的情形下参与人i对任何联盟的平均边际贡献。下面的例子说明班茨哈夫指数与夏普利 值不相同。 例29.10（班茨哈夫指数）考虑所谓的一致同意博弈（unanimitygame），这是一 类TU博弈（N，v)，它满足（N)=1以及u（C)=0，VCCN。容易算出，这个博弈 的夏普利值为 p;(N,u)=ViEN n 这个博弈的班茨哈夫指数为 (N,u)= 2n-1 根据上式可知，所有参与人的班茨哈夫指数之和不等于v（N)=1。因此，班茨哈夫指数 不满足帕累托效率，而夏普利值满足。事实上，除了帕累托效率之外，班茨哈夫指数满 足夏普利值的所有其他公理性质。口 一些文献发展出了班茨哈夫指数的若干变种。更多细节可参考Dubey andShapleyL6]。

29.8小结与参考文献 TU博弈的夏普利值是一个满足夏普利三个公理，即满足（1）对称性，（2）线性， 以及（3）载体性质的唯一配置向量。 ·（超可加博弈的）夏普利值将大联盟的值分配给各个成员，而且这种分配方法反 映了每个参与人对博弈的平均边际贡献。在这个意义上，夏普利值描述了一种公平分配 方法。然而，夏普利值隐含地假设大联盟能够形成。载体性质保证了每个没有影响力的 参与人（愧）的收益为零，而其他参与人的收益不为零。 ·夏普利值有若干等价的表达方法，本章给出了几种不同的发展方法。 ·夏普利值可能属于核也可能不属于核（若核非空）。这意味着虽然夏普利值是一 种公平分配方法，但与属于核的任何其他配置不同，它不是一个可持续的配置。 ·凸博弈的核非空，而且凸博弈的夏普利值总是属于核。 ·夏普利一舒比克权力指数适用于简单且单调的博弈，它试图确定参与人在决策过 程中的权力。这个指数就是该博弈的夏普利值。夏普利一舒比克权力指数描述了不同参 与人在决策过程中的权力，这个指数可以有效计算出，原因在于博弈拥有的特殊结构 （简单且单调）。 ·班茨哈夫指数是指在所有联盟发生概率相等的情形下，参与人i对任何联盟所做 的平均边际贡献。在计算时，夏普利值假设所有排列发生概率相等，而班茨哈夫指数假 第 设所有联盟发生概率相等。班茨哈夫指数不满足帕累托效率，但满足夏普利值的所有其 章 他公理性质。 夏 本章讨论的材料主要来自Myerson[7]。近期著作 Maschler，Solan，and Zamir[8] 普 是一本优秀的参考文献。Roth9综述了夏普利值的研究进展（截止到1988年）。 利 值 夏普利值的计算是一个NP-hard问题；显然，它有指数时间复杂性。Chalkiadakis， Elkind，andWooldridge[1o]给出了这个重要议题的一些参考文献。在一些特殊情形下， 比如凸博弈情形下，夏普利值的计算相对简单（在凸博弈情形下，夏普利值是核的重 心。 夏普利值在现实应用中非常有用。例如，集群（clustering）的有效率的算法[11]以 及确定社会网络中最有影响力的节点[12就是这方面的两个典型例子。 文献[2]提出了夏普利一舒比克权力指数，文献[13]讨论了班茨哈夫指数。关于 班茨哈夫指数的更多细节，读者可以参考DubeyandShapley[6]。 口参考文献 [1]D.Gale and L.S. Shapley.“College admissions and the stability of marriage”. In:TheAmericanMathematicalMonthly 69(1)(1962)，pp.9-15. [2]Lloyd S.Shapleyand MartinShubik.“Amethodfor evaluatingthe distribution ofpowerinacommittee system".In:AmericanPoliticalScienceReview48(1954), pp.787-792.

[3]Lloyd S.Shapley.“Stochastic games".In:Proceedings of the National A- cademy of Sciences 39 (10)(1953)，pp.1095-1100. [4]D.Monderer and L.S. Shapley.“Potential games”.In:Games and Economic Behavior 14(1996)，pp.124-143. [5]Lloyd S.Shapley.“A value for n-person games”.In:Contributions to the Theory of Games.Ed.by Robert Kuhn and Albert Tucker.Princeton University Press,1953,pp.307-317. [6]Pradeep Dubey and Lloyd S. Shapley.“Mathematical properties of the Banzhaf powerindex".In:Mathematicsof OperationsResearch 4(2)(1979),pp.99-131. [7]RogerB.Myerson.GameTheory:Analysisof Conflict.Harvard University Press,Cambridge,Massachusetts,USA,1997. [8]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam bridgeUniversityPress,2013. [9]AlvinE.Roth(Editor).TheShapleyValue:Essays in Honorof Lloyd S. Shapley.Cambridge UniversityPress,Cambridge,UK,1988. [10]Georgios Chalkiadakis,Edith Elkind,and Michael Wooldridge.Computa- tionalAspectsofCooperativeGameTheory.Morgan&Claypool,2011. [11] Vikas K. Garg,Y.Narahari,and M. Narasimha Murty. “Novel biobjective clustering（BiGC）based on cooperative game theory”.In:IEEE Transactions on KnowledgeandDataEngineering25(5）(2013)，pp.1070-1082. [12]Ramasuri Narayanam and Y.Narahari.“A Shapley value approach to discove- ring influentialnodes in socialnetworks".In:IEEE Transactions on Automation Sci- enceandEngineering8(1)（2011),pp.130-147. [13] John Banzhaf. “Weighted voting does not work:A mathematical analysis". In:Rutgers LawReview 19 (1965)，pp.317-343. 29.9习题 （1）利用夏普利值表达式证明所有参与人的夏普利值之和等于大联盟的值。 （2）假设博弈（N，v）是一个TU博弈，并且定义下列唯一转归（转归概念可参 见定义27.4)。 （N,u)=u（{i}）Vi∈N 上式满足哪个（些）夏普利公理？不满足哪个（些）？ （3）假设博弈（N，v）是一个TU博弈，我们定义如下唯一转归。 （N，u)=u（{1，,i-1,i})-u（{1,…,i-1}）i∈N 上式满足哪个（些）夏普利公理？不满足哪个（些）？ （4）考虑下列三人超可加博弈：v（1）=v（2）=（3）=0，（12）=a，（13）=b，

u（23）=c，u（123）=d，其中0≤a，b，c≤d。计算该博弈的夏普利值。 （5）考虑下列三人特征型博弈：（1）=（2）=（3）=0，（12）=a，v（13）=b， u（23）=c，v（123）=1。假设0≤a，b，c≤1。 （a）在什么条件下核非空？ （b）计算夏普利值。 （c）假设核非空，夏普利值属于该博弈的核吗？在什么条件下，夏普利值属于核？ （6）考虑分钱博弈的变种，现在有四个参与人（1，2，3，4），总价值为400。假 设含有三个或更多参与人的任何联盟都能实现这个总价值。另外，含有两个参与人的联 盟也能实现该总价值仅当参与人1是该联盟的成员。对这个TU博弈构建特征函数并计 算夏普利值。 （7）考虑分钱博弈的变种，现在有四个参与人（1，2，3，4}，总价值为400。任 何含有至少两个参与人的联盟仅当参与人1是该联盟的成员时都能实现这个总价值 400。类似地，任何含有至少三个参与人的联盟仅当参与人2是该联盟的成员时也能实 现这个总价值400。对这个TU博弈构建特征函数并计算夏普利值。 （8）对于下列每种情形，分别给出二人博弈的例子： ●核为空而且纳什议价解（NBS）与夏普利值（SV）相同； ·核为空而且NBS与SV不同； ·核非空而且NBS与SV相同； ·核非空而且NBS与SV不同。 （9）对于下列每种情形，分别给出一个TU博弈的例子： 第 ●核非空而且夏普利值属于核； 章 ●核非空而且夏普利值不属于核。 夏普利体 （10）给定TU博弈（N，v)，如果 u（C)=∑u({i}）C≤N 值 iEC 那么我们说这个博弈是可加的。确定这个博弈的夏普利值的闭形式（即解析式）。 （11）给定TU博弈（N，v)，定义对偶博弈（N，w）如下： w（C)=u（N)-u（M\C）C≤N 证明对偶博弈的对偶是原博弈本身。另外，证明原博弈的夏普利值与对偶博弈的夏普利 值相同。 （12）考虑下列三人TU博弈： v（1）=v（2）=v（3）=v（23）=0,u（12)=u（13）=v（123）=1 容易看到这个博弈是简单且单调的。事实上，这个博弈类似分钱博弈（版本3）。确定 这个博弈的夏普利一舒比克权力指数。 （13）考虑如下四人TU博弈： v（12）=v（13）=v（123）=v（134)=v（124）=v（234)=v（1234）=1 对于其他联盟，特征函数的值为零。

这个博弈是单调的吗？如果是，计算它的夏普利一舒比克权力指数。 （14）考察第27章例27.6讨论的投票博弈，它是单调的吗？如果是，计算它的夏 普利一舒比克权力指数。 （15）本章讨论的顶峰（apex）博弈是单调的吗？如果是，计算它的夏普利一舒比克 权力指数。 （16）（编程题）考察夏普利值的各种计算方法。实施计算夏普利值的有效率的 算法。 （17）（编程题）编程判断给定的TU博弈是否为凸博弈。实施计算凸博弈的夏普利 值的有效率的算法。