博弈论合作博弈

1、学术型博弈论杜少甫dsoft合作博弈 Cooperative Gameý前面讲述的博弈全部都属非合作博弈(Non-Cooperative Game)范畴ý合作博弈vs 非合作博弈F 定义上：v 非合作博弈：局中人间不能达成具有约束力的协议的博弈类型；v 合作博弈：局中人间能够达成可实施的(enforceable)协议的博弈类型。F 理性上：v 非合作博弈建立在理性(Individual Rationality)基础上 每个局中人均是单枪匹马与其他局中人展开博弈v 合作博弈则强调集体理性(Collective Rationality) 由多个局中人组成作为一个整体(如同一个强

2、势的局中人)与其他，或局中人展开博弈争取整体支付水平的上升中国科学技术大学管理学院 20132合作博弈(Cont.)在Nash之前，vonNeumann等则将二者等同ý合作博弈 vs 非合作博弈 (续)F 合作上：v 非合作博弈：“非合作(non-cooperative)”并非等同于“竞争(Competitive)” ，也并不排斥“合作”。只是，如果局中人间在博弈中达成了某种合作关系，那 也是自动实施的(self-enforcing)结果， 即：没有外力强制推动或局中人间的事先合谋，所有局中人都从达到的均衡是“合作的”理性出发，最终合作是博弈的一种结果，而非博弈开展的前提为，客观为他

3、人 例如：无限徒困境，在博弈开展前，并没有强制力要求各方合作，而是各方追求自己支付水平最大化，最终优化策略是“合作”。中国科学技术大学管理学院 20133合作博弈(Cont.)F 合作上：v 合作博弈：并非局中人合作的博弈就是“合作博弈”，而是说博弈是在一个合作的氛围下开展的。这种合作关系(协议)是博弈局外的努力促成且是可实施的(enforceable)。合作是博弈规则的一部分，而非博弈的结果F(如：等)强制推动；局外努力：由局外第、由某些局中人在事前合谋F所谓“可实施的”是指在合作的博弈规则下，的整体支付水平将会得到提升。由于支付增加的部分是合作的结果，故被称为“合作剩余(Cooperati

4、ve Surplus)”。F“整体支付水平的上升”并不是说“所有成员的支付水平有提升”，相反，在很多情况下，整体支付上升可能伴随支付的下降，或者说是以牺牲部分成员利益为代价。è个人利益服从集体利益中国科学技术大学管理学院 20134合作博弈(Cont.)F 关注点上：v 非合作博弈： 注重在博弈规则下的博弈过程，博弈结果问题是“策略选择问题” 博弈的解：策略组合，如Nash均衡、子博弈完美均衡等v 合作博弈： 不仅关心博弈结果通过合作带来的合作剩余，更关注合作剩余的分配问题 如何公平合理的让所有成员均能从合作中获益公平合理：考虑各方的贡献和实力中国科学技术大学管理学院 20135合作

5、博弈(Cont.)ý可将合作博弈视为两个阶段：集体理性F 利益争取阶段：v作为整体与外局中人或展开博弈，争取合作剩余；v 也有可能所有局中人全部在一个大之内，那么外的局中人就是“自然”，也就是个“单人博弈”问题，或称“集成(Integration)优化问题”)；理性F 利益分配阶段：v内成员合作剩余展开谈判、讨价还价，最终达成分配方案ý合理的分配方案是各方妥协的结果，也是各方形成的前提F 博弈的解：分配方案，如Nash付价还价解、(Core)、Shapley值等中国科学技术大学管理学院 20136合作博弈(Cont.)ý 例：开放要求合作，并有部分利益牺牲，但开放

6、果实应让所有人能够品尝，而且是公平品尝。F 不患寡而患不均F 均：非算术平均(大锅饭)，而是考虑贡献的平均合作博弈研究一般不关心形成的过程，只讨论形成后对博弈的影响，以及利益分配问题。我们要随时随刻呼声、回应期待，保证平等参与、平等发展权利，维护正效义率，、在公学平有所教、劳有所得、病有所医、老有所养、住有所居上持续取得新进展，不断实现好、维护好、发展好最广大根本利益，使发展成果更公平惠及全体，在不断发展的基础上，朝着共同富裕方向稳步前进。平中国科学技术大学管理学院 20137两人合作博弈Nash讨价还价问题 Nash Bargaining Gameý 源文献F Nash, J. T

7、he Bargaining Problem. Econometrica, 1950, 18(2): 155-162.(见附录6.1)F Nash, J. Two-Cooperative Games. Econometrica, 1953, 21(1): 128-140. (见附录6.2)ý Bargaining: 讨价还价、议价、谈判F 局中人间的合作将会带来福利的上升(合作剩余)F 局中人就如何分配合作剩余(切蛋糕)问题展开谈判磋商ý Nash讨价还价博弈即两人讨价还价博弈(two-问题bargaining)，是合作博弈的基本F 实质：两个主体间对特定利益的分割分配F 如

