合作博弈【优选内容】

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

2、的保障使局中人能够进行协商、谈判，联合选择行动，共同分享利益，我们就面对一个合作博弈问题。本章通过合作博弈模型的介绍，讨论在合作博弈中，局中人如何进行协商谈判、结成联盟及分享利益。 1、纳什讨价还价问题(略） 2、联盟博弈 3、联盟博弈的分配 4、核和稳定集 5、沙普利值,2,行业借鉴#,合作博弈的意义与构成,合作博弈的意义表现在它与非合作博弈的差别上。如果协议有外在力量保证强制执行，则为合作博弈，否则为非合作博弈。 非合作博弈的重点是在个体，是每个局中人该采用什么策略；强调个体理性（individual rationality） 合作博弈的重点则在群体，讨论何种联盟将会形成，联盟中的成员将如

3、何分配他们可以得到的支付；强调群体理性(group rationality) 合作：为共同的目的而一起行动 需要一个描述集体理性的效用函数。 描述n人合作博弈，通常假设合作博弈具有可传递效用。简单地说，该效用就像货币一样，可以在各局中人之间自由转让。 （合作，人类进化之舟。）,3,行业借鉴#,7.2 具有可转移支付的联盟博弈,7.2.1 具有可转移支付的联盟博弈及分类 具有可转移支付的 人合作博弈 在非合作的 人博弈中，局中人之间不允许事先协商如何选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配，一个局中人不能分享另一个局中人的支付，或支付是不可能转移的。 本章所讨论的 人

4、合作博弈对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让，或支付是可以转移的。在具有可转移支付的 人合作博弈中，局中人如何选择自己的策略已不是主要讨论的问题，我们主要讨论的问题是局中人如何分配通过合作所获得的收益或效用。,4,行业借鉴#,联盟与特征函数 设局中人集合 ，称 的任一子集为一个联盟。为方便，把 的空子集 也视为一个联盟。记所有联盟构成的集类为 。对 ，用 表示联盟 中的局中人通过合作所能获得的最大支付。且可认为这个值与 中的局中人的行为是独立的，因而 是定义于 上的函数，即 。 定义7.2 对于局中人集合 的任一子集 ，给定集合 的支付 ，如果 满足

5、,则称 为特征函数，称 为具有可转移支付的联盟博弈。 若 满足对 ， ，有 ，则说 满足超可加性。 下面讨论的联盟博弈都是指具有可转移支付的联盟博弈。特征函数满足超可加性。,5,行业借鉴#,例7.1 局中人1（卖主）要把一件物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是 x 元，则局中人2赢利 9-x 元。联盟 的总收益为9元。类似，联盟 的总赢利为10元。于是有 。 另一方面，单个局中人或者两个买主在一起都不可能赢利，即 ， 。 当三个局中人在一起交易时，局中人1显然要把物品卖给局中人3，从而 v(1,2,3)=10， 显然满足超可加性，于是我们建

6、立了联盟博弈 。 特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。 若对 ， ，都有 ,则称 满足可加性。,6,行业借鉴#,我们可以给出满足可加性的特征函数的例子。 例7.2 在某项工作中，不熟练工人 可获报酬 元，熟练工人可得报酬 元，于是可以定义特征函数 。 这里 表示集合 中的局中人个数，以后也用这种记法。 (小知识：中国参与环保组织的志愿者约30万人，美国有60%，欧洲有50%的人参与。参与环保，保护共同家园，需要我们合作，如二氧化碳排放，如如何保护森林。当前，最大的善，不是

7、施舍，而是节约资源！),7,行业借鉴#,7.3 联盟博弈的分配,转归或分配的定义 在联盟博弈中局中人通过合作，获得一定的联盟支付，联盟还要将这笔支付转归于每个局中人，联盟博弈中每个局中人 从联盟中所获的支付或转归可用 维向量 表示，这里 为局中人 所得到的支付。 定义7.3 称向量 是联盟博弈 的一个转归或分配，如果 满足 （1） ， （2） 。 （1）式表明n个局中人的支付总和应与他们全体构成一个联盟所获的支付相等。这说明如果要使某个局中人的支付增加，必需减少其它局中人的支付。这描写了帕累托最优性，因而，称（1）为整体合理性。 （2）式表明每个局中人在合作博弈中所获得的支付不应低于他“单干”

