中国人民大学：《博弈论》课程教学资源（讲义）第六章 合作博弈（主讲：张倩伟）

第六章合作博弈 一、合作博弈的概念及其表示 。一、合作博弃的概念及其表示 ,、 估值方法（合作弃的一亮郑概） Shapley值 一、 合作博弃的概念及其表示 一、合作博弃的概念及其表示 亮任量在素中水用2时表示 空集和全电可以看成 当然最点他是一个 定812给定一个人博弃，5是 表示与人与全体其人 为的作，其中是 新州 一、合作博弃的概念及其表示 作作博弃的瓶念及共表示 下面根据特 凸住表示跳盟大，新成员的资率就越 则，称作对称 因为设 有一个成员1cN为 如果-0S,则（，）移作简单博。 u(2.m) 约果55U对以将作a情先

1 第六章 合作博弈  一、合作博弈的概念及其表示  二、分配  三、占优方法（合作博弈的一类解概念）： 核心、核仁  四、估值方法（合作博弈的一类解概念）： Shapley值 一、合作博弈的概念及其表示 合作博弈，与非合作博弈相对称，是一种参与者能够 联合达成一个具有约束力且可强制执行的协议的博弈类型。 合作博弈强调的是集体理性,强调效率、公正、公平。 合作博弈最重要的两个概念是联盟和分配。每个参与 者从联盟中分配的收益正好是各种联盟形式的最大总收益, 每个参与者从联盟中分配到的收益不小于单独经营所得收 益。 合作博弈的基本形式是联盟博弈,它隐含的假设是存 在一个在参与者之间可以自由流动的交换媒介(如货币), 每个参与者的效用与它是线性相关的。这些博弈被称为 “ 单 边 支 付 ” 博 弈 , 或 可 转 移 效 用 (Transferable Utility ,TU)博弈。 合作博弈的结果必须是一个帕累托改进，合作双方的 利益都有所增加，或者至少是一方的利益增加，而另一方 的利益不受损害。合作博弈研究人们达成合作时如何分配 合作得到的收益，即收益分配问题。 合作博弈采取的是一种合作的方式，合作之所以能够 增进双方的利益，就是因为合作博弈能够产生一种合作剩 余。至于合作剩余在博弈各方之间如何分配，取决于博弈 各方的力量对比和制度设计。因此，合作剩余的分配既是 合作的结果，又是达成合作的条件。 合作博弈的核心问题是参与人如何联盟以及如何重新 分配联盟的支付。下面首先分析联盟的概念。与联盟相关 联的特征函数，特征函数的性质决定了合作博弈的特征。 一、合作博弈的概念及其表示 定义6.1.1 在 人博弈中，参与人集用 表示， 的任意子集 称为一个联盟（coalition）。 空集 和全集 也可以看成是一个联盟，当然单点集 也是一个联 盟。 定义6.1.2 给定一个 人博弈， 是一个联盟， 是指 和 的两组博弈中 的最大效用， 称为联盟 的特征函数（characteristic function）。 规定 。根据定义 ， 表示参与人 与全体其他人博弈时 的最大效用值，表示为 。 用 表示参与人集为 ，特征函数为 的合作博弈，其中 是定 义在 上的实值映射。 在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的行 动。 有时被解释为联盟 独立于联盟 的行动可保证的最大 支付 。 n N  {1,2,  , n} N S S S S S  N N {i} n v(S) v(S) v(S) NS {i|iN,iS} v()  0 v({i}) ( ) i v i (N, v) v v 2 N N  S 一、合作博弈的概念及其表示 S 合作博弈的分类主要是根据特征函数的性质。下面根据特征 函数的性质介绍几类特殊的合作对策。  如果 仅与 中元素的个数有关，则 称作对称博 弈。  如果 ，则 称作常和博弈。  如果 ， 则 称作简单博弈。 例如，在投票博弈中，每个参与人的权重 ， 如果 ，则 称作凸博弈。 v(S) S (N,v) (N, v) (N,v) (N,v) v S v N S v N ( ) ( ) ( )    0   ( ) 1 S i v S S N       ( ),1 w w Q i n i i    0 ( ) 1 i i S i i S w Q v S w Q             v S v T v S T v S T ( ) ( ) ( ) ( )      一、合作博弈的概念及其表示  凸性表示联盟越大，新成员的贡献率就越 大。因为设 {1, 2, } , K S 1 T=K {m+1}, ({1, 2, , }) ( {m+1}) {1,2, ,m+1} {1,2, ,m+1} - ({1, 2, , }) ( {m+1})- S S K S m N m N m K K m K K                         对于任意 ，有某一个成员 为加 入的新成员，记 则由凸性可知 （ ） + ({ }) 则有 （ ） ({ }) 即新成员 m+1加入联盟 后边际贡献不小于新成员与联盟 的任何 子联盟 所组合产生的边际贡献，即新成员的边 际贡献随联盟的 增大而越来越大。 一、合作博弈的概念及其表示

