合作博弈与讨价还价PPT课件

1、1,第5章合作博弈和讨价还价,非合作博弈与合作博弈 联盟型博弈 合作博弈解 讨价还价,2,一、非合作博弈与合作博弈,博弈根据是否可以达成具有约束力的协议分为合作博弈和非合作博弈。 非合作博弈研究参与人策略相互影响下理性经济人的决策及其均衡问题。 非合作博弈要素：参与人、策略、支付函数、均衡 参与人（局中人）： 双人博弈和多人博弈,3,非合作博弈要素,策略 指导参与人在每个信息集上如何选择行动 完全信息静态博弈：参与人只有一个信息集，策略和行动等价 完全信息动态博弈中，后行动者至少有两个信息集，策略告诉参与人在达到一个信息集时应如何行动 不完全信息博弈中，策略告诉不同类型的参与者选择类型依存的行

2、动 支付（效用）函数 参与人策略组合的函数 均衡分析 理性结局,4,合作博弈分配问题,合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。 熊、狼、狐狸一起抓到了一只兔子，协商如何分配。 在少数服从多数的规则下，理性的分配结局将如何？,5,合作博弈与非合作博弈比较,合约强制力不同 在合作博弈中，协议有外在力量保证强制执行；在非合作博弈中，协议没有外在力量保证强制执行。 囚徒困境博弈 研究重点不同： 非合作博弈的重点是个体，合作博弈研究的重点是群体，讨论何种联盟会形成，联盟中的成员如何分配。 用非合作博弈的框架来研究合作博弈： 将达成合作的谈判过程和执行合作协议的强制过程纳入扩展式

3、博弈中研究,6,熊、狼、狐狸瓜分猎物,熊、狼、狐狸一起抓到了一只兔子，协商如何分配。 狐狸对熊说：平分只能各得1/3，我们联合起来平分如何？熊要答应，狼急了。 狐狸对狼说：我和熊联合起来你什么也得不到，不如我和你合作，但你只得1/4如何？狼很感激地点头。 熊琢磨过来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。 狼正得意，没想到狐狸和熊又开始嘀咕起来，大有把自己晾在一边之势，狼连忙钻过去继续讨价还价。 三个家伙继续这样协商下去，结果呢？,7,合作博弈问题,合作博弈的本质是，局中人已经通过合作实现了收益，关键是如何分配这些利益。 合作博弈常可归为讨价还价问题：谈判 在熊、狼、狐狸博弈中，

4、任何两方结盟会对分配产生重大影响，因而合作博弈中需重点考虑局中人之间的结盟关系。,8,二、联盟型博弈,（一）合作博弈 联盟：局中人集合=1,2,3,I的任意一个非空子集S。 合作博弈的一个分配：指对I个局中人来说，存在一个向量x=(x1,x2, , xI) ，满足： （1） xi=V() （2） xi V(i) 条件（1）说明各人分配的收益总和正好是所有局中人的最大总和收益； 条件（2）说明从联盟中各人得到的收益不小于单独经营所得的收益。 局中人从联盟中分配得到的收益反映了每个人的讨价还价能力。,I个局中人的总和收益,局中人i不与任何人结盟时的收益,9,合作博弈存在的基本条件,合作博弈存在的两

5、个基本条件： （1）对联盟来说，整体收益大于其每个成员单独经营时的收益之和； （2）对联盟内部而言，应有着具有帕累托改进性质的分配规则，即每个成员能获得比不加入联盟时要多一些的收益。 实现和满足上述条件的保障：成员之间的信息是可相互交换的，所达成的协议是强制执行的。,10,（二）联盟型博弈,在策略型（标准型）博弈中，若引入合作博弈假设，不考虑策略细节，将研究重点放在合作的价值上，则形成联盟型博弈。 联盟型博弈：又称特征函数型博弈，它对每一种可能联盟给出相应的联盟总和收益，称为特征函数V()。 特征函数的超加性：对任意两个独立联盟S和T（S T=），有V(S T) V(S)+V(T)。 特征函数

