伴随可转移效用的 联盟博弈 上一章研究了两人议价问题，在那里，我们考察了两人合作产生的效应。在本章， 我们介绍多人联盟博弈。特别地，我们讨论伴随可转移效用的博弈[transferableutility （TU）games]，也称为特征型博弈。我们用一些例子说明如何利用可转移效用的博弈来 描述理性且智能的参与人之间的合作。 伴随可转移效用的联盟博弈 27.1多人合作博弈 与以前一样，令N={1，，n）为参与人集。我们已经考察了两人博弈的纳什议价 解。现在我们对n人博弈（其中n>2）的纳什议价解感兴趣。令F是参与人联合起来得 到的可行配置集。假设F是R”的一个闭的凸子集。假设（，"，）是争议点（即争 议收益配置或违约收益配置，指他们不合作时得到的期望收益）。另外，假设集合{（y， “，yn）EF：y≥u，V∈N}非空且有界。二元组（F，（，，u））称为一个n人议 价问题。如果存在y∈F使得y>，i∈N，那么我们说议价问题（F，（，，）） 是一个基本（essential）议价问题。 假设问题（F，（，，））是基本的。于是，它的纳什议价解可以定义为唯一 有强效率的配置向量x*=（x，，x）；对于所有满足x≥u，Vi∈N的向量x∈F， x*使得乘积（x一u）××（x一un）最大。然而，正如下面例子表明的，这个纳什议 价解可能忽略了某些参与人进行合作的可能性。因此，对于n>2，纳什议价解可能不 是一个合意解。因此，我们必须寻找更合适的解概念。

口分钱问题 例27.1（分钱博弈（版本1））在这个问题中，N={1，2，3）。这三个人希望分 300元钱。每个人都可以提出一个分配方案，使得任何参与人的收益（所得钱数）不为 负，而且所有参与人的收益之和不大于300。因此，策略集可以定义为： S=S2=S3={（x1,x2，x）∈R²:x1+x2+x3<300；x1≥0；x2≥0；x3≥0} 假设除非所有三个人提出相同的分配方案，否则每个参与人的收益都为零。也就是说， 对于i=1，2；3， u;（s1，S2，S3）=x;若s1=s2=s3=（x1，x2x3） =0其他情形 注意，参与人可以实现任何下列这样的分配方案：他们的收益非负而且收益之和不大于 300。每个人的最低收益为零。因此，上面的博奔可以描述为一个三人议价问题 (F，v)，其中： U=（1，U2，0）=（0,0,0) 这个问题的纳什议价解为x=（100，100，100），这显然是一个合理结果。口 例27.2（分钱博弈（版本2））这是分钱博奔（版本1）的变种，现在每个参与人 博 奔 的收益为零，除非参与人1和2提出了相同的分配方案；在这种情形下，参与人1和2 论 提出的方案得到实施。也就是说，对于=1，2，3， 与 机 ui（s1，S2，S3）=x;若s1=s2=（x1，x2C3） 制 设 =0其他情形 计 分钱博奔版本1中的议价问题（F，v），在这里也可行，因此这个问题的纳什议价解为 r=（100，100，100）。这个解看起来不合意，因为参与人1和2联合决定分钱方案，参 与人3未参与决策。因此，我们可以预期参与人1和2将均分300元，从而得到配置 （150，150，0）。另外一种支持这种论证的观点是下面这样的。设想参与人1和2忽略 3，进行两人合作博弈。在这个两人博弈的纳什议价解中，参与人1和2将各得150元。 然而，（100，100，100）这个解也并非不可能，原因如下： ●如果参与人同时选择他们的分钱方案，那么在这种情形下，（100，100，100）与 （150，150，0）都是纳什均衡，因为任何参与人单方面偏离这个均衡，都会使得自已的 收益为零。 ·如果参与人3有一定影响力，那么作为理性人，参与人3显然将试图影响参与人 1和2，从而得到均衡（100，100，100）。 现在，如果增加一个假设，我们就可以使（100，100，100）变得不可信。这个假设就是 有效协商（effectivenegotiation）假设，这是一个自然假设，正如Myerson指出的。口 迈尔森[1]定义了有效协商概念，并且断言有效协商是将合作博弈论与非合作博弈 论区分开的关键假设。

定义27.1（有效协商）假设一些参与人组成联盟，如果这些参与人认识到他们的 策略存在着对他们都有好处的可行变化，将一致同意做出这个变化，除非该变化违背了 联盟成员与联盟外的参与人的约定（这意味着还可能存在其他有效联盟），那么我们说 联盟成员是有效协商的（negotiateeffectively）而且说他们组成了一个有效联盟（effec- tive coalition)。 n人纳什议价解是重要的仅当能有效协商的唯一联盟是由所有n个参与人组成的大 联盟（grandcoalition）N。如果还存在着其他有效协商的联盟，那么纳什议价解变得 不重要。这是因为这个解忽略了多人联盟的权力信息，仅强调大联盟N的权力信息。 在分钱博弈（版本1）中，任何小于（1，2，3）的联盟都不能保证它的成员收益大于 零。在分钱博弈（版本2）中，联盟{1，2）可以保证其成员的收益不会小于联盟（1， 2，3）情形。 例27.3（分钱博弈（版本3））这是分钱博弈（版本2）的变种。现在每个参与人 得到的收益为零，除非参与人1和2提出相同分钱方案或者参与人1和3提出相同方案 （若事实如此，按这个分钱方案实施）。也就是说，对于i=1，2，3， ui（s1，S2，S）=x;若s1=s2=（x1，x2，x）或s1=s3=（x1，x2，x3） =0其他情形 分钱博弈（版本1）和分钱博弈（版本2）中的议价问题（F，v）也能描述这里的情形， 因此，这个问题的纳什议价解也为x=（100，100，100）。与版本2情形非常类似，这 个解也不合意，因为参与人1和2一起或参与人1和3一起决定了分钱方案。注意，对 第 于上面两种情形（分钱方案决策），参与人1必定都参与。因此，我们可以预期分钱结 章 果为参与人2和3的收益相同，但小于参与人1的收益（因为非零分钱方案必然要经过 参与人1同意）。这导致了无穷多个可能性，例如（120，90，90），（150，75，75）， 伴 随 （200，50，50），（280，10，10）等。甚至（300，0，0）也是可能的，因为参与人1必 可 须参与非零分配方案决策。口 转 移 例27.4（分钱博弈（版本4）：多数同意规则下的投票博弈）在这个版本中，每个 效 参与人的收益为零，除非存在着一对参与人（1，2）、{2，3）或{1，3}提出相同的分 用 的 钱方案（在这种情形下，他们按该方案分钱）。也就是说， 联 盟 ui（s1，S2，S3）=x:若对于某个j≠k，S;=sk=（x1，x2，x3） 博 =0其他情形 弈 这里，再一次地，纳什议价解为（100，100，100）。注意，对于版本4的博弈，这个解是 合理的，原因在于参与人地位的对称性以及相同的议价权力。注意到，这个配置是一个纳 什均衡。如果我们假设每个联盟能有效协商，那么分析过程比较有趣（Myerson1]）： （150，150，0），这个配置对他们两人都有吸引力。注意到，该配置显然是一个纳什均衡。 ·如果（150，150，0）是一个预期结果，那么参与人3将竭力说服参与人1或2 与他（参与人3）构建有效联盟。例如，参与人3与2协商，提出配置（0，225，75） 或者（0，200，100）等等。注意到，这些配置也是纳什均衡。 ·如果（0，225，75）是一个预期结果，那么参与人1将尽力与参与人3构建联

盟，提出让他们两人状况都更好的配置，比如，（100，0，200）。该配置也是一个纳什 均衡。 ·在这个博弈的任何均衡中，总存在着一对参与人，他们用有效联盟形式提出的方 案对联盟成员更好，从而使当前均衡移动到另外一个均衡。 上面的联盟协商可一直进行下去。终止协商有两种可能的方法。第一种方法如下。假 设某个参与人进人某个联盟（意味着一个协议），而且该联盟不是另外一个联盟的真子集， 那么后来该参与人不能进人后面这个联盟（意味着另外一个不同的协议）。例如，如果在 任何两人联盟单独协商之前，大联盟{1，2，3）已达成协议（100，100，100），那么任何 两人联盟不能否决这个结果。再举一个例子。假设参与人1和2已经先行达成协议（150， 150，0)，那么参与人3不能通过与参与人1或2单独协商来提高自已的收益。显然，在 这种情形下，联盟协商顺序决定了博奔结果。先协商的联盟有先发制人的优势。 现在来看第二种方法。假设协商达成的协议是实验性质的，没有约束力。因此，某 个参与人可以先后进人一系列联盟，从而意味着一系列协议，但后面的协议将前面的协 议废除。在这里，协商顺序对最终结果有影响。例如，假设协商顺序为{1，2）、{2， 3}、{1，3}以及{1，2，3}。在这里，{1，2}和{2，3}先后达成的使得参与人2的 收益不为零的分钱方案都会被联盟（1，3）推翻，比如，联盟（1，3）提出方案（150， 0，150）。在这种情形下，当轮到联盟{1，2，3}出现时，参与人2已经无能为力：他 无法让参与人1和3同意任何其他方案。再举一个例子。假设参与人1认为，他与参与 人2协商达成的任何协议都会被参与人3推翻。在这种情形下，参与人1可能首先提出 博 方案（100，100，100）并且一直坚持下去，这意味着他当然也会拒绝方案（150，150， 奔论与机 0）。这种做法能让参与人1保证自己的收益不为零。一般来说，在这种方法下，后协商 的联盟具有优势。口 制 在现实世界中，人们可以组成各种不同联盟，当参与人数众多时，协商方法可能接 设 近无穷多，从而使系统分析所有情形变得不可行。当参与人为n人时，可能涉及 计 2”一1个联盟，因此，如果合作博弈论能够指明各个联盟权力的平衡结果就好了。这种 与协商顺序无关的理论极其有用，但不容易合理解释，因为顺序通常自然而重要。[] 27.2伴随可转移效用的博弈 可转移效用（transferableutility，TU）假设使合作博弈变得容易分析和处理。可 转移效用意味着存在参与人之间可自由转移的一种商品，即货币，使得当任一参与人每 得到一单位货币时，他的收益也增加一单位。在可转移效用假设下，博弈的合作可能性 可用特征函数（characteristicfunction）u：2N→R描述，这个函数将数u（C）指定给相 应联盟CCN。v（）总是取零值。v（C）称为联盟C的价值（value或worth），它描 述联盟C的成员在没有外人（非该联盟的成员）帮助时得到的可转移效用总量。 定义27.2（伴随可转移效用的博弈）伴随可转移效用的博弈是一个二元组（N， v)，其中N={1，"，n}是参与人集合，u：2N→R是一个特征函数，其中u（）=0。 我们也将这样的博弈称为特征型博弈、联盟型博弈、联盟博弈或TU博弈。

注释在可转移效用假设下，对每个联盟指定一个数的做法足以描述联盟成员得到 的效用。 口伴随不可转移效用的博弈 不含可转移效用的博弈[也称为NTU（non-transferableutility）联盟博弈，或 NTU联盟型博弈]的定义如下。 定义27.3（NTU博弈）NTU联盟博弈是一个二元组（N，V)，其中N={1，， n）是参与人集合，V（·）是一个定义在2上的映射，使得对于每个联盟CCN， ·V（C）是RICI的一个非空、闭且凸的子集；而且 ●集合{x:xEV（C）且x≥u;，Vi∈C}是RICI的一个有界子集，其中 u;=max{yi:yEV（{i})}<oo,Vi∈N 在上面的定义中，V（C）是联盟C的成员在合作情形下可以保证他们得到的期望收 益配置集。伴随不可转移效用的博弈（NTU博弈）是伴随可转移效用的博弈（TU博 弈）的推广。在下面的讨论中，我们仅考虑TU博弈。 口伴随可转移效用的博弈的例子 例27.5（分钱博弈）对于例27.1讨论的分钱博弈（版本1)，特征函数为 v（{1,2,3}）=300 v（{1,2}）=v（{1,3}）=v（{2,3})=0 第 v（{1}）=v（{2}）=v（{3}）=0 章 对于例27.2讨论的分钱博弈（版本2），特征函数为 伴随 v（{1,2,3}）=v（{1,2}）=300 可转移放 u（{2,3}）=v（{1,3}）=0 v（{1}）=v（{2}）=v（{3}）=0 效 用 对于例27.3讨论的分钱博弈（版本3），特征函数为 的 联 （{1，2,3}）=v（{1,2}）=v（{1,3}）=300 盟 0=（{}）=（{})=（{}）=（{}） 博弈 对于例27.4讨论的分钱博弈（版本4）：多数同意规则下的投票博弈，特征函数为 （{1，2,3}）=v（{1，2}）=v（{2，3}）=（{1,3}）=300 口 （{1}）=v（{2}）=v（{3}）=0 注释后面，当表达特征函数v（·）的变量时，我们稍微滥用一下符号：在不至 于混淆的情形下，我们去掉集合变量的花括号与逗号；例如，我们将（{2，3}）记为 v（23），以此类推。 例27.6（投票博弈）这个例子来自文献[2]。假设某个国家的议会有四个政党， 即政党1、2、3、4，它们的成员数分别为45、25、15以及12。为了通过给定的任何议 案，至少需要51票。这个情形可以形式化为伴随可转移效用的博弈，其中：

