《合作博弈论》PPT课件.ppt

第9讲 合作博弈,一般来说，博弈论可以分为合作博弈（cooperative games）与非合作博弈（non-cooperative games），现代大多经济学家谈到的博弈论往往指的是非合作博弈论，很少提到合作博弈论，甚至很多博弈论教材也未曾提到合作博弈。实际上，合作博弈的出现和研究比非合作博弈要早，早在1881年，Edgeworth在他的数学心理学一书中就已经体现了合作博弈的思想。合作博弈的运用研究主要涉及企业、城市、区域经济以及国家之间的合作等多个方面问题。,参考教材:范如国：博弈论,武汉大学出版社，2011,虽然这些分析所针对的合作问题类型不同，研究重点或在于阐明合作的内在逻辑，或在于揭示合作的动因，但是研究结果则有助于加强企业的相互联系、完善城市的合作模式、推动区域经济合作实践、促进国家之间的经济交往。这里，我们首先介绍静态合作的基本概念，然后再介绍各种静态合作博弈的不同解法，包括核心（core）与稳定集（stable sets）、夏普利值（Shapley value）、谈判集（negotiation sets）、内核（kernel）与核仁（nucleolus），最后再举出静态合作在现实的经济方面的各种解法的应用例子。,导论,先回忆一下囚徒困境的例子：在囚徒困境中，还有另外一个策略组合，该组合为参与人带来的支付是。由到，每个参与人的支付都增加了，即得到一个帕累托改进。,构不成一个均衡是基于参与人的个人理性。在参与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机行为谋取超额收益1。如果两个参与人在博弈之前，签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第三方支付价值大于1的保证金；如果谁违背了这个协议，则放弃保证金。有了这样一个协议，就称为一个均衡，每个人的收益都得到改善。上述分析表明，通过一个有约束力的协议，原来不能实现的合作方案现在可以实现。这就是合作博弈与非合作博弈的区别。二者的主要区别在于人们的行为相互作用时,当事人是否达成一个具有约束力的协议。如果有,就是合作博弈；反之,则是非合作博弈。因此，博弈可以划分为合作博弈与非合作博弈。,第一节 合作博弈的基本概念,合作博弈是指参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型。合作博弈强调的是集体理性,强调效率、公正、公平。合作博弈最重要的两个概念是联盟和分配。每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益。每个参与者从联盟中分配到的收益不小于单独经营所得收益。合作博弈的基本形式是联盟博弈,它隐含的假设是存在一个在参与者之间可以自由流动的交换媒介(如货币),每个参与者的效用与它是线性相关的。这些博弈被称为“单边支付”博弈,或可转移效用(Transferable Utility,TU)博弈。,合作博弈的结果必须是一个帕累托改进，博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害。合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，合作之所以能够增进双方的利益，就是因为合作博弈能够产生一种合作剩余。至于合作剩余在博弈各方之间如何分配，取决于博弈各方的力量对比和制度设计。因此，合作剩余的分配既是合作的结果，又是达成合作的条件。合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的得益。下面首先分析联盟的概念，与联盟相关联的是特征函数。,在1950年到1953年间，纳什发表了四篇有关博弈论的重要文献（纳什，1950a，1950b，1951，1953），文献中很清楚地对合作博弈与非合作博弈进行了界定，他所用的界定条件就是博弈者之间是否具有约束力的协议。他认为如果一个博弈当中的博弈者能够作出具有约束力的协议，那么此博弈便是一个合作博弈，反之，则称为一个非合作博弈。根据纳什的这一界定条件，由于合作博弈中存在具有约束力的协议，因此，每位博弈者都能够按自己的利益与其他部分的博弈者组成一个小集团，彼此合作以谋求更大的总支付。我们称这些小集团为联盟（coalition），而由所有博弈者组成的联盟则称为总联盟（grand coalition）。因此，对有n个局中人参与的博弈，即，我们称集合 N 的任何一个子集 S 为一个联盟。,定义1.1 设博弈的局中人集合为，则对于任意，我们称 为 的一个联盟（coalition）。这里，允许取 和 两种特殊情况，我们把 称为一个大联盟。若，则 中联盟个数为。正式的合作博弈的定义是以特征函数（characteristic function form）的 形式给出的，简称博弈的特征性，也称联盟型。,定义1.2 给定一个有限的参与人集合，合作博弈的特征型是有序数对，其中特征函数 是从 到实数集 的映射，即，且。是 中的联盟 和 博弈时S的最大效用，称为联盟S的特征函数（characteristic function),表示联盟中参与人相互合作所能获得的得益（支付）。之所以称为特征函数，是因为这个合作博弈的性质基本由 决定。由此可见 对合作博弈的重要性。特征函数是研究联盟博弈的基础，确定特征函数的过程实际上就是一个建立合作博弈的过程。,在合作博弈中，支付可能是收益，也可能是成本（负效应）。如果这总得益是可以被瓜分的，我们则称它为可转移的（transferable）；反之，则称为不可转移的（non-transferable）。,合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。1.如果 仅与 的个数有关，则 称作对称博弈。2如果，则 称作常和博弈。3如果，则 称作简单博弈。例如在投票博弈中，每个参与人的权重，如果，则 称作凸博弈。,定义1.3 一个支付可转移的联盟型博弈是由一个有限的博弈者集合 和一个定义在集合 的函数 所组成的，而这函数 对集合 当中的每一个可能的非空子集 都会进行赋值，其值为一个实数，我们用 来表示合作博弈，而函数为每一个集合所赋的值则称为S的联盟值。,函数 对集合 当中的每一个可能的非空子集 都会进行赋值，其值为一个实数，我们用 来表示一个合作博弈，而函数为每一个集合所赋的值则称为S的联盟值。为了确保每位博弈者都愿意组成总联盟，合作博弈论一般要求支付可转移的联盟型博弈为有结合力的：定义1.4 一个支付可以转移的联盟型博弈 是有结合力的，当且仅当，对于集合 的每个分割物，即，且，以下的关系式都成立：根据上述定义，我们可以得知，在一个具有结合力的,支付可转移的联盟型博弈中，如果我们把总联盟 分成 个不相交的小联盟，那么，这 个小联盟的得益的总数是绝不会大于总联盟的得益。由于这些博弈中的支付都是可转移的，因此，总联盟型的情况必定是帕累托最优的。在很多情况下，为了使得每位博弈者有更大的意欲组成总联盟，合作博弈论更会要求博弈具有可超加性或是超可加的：定义1.5 在一个支付可转移的联盟型博弈 中，如果对于任意的，且，有，那么，我们称该合作博弈 是超可加的；如果对于任意的，且，有，那么，我们称该合作博弈 是次可加的；如果对于任意的，且，有，,那么，我们称该合作博弈 是可加的。定义1.6 在合作博弈 中，若对于任意的，满足以下条件：则称特征函数 具有凸性，相对应的博弈称为凸博弈。从上述定义中可以看出，参与人对某个联盟的边际贡献随着联盟规模的扩大而增加。也就是说，在凸博弈中，合作是规模报酬递增的。显然，特征函数满足凸性的一定满足超可加性。特征函数的凸性表示联盟越大，新成员的实际贡献就越大。,上式说明，特征函数只有满足超可加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么，其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。上式定义的逆命题也是正确的，即：是一个集合，是定义在 上的一个非负实值函数。满足：，如果 则存在一个 上的合作博弈，使 成为该合作博弈的特征函数。,对于合作博弈，特征函数 满足超加性，自然有：根据上述不等式，特征函数 分成两种类型：类型1，满足。即大联盟的效用是每个参与人的效用之和。这说明通过联盟并没有创造新的合作剩余，联盟没有价值，这种联盟也不可能维持。这种对策称为非实质性对策，没有研究价值，不是本章研究的范畴。对于非实质性对策，有，如果。,类型2，满足。即大联盟的效用大于每个参与人的效用之和。这说明通过联盟创造了新的合作剩余，联盟有意义，这种联盟能否维持，取决于如何分配合作剩余，使每个参与人的支付都有改善。这种对策称为实质性对策。,定义1.7 一个合作博弈，若特征函数满足下面的两个条件：则称该博弈为 标准化博弈。标准化博弈主要是为了简化证明过程而假设的，他们要求单个参与人不会产生任何得益，而大联盟所产生的得益标准化为1。,例.假设有五个人A、B、C、D、E，决定合资建厂。每个人或是以人力资本投资，或是以资金投资。经过认真的可行性研究，建成后的合资公司年利润为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单位，大于在大联盟中得到的64单位（46+18），而A、B没有足够的资金自行建厂。因此，A和B不得不分给C、D、E 71单位，而把剩下的29单位在A和B中平分。如果C、D、E将71单位利润平分的话，又会产生另一个问题。由于B、D、E三人合作建厂的年利润为65单位，就使得刚才那个分配又变得不可行。那么，它们该怎么办呢？,为了简单起见，我们将此博弈的特征函数形式列在表1中。该表列出了每个可能的联盟可能获得的总利润。,表1：各合作方案下联盟获得的总利润,通过观察表1，我们就会发现，当任意两个联盟的交集为空集的时候，这两个联盟中的所有参与人组成的新联盟的总利润总是不小于原先的两个联盟的利润之和。因此，这种博弈就是前面我们所讨论的超可加博弈。,第二节 核心与稳定集 下面，我们将首先介绍个体理性和整体理性，然后再分别介绍合作博弈的两个解法概念-核心和稳定集。一、个体理性和整体理性 当一个博弈具有超可加性，那么便只有组成总联盟才能最优化所有博弈者的总得益。在一个支付可转移的联盟型博弈中，我们可以用一个支付向量 来代表瓜分这总得益的方案，而这向量当中的 则是博弈者 组成联盟后所分得的支付(分配）。我们用 表示在这个支付向量中，每位博弈者所能获得的支付的总和。,由于每位博弈者都是理性的，所以一个能为所有博弈者接受的支付向量必定既符合联盟的整体理性，又符合每位参与联盟的博弈者的个体理性，而一个同时符合整体理性和个体理性的支付向量则称为一个分配或有效的分配。下面我们对整体理性和个体理想给出如下定义：定义2.1 在一个支付可转移的联盟型博弈中，支付向量是 符合整体理性的，当且仅当，每位博弈者所分得的支付的总和等于总联盟的价值，即:由于所有博弈者的总支付实现了最优化，因此，我们称之为整体理性或整体最优。,定义2.2 在一个支付可转移的联盟型博弈 中，支付向量 是符合个体理性的，当且仅当，每位博弈者所分得的支付都比各自为政时高，即在一个支付可转移的联盟型博弈 中，支付向量 称为一个分配或有效的分配，当且仅当，它是符合个体理性和整体理性的。定义2.3 一个支付可转移的联盟型博弈的分配集 定义为：且对于，都有。,二、核心（Core）与稳定集1.核心的概念 定义2.4 一个支付可转移联盟型博弈的核心 是一个集合，当中包含所有能满足以下两个条件的支付向量：（1）（2）根据上述定义，核心不仅要满足整体理性，还要满足集合N中每个小联盟S的“理性”。否则，联盟S的成员的整体支付便没有进行最优化。也就是说，只要通过脱离总联盟，然后成立新的联盟S，那么新联盟S的成员便能够瓜分一个比他们的分配的总和大的联盟价值。因此，核心是一个不仅能满足个体和整体理性，而且能满足每个联盟的“理性”的集合。,2.核心的应用核心作为合作博弈其中一个最基本的解法，其应用范围也非常广泛，以下是一个在现实经济方面的应用例子。例子：三人社会合作我们用 代表这三人的集合，如果三人同心协力地合作，并组成一个单一联盟，那么，他们便能把这个社会的总利益最优化，并通过协同效应创造出30个单位的总得益。而如果只有其中二人合作并组成联盟，而剩下的一人独自为政，那么这二人也能创造出 个单位的利益。但 个单位的利益只供那二人分享，而,剩下的一位在独自为政的情况下只能创造出6个单位的得益。现在把以上的三人社会转换为一个支付可转移的联盟型博弈：；当 其中，则代表联盟S的成员数目。由于这个博弈中共有三位博弈者，因而核心是一个由非负的支付向量 所组成的集合。在博弈中，核心要满足整体理性，故此，同时，核心又要满足由一位或两位博弈者所组成的小联盟S的“理性”，故此：，当；以及，当。,当，核心便是由无数个支付向量所组成，即 也就是说，每位博弈者至少也可以获得独自为政时的支付，但最多只可以得到整体合作下和其中二人合作下的利益的差。当，核心便只包含一个支付向量（10,10,10），就是三人平分整体合作下的利益。当，核心便是空的，也就是说，这个社会并不存在属于核心的合作方案。,3、稳定集（Stable Sets）的定义在一个 人博弈中，联盟 对于一个任意的分配 是有效果的，当且仅当，这个联盟的价值高于他们在 分配下的支付的总和，即。也就是说，如果联盟 对于 分配是有效果的，那么分配 便是不稳定的。有了“有效果”的概念，我们便可以介绍分配的占优，以下是它们的定义：定义2.5 在一个支付可转移的联盟性合作博弈中，分配x通过联盟S 占优分配y，当且仅当：且，当严格不等式成立时称分配x通过联盟S严格占优于分配y。,定义2.6 支付可转移的联盟性合作博弈的解集符合内部稳定性，如果该集合内的任何分配都不会通过联盟S 占优于该集合内的其他分配。也就是说内部稳定性要求联盟内部的任意两个分配不存在占优关系。定义2.7 支付可转移的联盟性合作博弈的解集符合外部稳定性，如果对于集合外的任意分配，联盟S都存在某配置占优于该集合外的分配。定义2.8 在支付可转移的联盟性合作博弈中，集合X称为稳定集，当且仅当该集合既符合内部稳定性，也符合外部稳定性。,第三节 夏普利值及其应用 分配是合作博弈最重要的概念，但遗憾的是在一个博弈中，分配有无限个，且许多根本就得不到执行。合作博弈最困难也最有挑战性之处在于建立一个统一的“解”的概念，即从各种各样不具有良好性质的解中挑选唯一的分配或成本分配方案。不难看出，这几乎是不可能也没有必要的事情。合作博弈与非合作博弈很大的不同之处在于合作博弈没有一个统一的解的概念，因为没有哪个解能够符合所有人对“公平”的理解。,根据前面的分析，我们知道博弈的核可能是空集，而且如果不是空集，核分配也很可能不唯一。随着合作博弈论的发展，现在已经有很多具有唯一解的概念，称为值（Values）,其中最重要的就是夏(沙)普利值。合作博弈在理论上的重要突破及其以后的发展在很大程度起源于夏普利(Shapley)提出的夏普利值的解的概念及其公理化刻画。Shapley值是一个很直观的解的概念，参与人按照Shapley值进行分配。,一、夏普利值(Shapley Values)夏普利值是由夏普利提出的，最初只是应用在支付可转移的情况下，其后由夏普利扩展到支付不可转移的情况，这里我们只介绍支付可转移的沙普利值。由于夏普利是建立在几个公理上，因此，在介绍夏普利值之前，我们需要介绍一些定义。在夏普利的设定中，存在着一个包含所有博弈者的宇集U，而每个博弈中的所有博弈者集合N，都是宇集的子集，并称为一个载形，以下是载形的定义：,定义3.1 在一个支付可转移的联盟型博弈，联盟 称为一个载形，当且仅当，对于任何一个联盟，都存在着以下的关系：根据定义3.1，一个载形包含了所有会对至少一个联盟作出贡献的博弈者，也就是说，任何不属于载形的博弈者都不会对任何联盟作出贡献。定义3.2 博弈者i和j在博弈中是可互换的，当对于所有包括博弈者 I 但不包含博弈者j的联盟S，都存在着以下的关系：根据定义3.2，博弈者i和j对于联盟S的用处和贡献都是完全一样的。,根据以上的定义，我们称n维向量 为一个值，这个值包含了n个实数，分别代表着在博弈 中的n位博弈者所分得的支付。这个值可以理解为每位博弈者在博弈开始之前对自己所分得的支付的合理期望，而这个值必须满足以下的三个公理：公理1 如果集合N是一个载形，那么此公理又称为效率公理，要求的是整体理性。公理2 如果博弈者i和j是可互换的，那么此公理又称对称公理，要求的是博弈者的名称并不会对影响博弈起任何作用。公理3 如果 和 是两个博弈，那么,此公理又称集成定律，要求的是任何两个独立的博弈联合在一起，那么所组成的新博弈的值是原来的两个博弈的值的直接相加。根据上述的定理和公理，可以得到一个能满足夏普利公理的函数：定理1（夏普利定理）函数 是唯一能够满足以上三个公理的函数，这函数可以表达为:（2）其中，（3）则为联盟S的成员数目，我们称 为夏普利值。,在定理1中，可以理解为博弈者 对联盟S的边际贡献，而 则是每个联盟S的加权因子。,对于 也可以作出这样解释：加入，其贡献是。，加入 的概率是多少？如果 个局中人依次参加博弈，当 加入该博弈时，其前面已有一些参与人，加入后，后继的参与人集合。和 中参与人的顺序与 无关。加入 的概率是，的数学期望（或者平均值）就是Shapley值。注：Shapley值不一定是个分配，即理性约束 可能不满足。,二、夏普利值的应用夏普利值的用途广泛，尤其常用于经贸合作和政治科学。早在20世纪50年代，夏普利与苏比克便利用夏普利值来计算联合国安全理事会成员国的权力值，这亦是博弈论对于社会科学的一项最早应用。在60年代，苏比克把夏普利值应用在会计学上，并指出夏普利值适用于计算一间公司的内部成本调配，而博克亦把夏普利值应用在保险学上，并指出夏普利值能合理地计算所有类别的风险。,例1 我国石油公司间竞合利益分配 近几年来，我国石油对外依存度已超过50%的警戒线，经济发展对石油的依赖性明显增强。我国石油公司如何为我国经济发展保驾护航，针对石油行业是资金与风险密集型行业的特性，走与国内石油公司、国外石油公司竞合之路是石油公司战略的必然选择。从近几年中石油、中石化、中海油的经营策略看，也明显呈现出这样的特性。仅2009年，中海油与中石化已经达成了华东、华南市场异地油源置换的协议；中石油与中石化将在塔里木盆地展开广泛的合作；中石油与中海油联手提出了收购其阿根廷子公司YPF的收购提议，都能说明我国各大石油公司间的关,系由原来单纯的竞争走向竞合。石油公司间要形成良好的合作关系，并能使该合作关系持续发展下去的基础就是有一个良好的利益分配机制。博弈论中的合作博弈为这种利益分配提供了理论基础。设有三家石油企业合作开发某油田区块，如果单独开发必然需要消耗大量的资金、技术、工具等有形或无形成本，相反，如果每家公司都能利用自己的优势进行合作，则进度更快、质量更高而且取得的效益更大。针对石油项目开发，利用我国西部某油田的基础数据，对基础数据进行简化得出下列模拟数据。数据主要反映三家公司单独开发、两家合作开发或三家共同开发的收益，即三人合作博弈的特征函数值如下：,。试计算三家油田企业合作的利益分配。显然，以上的博弈具有超可加性，因此，我们可以求取这博弈的夏普利值。根据上述对沙普利值方法的介绍，我们可以首先计算出第1家石油企业对每个可能联盟的平均边际贡献值：,然后，我们可以计算出第2家石油企业对每个可能联盟的平均边际贡献值：最后，我们可以计算出第3家石油企业对每个可能联盟的平均边际贡献值：因此，夏普利值为。,例2 汽车买卖有一个住三个人的小镇，我们用 代表这三人的集合。假设博弈者1在无意中得到一部汽车，但由于他不懂驾驶，该车对他来说只有观赏价值。博弈者2懂得驾驶，但他却没有汽车，而博弈者3则是经营废铁回收的。假定博弈者1认为该车的观赏价值相等于1000元，博弈者2认为该车价值10000元，而博弈者3则认为该车相等于3000元的废铁。可以把以上的决策情况转换为一个支付可转移的联盟型博弈：,显然，以上的博弈同样具有超可加性，因此，我们可以求取这博弈的夏普利值。首先，我们计算博弈者1对每个可能联盟的平均边际贡献值：然后，我们计算博弈者2对每个可能联盟的平均边际贡献值：,最后，我们计算博弈者3对每个可能联盟的平均边际贡献值：因此，夏普利值为。,