6、型博弈记为（，V）。,11,联盟型博弈的相关概念,合作博弈是非本质的，若有V()= V(i)。 合作博弈是本质的，若有V()V(i)。 合作博弈是常和的，若对任何联盟S，有V(S)+V(S)=V() 如何求得特征函数： 由策略型博弈导出特征函数型博弈：最小最大值法 对实际博弈局势的分析,12,由策略型博弈导出特征函数型博弈,V()=0 V(1)=0 V(2)=5 V(1,2)=10,最小最大值法：联盟外局中人将采取行动使该联盟的总和收益最小（极度悲观），联盟选择策略最大化这些最小值。,13,由策略型博弈导出特征函数型博弈,通常求法是：设联盟外局中人将采取行动使该联盟的总和收益最小（极度悲观，但

7、又非常有效），联盟将选取策略实现这些最小收益的最大化，即每个局中人面对的最小最大值 它忽略了联盟外局中人使联盟面临最糟处境时自己也将付出代价（有时代价极高） 豪尔绍尼认为，特征函数的取值应该由联盟与其对立联盟（联盟外所有局中人形成的联盟）之间的一次谈判而决定。,14,例：垃圾博弈分析博弈局势,在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。 记Vn(n=0,1, ,7)表示任意n个局中人组成的特征函数值，在合作博弈条件下，有： V0=V()=0 V1=-6 V2=-5 V3=-4，V4=-3，V5=-2 V6=-1， V7=-7,1

8、5,三、合作博弈解,（一）合作博弈求解 在合作博弈中，有多种解概念。 合作博弈解的核心思想是合作均衡概念。 合作博弈理论求解的目的是得到博弈的理性最终分配。 求解的方法主要有两种： 优超 赋值,16,1、优超,每个局中人有相应的可选择策略，在所有可能的策略组合上定义各局中人的效用函数，效用向量则表现了博弈的一种分配。 一种效用向量u=(u1,u2, , uI)被优超意味着存在一种联盟S(或者说，联盟S瓦解效用配置u)，对于联盟中的每一成员i，联盟赋予他的效用将大于效用向量中他得到的，即有ui(S)ui，对任意i S成立。 合作均衡，指这样的局中人策略组合，它产生的效用向量不被任何联盟所优超（核

9、） 对具有可转移效用的特征函数型博弈而言，一种效用分配向量被优超是指，存在一种联盟，该联盟获得的总和收益大于效用向量提供给该联盟各成员的效用之和。,17,优超的分析方法,在优超定义中，最关键的是联盟能提供给成员的效用分配，主要分析方法有三种： （1）联盟中各成员在联盟外成员策略固定时能获得的效用水平：联盟内的局中人将联盟外局中人所采取的策略视为既定的，即不期望任何报复性反应。 （2）联盟不能被阻止得到的效用：即不管联盟外成员如何行动，联盟总可以达成的效用水平。由此得到的合作博弈均衡集合称为合作博弈的核心。 （3）联盟能保证自己得到的效用，它是联盟外收益的最悲观的评价。对应的合作博弈均衡集合是合

10、作博弈的核心。 在优超这一思路下，合作博弈的解概念还包括：稳定集、谈判集、核心、核仁等,18,2、赋值,赋值：对每种博弈形式，构造一种考虑冲突各方要求折中的合理结果，通过公理化方法描述解的性质，进而得到惟一的解，及博弈后各局中人得到的效用分配。 夏普利值,19,（二）核,20,核的特征,定理2：本质的常和合作博弈的核是空的。,垃圾博弈：在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。,21,核的存在性定理,22,简单博弈的核,简单博弈：如果合作博弈中的联盟的特征函数值不是0就是1。 在简单博弈（，V）中，如果对于某局中人i0，有V（

