合作联盟博弈课件

博弈论

经济与管理学院刘洋博士

1博弈论经济与管理学院刘洋博士1博弈论经济与管理学院刘洋博士1博弈论经济与管理学合作博弈

（COOPERATIVEGAMES)2合作博弈

（COOPERATIVEGAMES)2合作博弈

（COOPERATIVEGAMES)2合作博

合作博弈

COOPERATIVEGAMES熊、狼、狐狸一起抓了一只兔子，民主协商如何分配。狐狸对熊说：平均分只能各得1/3，这样吧，我们俩联合起来，平分如何？熊要答应，狼急了，于是狐狸对狼说：怎么样，我和熊联合起来可以让你什么也得不到，我可以和你合作，不过我要3/4。狼感激的点头，熊琢磨过味来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。狐狸见势不妙，对狼说：别，我给你2/3，我只要1/3。狼成了抢手货，正得意，没留神狐狸和熊又开始嘀咕起来，有再次把自己晾在一边的不妙趋势，连忙钻去继续讨价还价。结果呢？3合作博弈

COOPERATIVEGAM合作博弈

COOPERATIVEGAM如果在实际博弈问题中，具有有力的保障使局中人能够进行协商、谈判，联合选择行动，共同分享利益，我们就面对一个合作博弈问题。本章通过合作博弈模型的介绍，讨论在合作博弈中，局中人如何进行协商谈判、结成联盟及分享利益。1、联盟博弈2、联盟博弈的分配3、核和稳定集4、沙普利值4444导论先回忆一下囚徒困境的例子：

在囚徒困境中，还有另外一个策略组合<抵抗，抵抗>，该组合为参与人带来的支付是<-1,-1>。由<-8,-8>到<-1,-1>，每个参与人的支付都增加了，即得到一个帕累托改进。坦白抵抗坦白-8，-80，-10抵抗-10，0-1，-15导论先回忆一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1导论先回忆一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1导论

<抵抗，抵抗>构不成一个均衡是基于参与人的个人理性。在参与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机行为谋取超额收益1。如果两个参与人在博弈之前，签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第三方支付价值大于1的保证金；如果谁违背了这个协议，则放弃保证金。有了这样一个协议，<抵抗，抵抗>就称为一个均衡，每个人的收益都得到改善。上述分析表明，通过一个有约束力的协议，原来不能实现的合作方案现在可以实现。这就是合作博弈与非合作博弈的区别。二者的主要区别在于人们的行为相互作用时,当事人是否达成一个具有约束力的协议。如果有,就是合作博弈；反之,则是非合作博弈。6导论<抵抗，抵抗>构不成一个均衡是基于参与人的个人导论<抵抗，抵抗>构不成一个均衡是基于参与人的个人合作博弈的概念及其表示

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

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

合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的支付。8合作博弈的概念及其表示合作博弈的结果必合作博弈的概念及其表示合作博弈的结果必合作博弈的概念及其表示

定义1

在人博弈中，参与人集用表示，的任意子集称为一个联盟（coalition）。

空集和全集也可以看成是一个联盟，当然单点集也是一个联盟。定义2

给定一个人博弈，是一个联盟，是指和的两人博弈中的最大效用，称为联盟的特征函数（characteristicfunction）。

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

合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。如果仅与的个数有关，则称作对称博弈。如果，则称作常和博弈。如果，则称作简单博弈。例如，在投票博弈中，每个参与人的权重，

如果，则称作凸博弈。10合作博弈的概念及其表示合作对策的分类主要是根据特征函合作博弈的概念及其表示合作对策的分类主要是根据特征函合作博弈的概念及其表示

之所以称为特征函数，是因为这个合作博弈的性质基本由决定。由此可见对合作博弈的重要性。定理设是参与人集合上的特征函数，则有如下的超可加性：对于联盟和，如果，则上式说明，特征函数只有满足超加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么，其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。11合作博弈的概念及其表示之所以称为特征函数，是因合作博弈的概念及其表示之所以称为特征函数，是因例：

局中人1（卖主）要把一件物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是x