一、合作博弈的概念及其表示 合作博弈的概念及其表示 L2) 要的 线有 足然，凸博弃的特征西数一定请风短可加性 21-) 合作博弈的概念及其表示 合作博弈的概念及其表示 上法 有3个以s-2 411-201 一、合作博弈的概念及其表示 一、合作博弈的概念及其表示 上还矩阵对笑有纯路，5的均衡是3效,2= 社于含著以小，特爱r锅定超n 2收2纱啡2一空 至此特征函数的值已全部求出， 的效用是年个

2  定义6.1.3如果特征函数 满足：对于联盟 和 ， ，有 则称特征函数具有超可加性。 超可加性表示两个不相交的联盟分别行动，其分别单干的结 果不如组成一个联盟的联合而共同行动，这是大联盟形成的 动因。特征函数只有满足超加性，才有形成新联盟的必要性 。否则，如果一个合作博弈的特征函数不满足超可加性，那 么，其成员没有动机形成联盟，已经形成的联盟将面临解散 的威胁。 显然，凸博弈的特征函数一定满足超可加性 。 v S v T v S T ( ) ( ) ( )    一、合作博弈的概念及其表示 v S1 S2 S 1  S 2   例6.1 设有一个3人合作对策，每个参与人各有两个纯策略A 和B。当三人不合作时，其支付见下表。假设采用最稳妥 策略，即最坏情况下选择最好，求合作博弈的支付函数 一、合作博弈的概念及其表示 解：用 表示一个联盟， 表示联盟中参与人的个数。 当 ＝0，自然 ，有 。 当 ＝1， 有3个，以 为例。 当 ，则 。 的策略集合 ， 策略组合 。 与 进行如下矩阵对策： S S S S S S S S   v( ) 0   S  2 S  2 N S   1,3 A B,  N S  ( , ), ( , ), ( , ), ( , ) A A A B B A B B  N S  一、合作博弈的概念及其表示 上述矩阵对策没有纯策略， 的混合策略是 ， 的混合策略是 。 的均衡值是 。 故 。 同理，可以求出 。 当 ＝2， 有3个，以 为例。 当 ，则 。 的策略集 合 , 策略组合 。 与 进行如下矩阵对策： S 3 1 , 4 4       N S  1 3 , 0 , 0 , 4 4       S 1 4   1 ( 2 ) 4 v  v v ( 1 ) 1, ( 3 ) 1        S S S  1, 2 S 1,2 N S   3 ( , ),( , ),( , ),( , ) A A AB B A BB S 一、合作博弈的概念及其表示 上述矩阵对策有纯策略， 的均衡值是 。故 。 同理，可以求出 。 当 ＝3， 有1个， ，最大的联盟.各策略组合对于 的支付总和如下： 至此特征函数的值已全部求出。 S 3 v( 1, 2 ) 3    v v ( 1, 3 ) 1, ( 2, 3 ) 1       S S S N  v N( ) max 2, 0, 4, 2, 2,1, 3, 2 4     一、合作博弈的概念及其表示 对于合作博弈 ，特征函数 满足超加 性，自然有： 根据上述不等式，特征函数 分成两种类型： 类型1： 满足 。即大联盟的效用是每个 参与人的效用之和。这说明通过联盟并没有创造新的合作 剩余，联盟没有价值，这种联盟也不可能维持。这种对策 称为非实质性对策，没有研究价值。 ( , ), 1, 2, , N v N n     v v v v N v v n v v v n ( ) ( 1 ) ( 2, , ) ( 1 ) ( 2 ) ( 3, , )                    1 ( ) n i v i        1 ( ) n i v i  v N( )  一、合作博弈的概念及其表示