N={1,2,3,4} u（1）=v（2)=v（3）=v（4）=0 v（12）=（13）=v（14）=v（123）=v（124）=v（134）=v（234）=v（1234）=1 （23）=v（24）=v（34）=0 口 到某个共享资源（例如，发电厂、同步加速器、射电望远镜、集群计算、物流站、中央 排水系统等）。为了使用这个资源，用户要么直接连接到设施上，要么连接到某个已连 接到设施上的用户。图27一1（a）画出了典型客户网络，它由三个参与人（客户1、2 和3）以及一个中央共享设施F组成。下面我们提供几个关于这种网络的典型例子。 ·参与人1、2和3为三个不同企业，设施F为发电厂。图中的边表示高负载电线， 边上标注的权重表示配电成本。 ·参与人1、2和3为位于同一城市的三个不同公司，设施F为中央排水系统。边 表示排水管道，边上的权重为维护和使用管道的成本。 ·参与人1、2和3为同一物流网络中的三个分栋点，设施F为物流站。边表示该 物流网中的道路，边上的权重表示路程。 假设当参与人直接或间接连接到F上时，他得到了10单位收益。注意，给定联盟 C二{1，2，3），联盟C成员因连接到设施F而产生的最小成本等于（对应设施F和联 盟C成员的）最小生成树中各边权重的和。例如，假设C={2，3}。于是，对应于C的 最小成本等于涉及顶点2、3和F的最小生成树各边的成本之和。这个最小生成树由边 博弈论与机制 （2，F）与边（2，3）组成，因此，最小总成本为3。再例如，如果C={1，2，3}，那 么最小成本将是涉及顶点1、2、3和F的最小生成树各边成本之和，容易看出它等于 7，即最小总成本为7。图27一1（b）用粗线描述了涉及1、2、3和F的最小生成树。 制 设计 (a) (b) 图27—1连接到中央设施F的客户网络 我们可以将每个联盟的价值自然地定义为，联盟成员得到的总收益减去该联盟所有 成员连接到设施F而产生的最小成本。例如，v（23）等于20一3，这是因为20是参与 人2和3得到的总收益，而3是涉及节点2、3以及F的最小生成树的成本。我们可以 将上述情形形式化为伴随可转移效用的博弈，其中特征函数为 u（）=0;v（1）=10-5=5;v（2）=10-1=9;v（3）=10-3=7 0（0（0（0（ 在确定相关参与人的成本和收益时，这样的博弈表达法非常有用。口

例27.8（物流博弈）图27—2画出了一个物流网络，它连接了两个重要城市S和 T。该网络中有五个物流站A、B、C、D和E，它们是S到T的中间点。服务商1、2、 3和4提供运输服务。网络中的每条边标注了两个数字，它们分别表示服务提供商和服 务成本。例如，AB边上的数字（3，15）表示服务商3提供从A到B的运输服务，成 本为15单位。假设从S到T的物流产生的收益为100单位。我们的目标是选择从S到 T的最优路径，使得利润最大。我们可以将这个问题形式化为合作博弈，其中： 参与人集为N={1，2，3，4} 特征函数为： u（1）=v（2）=v（3）=v（4）=0 v（12）=v（13）=v（14）=v（23）=v（24）=v（34）=v（234）=v（123）=0 v（134）=100-60=40 v（124)=100-55=45 v（1234)=100-35=65 在确定服务商利润分享规则时，上面的博弈非常有用。口 3,50 3,15 1,10 4,0 1,10 2,15 3,10 伴随可转移效用的联盟博弈 1,40 图27—2一个物流网络 口将策略型博奔转换为伴随可转移效用的博弈 如果我们有了模拟参与人之间互动行为的策略型博弈，而且希望模拟这些参与人的合作 行为，那么我们有几种定义伴随可转移效用的博弈（TU博弈）的特征函数的方法。达成此 事的常见方法有三种：（1）最小最大值表达法；（2）防御均衡表达法；（3）理性威胁表达法。 对于这方面的更多细节，读者可以参考Myerson[1]以及Maschler，Solan，andZamir3]。 转归 定义27.4（转归）给定TU博弈（N，v），转归（imputation）是一个满足下列 两个性质的配置x=（x1，，n）∈R”： 个体理性：xi≥u（{i}），ViEN； ·集体理性：∈n;=v(N）。 转归使得每个参与人的状况都变好，而且将大联盟的总价值在参与人之间分配（帕 累托效率）。

定义（优势转归）给定TU博弈（N，）的一个转归x=（x，，n）以及另外 一个转归y=（yi，，y），如果存在联盟C使得 <) 那么我们说x优于（dominate）y。 例27.9（转归与优势转归）我们对转归概念做出一些观察。考虑多数同意规则下 的投票博弈。 （1）配置（150，150，0）以及配置（100，0，200）都是转归，但配置（0，0，0) 以及（100，50，50）不是转归。转归（150，150，0）优于转归（100，0，200），这是 （2）给定两个转归x与y，它们可能都不是优势转归。例如，在多数同意规则下的 投票博弈中，x=（150，150，0）不优于也不劣于y=（0，150，150）。 （3）优势关系不是传递的（transitive），可能出现循环。例如，在多数同意规则下 的投票博弈中，转归（0，180，120）优于转归（150，150，0），转归（150，150，0) 优于转归（90，0，210)，转归（90，0，210）优于转归（0，180，120）。口 27.3伴随特殊结构的TU博弈 博奔论与机制设计 在本节，我们定义几类特殊的TU博弈。 口单调博弈 在单调的TU博弈中，当我们向给定的联盟增加成员时，该联盟的价值不会降低。 定义27.6（单调博弈）给定TU博弈（N，v)，如果 那么我们说这个博弈是单调的（monotonic）。 例27.10可以验证，例27.7中的最小生成树博弈以及例27.8中的物流博弈都是 单调的。事实上，到目前为止，本章讨论的所有例子都是单调的。举个非单调博弈的例 子：在TU博弈（N，v）中，N={1，2}，v（1）=10，v（2)=20，v（12)=15。根据单 调博弈的定义可知，这个博弈不是单调的。口 口超可加博弈 在超可加的TU博弈中，任何两个不相交联盟的并的价值不小于这两个联盟的价值 之和。也就是说，两个不相交的联盟在合并之后能产生超出个体价值之和的非负的额外 价值。 定义27.7（超可加博弈）给定TU博弈（N，v)，如果 u（CUD)≥u(C)+u（D）C,D≤N且CND=Q

