,经济博弈论基础 Economic Game Theory,第四部分 合作博弈理论,第一节 合作博弈的基本问题 第二节 合作博弈解 第三节 合作博弈应用,第六章 合作博弈 从对手到合作，如何决策,一、合作博弈的意义 合作博弈的意义表现在它与非合作博弈的差别上。豪尔绍尼（1966）提出，在博弈局势中，如果意愿表示（如协议、承诺、威胁等）具有完全的约束力且可强制执行的，则该博弈为合作博弈。如果意愿表示不可强制执行，即使局中人之间在博弈之前可以互相交往，则只能是非合作博弈。,第一节 合作博弈的基本问题,在形式上，有一种观点认为： 可从如下角度把合作博弈看成是非合作博弈的特殊情形，即把达成合作的谈判过程和执行合作协议的强制过程明确地纳入博弈的扩展形式，用扩展型博弈研究合作博弈，从而将合作博弈理论纳入非合作博弈理论体系中。,第一节 合作博弈的基本问题,非合作博弈的重点在个体，是每个局中人该采用什么策略。 合作博弈的重点在群体，何种联盟将会形成，联盟中的成员将如何分配他们可以得到的支付。即使可以把所形成的联盟看作是一个利益主体参与博弈，但如何在联盟内部分配他们的支付则是合作博弈所特有的研究内容。 合作博弈有其独立存在的理论价值，也有比较广泛的应用领域。,第一节 合作博弈的基本问题,(1) 联盟：设N1, 2, , n为局中人集合，则称其中任意一个子集S为一个联盟。所有联盟构成的集合记为P(N)。 (2) 分配：合作博弈的一个分配是指对n个局中人来说，存在一个向量 ，满足： (1) ；(2) 。 其中V(N)表示n个局中人总的最大收益，V(i)表示局中人i不与任何人结盟时的收益。,二、两个重要概念,条件(1)是群体理性，说明个人分配的收益和正好是各种联盟形式总的最大收益； 条件(2)是个体理性，说明从联盟中每个人分配到的收益不小于单独“经营”所得收益，即分配必须使每个人都能得到更多的好处。,三、分配定义中两个条件的含义,（1）对联盟来说，整体收益大于其每个成员单独经营时的收益之和， ； （2）对联盟内部而言，应存在着具有帕累托改进性质的分配规则 ，即每个成员都能获得比不加入联盟时要多一些的收益 , 。 如何保证实现和满足这些条件，这是由合作博弈的本质特点所决定的，也就是联盟内部成员之间的信息是可互相交换的，所达成的协议必须是强制执行的。,四、合作博弈存在的两个基本条件,（1）具有可转移效用的：可转移效用是指联盟中各局中人获得的效用可以相互转移； （2）具有不可转移效用的：不可转移效用是指局中人获得的效用不可转移。 合作博弈中一般研究的是具有可转移效用的合作博弈，应用的工具就是联盟型博弈，在理论上常常称为特征函数型博弈。,五、合作博弈分为两类,联盟型博弈(特征函数型博弈)：对每一种可能联盟给出相应的联盟总和收益，也就是给出了一种集合函数，称为特征函数V（）。 特征函数具有超加性：对任意两个独立联盟S与T（两者没有公共成员，即ST=），有V(ST)V(S)+V(T)。 具有n个局中人，局中人集合为N1,2,n ，特征函数为V(）的特征函数型博弈被记为（N,V)。,六、联盟型博弈,在合作博弈中如果有 ，则称该合作博弈是非本质的，其中V(i)表示局中人i一人组成的联盟； 若有 ，则此合作博弈是本质的，即存在有净增收益的联盟。 如果对于任何联盟S，有V(S)+V(NS)=V(N)，其中NS表示N中除了S成员之外的其他成员组成的联盟，那么此合作博弈被称为常和的。,六、联盟型博弈,例1：策略型博弈,七、策略型博弈向特征函数型博弈的转化,例1中存在四个联盟：、1、2、1,2。 特征函数即对这四种联盟求得他们各自的总和收益，一般的求法是设联盟外局中人将采取行动使该联盟的总和收益最少（体现了“从坏处着想，往好处努力”的思想）。,七、策略型博弈向特征函数型博弈的转化,V()=0，没有人的联盟是不会有任何收益的; V(1)=0，局中人2能使局中人1面临的最坏情形是局中人2取策略 ，局中人1将不得不在0与-1之间选择。 V(2)=5，局中人1能使局中人2面临的最坏情形是局中人1取 ，局中人2将不得不在2与5之间选择。 V(1, 2)=10，没有联盟外局中人，10是局中人1与2能取得最大总和收益。,七、策略型博弈向特征函数型博弈的转化,对于特征函数的上述求法，主要的批评是：它忽略了联盟外局中人使联盟面临最坏处境时，自己也将付出代价（有时代价很高）。 Harsayni认为，特征函数的取值应该由联盟与其对立联盟（联盟外所有局中人形成的联盟）之间的一次谈判而决定。,七、策略型博弈向特征函数型博弈的转化,例2：垃圾博弈： 在一区域中居住着7户居民，每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家中（区域中没有空地）。 这就构成了一种博弈局势，在合作博弈条件下，可以直接分析得到其中的特征函数。,八、实际博弈局势分析得到特征函数型博弈,Vn表示任意n个局中人组成联盟的特征函数值，n=1, , 7。 V0=V()=0； V1=-6，1个局中人组成的联盟所遇到的最糟处境是其他6个局中人将他们产生的垃圾扔到他自己的地里，即收到6袋垃圾，自己则可将垃圾扔到其他任意一个局中人的地里；,八、实际博弈局势分析得到特征函数型博弈,V2=-5，两个局中人组成的联盟则将收到5袋垃圾，联盟产生的两袋垃圾处理到联盟外局中人的地中； 同理，V3=-4， V4=-3，V5=-2，V6=-1 V7=-7，而全部7个局中人组成的联盟的特征函数值有所不同，他们无法将垃圾扔到非联盟成员的地里，收到7袋垃圾。,八、实际博弈局势分析得到特征函数型博弈,一、合作博弈求解思路 合作博弈理论求解的目的： 得到博弈的“理性”最终分配，主要方法有两种：优超与赋值。,第二节 合作博弈解,优 超,设有n个局中人，每个局中人有相应的可选择策略，在（所有）可能的策略组合上定义各局中人的效用函数。效用向量 则表现博弈的一种分配。 对于不可转移效用情形的合作博弈，定义优超为： 一种效用向量 被优超是指存在一种联盟S，对于联盟中的每一成员i，联盟给予他的效用将大于效用向量中他得到的，即对任意 ， 。,优 超,直观上说优超就是联盟中的每个人都感觉好的分配原则肯定比只有部分人感觉好的分配准则更可取。 利用优超可以定义合作博弈均衡，即指这样的局中人策略组合，它产生的效用向量不被任何联盟所优超（核）。,优 超,对于可转移效用情形的合作博弈，定义优超为： 一种效用分配 被优超是指存在一种联盟S，该联盟获得的总和收益V(S)大于效用分配向量提供给该联盟个成员的效用之和，即 。,二、合作博弈解,1、核 定义1: 设x和y为n人合作博弈(N,V)的两个分配， 为一个联盟，如果：(1)对任意 ，有 ；(2) ，则称x在S上优超y，记为 。 对于两个分配x和y，如果存在某联盟S，使得 ，则称x优超y，记为 。 注意:对于联盟S=N 或S=i，不能有 。,1、核,一旦联盟S发现有 ，它将放弃分配y而接受x。所以，只有不被优超的分配对局中人来说才令人满意。这就是核的意义。 定义2: n人合作博弈(N,V)的所有不被优超的分配的集合称为它的核，记为C(V)。,1、核,定理1(核的特征): n人合作博弈(N,V)的核由所有满足以下条件的n维向量 组成： (1) 对任意 ， ；(2) 。 由此定理可知核是闭凸集。如果博弈的核非空，就可以将总收益V(N)按这样一种方式分配给各个局中人，使之不仅满足个体理性和群体理性，而且满足联盟理性，即任何联盟在这种方式下的所得都不小于它独立出来时的所得，因而也就没有积极性拒绝这样的分配。,1、核,把核中的分配作为合作博弈的解，一个致命的缺陷就是核有时是空的。例如，有以下的定理。 定理2： 常和合作博弈的核是空的。 作为一种解，存在性可说是最重要的性质，核有时存在，有时不存在，这样何时核存在就称为一个很重要的问题，以下是关于核存在性的定理。,1、核,定理3（核的存在性）：对于n人合作博弈(N,V)，核C(V) 非空的充分必要条件是下述线性规划: 有最小值 。,简单博弈,定义3：如果合作博弈中联盟的特征函数值不是0就是1，那么称之为简单博弈。在简单博弈(N,V)中，如果对于某局中人 ，则称局中人 为具有否决权的局中人。 简单博弈常用来描述投票问题。这种博弈的核有以下结论 定理4：在简单博弈(N,V)中，核C(V)非空的充分必要条件是存在有否决权的局中人。,稳定集是由冯诺依曼与摩根斯特恩提出来的概念，有时被记为VN-M解。记所有可能分配组成的集合为E(V)，则稳定集定义如下： 定义4：对于n人合作博弈(N,V)，分配集 为稳定集，则W满足: (1)（内部稳定性）不存在 ，满足 ； (2)（外部稳定性）对 ，使得 。,2、稳定集,作为稳定集存在的例子有： 定理5：对于简单博弈(N,V)，S是一个极小获胜联盟（即 V(S)=1，但对S的任何真子集T 有V(T)=0），则稳定集为:,2、稳定集,2、稳定集,稳定集和核之间有如下关系： 定理6：设n人合作博弈(N,V)的稳定集为W，核为C(V)，则 。 稳定集的存在性比核要好一些，但有时稳定集仍是不存在的，这就需要其它解的概念。,核仁具有如下性质：(1)每个博弈有且仅有一个核仁；(2)如果核存在的话，核仁是它的一部分。 为了定义核仁，首先定义剩余的概念。 定义5：对于n人合作博弈(N,V)，S为一个联盟， 为一个分配，记 ，则 称为S关于x的剩余。,3、核仁,剩余 反映了联盟对于分配的不满意程度，当然每个联 盟都希望剩余越小越好。因为N的子集共有 个, 也 有 个，可以将它们按照由小到大的顺序排列为一个向量 。设x，y为两个向量，为了比较好坏 引入“”, 是指或者 或者对k=1, (i-1), 有 而 。,3、核仁,3、核仁,定义6：对于n人合作博弈(N,V)，它的核仁 N(V)是指集合 定理7（核仁的性质）：对于n人合作博弈(N,V)，则有： (1) 它的核仁N(V)非空，而且只包含一个元素； (2) 若核C(V)非空，则它必定包含核仁，即,4、夏普利值（Shapley value）,夏普利值是利用公理化方法得到合作博弈的唯一解。 设 为局中人i在博弈(N,V)中应该得到的期望收益，则夏普利指出，它应该满足几种公理。首先给出辅助性定义。 定义7：对于n人合作博弈(N,V)，T是一个联盟，如果对任意联盟S均有 ，则称T为这个博弈的承载 。,4、夏普利值（Shapley value）,承载常常不唯一。如果T是承载，则 也是承载。 如果T为承载，那么在T以外的局中人对任何联盟都没有什么贡献，相当于哑元(dummy)。 定义8： 对于n人合作博弈(N,V)， 为N上的一个置换运算。定义博弈 为这样一个新博弈(N,U) ，对任意联盟 ，有 .,4、夏普利值（Shapley value）,值 应满足以下公理： （有效性公理） 若S为(N,V)的任意一个承载，则有 ； （对称性公理）: 对N的任意置换 和 ，有 （可加性公理）对任意两个 n人合作博弈(N,U) 和 (N,V