元，则局中人2赢利9-x元。联盟的总收益为9元。类似，联盟的总赢利为10元。于是有。另一方面，单个局中人或者两个买主在一起都不可能赢利，即，。当三个局中人在一起交易时，局中人1显然要把物品卖给局中人3，从而v({1,2,3})=10，显然满足超可加性，于是我们建立了联盟博弈。特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。12例：局中人1（卖主）要把一件物品卖掉，局中人2和3（买主例：局中人1（卖主）要把一件物品卖掉，局中人2和3（买主由策略型博弈导出特征函数型博弈V()=0V(1)=0V(2)=5V(1,2)=10局中人2LR局中人1U-1，25，5D0，100，10最小最大值法：联盟外局中人将采取行动使该联盟的总和收益最小（极度悲观），联盟选择策略－－最大化这些最小值。13由策略型博弈导出特征函数型博弈V()=0局中人2LR局中人由策略型博弈导出特征函数型博弈V()=0局中人2LR局中人例：垃圾博弈－－分析博弈局势在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。记Vn(n=0,1,…,7)表示任意n个局中人组成的特征函数值，在合作博弈条件下，有：

V0=V()=0

V1=-6

V2=-5V3=-4，V4=-3，V5=-2

V6=-1，V7=-714例：垃圾博弈－－分析博弈局势在一区域中住着7户居民，每户居民例：垃圾博弈－－分析博弈局势在一区域中住着7户居民，每户居民合作博弈的概念及其表示例：设有一个3人合作对策，每个参与人各有两个纯策略。当三人不合作时，其支付见下表。假设采用最稳妥策略，即最坏情况下选择最好，求合作博弈的支付函数15合作博弈的概念及其表示例：设有一个3人合作对策，每个参与人各合作博弈的概念及其表示例：设有一个3人合作对策，每个参与人各合作博弈的概念及其表示解：用表示一个联盟，表示联盟中参与人的个数。当＝0，自然，有。当＝1，有3个，以为例。当，则。的策略集合，策略组合。与进行如下矩阵对策：16合作博弈的概念及其表示解：用表示一个联盟，合作博弈的概念及其表示解：用表示一个联盟，合作博弈的概念及其表示

上述矩阵对策没有纯策略，的混合策略是，的混合策略是。的均衡值是。故。同理，可以求出。当＝2，有3个，以为例。当，则。的策略集合,

策略组合。与进行如下矩阵对策：17合作博弈的概念及其表示上述矩阵对策没有纯策略，合作博弈的概念及其表示上述矩阵对策没有纯策略，合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值是3。故。同理，可以求出。当＝3，有1个，，最大的联盟。的策略空间。有。至此特征函数的值已全部求出。18合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值分配

所谓分配就是博弈的一个维向量集合，之所以是维向量，是由于每个参与人都要得到相应的分配。维的分配向量称为博弈的“解”。定义3

对于合作博弈，对每个参与人，给予一个实值参数，形成维向量且其满足：

则称是联盟的一个分配方案。19分配所谓分配就是博弈的一个维向量集合，之分配所谓分配就是博弈的一个维向量集合，之分配

分配的定义中，是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约束。如果，那么，参与人是不可能参加联盟的。是基于集体理性，每个参与人的分配之和不能超过集体剩余。另外若没有全部被分配，显然不是一个帕累托最优的分配方案，不会参与人所接受。20分配分配的定义中，分配分配的定义中，

在前面的例子分配中，分配显然不是一个，而是无限个，无限个分配形成一个分配集合。对于实质博弈，其分配总是有无限个。例如，对于实质博弈，由于存在无限个正向量，满足。显然如下的都是分配，其中。用表示一个博弈的所有分配方案组成的集合。分配21在前面的例子分配中，分配显然不是一个，而是无限个，无在前面的例子分配中，分配显然不是一个，而是无限个，无分配中的优超定义4