那么我们说这个博弈是超可加的（superadditive）。 例27.11给定下列多数同意规则下的投票博弈：N={1，2，3}，v（1）=v（2）= v（3）=0，v（12）=v（13）=v（23）=v（123）=300。这个博弈是超可加的。另外，例27.7 讨论的最小生成树博弈也是超可加的。口 例27.12（非超可加博弈）下列三人博弈不是超可加的： v（1）=10，v（2）=15，v（3）=20，v（12）=20 v（13）=30，v（23）=35，v（123）=40 口 注释注意，单调博弈未必是超可加的，超可加博弈未必是单调的。读者可以构建 以下情形的例子：（a）单调且超可加；（b）单调但不超可加；（c）不单调但超可加； （d）不单调也不超可加。 口基本博弈与非基本博弈 定义27.8（基本超可加博弈）给定超可加博弈（N，v），如果 Zu(i)=u(N) iEN 那么我们说这个博弈为非基本的（inessential）；否则，我们说它是基本的（essential）。 如果（N，v）为非基本的，那么 ∑u(i)=u(C)C≤N iEC 因此，对于非基本博弈，（v（1），v（2），“，v（n））是唯一可能的转归。另一方面，对 第 于基本博弈，可能有无穷多个转归。 章 口策略上等价的TU博弈 伴随可转移效用的联盟博弈 定义27.9给定两个TU博弈（N，u）与（N，w），如果存在常数c1，C2， C以及6>0使得 w(C)=b（u(C)+>c)，C≤N iEC 那么我们说这两个博弈在策略上等价（strategicallyequivalent）。 在直觉上，两个博弈在策略上的等价性意味着其中一个博弈的参与人的“动态”与 另外一个博弈的参与人的“动态”是相同的。 在策略等价层面上有一个重要结果：任何超可加且基本的n人特征型博弈G在策略 上等价于下列唯一博弈： N={1,2,.,n} v（1）=v（2）=·=v（n）=0;v（N）=1 0≤u(C)≤1VCCN 这个唯一博弈称为原博弈的0-1标准化（0-1normalization）。 口三人超可加博奔的三角表示法 给定任何三人博弈，其中v（1）=v（2）=u（3）=0，v（N）=1。这种博弈的转归可用