一、合作博弃的概念及其表示 二、分配 一个维向量合 所以是 T新的合于 付 有改善。这种对策称为实质性 且其足给一 =(N) 到称：联盟5的一个分配方 二、分配 二、分配 61中存在 x,2.,=(N) aw=W-2>0 在无限个正向量 ，满足如+， 二、分配 二、分配 如果分配方案在 5对干不高的联盟，优超关系不具有传运性

3 类型2： 满足 。即大联盟的效用大于每个 参与人的效用之和。这说明通过联盟创造了新的合作剩余， 联盟有意义，这种联盟能否维持，取决于如何分配合作剩 余，使每个参与人的支付都有改善。这种对策称为实质性 对策，是本部分研究的范畴。 v v N( )   1 ( ) n i v i   一、合作博弈的概念及其表示 二、分配 所谓分配就是博弈的一个 维向量集合，之所以是 维向 量，是由于每个参与人都要得到相应的分配。 维的分配 向量称为博弈的“解”，各种方法即各种解概念代表着分 配的不同观点。 定义6.2.1 对于合作博弈 ，对每个参与 人 ，给予一个实值参数 ，形成 维向量 且其满足： 则称 是联盟 的一个分配方案。 n n n n ( , ), 1, 2, , N v N n     i N  i x 1 ( , , ) n x x x     1 ( ), ( ) n i i i x v i x v N     x S 二、分配 分配的定义中 ， 是基于个人理性，合作中的收益 不能小于非合作中的收益，反映了参与人的参与约束。如 果 ，那么，参与人 是不可能参加联盟的。 是基于集体理性，每个参与人的分配之和不 能超过集体剩余 。另外若 没有全部被分配，显然 不是一个帕类托最优的分配方案，不会参与人所接受。 x v i i  ( )   x v(i) i  i 1 ( ) n i i x v N   v N( ) v N( ) x   1 ( ) , ( ) n i i i x v i x v N      二、分配 分配显然不是一个，而是无限个，无限个分配形成一个分配 集合。对于实质博弈，其分配总是有无限个。 例如，对于实质博弈 ，由于 存在无限个正向量 ，满足 。 显然如下的 都是分配，其中 。 用 表示一个博弈 的所有分配方案组成的集合。 ( , ) N v    u v N( )   1 ( ) 0 n i v i    1 2 ( , , , ) n u u u u   1 2 , , n     u u u u  1 ( , , ) n x x x     ,1 i i x v i u i n     E(v) ( N ,v ) 在例6.1中存在一种分配方案： 1 2 3 x x x x  { , , }满足: 1 2 3 1 2 3 1 ({1}) 1, ({2}) , ({3}) 1, 4 4 x v x v x v x x x           二、分配 定义6.2.2 设 的两个分配 和 ， 是一个联盟。如果 分配方案 和 满足 （i） ， ； （ii） 。 则称分配方案 在 上优超于 ，或称分配方案 在 上 劣于 ，记为 。 如果分配方案 在 上优超于 ，则联盟 会拒绝分配 方案 ， 方案得不到切实执行。因为从 到 ， 中的 每个参与人的收益都得到改善， 创造的剩余 又足以满 足他们在 中的分配。 E(v) x x x x y y y y y y y y S S S S S S S x x x i i x  y i  S x v(S ) i S  i   x y S v S( ) 二、分配 在优超关系中，联盟 的特征： 1.单人联盟不可能有优超关系。 2.全联盟 上也不可能有优超关系。 因此，如果在 上有优超关系， 则 。 3.优超关系是集合 上的序关系，这种序关系一般情况下 不具有传递性和反身性。 4.对于相同的联盟 ，优超关系具有传递性， 即 ， ，则有 。 5.对于不同的联盟 ，优超关系不具有传递性。 N S S S S 2 1    S n E(v) S x y  S y z  S x z  { } , ({ }), ({ }) i i i i 否则，x 则有 与 是分配方案矛  y y x v i y v i y    盾