8、：双方价格谈判、劳资双方的工资争端、合作者的利润分配、权的分割等F 讨价还价博弈的解：Nash讨价还价解，简称Nash解中国科学技术大学管理学院 20138两人合作博弈Nash讨价还价问题 Nash Bargaining Game本课程介绍ýNash解有多种等价定义F Nash(1950, 1953)：Nash解的公理化定义(axiomatic definition)F Osborne & Rubinstein(1994)：基于异议(objection)与反异议(counterobjection)的定义ýNash讨价还价博弈的基本要素F 1、分配协议(agreeme

9、nt)：是个二元组s=(s1, s2)，描述了每个人所得到的利益v例：两人分100元，各方想得到多少并没有太大意义，有意义的是分配协议如(40, 60),(50, 50), (60, 40)等v分配协议受问题条件和基本理性要求的约束 è 可行分配协议(feasible agreement) 问题条件：双方利益之和不超过100 基本理性要求：各方利益不可能低于0v可行分配协议集：由所有可行分配协议所的集合，例如上例中S = (s1 , s2 ) | s1 + s2 £ 100; s1 , s2 ³ 0分配协议是Nash讨价还价博弈的要素中国科学技术大学管理学院 20

10、139两人合作博弈Nash讨价还价问题 Nash Bargaining GameF 2、效用偶(utility pair)：是个二元组u=(u1, u2)，分别描述了双方对分效用评价。其中ui是局中人i的期望效用(expected utility)，配协议的是可行分配协议集S到实数集的实值函数，ui: SRv 由于博弈各方对分配会有各自的评价，当评价存在差异时，会影响双方讨价还价的态度与结果v 此处只考虑各方效用是自身利益的函数，即ui=ui(si)v 若考虑人的公平关切(fairness concerns)倾向，那么他方利益也会影响己方效用u1=u1(s1, s2)中国科学技术大学管理学院