8、所获的支付。称（2）为个体合理性。,8,行业借鉴#,分配的优超关系 为了比较哪个分配好些，给出以下定义。 定义7.4 设有分配 ，及联盟 ,如果 (1) 对 ， (2) 则称联盟 为分配 优于分配 ，记作 。如果对于 ，存在一个联盟 ，使 ，则称 优于 ，记为 。 定义中条件（1）表明，联盟 中每个成员都认为分配 比 好。条件（2）表明分配 对 中成员的支付能够由联盟 付出。,9,行业借鉴#,单人联盟不可能存在转归之间的占优关系 实际，如果 ，由定义 ，且 ，于是有 ，这与 为转归相矛盾。 全联盟 也不可能存在转归之间的占优关系 如果 ，则 ， ， 。于是 ，这与 为转归矛盾。 关于某个联盟

9、转归之间的占优关系满足下述的传递性： 设 ，如果 ， ，则 。但由 ，一般不能得到 的结论。,10,行业借鉴#,7.4 稳定集与核,稳定集的定义 定义7.5 对于联盟博弈 ，集合 称为联盟博弈 的稳定集（stable set），如果以下条件成立。 （1） 中任意分配 都不优于 中的其余分配。 （2） 不属于 中的任何分配 ，总可以在 中找到优于 的分配 。 稳定集定义中第1条表明在稳定集内部的任何两个分配之间不存在优超关系，称为稳定集的内稳定性，它可以防止由于联盟内部成员因利益冲突而导致联盟解体；第2条表明稳定集外的任一分配，至少被稳定集内的某个分配优超，称为稳定集的外稳定性。稳定集的概念由冯

10、.诺依曼（V.Neumann）和摩根斯坦恩（Morgenstern）提出，也称为合作博弈的 解。,11,行业借鉴#,例7.3 设有三个局中人 ，拟合伙开商店，每月可赢利2000元。要使商店正常营业，起码需要两人。试问，应采用怎样的方式经营，以及怎样分配利润才是合理的。 这是一个联盟博弈问题。特征函数为 三人利润分配是向量 ，满足 如果联盟 形成，即局中人 1、2合伙，则分配 是合理的。否则，局中人1要求采取分配 ，其中 ，那么局中人2将与局中人3合伙。如果局中人3也采取类似的要求，则局中人2不与任何人结盟，余下1与3各持己见。 不构成分配。同样，如果 结盟， 是合理的分配 ； 结盟， 是合理的

11、分配。易知 是稳定集 （1） x, y, z 之间没有优超关系； （2）对于 W 之外的任何一个分配 ，必被中某个分配优超。,12,行业借鉴#,人们花费了近20年的时间来证明联盟博弈的存在性。但卢卡斯（Lucas，）举出了反例说明联盟博弈的稳定集可以是空的。另外，寻求稳定集至今还没有通用的方法。 核的定义 定义7.6 人联盟博弈 的所有不被优超的分配构成的集合称为核，记为 。 对于核中的分配 ，局中人不能通过重组联盟而增加支付。 核的充要条件 定理7.2 是 人联盟博弈 的核中的分配的充要条件是 （1） （2）对 ， 。,13,行业借鉴#,例7.4 设有三人联盟对策，其特征函数 ， 由定理7.

12、2 易知,该博弈的核由下面不等式组确定： 易知 ， ， ， 。 故该博弈的核 其图形为单纯形 内以 为顶点的四边形，如图7-1所示(p201) 。,14,行业借鉴#,(5,0,0),（0,5,0）,（0,0,5）,(2,2,1),（3,2,0）,(4,1,0),图 7-1,(4,0,1),15,行业借鉴#,例7.5 污染问题 沙普利（Shaplay） 和舒比克（ Shubik）描述了一个湖的污染模型。设有个工厂分布在某湖的沿岸，为简便起见，设问题是对称的。即每个工厂的污染程度相同。假设每个工厂每天必须在湖里抽取相同数量的清洁水，用完后将污水排入湖中。所涉及的方案和费用如下: (1) 每个工厂每