三角法表示。这种表示法利用了下列性质：假设P是等边三角形内的任何一点，而且 这个等边三角形的高为h。于是，从P到该三角形三条边的垂直距离之和等于h。参见 图27—3。 图27一3等边三角形及其性质x十x2十x3=h 例27.13给定多数同意规则下的投票博弈，其中v（1）=v（2）=v（3）=0，v（12）= v（13）=v（23）=v（123）=1。于是，等边三角形内的任何一点p=（x1，x2，x3）都代表 一个转归，这是因为：x1≥0；x2≥0；x≥0；x十c2十x=1。图27-4画出了几个具 有代表性的转归。口 R 图27-4Q=(，↓，↓),R=(↓，，0)，S=(0,0,1) 以及T=（，，）都是转归 例27.14（多数同意规则下的投票博弈中的议价）给定多数同意规则下的投票博 弈，其中N={1，2，3}，v（1）=v（2）=v（3）=0；v（12）=v（13）=v（23）=v（123）= 300。假设我们从配置（150，150，0）出发，这个配置意味着参与人1和2组成了联 盟。参与人3可以通过提出（180，0，120）这样的分配方案来诱惑参与人1构成新的

联盟。现在，参与人2可以提出（0，120，180）这样的方案来吸引参与人3与他联盟。 在这个特定博弈中，议价可以一直进行下去，无法达成一致同意的分配方案。图27一5 说明了这种情形。口 (20,0,280) （0,30,270) (60,0,240) (0,120,180) (150,0,150) (180,0,120) (150,150,0) (60,240,0) 图27一5多数同意规则下的投票博弈中的议价 凸博弈 在凸的TU博弈中，给定某个联盟，随着更多参与人加人该联盟，该联盟任一成员 的边际贡献也增加。也就是说，参与人有激励加人大型联盟而不是小型联盟。凸博弈的 伴随可转移效用的联盟博弈 正式定义如下。 定义27.10（凸博弈）给定TU博弈，如果 u（CUD)+u（CND)≥u（C)+（D)C,D≤N 那么我们说这个博弈是凸的（convex）。 注释在上面的定义中，假设C与D不相交。于是，我们有 u（CUD)≥u（C)+u（D)C,DCN且CND= 上式正好是超可加性的定义。因此，每个凸博弈都是超可加的。但超可加的博弈未必是 凸的。 在下列命题中，我们提供凸博弈的两个等价定义。我们将这些命题的证明留作 习题。 命题27.1TU博弈（N，v）是凸的当且仅当 u（CU{i})-u（C)≤u（DU{i})-u(D)CCDCN，ViEM\D 命题27.2TU博弈（N，v）是凸的当且仅当 u（CUE)-u（C)≤u（DUE)-u（D)CCDCN,VECM\D