三、占优方法：校心、核仁 三、占优方法：核心、核 能参 说明。 个闭几 又格中的向量作为分配既足 有CE可， 三、占优方法：心、 三、占优方法：核心、核仁 零找教地的力特 在之0 三、占优方法：核心、核仁 三、占优方法：核心、核日 国安全理事会投票，超过两票算通过。该 例.3设3人合作博弃章的特征函数如下： 而时有货第5，心，应用定3山有空= x,20.1-12345 写+场+%214+场+，21无+5+521 ,2 解世不等式组得 20,￥2 C)=fa.l-a0.Q0:0≤asy ,20,412,3

4 三、占优方法：核心、核仁 尽管可行分配集合 中有无限个分配，但实际上，有 许多分配是不会被执行的，或者不可能被参与人所接受的 。 很显然，联盟的每一个成员都不偏好于劣分配方案，因此， 真实可行的分配方案应该剔除劣分配方案。 定义6.3.1 在一个 人合作博弈 中，全体最优分配 方案形成的集合称为博弈的核心(core)，记为 。显然 有 。 E(v) n ( , ) N v C (v ) C v E v ( ) ( )  说明： 1.核心 是 中的一个闭凸集。 2.若 ，则将 中的向量 作为分配， 既满足 个人理性，又满足集体理性。 3.用核心作为博弈的解，其最大缺陷是 可能是空集，也 可能不唯一。 C(v) C(v) C(v) E v( ) C v( )   x x 三、占优方法：核心、核仁 定理6.3.1 分配方案 在核心 中的充要条件 是： （i） ， (个体理性) ， (ii) （集体里性）。 证明 （充分性） 如果 ， 满足（i）、(ii)，则 不可能被优 超，即 。 反证法，设存在 ，使 。根据优超的定义，有: 则有 ，矛盾。下证必要性（逆否命题）： 如果 ， 不满足 （i）(ii)，则 一定被优超，即 。 ( , , ) 1 n x  x  x C(v) x v(S) i S  i   S  N ( ) 1 x v N n i  i   x E v  ( ) x x x C v  ( ) S S y x  i i x y  i  S ( ) i i S y v S    ( ) ( ) i i i S i S v S x y v S        x E v  ( ) x x x C v  ( ) 三、占优方法：核心、核仁 寻找核心的方法 对于 ，存在联盟 ，有 ，则定义 ， 定义 ，使得 在 中平均分 配， 在 中平均分配，从而得到一个新的分配 如下： 显然如此定义得向量 是个分配，且有 。 x E v  ( ) S S ( ) i i S x v S    ( ) 0 i i S  v S x        \ ( ) ( ) ( ) 0 i N S  v N v S v i         N S  1 ( , , ) n y y y     , ( ) , i i x i S S y v i i S n S                  1 ( , , ) n y y y   S y x  三、占优方法：核心、核仁 例6.2 假想的联合国安全理事会投票，超过两票算通过。该 博弈的特征函数为 而对所有其他的 ， 。应用定理6.3.1，有 ， 对各个联盟有 由 ， ， ， 推 得 ， ， ，而用 ， ， 又得到 和 ，所以，核心是 v(1,2,3)  v(1,2,4)  v(1,2,5)  v(1,2,3,4)  v(1,2,3,5)  v(1,2,4,5)  v(1,2,3,4,5) 1 S v(S)  0 1 5 1   i i x x  0, i  1,2,3,4,5 i 1 x1  x2  x3  1 x1  x2  x4  1 x1  x2  x5  1 5 1   i i x x1  x2  x3  1 0 x4  x5  0 x1  x2  x3  1 0 x4  0 x5  x1  x2  x4  1 0 x 3  0 x 5  0 x3  1 x1  x 2  C v a a a ( ) ( ,1 , 0,0,0): 0 1       三、占优方法：核心、核仁 例6.3 设3人合作博弈 的特征函数如下： ， ， ， ， 求其核心 。 解 由核心定义，若 ，则它必满足 解此不等式组，得 v v(i)  0 i  1,2 ,3 3 2 v({1,2})  12 7 v({1,3})  2 1 v({2,3})  v ({1,2 ,3})  1 C(v) ( , , ) ( ) 1 2 3 x  x x x C v                         0 , 1 , 2 , 3 1 1 2 3 2 1 2 3 12 7 1 3 3 2 1 2 x i x x x x x x x x x i                 1 0 0 0 1 2 3 3 1 3 12 5 2 2 1 1 x x x x x x 三、占优方法：核心、核仁