13、天必须因每个直接向湖中排放污水的工厂（包括自身）花费 c 美元净化它所用的水。 （2）每个工厂可以安装一个过滤器，在污水排回湖中之前就将水净化。每个工厂每天的净水费用为 b 美元。 为使问题有意义，假设 。 （3） 个局中人可以组成一个联盟 ，共同决定是否采用过滤器。注意，如果 决定采用过滤器，联盟 之外的工厂仍会向湖中排放污水。因而联盟 的特征函数值为,16,行业借鉴#,即当 时，联盟 决定采用过滤器， 时 决定不采用过滤器。 设 ，有 由定理7.2， 的充要条件是 满足下述不等式组 由 知 即 。由问题的对称性知 ， 。故该联盟博弈的核为 ， 。,17,行业借鉴#,例7.7 具有否决人的0

14、-1规范简单联盟博弈 设 是一个0-1规范简单的联盟博弈，即 取0与1两个值，且 ， ， 。如果局中人 满足 ，称 为具有否决权的局中人或否决人。 对于 ， 的充要条件是 存在否决人。 证明 必要性 若 ，但 没有否决人，即 对 成立。对 有 ， 。于是 ， 。这与 相矛盾。因而 存在否决人。 充分性 设 的全体否决人集合为 ，设 满 足 ，当 时， 。当 时， 。 可以证明 。 (联合国的安理会),18,行业借鉴#,例7.8 多数博弈 联盟博弈 满足 （1）局中人集合 中元素个数 且为奇数。 （2） 则 。 显然， 为一0-1规范简单博弈且不存在否决人，由例7.7知 。 熊、狼、狐狸合作博弈

15、的核。 有V()=0,单干时由于无法战胜另两个的联盟，所以V1=0,两个结盟就可获得整只兔子，因此V2=1,同样， V3=1。考虑分配（x,y,z)之间的优超关系。首先，熊和狐狸，（1/2，0，1/2），优超平均方案（1/3,1/3,1/3)；狼和狐狸，（0,1/4,3/4）,优超前面，这种优超关系可以进一步继续下去。该联盟博弈的核不存在。（怎么证明？）,19,行业借鉴#,为了解决解的存在性问题，提出了核仁（Nucleus）的概念。核仁具有如下性质：（1）每个博弈有且仅有一个核仁；（2）如果核存在，则核仁是其一部分。 剩余的定义：对于n人合作博弈(N,v)，S为一个联盟，x=(x1,x2,xn