设的两个分配和，是一个联盟。如果分配方案和满足（i），；（ii）。则称分配方案在上优超于，或称分配方案在上劣于，记为。如果分配方案在上优超于，则联盟会拒绝分配方案，方案得不到切实执行。因为从到，中的每个参与人的收益都得到改善，创造的剩余又足以满足他们在中的分配。22分配中的优超定义4设的两个分配和分配中的优超定义4设的两个分配和分配中的优超在优超关系中，联盟的特征：1.单人联盟不可能有优超关系。2.全联盟上也不可能有优超关系。因此，如果在上有优超关系，则。3.优超关系是集合上的序关系，这种序关系一般情况下不具有传递性和反身性。4.对于相同的联盟，优超关系具有传递性，即，，则有。5.对于不同的联盟，优超关系不具有传递性。23分配中的优超在优超关系中，联盟的特征：23分配中的优超在优超关系中，联盟的特征：23分配中的优核心

尽管可行分配集合中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所接受的。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。定义5

在一个人合作博弈中，全体优分配方案形成的集合称为博弈的核心(core)，记为。显然有。24核心尽管可行分配集合中有核心尽管可行分配集合中有核心说明：

1.核心是中的一个闭凸集。

2.若，则将中的向量作为分配，既满足个人理性，又满足集体理性。

3.用核心作为博弈的解，其最大缺陷是可能是空集。25核心说明：25核心说明：25核心说明：25核心定理1

分配方案在核心中的充要条件是：（i），，