27.4成本博弈 到目前为止，我们讨论的TU博弈都是利润博弈（profitgames），这是因为联盟C 的价值（C）代表联盟成员在没有联盟外成员帮助的情形下得到的（最大）总价值。另 一方面，如果联盟C的价值代表联盟成员必须支付的最低总价格，那么这个TU博弈称 为成本博弈（costgame）。正如下面例子表明的，成本博弈是利润博弈的补。下面这个 例子也说明，在一些情形下，成本博弈比利润博弈更自然。 例27.15（成本博弈）考虑例27.7中的最小生成树博弈。在这里，我们将每个联 盟的价值定义为联盟C的成员因连接到设施F上而产生的最小成本。回忆一下，给定 联盟C二{1，2，3），上述最小成本等于对应于设施F和联盟C的成员的最小生成树各 边权重之和。在这种情形下，成本博弈的特征函数为： u（）=0，v（1）=5，v（2）=1,v（3）=3 （12）=5，（13）=8，u（23）=3，v（123）=7 在确定相关参与人分担的成本时，这样的博弈非常有用。口 27.5小结与参考文献 博 奔论与机 本章重要知识点如下： ·纳什议价解不能自然推广到三人或多人合作博弈，这是因为纳什议价仅考虑了大 制 设计 联盟中参与人之间的议价。这一点可从各个版本的分钱博弈中看出来。 ·在合作博弈中，联盟的形成以及参与人之间的议价可能涉及非常复杂的分析，因 为议价可能无休止地进行下去：在这种情形下，参与人总有激励离开某个联盟，然后加 人新的联盟。合作博弈论提供了各种解概念，旨在为这些复杂议价提供可被接受且科学 的结果。 ·伴随可转移效用的博弈（TU博弈）或称特征型博弈，用特征函数：2V→R描述 合作博弈，其中特征函数对每个联盟指定一个值，这样的值称为联盟的价值。联盟的 价值是联盟成员得到的总效用。一旦我们定义了特征函数，就可以按部就班地进行 分析。 u（·）。通常，潜在问题的结构能指明如何计算不同联盟的特征函数。 ·TU博弈（N，v）中的每个转归都是如下收益配置：所有参与人的收益之和等 于u（N)，而且每个参与人iN的收益至少为v（{i}）。 ·在超可加的TU博弈中，对任何不相交的联盟取并，这个并集的价值不小于这些 个体联盟的价值之和。三人超可加的博弈通常可用三角法表示。 ·在凸博弈中，参与人对任何联盟的边际贡献小于或等于他对该联盟的任何真父集