11、201310两人合作博弈Nash讨价还价问题 Nash Bargaining Gamev 例如： 一个学者和一个收废品的分一批(讨价还价对象是这批)，二者对分配协议的评价会不同 一个果农和一个粮农分一片土地，种粮与种果的利润率不同，那么二者的态度和评价也不同v 效用偶集：所有可能的效用配置的集合U = (u1 (s1 ), u2 (s2 ) | (s1 , s2 ) Î S一般认为：讨价还价博弈中的可行分配协议集和效用偶集均为紧凸集中国科学技术大学管理学院 201311两人合作博弈Nash讨价还价问题 Nash Bargaining GameF 3、谈判破裂点(disagreemen

12、t point)：二元组d=(d1, d2)，任何谈判都有破裂的可能，di表示谈判破裂时局中人i能得到的利益v 谈判破裂点既意味着未达成协议，也是可行分配方案之一，故dSv 例如： 甲乙两人就某项目合作展开谈判，项目预期利润为10000元，若甲单独做此项目能获利2000元，而乙没有单独做此项目的能力。 那么若谈判破裂，甲可仍获利2000元，乙一无所获，则此博弈的谈判破裂点就为(2000, 0)中国科学技术大学管理学院 201312两人合作博弈Nash讨价还价问题 Nash Bargaining GameF 谈判破裂点对双方讨价还价的态度和结果会产生重要影响v 它刻画了博弈双方可能接受的利益底限

13、，各方均点利益的分配协议接受低于破裂v “底牌”、“谈判筹码”、“威胁”v 一个有意义的讨价还价博弈至少存在一个比谈判破裂点Pareto有效的可行分配协议，否则就不可能同时引起双方即，谈判注定破裂。(𝒔𝒔𝟏𝟏, 𝒔𝒔𝟐𝟐) 𝑺𝑺, 使得𝒔𝒔𝟏𝟏 > 𝒅𝒅𝟏𝟏, 𝒔𝒔

14、0784;𝟐> 𝒅𝒅𝟐𝟐中国科学技术大学管理学院 201313两人合作博弈Nash讨价还价问题 Nash Bargaining GameýNash讨价还价博弈的形式化表述F 基于Nash讨价还价博弈的三个基本要素，可对其加以形式化表述F 一个两人讨价还价问题可用B(S, d, U)来表示，其中v S: 可行分配协议集，其中元素形式为(s1, s2)，分别表示两人的分配v d: 谈判破裂点，d=(d1, d2)，分别表示两人的谈判v U: 效用偶集合，𝑼𝑼 =w

15、958;𝒖𝟏𝟏(𝒔𝒔𝟏𝟏), 𝒖𝒖𝟐𝟐(𝒔𝒔𝟐𝟐) |(𝒔𝒔𝟏𝟏, 𝒔𝒔𝟐𝟐) 𝑺𝑺中国科学技术大学管理学院 201314两人合作博弈Nash讨价还价问题 Nash Bargaining Game&#

16、253;Nash讨价还价博弈的对称性F 若讨价还价的双方在立场地位、效用函数、破裂点等方面都无差异(完全对等的关系)，则称此博弈为对称的(Symmetry)对称线u2讨价还价博弈的对称性ó其效用偶集和谈判破裂点的对称性，即：若讨价还价博弈对称，则 效用函数一致且对于任意(u1, u2)U，必有(u2, u1)U 谈判破裂点相同：d1=d2 ó u1(d1)=u2(d2)效用偶集Uu1(u1(d1), u2(d2)中国科学技术大学管理学院 201315Nash解的公理化定义 Axiomatic Definition*ý上述两人讨价还价博弈最终会达成稳定的分配协议s*

17、=(s1*, s2 )，被称为Nash解ýNash(1950, 1953)提出一套公理体系，在此基础上导出Nash解1.帕累托效率公理(Pareto Efficiency)2.对称性公理(Symmetry)3.线性变换不变性公理(Invariance of Linear Transformations, ILT)4.性公理(Independence of Irrelevant Alternatives, IIA)无关方案中国科学技术大学管理学院 201316Nash解的公理化定义 Axiomatic DefinitionÜ一、帕累托效率公理(Pareto Efficienc

18、y)若(s1, s2)和(s1, s2)均是两人讨价还价问题的可行分配协议，且u1(s1)>u1(s1)， u2(s2)>u2(s2)，那么(s1, s2)必然不是讨价还价博弈的结果(Nash解)。说明：博弈双方通过协商，放弃双赢的分配方案 Nash解不被任意其他分配协议优超局中人通过合作能达到最优效率，没有未分配的合作剩余，因为u1 (s1 ) > u1 (s1¢ ) Û s1 > s1¢ u2 (s2 ) > u2 (s2¢ ) Û s2 > s2¢中国科学技术大学管理学院 201317Nash

19、解的公理化定义 Axiomatic DefinitionÜ满足帕累托效率要求的效用偶均落在效用偶集合的右上边界上，即图中的红色线条区域帕累托边界/前沿(Pareto Frontier)u2根据帕累托效率公理，Nash解对应的效用偶必落在帕累托边界上帕累托边界上的效用偶反映了分配协议的效率性，但未反映公平性。而谈判双方必然在追求效率的同时要追求公平u1中国科学技术大学管理学院 201318帕累托边界Nash解的公理化定义 Axiomatic Definitionu2Ü二、对称性公理(Symmetry)F 普遍接受的公平原则：若双方地位对等，实力相当，则双方应得到同样待遇u2

20、(d2 )若两人讨价还价博弈B(S, d, U)是对称的，则u1 (d1 )u1Nash解下的效用偶u*=(u *, u *)必然满足u *=u*。1212Nash解下的效用偶u2说明： 对称讨价还价博弈的Nash解对应的效用偶必处在效用偶集的对称线u1=u2上 结合帕累托效率公理可知，对称线与帕累托边界的交点即为对称讨价还价博弈的Nash解所对 应的效用偶u2 (d2 )u1 (d1 )u1中国科学技术大学管理学院 201319Nash解的公理化定义 Axiomatic Definitionu2(0,100)Ü对称讨价还价博弈的例子：F 两人谈判分100元钱，双方的谈判破裂点均是0

21、= u2u1F 双方对钱的态度一致，即对任一笔钱s，两人的效用(满足程度)是一样的，不妨直接用钱数s来(50, 50)u (s) = u (s) = s度量效用值12F 显然，此博弈的效用偶集就是可行分配协议集，即对应右图阴影部分u1(100, 0)U = (u1 (s1 ), u2 (s2 ) | s1 + s2 £ 100; s1 , s2 ³ 0，对称线为 u1 = u2u1 + u2 = 100F 此博弈是对称的，其帕累托边界为()u*=u , u= (50, 50)*v 故Nash解对应的效用偶为12()s*=s , s= (50, 50)v Nash解就为12中

22、国科学技术大学管理学院 201320Nash解的公理化定义 Axiomatic DefinitionÜ 有了帕累托效率公理和对称性公理，就可以解决对称讨价还价问题，而且结论是显而易见的。然而大多数两人讨价还价问题并不对称，此时对称性公理不再适用如何将不对称的讨价还价问题通过合适的方式转化成等价的对称讨价还价问题，进而求解？Ü 对于谈判破裂点不同所带来的不对称性，只须考虑相对于谈判破裂点的净效用增量即可转化为对称问题u2¢u2u2 (d2 )u¢1u1u1 (d1 )ìu1¢ = u1 (s) - u1 (d )íu¢

23、; = u (s) - u (d )î 222B¢(S, 0,U ¢)B(S, d ,U )中国科学技术大学管理学院 201321Nash解的公理化定义 Axiomatic DefinitionÜ 效用函数的差异也会导致不对称性，例如F双方来自物价水平不同的地方，同样收入的实际看法就不一致力不同，则两人对同样一笔钱的F同样一本书在学者和废品回收者眼中价值不同F科大对NSFC科研项目无配套，而国内许多其他高校则按1:1配套，那么相同经费额的同类NSFC项目对科大和其他高校的获资助者间就不同F这种因博弈方自身因素造成的效用函数差异事实上是对效用函数的仿射变换

24、(AffineTransformation)，即ìu1¢ = a1 + b1u1, b , b > 0íu¢ = a + b u12î 2222显然，上述仿射变换具有保序性，即影响各方的偏好结构注：Nash(1950, 1953)中称其为“线性变换”是确的è严格的说，只有当a1, a2为0时才是线性变换，仿射变换即为“线性变换+平移”中国科学技术大学管理学院 201322Nash解的公理化定义 Axiomatic DefinitionÜ 三、线性变换不变性公理(Invariance of Linear Transfor

25、mations, ILT)F 不难理解，这种因博弈方自身因素造成的效用函数差异(仿射变换)不应影响讨价还价结果，否则是的*若分配协议(s1 , s2 )是一个讨价还价博弈的解，则当博弈中的效用变*换为ui=ai+biui(bi>0)时， (s1 , s2 ) 仍然是新讨价还价博弈的解。说明： Osborne & Rubinstein(1994, p.309)称此公理为Covariance with Positive Affine Transformations(正仿射变换协变性)，似乎更为准确。 虽然效用的仿射变换会改变Nash解所对应的效用偶值，但该点在效用偶集U中的相对位置保

26、持不变 Nash解受效用函数的具体形式影响中国科学技术大学管理学院 201323Nash解的公理化定义 Axiomatic DefinitionÜ有了ILT公理，可将许多非对称的讨价还价问题通过仿射变换转化为对称问题，进而通过对称性公理和帕累托效率公理求解，再反推原问题的Nash解F 例：粮农和果农分100亩土地，种粮和水果的利润分别为800元/亩和500元/亩，他们谈判破裂均无利可图，故此博弈的可行分配协议集和效用偶集分别为S = (s1 , s2 ) | s1 + s2 £ 100; s1 , s2 ³ 0U = (u1 , u2 ) | u1 = 800s1

27、 , u2 = 500s2 , (s1 , s2 ) Î SF 此博弈是不对称的，可对效用函数作如下变换，即转化成对称问题ìu1¢ = u1 / 800 = s1íu¢ = u / 500 = sî 222中国科学技术大学管理学院 201324Nash解的公理化定义 Axiomatic Definitionu2¢100u250000(50, 50)u1¢80000 u1100()Ü新博弈在Nash解下的效用偶就为¢¢*= (50, 50)u, u12()F 因此，新博弈的Nash解就为

28、s , s= (50, 50)*12F 应用ILT公理知，新博弈和原博弈的Nash解相同，故各方均分得50亩v 代入到原博弈，则效用偶解就为()*= (40000, 25000)u , u12中国科学技术大学管理学院 201325Nash解的公理化定义 Axiomatic DefinitionÜ通过仿射变换可解决一些讨价还价博弈的不对称性，但若效用偶集合形状不规则，仿射变换就u2为力了 引入一个对称于u1=u2且倾斜45°的正方形，保 证该正方形的右上边与原效用偶集相切。 此正方形是对原效用偶集的一种扩展，且扩展 后的新博弈是对称的u说明： 应用帕累托效率公理和对称性公理，

29、上述扩展后的新讨价还价博弈的*效用偶解为(u1 , u2 )* 图中所示情形是： (u1 , u2 )正好在原问题的效用偶集中(边界上)，故所1增加的效用偶实际上都是 普遍结论：如果一个具有被选择的无关方案，不影响博弈的解选择的问题最优解落在某一较小范围中，无关方案那么较小范围的最优解就是较大范围的最优解例如：若全校最帅的同学在我们班，那么该同学也必然是我们班最帅的；Bill Gates是世界首富，他也必是美国首富中国科学技术大学管理学院 201326Nash解的公理化定义 Axiomatic DefinitionÜ四、无关方案性公理(Independence of Irreleva

30、nt Alternatives, IIA)两个讨价还价博弈B(S, d, U)和B(S, d, U)，若SS，则B(S, d, U)*的Nash解(s1 , s2 )(对应于效用偶解(u1 , u2 )落在S中，则(s1 , s2 )也一定是B(S, d, U)的Nash解说明：利用IIA公理解决非对称讨价还价问题的关键在于：要让扩展博弈的效用偶解落在原问题的 效用偶集合中ó扩展问题与原问题的帕累托边 界相切于该点中国科学技术大学管理学院 201327Nash解的公理化定义 Axiomatic DefinitionÜ 仍有许多讨价还价博弈不能符合上述要求，即经上述扩展后，扩

31、展问题的效用偶解并不在原问题的帕累托边界上，例如：u2u2扩展问题的效用偶解不在原问题的帕累托边界上伸缩+平移u1u1只要配合使用仿射变换和ILT公理，就可以解决此类问题1.先通过仿射变换使原问题的效用偶集与扩展问题的帕累托边界在解处正好相切，从而得到新问题的效用偶解再用逆仿射变换得到原问题的效用偶解，进而得到Nash解通过这一系列处理方法，理论上已可以解决所有两人讨价还价问题2.3.中国科学技术大学管理学院 201328Nash解的公理化定义 Axiomatic Definitioný 有了前述四个公理，理论上已可解决所有两人讨价还价博弈问题，然而用起来未必方便。Nash在这四条公

32、理基础上，证明出Nash解的通用求解方法，而不必关心博弈是否对称、效用偶集是否规则若帕累托效率公理、对称性公理、线性变换不变性公理、无关方案独立性公理是成立的，那么两人讨价还价博弈就存在唯一解，且为如下 问题的最优解()()éùu (s) - u (d )u (s) - u (d )maxsÎSs.t.ëû1122s1 ³ d1 , s2 ³ d2 ;s º (s1 , s2 ), d º (d1 , d2 )这个解就被称为讨价还价问题的“纳什解(Nash Bargaining Solution)”，问题

33、的目标函数被称为“纳什积(Nash Product)”此即著名的两人讨价还价博弈解的公理化定义中国科学技术大学管理学院 201329Nash解的公理化定义 Axiomatic Definitioný例：两人谈判分100元未来，存在一定的风险性，越大，风险性越高。双方的谈判破裂点均为0F 若局中人1是风险中性(risk-neutral)的，即可直接用所分得的钱数描述其效用F 局中人 2是风险规避的(risk-aversion)的，不妨用如下效用函数刻画ìïu1 (s1 ) = s1íu (s ) = (s )b , b < 1ïî

34、222F 显然，多得一部分会提升局中人2的效用(满足感)，但随着的上升，风险也越大，故对于损失规避的局中人2来说，效用上升没有上升那么快中国科学技术大学管理学院 201330Nash解的公理化定义 Axiomatic DefinitionF 此博弈的可行分配协议集和效用偶集如下S = (s1 , s2 ) | s1+ s2 £ 100; s1 , s2 ³ 0U = (u , u ) | u + (u£ 100; u , u ³ 0)1/ b121212F 故：此博弈Nash解所对应的策略偶解就是如下问题的最优解= (100 - u )bmax u um

35、ax u uu121221u ,uu ,u1212ós.t. u + (u£ 100s.t. u + (u= 100)1/ b)1/ b1212u1 , u2 ³ 0u1 , u2 ³ 0中国科学技术大学管理学院 201331Nash解的公理化定义 Axiomatic Definitioný 因此就是求如下单变量函数在0, 100范围内求最大值解的问题f (u ) = u (100 - u )b111ý 二阶偏导小于0，故为严格凹函数，有唯一最大值解¶ 2f (u )bu= -1< 0 1¶u(100 - u

36、 )2-b211æ 100b öb100ý 通过一阶条件求解得 u*=，故u*=ç 1 + b ÷11 + b2èø性格决定命运= æ 100100b öý 所对应的Nash解就为s= (s , s )*ç 1 + b , 1 + b ÷12èø可见，分配方案受风险规避系数b的影响，b越小，风险规避程度越大，局中人2分得的越少；若b=1，即局中人2也是风险中性的，那么两人 将各得50中国科学技术大学管理学院 201332多人合作博弈博弈 Coalition

37、 Gameý在多人合作博弈中，局中人间可以形成不同形式的，局中人相互交流信息，签订各种形式的契约，契约规定了如何展开合作以及利益分配方案。ý一旦形成，各成员不再关心利益，而是同心协力，按契约行事，保证获得最大利益。ý例：某公司有三个股东A、B、C，分别持股36%、30%和34%。董事会章程规定：若某项提案要通过，必须有2/3以上多数股权持 赞成意见。F A若想推动一项提案，可有两种合作方案：v 只与C结盟；v 同时与B、C结盟F B若想推动一项提案，只有同时与A、C结盟中国科学技术大学管理学院 201333多人合作博弈博弈 Coalition Gameý

38、定义6.1：在n人博弈中，局中人集合为N=1,2,n，则N的任意一个子集S均被称为一个(Coalition)。即= 𝟐𝟐𝒏𝒏𝑺𝑺 𝟐𝟐𝑵𝑵，各种可能的数为 𝟐𝟐𝑵𝑵𝟐𝟐 , , 𝒏𝒏 𝟐𝟐𝑵𝑵，根据定义， 和任意单成员子集F ,𝟏&

39、#120783; ,也均被视为。F 上例中，共有8个，即,𝑨𝑨 ,𝑩𝑩 ,𝑪𝑪 ,𝑨𝑨, 𝑩𝑩 ,𝑨𝑨, 𝑪𝑪 ,𝑩𝑩, 𝑪𝑪, 𝑨𝑨, 𝑩𝑩, 𝑪𝑪F 作为特例，由所有局中人形成的盟(grand coalition

40、)，即N被称为大联中国科学技术大学管理学院 201334多人合作博弈特征函数 Characteristic Functioný一个合作博弈通常用局中人集和特征函数的二元组表示，𝑮𝑮 =𝑵𝑵, 𝝂𝝂 。F 在许多文献中，直接用特征函数𝝂𝝂来表示一个合作博弈。中各成员通过合作所取得的整体ý定义6.2：在合作博弈 𝑵𝑵, 𝝂𝝂 中，支付水平被称为特征函数v。F 它是关于任一S的函数，

41、0642;𝝂 𝑺𝑺 , 𝑺𝑺 𝟐𝟐𝑵𝑵，即𝟐𝟐𝑵𝑵𝝂𝝂: 𝑹𝑹v 单成员的特征函数𝝂𝝂 𝒊𝒊 常简记为𝝂𝝂 𝒊𝒊F 对于任一S，之外的其他局中人有许多不同的结盟方式S外的局中人也结成S能取得的最大支付

42、。N-S，特征函数𝝂𝝂𝑺𝑺 通常反映的是两个间展开双人博弈，最终F 完全信息：N和v均是共同知识Fv全信息：v不是共同知识(本课程不涉及)参考附件6.3：Myerson, R.B. Cooperative Games with Incomplete Information. International Journal of Game Theory, 1984, 13(2): 69-96中国科学技术大学管理学院 201335多人合作博弈特征函数(Cont.)ý特征函数的性质见Owen, G. Game Theory (3r

43、d ed.). San Diego: Academic Press, 1995, p. 213F 1、𝝂𝝂 = 𝟎𝟎：空取得不了任何利益F 2、超可加性(Superadditivity)：𝑺𝑺𝟏𝟏, 𝑺𝑺𝟐𝟐 𝟐𝟐𝑵𝑵，若𝑺𝑺𝟏𝟏 𝑺𝑺ҷ

44、84;𝟐 = ，则𝝂𝝂 𝑺𝑺𝟏𝟏 𝑺𝑺𝟐𝟐 𝝂𝝂 𝑺𝑺𝟏𝟏+ 𝝂𝝂 𝑺𝑺𝟐𝟐vv使总支付水平下降 è 1+12即：合作总比不合作差，v通过超可加性，显然有𝝂𝝂 𝑵ү

45、25; 𝝂𝝂 𝟏𝟏+ 𝝂𝝂 𝟐𝟐+ + 𝝂𝝂 𝒏𝒏若某没有组成的特征函数不满足超可加性，则其成员的，已结成的也将解散F 3、单调性(Monotonicity)：从超可加性直接得出v 𝑺𝑺, 𝑻𝑻 𝟐𝟐𝑵𝑵，若𝑺𝑺 𝑻𝑻

46、; ，则𝝂𝝂(𝑺𝑺) 𝝂𝝂(𝑻𝑻)v越大，合作所获越大中国科学技术大学管理学院 201336多人合作博弈 常和博弈、实质博弈与子博弈ý定义6.3：合作博弈𝝂𝝂若满足：对于𝑺𝑺 𝟐𝟐𝑵𝑵均有𝝂𝝂(𝑺𝑺) + 𝝂𝝂(𝑺

47、9930;) = 𝝂𝝂(𝑵𝑵), 𝑺𝑺 𝑵𝑵 𝑺𝑺，则称为常和博弈ý定义6.4：合作博弈𝝂𝝂若满足𝝂𝝂(𝑵𝑵) > 𝝂𝝂(𝒊𝒊) ，则称为此博弈为实质的𝒊𝒊𝑵𝑵(Essential)F 在实质的合作博

48、弈中，全体合作能共赢，各局中面合作的有形成大、展开全F 而在非实质的合作博弈中，全体合作不能带来支付水平的，各局中人无促成大的愿望ý定义6.5：合作博弈的子博弈(Subgames)F 𝑺𝑺 𝟐𝟐𝑵𝑵, 𝑺𝑺 ，若合作博弈 𝑺𝑺, 𝝂𝝂𝑺𝑺 满足𝝂𝝂𝑺𝑺(𝑻𝑻) = &#

49、120642;𝝂(𝑻𝑻), 𝑻𝑻 𝟐𝟐𝑺𝑺 ，被称为原博弈 𝑵𝑵, 𝝂𝝂 的子博弈中国科学技术大学管理学院 201337多人合作博弈 凸博弈 Convex Gamesý定义6.6：对于n人合作博弈 𝑵𝑵, 𝝂𝝂 ，若对𝑺𝑺, 𝑻𝑻 𝟐&#

50、120784;𝑵𝑵均有v( S ) + v(T ) £ v( S U T ) + v( S I T )则此博弈为凸博弈(Convex Games)；若只在𝑺𝑺 = 𝑻𝑻时等式成立，则称为严格凸博弈(Strict Convex Games)ý凸博弈的性质，证明见附录6.4F (1) 超可加性： 𝑺𝑺, 𝑻𝑻 𝟐𝟐𝑵𝑵且𝑺𝑺

51、𝑻𝑻 = ，有𝝂𝝂 𝑺𝑺+ 𝝂𝝂 𝑻𝑻 𝝂𝝂 𝑺𝑺 𝑻𝑻F (2) 对于固定的局中人集N，所有凸博弈的全体形成凸锥(convex cone)F (3) 合作博弈 𝑵𝑵, 𝝂𝝂 为凸博弈等价于以下条件之一v( S U i) - v( S ) £ v(T U i) - v(

52、T ), "S Í T Í N - iv( S U C ) - v( S ) £ v(T U C ) - v(T ), "S Í T Í N - C中国科学技术大学管理学院 201338多人合作博弈的解概念 Solution ConceptsNý合作博弈假设：各局中人能够形成大F 最大：如何以某种公平方式在局中人间分配大支𝝂𝝂(𝑵𝑵)注：上述假设并不具有约束性，即使局中人脱离大𝑵𝑵, 𝝂𝝂

53、 的有关结论对子博弈N组成较小的S，那么𝑺𝑺, 𝝂𝝂𝑺𝑺 也是适用的。ý合作博弈的解概念(Solution Concept)：F 反映各局中人最终所得的一个n维实支付向量) Î Rnn中国科学技术大学管理学院 201339多人合作博弈的解概念 Solution Concepts得到不同的解概念 è 存在共性ý基于对公平性(fairness)的不同看F 有效性(Efficiency)：支付向量是对总支付的剖分è合作剩余全被分配å xi= v(

54、 N )iÎN理性(Individual Rationality)：任何局中人F接受低于他不结盟即可获得的支付水平è帕累托有效xi ³ v(i), "i Î NF 对称性(Symmetry)：对称的局中人将获得相同的支付。v 两局中人i、j是对称的：若对于任意不包括局中人i和j的，将局中人i纳盟与将局中人j纳盟，所得两个新的支付水平是一样的。 即：任意包含局中人i和j两者之一的，若将两者替换，支付水平发生变化。è局中人i和j对任意的贡献是一样的 v(S U i) = v(S U j), "S Í N - i, j中

55、国科学技术大学管理学院 201340多人合作博弈的解概念(Cont.)ý定义6.7：合作博弈 𝑵𝑵, 𝝂𝝂 ， S是一个，𝑺𝑺 𝟐𝟐𝑵𝑵，若向量𝐱𝐱 (𝒙𝒙𝒊𝒊)|𝑺𝑺|满足如下条件，则称x是å xiS上的一个分配(Imputation)= v( S ) andxi ³ v(i),

56、 "i Î SiÎSF 显然，满足上述条件的x是支付在成员间的一种分割 è 共享合作果实若存在某一局中人i，某种分成方案下他的支付低于他不参时的支付，即𝒙𝒙𝒊𝒊 < 𝝂𝝂(𝒊𝒊)，那么理性的局中人i会加此方案；若无其他可行方案，S就无法形成F 大N上的分配，通常简称为“分配”。所有分配的集合，记为𝑬𝑬(𝝂𝝂)中国科学技术大学管理学院 201341ìn

57、=³=üE(v)í(iv( N ), xiv(i), i1,L, nýîi =1þ多人合作博弈的解概念(Cont.)ý“分配”是所有局中人有可能接受的利益分成方案F 有可能接受一定接受，S的一个分配说明v 任一局中人加盟S肯定不比“单打独斗”差v 但并不代表一定不存在其他T，让局中人觉得加入T比加入S更好。F “分配” ：分成方案备选，不能作为博弈的“解”，但可作为“解”的基础F 大多数合作博弈的“解”概念都是建立在“分配”基础之上的。Ü分配的比较问题Ü 大分配集𝑬𝑬(&#

58、120642;𝝂)中有很多“分配”，各局中人在个人理性情况下总是争取最有利的“分配”，局中人可能会以“”相威胁中国科学技术大学管理学院 201342多人合作博弈的解概念(Cont.)ý定义6.8：x和y是大上的两个分配,x,yE(v)，S是一个, 𝑺𝑺 𝟐𝟐𝑵𝑵，若两条件缺一不可则称分配x在S上优超(dominate)分配y，记为𝐱𝐱 𝑺𝑺 𝐲𝐲只要存在一个𝑺&#

59、119930; 𝟐𝟐𝑵𝑵，使得𝐱𝐱 𝑺𝑺 𝐲𝐲，就称x优超y，记作𝐱𝐱 𝐲𝐲条件(1)：S内的局中人都会将y视作劣分配，但未必有逼迫S以外局中人采用x的能力条件(2)：若S以外局中人坚持分配y，则S中的局中人将会以大N而形成S相威胁，这个威胁是的，因为通过结成S的所得至少与x方案相同(甚至还会有改进)，从而可逼迫其他局中人放弃y方案。Note: x的存在，就给小圈子S提供了

60、一弃了y，S中局中人就会同意结成大迫其他人放弃y的借口；但并不是说其它局中人放N。S的所得均不大于大N的某种方案，各方才 只有存在所有小脱离。中国科学技术大学管理学院 201343(1)xi > yi , "i Î S;(2) åiÎS xi £ v( S ).多人合作博弈的解概念(Cont.)ý命题6.1：优超关系在E(v)上的不是个偏序关系"x Î E(v), x f x is False"x, y,z Î E(v), if x f y and y f z, then x f z&qu

61、ot;x, y Î E(v), if x f y, then y f x is False情况F 1、非自反性：F 2、传递性×：F 3、不对称性× ：ý可能出现两种F E(v)中的任一“分配”都会被另一“分配”优超 è E(v)的所有元素都是劣分配 è 因不同“小圈子”利益得不到平衡（扯皮）而遭到è 大N无法形成F 可能会出现两个分配相互优超：如x fS y and y fTx中国科学技术大学管理学院 201344多人合作博弈的解概念 Coreý定义6.9：在合作博弈 𝑵𝑵, &#

62、120642;𝝂 中，所有不被优超的分配集合称为(Core)，记为𝑪𝑪(𝝂𝝂) 。F 𝑬𝑬(𝝂𝝂)为博弈𝝂𝝂大N的所有分配集合，显然有𝑪𝑪(𝝂𝝂) 𝑬𝑬(𝝂𝝂)F元素是(大N下的)分配v任意局中人加入大N均不比“单打独斗”差F元素不被优超v𝑺𝑺 𝑵

63、𝑵，让局中人觉得加入S比加入N更好对任意局中人而言，都不存在小S都不愿意内的分配方案下，任何小N而“另立门户”脱离大F Shapley(1971)认为：是“稳定(Social Stable)”结果的集合，任何联盟都不可能在基础上再有改进。 F具有稳定性，可作为合作博弈的“解”；但并不意味着这种“解”存在中国科学技术大学管理学院 201345多人合作博弈的解概念 Coreý定理6.1：分配𝐱𝐱 =𝒙𝒙𝟏𝟏, , 𝒙𝒙𝒏w

64、951;处于𝑪𝑪(𝝂𝝂)中，当且仅当F 证明：见附录6.5中国科学技术大学管理学院 201346ì(1) å x ³ v( S ), "S Î 2N ;ïiíiÎSï(2) å xi= v( N ).îiÎN多人合作博弈的解概念(Cont.)ý例：三人合作博弈 𝑵𝑵, 𝝂𝝂 ，|N|=3，对于任意试求此博弈的| S |£ 1

65、19930;𝑺 𝑵𝑵 ，特征函数𝝂𝝂 如下，ì0,if ififv( S ) = ïa ,| S |= 2 , 其中a Î (0,1)S = Níï1,îF 根据定理6.1可知，此博弈的任一元素满足= 1ììï= 1;üï3C(v) = í3ï x3 )ý³ a³ a³ a+ x3 Î0,1 - a ïþïî12ï+ x3í x2ï x+ xïïî13若2/3，C(v)非空；若2/3，C(v)为空；³ 03中国科学技术大学管理学院 201347解存在性定理ý定理6.2：n人非空 ó 如下线性博弈有解且最优目标值𝒛𝒛 𝝂𝝂(𝑵𝑵)F 证明：见附录6.6中国科学技术大学管理学院 201348nmin z = å xii =1s.t.å xi ³ v( S