(ii)。证明如果，满足（i）、(ii)，则不可能被优超，即。反证法，设存在，使。根据优超的定义，有:则有，矛盾。如果，不满足(ii)，则一定被优超，即。26核心定理1分配方案核心定理1分配方案核心对于，存在联盟，有，则定义，定义，使得在中平均分配，在中平均分配，从而得到一个新的分配如下：显然如此定义得向量是个分配，且有。27核心对于，存在联盟，有核心对于，存在联盟，有例2设有三人联盟对策，其特征函数，若由定理1易知,该博弈的核由下面不等式组确定：易知，，，。故该博弈的核其图形为单纯形内以为顶点的四边形，如图1所示。}10,20,40,5),,{()(321321321££££££=++=xxxxxxxxxvc28例2设有三人联盟对策，其特征函数}10,20,4例2设有三人联盟对策，其特征函数}10,20,4图1(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)(4,0,1)29图1(5,0,0)（0,5,0）（0,0,5）(2,2,1图1(5,0,0)（0,5,0）（0,0,5）(2,2,1核心练习1：设3人合作博弈的特征函数如下：，，，，求其核心。

解由核心定义，若，则它必满足30核心练习1：设3人合作博弈的特征函数如下：解由核核心练习1：设3人合作博弈的特征函数如下：解由核解线形不等式组：该不等式组无解，即。上面三个例子说明了求解核心的方法。核心练习2考虑如下的合作博弈，特征函数如下：，；。31解线形不等式组：解线形不等式组：核心

在合作博弈中，用核心代替分配具有明显得优点，即的稳定性。对于中的每一个分配，每个联盟都没有反对意见，都没有更好的分配，每个分配都可以得到执行。当然，用代替也有致命的缺陷，即可能是空集，而。定理2

对于人的联盟博弈，核心非空的充分必要条件是线性规划有解。

，32核心在合作博弈中，用核心代替分配具有明显得优点，即核心在合作博弈中，用核心代替分配具有明显得优点，即核心

定理的直观意义很明显，线性规划（L）若有解，则最优解一定属于；若，则中的每个向量都是可行解，自然线性规划（L）有最优解。对于原线性规划（P），写出它的对偶规划（DP）：

，33核心定理的直观意义很明显，线性规划（L）若有解，则最优核心定理的直观意义很明显，线性规划（L）若有解，则最优核心定理对策有的充分必要条件是：对于满足的向量，有。定义设是个0-1简单对策，若存在一个参与人，满足，则称作一个否决人。定理

简单对策中，充分必要条件是中存在一个否决人。34核心定理对策有核心定理对策有核心证明设是中一个否决人，定义，1处于第的位置。根据定理2，

是一个分配，且。用反证法。设，且不存在否决人，即。，则。故有，从而。也即，矛盾。35核心证明设是中一个否决人，定义核心证明设是中一个否决人，定义核仁为评估对满意性，定义如下的被称作超出一个指标：

的大小反映了对满意性。越大，对越不满意，因为中所有参与人的分配之和远没有达到其所创造的合作剩余；越小，对越满意，当为负值时，中所有参与人不但分配了其所创造的合作剩余，还分配了其他联盟所创造的价值。

36核仁为评估对满意性，定义如下的被称作超出一核仁为评估对满意性，定义如下的被称作超出一核仁

对于同一个，共有个，可以表示为。故可以计算出个。联盟对的满意性取决于中的最大的，故可以对个由大到小排列，得到一个的向量：其中。联盟对的满意性取决于的大小，越小，联盟对越满意。37核仁对于同一个，共有个，可以表核仁对于同一个，共有个，可以表核仁

对于两个不同的分配，分别计算出。如果是小的，则联盟对的满意性大于联盟对的满意性，自然优于。当然这种向量大小的比较不同于数字的比较，是采用字典序的比较方法。字典序的比较方法的比较方法如下：对于向量和，存在一个下标，使得，，则称字典序小于，用符号表示。有了上述的定义，就可以给出核仁的定义了。38核仁对于两个不同的分配，分别计核仁对于两个不同的分配，分别计核仁

定义

对于合作博弈，核仁是一些分配的集合，即，使得任取一个，都是字典序最小的，即。定理4

对于合作博弈，其核仁，且只包含一个元素。定理5对于合作博弈，如果核心，则有。39核仁定义对于合作博弈，核核仁定义对于合作博弈，核核仁

例5

考虑如下的合作博弈，，特征函数如下：；；。求该博弈的核仁。解先求出该博弈的核心，再求核仁。根据核心的条件，充分必要条件：解此不等式组，得到。40核仁例5考虑如下的合作博弈，核仁例5考虑如下的合作博弈，核仁

，故有。下面开始求。对于核心，开始求，。，有＝4－4＝0；，有＝0－＝；，有＝0－＝；，有＝5－＝；，有＝7－＝；，有＝6－＝0；，有＝10－10＝0；当，。上式在达到，故有＝。该结果验证了，。41核仁，故有核仁，故有Shapley值

分配是合作博弈最重要的概念，但遗憾的是在一个博弈中，分配有无限个，且许多根本就得不到执行。利用优超的概念，对分配进行了分类，形成了核心的概念，但遗憾的是，许多博弈中核心可能是空集。为此，引入了超出这一指标，寻求最大超出最小化的分配，即核仁。核仁这一解的优势体现在核仁总存在，且是唯一的，这一解的缺陷就是计算太复杂，因为共有个。本节引入了一个很直观的解的概念，即Shapley值。参与人按照Shapley值进行分配。42Shapley值分配是合作博弈最重要的概念，但遗憾的Shapley值分配是合作博弈最重要的概念，但遗憾的Shapley值

定理6

对每个博弈，存在唯一的Shapley值，其中（8.5.1）下面对这一计算公式给出非数学化的解释：1、，就是按照参与人的平均贡献来安排的分配设计。2、在一个博弈中，每个人的所得应该与其贡献成正比。对于联盟，其合作剩余。如加入，则新联盟的合作剩余是。因此的贡献是。43Shapley值定理6对每个博弈Shapley值定理6对每个博弈Shapley值3、在博弈中，不包含的有个，对每个都有一个贡献值，因此，Shapley值的计算公式中有项。4、即使对于一个固定的，与中参与人的排列顺序无关，与中参与人的顺序无关。因此的系数中存在。为什么系数中有？主要是为了计算的平均值。44Shapley值3、在博弈中，不包含Shapley值3、在博弈中，不包含Shapley值5、对于也可以作出这样解释：加入，其贡献是。加入的概率是多少？如果个局中人以次参加博弈，当加入该博弈时，其前面已有一些参与人，加入后，后继的参与人集合。和中参与人的顺序与无关。加入的概率是，的数学期望（或者平均值）就是Shapley值。

6、Shapley值不一定是个分配，即理性约束可能不满足。45Shapley值5、对于Shapley值5、对于Shapley值例1假设联合国安理会进行投票，部分国家可以形成联盟。该博弈的特征函数为：而对所有其他，。为了求，对所有包含参与人1的联盟按Shapley值求和。与有差异的联盟只有、、、、、和，对于其他的，＝0。所以有

类似地，。于是，，。这样，参与人1、2比参与人3、4、5重要得多。46Shapley值例1假设联合国安理会进行投票，部分国家可以Shapley值例1假设联合国安理会进行投票，部分国家可以Shapley值定理若博弈满足超加性，即,,则Shapley向量，即Shapley值是分配。证明满足超加性，则。47Shapley值定理若博弈满足超加性，即Shapley值定理若博弈满足超加性，即谢谢！48谢谢！48谢谢！48谢谢！48博弈论

经济与管理学院刘洋博士

49博弈论经济与管理学院刘洋博士1博弈论经济与管理学院刘洋博士49博弈论经济与管理合作博弈

（COOPERATIVEGAMES)50合作博弈

（COOPERATIVEGAMES)2合作博弈