的边际贡献。在直觉上，随着更多参与人加人某个联盟，该联盟成员的边际贡献是单调 递增的。凸博弈是超可加的，但超可加博弈未必是凸的。 ·在成本博弈中，联盟的价值用参与人承担的最小成本衡量，而不是用他们得到的 最大利润衡量。我们通常研究的TU博弈是利润博弈，成本博弈是利润博弈的补充。 本章的材料主要来自Myerson[1]以及Straffin[4]。另外，Maschler，Solan，and Zamir3]也是一本很好的书。接下来的三章将讨论TU博弈的各种解概念。 参考文献 [1]Roger B.Myerson.GameTheory:Analysisof Conflict.Harvard University Press, Cambridge,Massachusetts,USA,1997. [2]YoamShoham and KevinLeyton-Brown.MultiagentSystems:Algorithmic, Game—Theoretic,and Logical Foundations.Cambridge University Press,New York，USA,2009,2009. [3]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam- bridgeUniversityPress,2013. [4]PhilipD.StraffinJr.GameTheory andStrategy.TheMathematicalAssocia- tion of America,1993 27.6习题 第27 章 （1）给出如下TU博弈的例子：每个转归都劣于另外一个转归。 伴 （2）对于下面每种情形，给出一个TU博弈的例子： 随可转移效用的联盟博弈 ·单调且超可加； ·单调但不超可加； ●超可加但不单调； ·不超可加也不单调。 (3）给定下列博弈（称为通信卫星博弈）： （1）=3，v（2)=2，v（3)=1,v（12)=8，v（13）=6.5,v（23)=8.2，v（123）=11.2 证明这个博弈是超可加的。它是凸的吗？（资料来源：文献[3]。） （4）给定下列TU博弈（N，v)： N={1，2,3};v（1）=（2）=1,v（3）=2，v（12）=v（23）=v（13）=4，v（123）=5 这个博弈是超可加的吗？是凸的吗？（资料来源：文献[3」。） （5）给出一个TU博弈，它是超可加的但不是凸的。 （6）给定任何三人常和（constantsum）博弈（这是一种TU博弈，它的特征是对 于每个联盟C二N，v（C)十v（N\C）是一个常数），将其进行0一1标准化，证明标准 化后的博弈是一个多数同意规则下的投票博弈。 （7）给定两个TU博弈（N，v）与（N，w），给定数入E[0，1]，将这两个博弈的

凸组合定义为博弈（N，)，其中 x（C)=>（C)+(1-x）(C)C≤N 如果（N，v）与（N，）都是凸的，那么（N，z）也是凸的吗？证明你的结论。 （8）证明命题27.1：TU博弈（N，）是凸的当且仅当 u（CU{i})-u（C)≤u（DU{i})-u(D)C≤D≤N，ViEM\D （9）证明命题27.2：TU博弈（N，v）是凸的当且仅当 u（CUE)-u(C)≤u（DUE)-u(D)CCDCN，VECM\D