三、占优方法：核心、核仁 三、占优方法：核心、核仁 s204-23 解线形不等式+ 该不等式组无解，Q小-0。 上面三个子说明了末解核心的方法。 三、占优方法：技心、仁 三、占优方法：心、核 定理63.3.博弈w,有C)z的充分必要条件是 对于原线性规划（印，写出它的对偶规划OP): (DP)ma 5)s N) 三、占优方法：核心、核 三、占优方法：核心、核日 理袋蜜个香洗人定议从月·线 为评估S对x满意性，定义如下的被称作想出值的指标： 5,)-3)-∑ 中所有参与人不但分配 ,从 叫，还分了其他所创的价值

5 例6.4 考虑如下的合作博弈， ，特征函数如 下： 解线形不等式组： 。 该不等式组无解， 。 上面三个例子说明了求解核心的方法。 1 2 1 3 2 3 1 2 3 0, 1,2,3 1 1 1 1 i x i x x x x x x x x x                    C v( )   ( , ), 1, 2, 3 N v N    v i ( ) 0    i  1,2,3 v S S ( ) 1, 2 3      三、占优方法：核心、核仁 1 2 3 1 2 3 3 2 1 x x x x x x            解得 在合作博弈中，用核心代替分配具有明显得优点，即 的稳定性。对于 中的每一个分配，每个联盟都没有反 对意见，都没有更好的分配，每个分配都可以得到执行。 当然，用 代替 也有致命的缺陷，即 可能是空 集，而 。 定理6.3.2 对于 人的联盟博弈，核心 非空的充分必 要条件是线性规划 有解。 ， C v( ) C v( ) C v( ) C v( ) C v( ) E v( ) E v( )   n ( ) P ( ) P min ( ) 1 x v N n i  i   1 ( ) . ( ) i i S n i i x v S s t x v N            S  N 三、占优方法：核心、核仁 定理的直观意义很明显，线性规划（P）若有解，则最优解 一定属于 ；若 ，则 中的每个向量都是可 行解，自然线性规划（P）有最优解。 对于原线性规划（P），写出它的对偶规划（DP）： ， C(v) C v( )   C v( ) ( ) DP max ( ) ( ) S S N y v S v N    1 . 0 S S N S y s t y         S  N 三、占优方法：核心、核仁 定理 6.3.3.博弈 有 的充分必要条件是： 对于满足 的向量 ，有 。 定义6.3.1 设 是个0-1简单对策，若存在一个参与 人 ，满足 ，则 称作一个否决人。 定理 6.3.4 简单对策 中， 充分必要条件是 中存 在一个否决人。 ( , ) N v ( , ) N v ( , ) N v C v( )   C v( )   1 . 0 S S N S y s t y          yS  ( ) ( ) S S N y v S v N    i v N i ( ) 0     N i 三、占优方法：核心、核仁 证明 设 是 中一个否决人，定义 ，1处 于第 的位置。 根据定理6.3.2， 是一个分配， 且 。下证必要性。 用反证法。 设 ，且不存在否决人， 即 。 则 。 故有 ，从 而 。也即 ，矛盾。 i N ei 0,0, ,1,0, ,0    i 0, 0, ,1, 0, , 0 i e    ( ) i e C v  C v( )   v N i ( ) 1      x C v( ) x N x N i v N i i N ( ) 1, ( ) ( )=1,          1 ( ) ( ) ( ) 1 ,     i        x N x N i x i x i N 0, i x i N   ( ) 0 i i N v N x     三、占优方法：核心、核仁 为评估 对 满意性，定义如下的被称作超出值的指标： 的大小反映了 对 满意性。 越大， 对 越不满意，因为 中所有参与人的分配之和远没有达到其 所创造的合作剩余 ； 越小， 对 越满意，当 为负值时， 中所有参与人不但分配了其所创造的合作剩 余 ，还分配了其他联盟所创造的价值。 S S S S S S x x x x ( , ) ( ) i i S e S x v S x     e S x ( , ) e S x ( , ) v S( ) e S x ( , ) e S x ( , ) v S( ) 三、占优方法：核心、核仁