（COOPERATIVEGAMES)50合作

合作博弈

COOPERATIVEGAMES熊、狼、狐狸一起抓了一只兔子，民主协商如何分配。狐狸对熊说：平均分只能各得1/3，这样吧，我们俩联合起来，平分如何？熊要答应，狼急了，于是狐狸对狼说：怎么样，我和熊联合起来可以让你什么也得不到，我可以和你合作，不过我要3/4。狼感激的点头，熊琢磨过味来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。狐狸见势不妙，对狼说：别，我给你2/3，我只要1/3。狼成了抢手货，正得意，没留神狐狸和熊又开始嘀咕起来，有再次把自己晾在一边的不妙趋势，连忙钻去继续讨价还价。结果呢？51合作博弈

COOPERATIVEGAM合作博弈

COOPERATIVEGAM如果在实际博弈问题中，具有有力的保障使局中人能够进行协商、谈判，联合选择行动，共同分享利益，我们就面对一个合作博弈问题。本章通过合作博弈模型的介绍，讨论在合作博弈中，局中人如何进行协商谈判、结成联盟及分享利益。1、联盟博弈2、联盟博弈的分配3、核和稳定集4、沙普利值524524导论先回忆一下囚徒困境的例子：

在囚徒困境中，还有另外一个策略组合<抵抗，抵抗>，该组合为参与人带来的支付是<-1,-1>。由<-8,-8>到<-1,-1>，每个参与人的支付都增加了，即得到一个帕累托改进。坦白抵抗坦白-8，-80，-10抵抗-10，0-1，-153导论先回忆一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1导论先回忆一下囚徒困境的例子：坦白抵抗坦白-8，-80，-1导论

<抵抗，抵抗>构不成一个均衡是基于参与人的个人理性。在参与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机行为谋取超额收益1。如果两个参与人在博弈之前，签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第三方支付价值大于1的保证金；如果谁违背了这个协议，则放弃保证金。有了这样一个协议，<抵抗，抵抗>就称为一个均衡，每个人的收益都得到改善。上述分析表明，通过一个有约束力的协议，原来不能实现的合作方案现在可以实现。这就是合作博弈与非合作博弈的区别。二者的主要区别在于人们的行为相互作用时,当事人是否达成一个具有约束力的协议。如果有,就是合作博弈；反之,则是非合作博弈。54导论<抵抗，抵抗>构不成一个均衡是基于参与人的个人导论<抵抗，抵抗>构不成一个均衡是基于参与人的个人合作博弈的概念及其表示

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

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

合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的支付。56合作博弈的概念及其表示合作博弈的结果必合作博弈的概念及其表示合作博弈的结果必合作博弈的概念及其表示

定义1

在人博弈中，参与人集用表示，的任意子集称为一个联盟（coalition）。

空集和全集也可以看成是一个联盟，当然单点集也是一个联盟。定义2

给定一个人博弈，是一个联盟，是指和的两人博弈中的最大效用，称为联盟的特征函数（characteristicfunction）。

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

合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。如果仅与的个数有关，则称作对称博弈。如果，则称作常和博弈。如果，则称作简单博弈。例如，在投票博弈中，每个参与人的权重，

如果，则称作凸博弈。58合作博弈的概念及其表示合作对策的分类主要是根据特征函合作博弈的概念及其表示合作对策的分类主要是根据特征函合作博弈的概念及其表示