16、)为一个收益向量（不一定为一个分配），记为x(S)=xi,则：e(s,x)=v(S)-x(S),称为S关于x的剩余。 如果x为一个分配，则剩余反映了联盟对于分配的不满意程度。剩余有2n个，可以将其按从小到大排列为一个向量： (x)=(1(x), 2(x), 2n(x)。 核仁（Nucleus）的定义：对于n人合作博弈(N,v)，核仁是指集合：N(V)=x xI(v),对一切 y I(v) ，yx,有(x) (y) 。,20,行业借鉴#,7.5 联盟博弈的沙普利值,联盟博弈的沙普利值 沙普利（Shapley，L.S.）（1953）给出的 n 人合作博弈的另一个解的概念沙普利值，它不仅可以解决经济

17、活动中效益分配问题，而且能够估计社会活动中各团体或派别的权利。为使沙普利值为联盟博弈 的分配，需假设特征函数 满足 对 成立。 设 为一联盟博弈，对于给定的特征函数 v 可以确定出特定的分配 ，这里 , 。 称为 联盟博弈 的沙普利值。 的表达式的右端表示对于 对联盟 S 的贡献 的加权平均。权数 表示在 n 个局中人的任意排列中， i 仅属于联盟 S 的概率。,21,行业借鉴#,沙普利值所满足的公理 可以证明沙普利值是满足下述公理的唯一向量。 A1. 对称性公理。 每个局中人 所得的收益 与 的序号无关。 A2. 有效性公理。 。 有效性公理反映了 作为分配的整体合理性。 A3. 虚设人公理

18、。 对于虚设人 ，有 ，所谓虚设人 指满足 的局中人。 该公理表明，若虚设人 加入联盟 后，并没有给 带来额外的收益，则对 的分配 与他单干时的收益 相等。 A4.聚合公理。 对于两个联盟博弈 和 有 。 聚合公理表明局中人参加两个博弈，其收益为在两个博弈中的分别收益之和。我们用两个例子说明沙普利值的应用。,22,行业借鉴#,例7.9 污水处理费用的合理负担 沿河有三城镇1、2和3，位置如图5-3所示。污水需处理后排入河中。三城镇既可单独建立污水处理厂，也可以联合建厂，用管道将污水集中处理，向河流下游城镇输送。用 表示污水量（吨/秒）， 表示管道长度（千米）。按照经验公式，建立污水厂的费用 ，

19、铺设管道费用为 . 已知三城镇污水量为 ， 的数值如图7-2所示。试从节约总投资的角度为三城镇制定污水处理方案。如果联合建厂，各城镇如何分担费用。,23,行业借鉴#,三城镇污水处理共有以下5种方案,计算出费用以作比较。 (1) 分别建厂，投资分别为 总投资 （2）1,2合作,在城2建厂，投资为 总投资 （3）2,3合作,在城3建厂，投资为 总投资 （4）1,3合作,在城3建厂，投资为 这个费用超过了1，3分别建厂的费用 ，合作没有效益，不可能实现。 （5）三城合作，在城3建厂，总投资为,24,行业借鉴#,比较结果以 （千元）最小，所以应选择联合建厂方案。下面的问题是如何分担费用 。 总费用 中

20、有3部分： 联合建厂费 城1至城2的管道费 城2至城3的管道费 城3提出， 由三城按污水比例5：3：5分担， 是为城1，2铺设的管道费，应由他们担负。城2同意，并提出 由城1，2按污水量之比5：3分担， 则应由城1自己担负。城1提不出反对意见，但他们计算了一下按上述方法各城应分担的费用： 城3分担费用为 城2分担费用为 城1分担费用为,25,行业借鉴#,结果表明2，3分担的费用均比他们单独建厂费用 小，而城1分担费用却比 大。显然，城1不能同意这种分担总费用的办法。 为了促成三城联合建厂以节约总投资，应该寻求合理分担总费用的方案。三城的合作节约了投资，产生了效益，是一个 人合作对策问题，可以用

21、Shapley值方法圆满地分配这个效益。 把分担费用转化为分配效益，就不会出现联合建厂城1分担的费用反比单独建厂费用高的情况。将三城镇记为 ，联合建厂比单建厂节约的投资定义为特征函数，于是有,26,行业借鉴#,三城联合建厂的效益为64（千元），用Shapley值方法计算这个效益的分配。城1应分得的份额 的计算结果列入表7.1，得到 （千元）。类似地算出 。 可以验证： 。 看来城2从总效益64（千元）中分配的份额最大。,27,行业借鉴#,表7.1 污水处理问题中 的计算,28,行业借鉴#,在联合建厂方案总投资额556（千元）中各城的分担费用为 城1是 城2是 城3是 。 (沙普利值也存在缺陷：

22、城1和城3在不合作时，成本是相同的，但合作后，成本却不相同了，这是否合理呢？是否还有其他方法可行？如果不是一条河，而是在海边，情况会怎么样呢？) 练习：刘备、关羽、张飞三人桃园结义，结果最后建立了蜀国。设三人合作收益为10，现假设三人单干的收益分别为1、3、2，刘关、刘张、关张合作收益分别为6、4、5，那么三人如何分配收益。(能体现刘备的核心作用吗？),29,行业借鉴#,例7.10 联合国安理会有15个成员国,其中有5个常任理事国，它们有否决权,一项议案被通过,必须不被任何常任理事国否决而且还要求有9国赞成，我们来考察每个成员国在否决提案时所具有的实力。 设局中人集合 ,其中1,2,3,4,5为常任理事国。如果联盟 能否决提案，则规定 ，否则，规定 ，于是 表示联盟 否决提案的实力。我们来计算对策 的公平值 ，其中 可理解为成员国 所具有的实力。 由对称性公理A1知,30,行业借鉴#,所以 由此推出 。 这表明5个常任理事国掌握 的否决权。,31,行业借鉴#,凸博弈 如果联盟博弈的沙普利值不是核 的分