三、占优方法：核心、核 三、占优方法：枝心、 于同-个x,s共有个，可以表示为s-1,，…，2 :分别 <0,则聚字典序小于代功.用符号表 有了上速的定文，就可以给出核仁的定义了. 三、占优方法：核心、被 三、占优方法：核心、核 满足8=a0 reCm”1=(6a风UA-,0月t40)s0 这与，心)矛。定理稠证。 三、占优方法：核心、枝仁 三、占优方法：核心、核仁 洲65考如下的合作，成2动，特通数如 -6

6 对于同一个 ， 共有 个，可以表示为 。 故可以计算出 个 。联盟对 的满意性 取决于 中的最大的 ，故可以对 个 由大到小排列，得到一个 的向量： 其中 。 联盟对 的满意性取决于 的大小， 越小，联盟对 越满意。 x x S 2 n , 1, 2, , 2n j S j   2 n ( , ), 1,2, ,2n j e S x j   x ( , ) j e S x 1,2, ,2n j   2 n ( , ) j e S x 2 n  1 2  2     ( ) ( ), ( ), , ( ) x x x x   n 1 2 2 ( ) ( , ), 1, 2, , 2 , ( ) ( ) ( ) n n j j     x e S x j x x x         ( ) x  ( ) x x 三、占优方法：核心、核仁 对于两个不同的分配 ，分别计算出 。如果 是 小，则联盟对 的满意性大于联盟对 的满意性， 自然 优于 。当然这种向量大小的比较不同于数字的比 较，是采用字典序的比较方法。字典序的比较方法如下： 对于向量 和 存在一个下标 ，使得 ，则称 字典序小于 ，用符号表 示 。 有了上述的定义，就可以给出核仁的定义了。 x y 、   ( ) ) x y 、 (  ( ) x x y x y  1 2  2     ( ) ( ), ( ), , ( ) x x x x   n  1 2  2     ( ) ( ), ( ), , ( ) y y y y   n k ( ) ( ),1 1 j j   x y j k     ( ) ( ) k k   x y   ( ) x  ( ) y ( ) ( ) L   x y  三、占优方法：核心、核仁 定义6.3.2 对于合作博弈 ，核仁 是一些分配的集 合，即 ，使得任取一个 ， 都是字典序最 小的，即 定理6.3.5 对于合作博弈 ，其核仁 ，且 只 包含一个元素 。 定理6.3.6 对于合作博弈 ，如果核心 ， 则有 。 证明 用反证法。设存在一个分配 。根据核心的性质， 由 可知：必存在一个联盟 ，满足 ，由此可 知 。 设 。 是所有 中最大的，故有 ( , ) N v ( , ) N v ( , ) N v N N N E v  ( )  x N   N x E v y E v y x x y       ( ) : ( ), , ( ) ( )  L    N   x C( v )   N C v  ( )  x N x C v   , ( )  x C v  ( ) S ( ) i i S x v S   ( , ) ( ) 0 i i S e S x v S x       1 2  2     ( ) ( ) , ( ) , , ( ) x x x x   n 1  ( ) x ( , ), 1, 2, , 2 n j e S x j   1 ( ) ( , ) ( ) 0 i i S  x e S x v S x        ( ) x 三、占优方法：核心、核仁 由 可知，存在分配 。根据核心的性质， 任取一个 ， 有 ，由此可知 满足 ， ， ； 这与 矛盾。定理得证。 C v( )   y C v  ( ) , 1, 2 , , 2 n j S j   ( , ) ( ) 0 j j j i i S e S y v S y       1 2  2     ( ) ( ), ( ), , ( ) y y y y   n ( ) 0, 1,2, ,2n j  y j    x N    1 2  2     ( ) ( ), ( ), , ( ) x x x x   n 1  ( ) 0 x  y C v  ( )  1 2  2     ( ) ( ), ( ), , ( ) y y y y   n 1  ( ) 0 y  ( ) ( ) L   x y  三、占优方法：核心、核仁 例6.5 考虑如下的合作博弈， ，特征函数如 下： ； ； 。 求该博弈的核仁。 解 先求出该博弈的核心，再求核仁。 根据核心的充分必要条件： 解此不等式组，得到 。 ( , ), 1, 2, 3 N v N    v v v ( 1 ) 4, ( 2 ) ( 3 ) 0          v v v ( 1, 2 ) 5, ( 1, 3 ) 7, ( 2, 3 ) 6          v( 1, 2,3 ) 10    1 2 3 x x x x C v   ( , , ) ( ) 1 1 2 1 3 2 3 1 2 3 4, 0 , 2, 3 5 7 6 1 0 i x x i x x x x x x x x x                     C v x x x ( ) (4, 6 , ) : 3 5       三、占优方法：核心、核仁 三、占优方法：核心、核仁 ，故有 。下面开始求 。 对于核心 ， 求 ， 。 ，有 ＝4－4＝0； ，有 ＝0－ ＝ ； ，有 ＝0－ ＝ ； ，有 ＝5－ ＝ ； ，有 ＝7－ ＝ ； ，有 ＝6－ ＝0； ，有 ＝10－10＝0； 当 ， 。上式在 达到，故有 ＝ 。该结果验证 了 ， 。 C v( )   N C   N C v x x x ( ) (4, 6 , ) : 3 5       ( , ) ( ) i i S e S x v S x    x C v  ( ) S1  1 1 e S x ( , ) S2  2 2 e S x ( , ) (6 )  x x 6 S3  3 3 e S x ( , ) S4  1, 2 S5  1, 3 S6  2, 3 S7  1, 2,3 7 e S x ( , ) 6 e S x ( , ) 5 e S x ( , ) 4 e S x ( , ) ( ) x x 4 (6 )   x  x 5 4  x (6 )   x x 3 5  x   7 1 1 3 5 ( ) min max ( , ) min max 5,3 j j x  x e S x x x        N (4, 6 , ) : 4 (4, 2, 4 )    x x x     N   N  1  3 x x  4

三、占优方法：核心、核 四、估值方法：Shapleyt值 中 r2 0=0 W-I 四、估值方法：Shapley值 四、估值方法：Shapleyt值 5u- 式中有项。 下面对这 公出数学化的解就是按参与人的 博弃中 每个人 四、估值方法：Shapley值 四、估值方法：Shapleyt值 5,对于业此业也可以作出这样解释： 2429L245-L2349- 与 的 合不不一是个分配性时来 -号0-- 类似地，--1一

7 三、占优方法：核心、核仁 ，故有 。下面开始求 。 对于核心 ， 求 ， 。 ，有 ＝4－4＝0； ，有 ＝0－ ＝ ； ，有 ＝0－ ＝ ； ，有 ＝5－ ＝ ； ，有 ＝7－ ＝ ； ，有 ＝6－ ＝0； ，有 ＝10－10＝0； 当 ， 。上式在 达到，故有 ＝ 。该结果验证 了 ， 。 C v( )   N C   N C v x x x ( ) (4, 6 , ) : 3 5       ( , ) ( ) i i S e S x v S x    x C v  ( ) S1  1 1 e S x ( , ) S2  2 2 e S x ( , ) (6 )  x x 6 S3  3 3 e S x ( , ) S4  1, 2 S5  1, 3 S6  2, 3 S7  1, 2,3 7 e S x ( , ) 6 e S x ( , ) 5 e S x ( , ) 4 e S x ( , ) ( ) x x 4 (6 )   x  x 5 4  x (6 )   x x 3 5  x   7 1 1 3 5 ( ) min max ( , ) min max 5,3 j j x  x e S x x x        N (4, 6 , ) : 4 (4, 2, 4 )    x x x     N   N  1  3 x 四、估值方法：Shapley值 分配是合作博弈最重要的概念，但遗憾的是在一个博 弈中，分配有无限个，且许多根本就得不到执行。利用优 超的概念，对分配进行了分类，形成了核心的概念，但遗 憾的是，许多博弈中核心可能是空集。为此，引入了超出 这一指标，寻求最大超出最小化的分配，即核仁。核仁这 一解的优势体现在核仁总存在，且是唯一的，这一解的缺 陷就是计算太复杂，因为共有 个。 本部分引入了一个很直观的解的概念，即Shapley值。 参与人按照Shapley值进行分配。 2 n 定理6.4.1 对每个博弈 ，存在唯一的Shapley 值 ，其中 下面对这一计算公式给出非数学化的解释： 1， ， 就是按照参与人的 平均贡献来安排的分配设计。 2，在一个博弈中，每个人的所得应该与其贡献成正比。对 于联盟 ，其合作剩余 。如 加入 ，则新联盟的 合作剩余是 。因此 的贡献是 。 ( , ) N v     ( ) ( ), ( ), , ( ) v v v v   1 2  n      / !( 1)! ( ) ( ( ) ( )) ! i S N i S n S v v S i v S n             ( ) ( ), ( ), , ( ) v v v v   1 2  n  ( ) i i x v  S v S( ) i S v S i ( )   i v S i v S ( ) ( )     四、估值方法：Shapley值 3，在博弈 中，不包含 的 有 个，对每个 都有 一个贡献值 ，因此，Shapley值的计算公 式中有 项。 4，即使对于一个固定的 ， 与 中参与人 的排列顺序无关，与 中参与人的顺序无关。因 此Shapley值系数中存在 以及 。这主要 是为了计算 对联盟 贡献 的平均值。 ( , ) N v i S S S 1 2 n v S i v S ( ) ( )      v S i v S ( ) ( )     S N S i    S n S !( 1)!   n! v S i v S ( ) ( )     四、估值方法：Shapley值 i S 5，对于 也可以作出这样解释： 加入 ，其贡献是 。 加入 的概率 是多少？如果 个局中人参加依次博弈，当 加入该博弈 时，其前面已有一些参与人 ， 加入后，后继的参与人 集合 。 和 中参与人的顺序与 无关。 加入 的概率是 ， 的数学期望（或者平均值）就是Shapley值。 6，Shapley值不一定是个分配，即理性约束 可能不满足。 !( 1)! ! S n S n   i i i i S S S S v S i v S ( ) ( )     i n N S i     S N S i    v S i v S ( ) ( )     !( 1)! ! S n S n   v S i v S ( ) ( )     i ( ) v v i    四、估值方法：Shapley值 例6..6 假设联合国安理会进行投票，部分国家可以形成联盟。 该博弈的特征函数为： 而对所有其他 ， 。为了求 ，对所有包 含参与人1的联盟按Shapley值求和。 与 无差异的联盟 有 、 、 、 、 、 和 ，对于其他的 ， ＝1。所以有 类似地， 。 于是， ， 。 这样，参与人1、2比参与人3、4、5重要得多。 v(1,2,3)  v(1,2,4)  v(1,2,5)  v(1,2,3,4)  v(1,2,3,5)  v(1,2,4,5)  v(1,2,3,4,5) 1 S S( 2)  v(S)  0 ( ) 1  v v S( 1 )   v S( ) S S {1, 2, 3} {1,2, 4} {1, 2, 5} {1, 2,3,4} {1, 2,3,5} {1, 2, 4, 5} {1, 2,3, 4,5} v S i v S ( ) ( )     20 9 (1 0) 5! 4!0! (1 0) 5! 3!1! (1 0) 3 5! 2!2! 1 (v)  3           30 1 (1 0) 5! 2!2! ( )  3 v     ( ) ( ) 0.45 1 v   2 v   3 (v)   4 (v)   5 (v)  0.0333 四、估值方法：Shapley值

四、估值方法：Shapley值 证明满足超加性.则5U-之的。 2x:

8 定理6.4.2若博弈 满足超可加性，即 , ,则Shapley向量 即Shapley值是分配。 证明 满足超加性，则 。   1 2 ( ) ( ), ( ), , ( ) ( ) n     v v v v E v              / / !( 1) ! ( ) ( ( ) ( )) ! !( 1) ! ( ) ( ) ! i S N i S N i S n S v v S i v S n S n S v i v i n               。 ( , ) N v v S i v S v i ( ) ( ) ( )        ( , ) N v ( ) ( ) ( ) 1 2 1 S2 v S  S  v S  v S1  S2   四、估值方法：Shapley值