11、i0）0，则称该局中人为具有否决权的局中人。 定理4：在简单博弈（，V）中，核C(V)非空的充要条件是存在有否决权的局中人。,23,熊、狼、狐狸瓜分猎物,熊、狼、狐狸一起抓到了一只兔子，协商如何分配。 狐狸对熊说：平分只能各得1/3，我们联合起来平分如何？熊要答应，狼急了。 狐狸对狼说：我和熊联合起来你什么也得不到，不如我和你合作，但你只得1/4如何？狼很感激地点头。 熊琢磨过来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。 狼正得意，没想到狐狸和熊又开始嘀咕起来，大有把自己晾在一边之势，狼连忙钻过去继续讨价还价。 三个家伙继续这样协商下去，结果呢？,24,熊、狼、狐狸合作博弈求解,该

12、博弈的特征函数为：V0=V()=0 ，V1=0，V2=1，V3=1。 在该博弈中，没有任何一种方案不被另一种方案在某个联盟上优超。 若分配（x,y,z） C(V)，则存在非负的x,y,z满足： x+y+z=1 x+y1 y+z1 x+z1,25,（三）稳定集,稳定集是由冯诺依曼与摩根斯坦提出，也被称为VN-M解。记所有可能分配的集合为E(V)。,定理5：对简单博弈（，V），S是一个极小获胜联盟（即V(S)=1，对任一TS，有V(T)=0）则稳定集为： W=x|x=(x1,x2, , xI) E(V)，若i S，则xi=0 定理6：设I人合作博弈（，V）的稳定集为W，核为C（V），则C(V)W。

13、,26,熊、狼、狐狸合作博弈的稳定集,在该简单博弈中，有三种稳定集： (x,y,0)|x,y0,x+y=1 (x,0,z)|x,z0,x+z=1 (0,y,z)|y,z0,y+z=1 该稳定集中不包含平均分配。 接下来将考察公平如何进入合作解概念。,27,（四）核仁,核仁具有如下意义的性质：1）每个博弈有且仅有一个核仁；2）如果核存在的话，则核仁是它的一部分。 对于I人合作博弈（，V），S为一个联盟， x=(x1,x2, , xI) 为一个收益向量（不一定为一个分配），记x(S)=iSxi，则称e(S,x)=V(S)-x(S)为S关于x的剩余。 若x为一个分配，则剩余e(S,x)反映了联盟对于

14、分配的不满意程度。,28,由于的子集共有2I个，故e(S,x)也有2I个，将它们按照由大到小的顺序排列为一个向量(x)=（1(x), 2(x), ,2I(x)）。 定义(x)(y)，是指或者1(x)1(y)，或者对k=1,2, ,i-1，有k(x)=k(y)，而 i(x)i(y)。 对于I人合作博弈（，V），核仁是指集合： N(V)=x|xE(V)，对一切yE(V)，y x，有(x)(y) 定理7：对于I人合作博弈（，V），有： （1）它的核仁非空，且只包含一个元素； （2）若核C（V）非空，则必定包含核仁N（V）。,29,核仁的求解,定义一个任意的实数，满足条件e(T,x), nucleol

15、us就是在n个博弈者可能组成的2n-1种组合中，出现最大的时，最小化e(T,x)所得到的解矢量x=(x1,x2,xn)，即 它可转化为一线性规划问题：,30,（五）夏普利值,夏普利值利用公理化方法得到合作博弈的惟一解。 其核心思想是按照参与人对联盟的贡献来分配联盟得到的总效用。 在熊、狼、狐狸瓜分猎物博弈中，夏普利值就是平均分配。,31,承载和置换,承载：对于I人合作博弈（，V），T为一个联盟，若对任意联盟S，有V(ST)=V(S)，则称T为这个博弈的承载。 承载外的局中人对任何联盟都没有贡献。 置换博弈：对于I人合作博弈（，V）， 为上一个置换运算，对任意i人联盟S，定义博弈（ ，v)为这样