之所以称为特征函数，是因为这个合作博弈的性质基本由决定。由此可见对合作博弈的重要性。定理设是参与人集合上的特征函数，则有如下的超可加性：对于联盟和，如果，则上式说明，特征函数只有满足超加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么，其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。59合作博弈的概念及其表示之所以称为特征函数，是因合作博弈的概念及其表示之所以称为特征函数，是因例：

局中人1（卖主）要把一件物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是x

元，则局中人2赢利9-x元。联盟的总收益为9元。类似，联盟的总赢利为10元。于是有。另一方面，单个局中人或者两个买主在一起都不可能赢利，即，。当三个局中人在一起交易时，局中人1显然要把物品卖给局中人3，从而v({1,2,3})=10，显然满足超可加性，于是我们建立了联盟博弈。特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。60例：局中人1（卖主）要把一件物品卖掉，局中人2和3（买主例：局中人1（卖主）要把一件物品卖掉，局中人2和3（买主由策略型博弈导出特征函数型博弈V()=0V(1)=0V(2)=5V(1,2)=10局中人2LR局中人1U-1，25，5D0，100，10最小最大值法：联盟外局中人将采取行动使该联盟的总和收益最小（极度悲观），联盟选择策略－－最大化这些最小值。61由策略型博弈导出特征函数型博弈V()=0局中人2LR局中人由策略型博弈导出特征函数型博弈V()=0局中人2LR局中人例：垃圾博弈－－分析博弈局势在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。记Vn(n=0,1,…,7)表示任意n个局中人组成的特征函数值，在合作博弈条件下，有：

V0=V()=0

V1=-6

V2=-5V3=-4，V4=-3，V5=-2

V6=-1，V7=-762例：垃圾博弈－－分析博弈局势在一区域中住着7户居民，每户居民例：垃圾博弈－－分析博弈局势在一区域中住着7户居民，每户居民合作博弈的概念及其表示例：设有一个3人合作对策，每个参与人各有两个纯策略。当三人不合作时，其支付见下表。假设采用最稳妥策略，即最坏情况下选择最好，求合作博弈的支付函数63合作博弈的概念及其表示例：设有一个3人合作对策，每个参与人各合作博弈的概念及其表示例：设有一个3人合作对策，每个参与人各合作博弈的概念及其表示解：用表示一个联盟，表示联盟中参与人的个数。当＝0，自然，有。当＝1，有3个，以为例。当，则。的策略集合，策略组合。与进行如下矩阵对策：64合作博弈的概念及其表示解：用表示一个联盟，合作博弈的概念及其表示解：用表示一个联盟，合作博弈的概念及其表示

上述矩阵对策没有纯策略，的混合策略是，的混合策略是。的均衡值是。故。同理，可以求出。当＝2，有3个，以为例。当，则。的策略集合,

策略组合。与进行如下矩阵对策：65合作博弈的概念及其表示上述矩阵对策没有纯策略，合作博弈的概念及其表示上述矩阵对策没有纯策略，合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值是3。故。同理，可以求出。当＝3，有1个，，最大的联盟。的策略空间。有。至此特征函数的值已全部求出。66合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值分配

所谓分配就是博弈的一个维向量集合，之所以是维向量，是由于每个参与人都要得到相应的分配。维的分配向量称为博弈的“解”。定义3

对于合作博弈，对每个参与人，给予一个实值参数，形成维向量且其满足：

则称是联盟的一个分配方案。67分配所谓分配就是博弈的一个维向量集合，之分配所谓分配就是博弈的一个维向量集合，之分配

分配的定义中，是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约束。如果，那么，参与人是不可能参加联盟的。是基于集体理性，每个参与人的分配之和不能超过集体剩余。另外若没有全部被分配，显然不是一个帕累托最优的分配方案，不会参与人所接受。68分配分配的定义中，分配分配的定义中，

在前面的例子分配中，分配显然不是一个，而是无限个，无限个分配形成一个分配集合。对于实质博弈，其分配总是有无限个。例如，对于实质博弈，由于存在无限个正向量，满足。显然如下的都是分配，其中。用表示一个博弈的所有分配方案组成的集合。分配69在前面的例子分配中，分配显然不是一个，而是无限个，无在前面的例子分配中，分配显然不是一个，而是无限个，无分配中的优超定义4