16、一个新博弈（，U），使得U(S)=V(S),32,iV （ i ）应满足的公理,公理1（帕累托最优性要求）：若S为（，V）任意一个承载，则有：iSiV =V(S) 。 公理2（对称性要求）：对任一个置换运算和i ，有： (i)(V)=iV 公理3（可加性要求）：对任意两个I人合作博弈（，U）和（，V）有： iU+V =iU +iV,33,夏普利值,上述公理确定了合作博弈(,V)存在唯一的向量函数： 式中|S|表示联盟内部成员的个数， Shapley值第i分量为 表示局中人i应得到的期望收益。 Shapley值是局中人对联盟的贡献期望边际价值，体现了收益分配中的“公平”概念。 若V(S)-V(S

17、i)=0，称局中人i是联盟S的一个无为局中人。 计算熊、狼、狐狸合作博弈的夏普利值。,34,Shapley值解释,Shapley值可以认为是出自于一种概率的解释。假定局中人依随机次序形成联盟，各种次序发生的概率假定相等，均为1/I!。 局中人与前面|S|-1人形成联盟S，局中人i对这个联盟的贡献为V(S)-V(Si)。Si与S的局中人相继排列的次序为(|S|-1)! (I-|S|)!种，因此，各种次序出现的概率为：(|S|-1)!(I-|S|)! /I!。 根据这种解释，局中人i所做贡献的期望正好就是夏普利值。 局中人对联盟的重要程度是由贡献和机会共同决定的。夏普利值是联盟博弈条件下市场机制的

18、模拟。,35,夏普利值应用权力指数,在投票选举中，投票者的权力体现在他能够通过自己加入一个要失败的联盟而挽救这个联盟，使得它获胜。这同时也意味着他能背弃一个本来要胜利的联盟而使其失败。 权力指数是指能够以他作为关键加入者而获胜联盟的数目。 定义特征函数： V(C)-V(Ci)=1，若联盟C胜出而Ci落败 V(C)-V(Ci)=0，其它情形,36,议会投票,议会投票(多数规则)： (1)三个议员：A有2票、B和C各1票，其权力指数和夏普利值各是多少？ (2)某议会有100个议席：红党43席，蓝党33席，绿党16席，白党8席。其权力指数和夏普利值各是多少？ 从（2）中发现，权力指数和议会议席完全不

19、同，票数要通过权力指数才能发生作用。 设计具体的投票制度时，票数的分配要考虑由此实现的权力指数，以实现真正民主。,37,成本分配问题,公共产品的成本分摊 费用分摊： 吃饭AA制： 问题：三人顺路一起打的回家，假设小赵家离公司最近，小钱次之，小孙家离公司最远。三人应如何分摊费用？ 方案：小赵到家时将打表费用1/3交给小孙，小钱到家时将打表费用1/2交给小孙，最后小孙支付全程车费。,38,最后下车者包干,方案：小赵到家时将打表费用1/3交给小孙，小钱到家时将打表费用1/2交给小孙，最后小孙支付全程车费。 小孙节省车费的不确定性： 若三次显示费用分别为： 12、14、15元：三人各摊4、7和4元，小

20、孙省11/15。 12、14、20元：三人各摊4、7和9元，小孙省11/20。 12、14、30元：三人各摊4、7和19元，小孙省11/30。 12、14、40元：三人各摊4、7和29元，小孙省11/40。,39,“人次公里”分摊,一个公平的方案是，按有效的“人次公里”里程数计算单位人次公里的应摊费用，由此计算每人应摊车费。 在上述三次显示费用下，计算得： 12、14、15元：三人应摊180/41、210/41和225/41元，即4.39、5.12和5.49元。 12、14、20元：三人应摊240/46、280/46和400/46元，即5.22、6.09和8.69元。 12、14、30元：三人