设的两个分配和，是一个联盟。如果分配方案和满足（i），；（ii）。则称分配方案在上优超于，或称分配方案在上劣于，记为。如果分配方案在上优超于，则联盟会拒绝分配方案，方案得不到切实执行。因为从到，中的每个参与人的收益都得到改善，创造的剩余又足以满足他们在中的分配。70分配中的优超定义4设的两个分配和分配中的优超定义4设的两个分配和分配中的优超在优超关系中，联盟的特征：1.单人联盟不可能有优超关系。2.全联盟上也不可能有优超关系。因此，如果在上有优超关系，则。3.优超关系是集合上的序关系，这种序关系一般情况下不具有传递性和反身性。4.对于相同的联盟，优超关系具有传递性，即，，则有。5.对于不同的联盟，优超关系不具有传递性。71分配中的优超在优超关系中，联盟的特征：23分配中的优超在优超关系中，联盟的特征：71分配中的优核心

尽管可行分配集合中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所接受的。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。定义5

在一个人合作博弈中，全体优分配方案形成的集合称为博弈的核心(core)，记为。显然有。72核心尽管可行分配集合中有核心尽管可行分配集合中有核心说明：

1.核心是中的一个闭凸集。

2.若，则将中的向量作为分配，既满足个人理性，又满足集体理性。

3.用核心作为博弈的解，其最大缺陷是可能是空集。73核心说明：25核心说明：73核心说明：25核心定理1

分配方案在核心中的充要条件是：（i），，

(ii)。证明如果，满足（i）、(ii)，则不可能被优超，即。反证法，设存在，使。根据优超的定义，有:则有，矛盾。如果，不满足(ii)，则一定被优超，即。74核心定理1分配方案核心定理1分配方案核心对于，存在联盟，有，则定义，定义，使得在中平均分配，在中平均分配，从而得到一个新的分配如下：显然如此定义得向量是个分配，且有。75核心对于，存在联盟，有核心对于，存在联盟，有例2设有三人联盟对策，其特征函数，若由定理1易知,该博弈的核由下面不等式组确定：易知，，，。故该博弈的核其图形为单纯形内以为顶点的四边形，如图1所示。}10,20,40,5),,{()(321321321££££££=++=xxxxxxxxxvc76例2设有三人联盟对策，其特征函数}10,20,4例2设有三人联盟对策，其特征函数}10,20,4图1(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)(4,0,1)77图1(5,0,0)（0,5,0）（0,0,5）(2,2,1图1(5,0,0)（0,5,0）（0,0,5）(2,2,1核心练习1：设3人合作博弈的特征函数如下：，，，，求其核心。

解由核心定义，若，则它必满足78核心练习1：设3人合作博弈的特征函数如下：解由核核心练习1：设3人合作博弈的特征函数如下：解由核解线形不等式组：该不等式组无解，即。上面三个例子说明了求解核心的方法。核心练习2考虑如下的合作博弈，特征函数如下：，；。79解线形不等式组：解线形不等式组：核心

在合作博弈中，用核心代替分配具有明显得优点，即的稳定性。对于中的每一个分配，每个联盟都没有反对意见，都没有更好的分配，每个分配都可以得到执行。当然，用代替也有致命的缺陷，即可能是空集，而。定理2

对于人的联盟博弈，核心非空的充分必要条件是线性规划有解。

，80核心在合作博弈中，用核心代替分配具有明显得优点，即核心在合作博弈中，用核心代替分配具有明显得优点，即核心

定理的直观意义很明显，线性规划（L）若有解，则最优解一定属于；若，则中的每个向量都是可行解，自然线性规划（L）有最优解。对于原线性规划（P），写出它的对偶规划（DP）：

，81核心定理的直观意义很明显，线性规划（L）若有解，则最优核心定理的直观意义很明显，线性规划（L）若有解，则最优核心定理对策有的充分必要条件是：对于满足的向量，有。定义设是个0-1