21、应摊360/56、420/56和900/56元，即6.43、7.5和16.07元。 12、14、40元：三人应摊480/66、560/66和1600/66元，即7.27、8.49和24.24元。 不难发现，相距不远的同事拼车方式最有效率。,40,集资修路,或许上述拼车计较过于小气，但大工程就值得计较了。 三家集资修路：三家到大路口的距离分别为x、y和z，工程总造价为m元，应如何分摊费用？ 农村“村村通公路”：国家拨款农户集资,41,四、讨价还价,交易价格： 供给 需求 市场结构：假定市场需求是完全竞争的 供给结构：完全竞争、垄断及寡头竞争 若市场需求不是竞争的：一个买家或少数买家 一个卖家面对

22、少数（许多）买家：拍卖或招标 少数（许多）卖家面对一个买家：招标 一个卖家面对一个买家：讨价还价 少数卖家面对少数买家：可归于讨价还价,42,谈判,谈判，又称讨价还价，含义是：双方或者多方关于可能达成合作的条件的协商。 讨价还价的实质就是如何瓜分买者的最高限价B与卖者的最低保留价格S之间的差额。 在讨价还价模型中，常将利益分配抽象为一块蛋糕的分配。 规范化谈判由两个部分组成： 可行集：谈判的所有可能结局（所有现实中可执行的结果）的集合 冲突点：指如果谈判双方不能达成一致，即不能产生协议约定而出现的一种谈判结局。,43,（一）双人讨价还价问题,局中人：1和2 结果集合S：包括谈判破裂的所有可行备

23、选方案 效用函数ui：SR，满足： （1）谈判破裂对两个局中人的效用都是最低的； （2）至少有一个结果给两个局中人带来的效用，要大于谈判破裂时的效用。,44,实物结局和效用结局,谈判结局常有两种表述方式：实物结局和效用结局 对2人谈判： 谈判的实物结局：s=(s1,s2) 谈判的效用结局：u=(u1,u2) 在研究中一般使用谈判的效用结局。,45,黄沙讨价还价问题(P308),问题：某工程需要1000吨黄沙，供应商有两家，企业1和企业2每供应一吨黄沙可获利100元。无论能否承揽黄沙业务，两企业在黄沙外的固定盈利各为5万元和3万元。两企业谈判的理性结局是什么？ 企业1效用函数： u1(s1,s2

24、)=100s1+30000 企业2效用函数： u2(s1,s2)=100s2+50000 可行结果集： 效用配置集：,46,双人谈判结局的图示法,古典谈判理论指出谈判的最终结局需要符合两种理性前提。,F,u1,u2,0,a,c,d,个体理性：区域acd内 联合理性：曲线bde上 曲线bd是满足两种理性要求的谈判结局集合。,b,e,47,古典谈判理论的缺陷,古典谈判理论称为弱谈判理论，它仅仅指出谈判的结构将为协商集上的一点，而不能确定具体是一点，以及这一点如何达成。,F,u1,u2,0,a,c,d,曲线bd是满足两种理性要求的谈判结局集合。,b,e,48,纳什讨价还价解,在两个局中人初始禀赋和讨

25、价还价能力都相同时，参与人联合效用函数： 一般情况下，参与人联合效用函数： 纳什讨价还价解：使上述联合效用函数最大化对应的结局。,49,黄沙问题的纳什讨价还价解,最优化问题： max (100s1)(100s2) s.t. s10，s20，s1+s21000 线性规划问题求解： 图形求解（单纯形法）：无差异曲线与可行结果集外边界的切点 代数计算,50,（二）纳什讨价还价解的理论基础,纳什认为，纳什谈判解应该满足四条公理： 有效性公理：谈判解应该满足上述个体理性与联合理性的要求。 独立无关选择公理：记G为一种谈判局势，冲突点为d，可行集为F，解为u*。G按如下方式得到：将可行集限制到一个更小的集合F上，让d与u*仍保留在新的可行集F中，则新谈判G的解仍为u*（从谈判中排除无关选择不会改变谈判解）。,51,线性不变