合作博弈与讨价还价

第5章合作博弈和讨价还价非合作博弈与合作博弈联盟型博弈合作博弈解讨价还价一、非合作博弈与合作博弈•博弈根据是否可以达成具有约束力的协议分为合作博弈和非合作博弈。•非合作博弈研究参与人策略相互影响下理性经济人的决策及其均衡问题。•非合作博弈要素：参与人、策略、支付函数、均衡•参与人（局中人）：双人博弈和多人博弈非合作博弈要素•策略指导参与人在每个信息集上如何选择行动完全信息静态博弈：参与人只有一个信息集，策略和行动等价完全信息动态博弈中，后行动者至少有两个信息集，策略告诉参与人在达到一个信息集时应如何行动不完全信息博弈中，策略告诉不同类型的参与者选择类型依存的行动•支付（效用）函数参与人策略组合的函数•均衡分析理性结局合作博弈－－分配问题•合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。•熊、狼、狐狸一起抓到了一只兔子，协商如何分配。•在少数服从多数的规则下，理性的分配结局将如何？合作博弈与非合作博弈比较•合约强制力不同在合作博弈中，协议有外在力量保证强制执行；在非合作博弈中，协议没有外在力量保证强制执行。囚徒困境博弈•研究重点不同：非合作博弈的重点是个体，合作博弈研究的重点是群体，讨论何种联盟会形成，联盟中的成员如何分配。•用非合作博弈的框架来研究合作博弈：将达成合作的谈判过程和执行合作协议的强制过程纳入扩展式博弈中研究熊、狼、狐狸瓜分猎物•熊、狼、狐狸一起抓到了一只兔子，协商如何分配。•狐狸对熊说：平分只能各得1/3，我们联合起来平分如何？熊要答应，狼急了。•狐狸对狼说：我和熊联合起来你什么也得不到，不如我和你合作，但你只得1/4如何？狼很感激地点头。•熊琢磨过来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。•狼正得意，没想到狐狸和熊又开始嘀咕起来，大有把自己晾在一边之势，狼连忙钻过去继续讨价还价。•三个家伙继续这样协商下去，结果呢？合作博弈问题•合作博弈的本质是，局中人已经通过合作实现了收益，关键是如何分配这些利益。•合作博弈常可归为讨价还价问题：谈判•在熊、狼、狐狸博弈中，任何两方结盟会对分配产生重大影响，因而合作博弈中需重点考虑局中人之间的结盟关系。二、联盟型博弈（一）合作博弈•联盟：局中人集合={1,2,3,…,I}的任意一个非空子集S。•合作博弈的一个分配：指对I个局中人来说，存在一个向量x=(x1,x2,…,xI)，满足：（1）∑xi=V()（2）xi≥V(i)•条件（1）说明各人分配的收益总和正好是所有局中人的最大总和收益；•条件（2）说明从联盟中各人得到的收益不小于单独经营所得的收益。•局中人从联盟中分配得到的收益反映了每个人的讨价还价能力。－－I个局中人的总和收益－－局中人i不与任何人结盟时的收益合作博弈存在的基本条件•合作博弈存在的两个基本条件：（1）对联盟来说，整体收益大于其每个成员单独经营时的收益之和；（2）对联盟内部而言，应有着具有帕累托改进性质的分配规则，即每个成员能获得比不加入联盟时要多一些的收益。•实现和满足上述条件的保障：成员之间的信息是可相互交换的，所达成的协议是强制执行的。（二）联盟型博弈•在策略型（标准型）博弈中，若引入合作博弈假设，不考虑策略细节，将研究重点放在合作的价值上，则形成联盟型博弈。•联盟型博弈：又称特征函数型博弈，它对每一种可能联盟给出相应的联盟总和收益，称为特征函数V(·)。•特征函数的超加性：对任意两个独立联盟S和T（S∩T=），有V(S∪T)≥V(S)+V(T)。•特征函数型博弈记为（，V）。联盟型博弈的相关概念•合作博弈是非本质的，若有V()=∑V(i)。•合作博弈是本质的，若有V()∑V(i)。•合作博弈是常和的，若对任何联盟S，有V(S)+V(\S)=V()•如何求得特征函数：由策略型博弈导出特征函数型博弈：最小最大值法对实际博弈局势的分析由策略型博弈导出特征函数型博弈•V()=0•V(1)=0•V(2)=5•V(1,2)=10局中人2LR局中人1U-1，25，5D0，100，10最小最大值法：联盟外局中人将采取行动使该联盟的总和收益最小（极度悲观），联盟选择策略－－最大化这些最小值。由策略型博弈导出特征函数型博弈•通常求法是：设联盟外局中人将采取行动使该联盟的总和收益最小（极度悲观，但又非常有效），联盟将选取策略实现这些最小收益的最大化，即每个局中人面对的最小最大值它忽略了联盟外局中人使联盟面临最糟处境时自己也将付出代价（有时代价极高）•豪尔绍尼认为，特征函数的取值应该由联盟与其对立联盟（联盟外所有局中人形成的联盟）之间的一次谈判而决定。例：垃圾博弈－－分析博弈局势•在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。•记Vn(n=0,1,…,7)表示任意n个局中人组成的特征函数值，在合作博弈条件下，有：V0=V()=0V1=-6V2=-5V3=-4，V4=-3，V5=-2V6=-1，V7=-7三、合作博弈解（一）合作博弈求解•在合作博弈中，有多种解概念。•合作博弈解的核心思想是合作均衡概念。•合作博弈理论求解的目的是得到博弈的理性最终分配。•求解的方法主要有两种：优超赋值1、优超•每个局中人有相应的可选择策略，在所有可能的策略组合上定义各局中人的效用函数，效用向量则表现了博弈的一种分配。•一种效用向量u=(u1,u2,…,uI)被优超意味着存在一种联盟S(或者说，联盟S瓦解效用配置u)，对于联盟中的每一成员i，联盟赋予他的效用将大于效用向量中他得到的，即有ui(S)ui，对任意i∈S成立。•合作均衡，指这样的局中人策略组合，它产生的效用向量不被任何联盟所优超（核）•对具有可转移效用的特征函数型博弈而言，一种效用分配向量被优超是指，存在一种联盟，该联盟获得的总和收益大于效用向量提供给该联盟各成员的效用之和。优超的分析方法•在优超定义中，最关键的是联盟能提供给成员的效用分配，主要分析方法有三种：（1）联盟中各成员在联盟外成员策略固定时能获得的效用水平：联盟内的局中人将联盟外局中人所采取的策略视为既定的，即不期望任何报复性反应。（2）联盟不能被阻止得到的效用：即不管联盟外成员如何行动，联盟总可以达成的效用水平。由此得到的合作博弈均衡集合称为合作博弈的核心。（3）联盟能保证自己得到的效用，它是联盟外收益的最悲观的评价。对应的合作博弈均衡集合是合作博弈的核心。•在优超这一思路下，合作博弈的解概念还包括：稳定集、谈判集、核心、核仁等2、赋值•赋值：对每种博弈形式，构造一种考虑冲突各方要求折中的合理结果，通过公理化方法描述解的性质，进而得到惟一的解，及博弈后各局中人得到的效用分配。夏普利值（二）核。，记为上优超在则称，），（，有）对任意一个联盟，如果（为）的两个分配，，人合作博弈（为和优超：设yxyxSVxyxiyxSiiiiSS)(2S1SVISSSS=S={}xyxyxyxyixy对于两个分配和，如果存在某联盟，使得，则称优超，也记为。对或，不可能有。。记为配的集合，）中所有不被优超的分，人合作博弈（核：)V(CVI核的特征•定理2：本质的常和合作博弈的核是空的。)()2();(S1),,,(IVI121VxSVxxxxxiiSiiI，）对任意（组成：维向量件的下条）中的核由所有满足以，人合作博弈（：定理•垃圾博弈：在一区域中住着7户居民，每户居民每天产生一袋垃圾，这些垃圾只能扔在这一区域的某一户人家领地（区域中没有空地）。核的存在性定理13IV()min..()S*()IiiiiSCVzxstxVSzV定理：人合作博弈（，）的核非空的充要条件是下述线性规划　　，　　　，对任意有最小值。简单博弈的核•简单博弈：如果合作博弈中的联盟的特征函数值不是0就是1。•在简单博弈（，V）中，如果对于某局中人i0，有V（\｛i0｝）＝0，则称该局中人为具有否决权的局中人。•定理4：在简单博弈（，V）中，核C(V)非空的充要条件是存在有否决权的局中人。熊、狼、狐狸瓜分猎物•熊、狼、狐狸一起抓到了一只兔子，协商如何分配。•狐狸对熊说：平分只能各得1/3，我们联合起来平分如何？熊要答应，狼急了。•狐狸对狼说：我和熊联合起来你什么也得不到，不如我和你合作，但你只得1/4如何？狼很感激地点头。•熊琢磨过来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。•狼正得意，没想到狐狸和熊又开始嘀咕起来，大有把自己晾在一边之势，狼连忙钻过去继续讨价还价。•三个家伙继续这样协商下去，结果呢？熊、狼、狐狸合作博弈求解•该博弈的特征函数为：V0=V()=0，V1=0，V2=1，V3=1。•在该博弈中，没有任何一种方案不被另一种方案在某个联盟上优超。•若分配（x,y,z）∈C(V)，则存在非负的x,y,z满足：x+y+z=1x+y≥1y+z≥1x+z≥1（三）稳定集•稳定集是由冯·诺依曼与摩根斯坦提出，也被称为VN-M解。记所有可能分配的集合为E(V)。。使得，，存在任意）（外部稳定性）对于（；，满足在）（内部稳定性）不存（）为稳定集，若：（）的分配集，合作博弈（xyyxyxyxWW2W,1VEWV•定理5：对简单博弈（，V），S是一个极小获胜联盟（即V(S)=1，对任一TS，有V(T)=0）则稳定集为：W={x|x=(x1,x2,…,xI)∈E(V)，若iS，则xi=0}•定理6：设I人合作博弈（，V）的稳定集为W，核为C（V），则C(V)W。熊、狼、狐狸合作博弈的稳定集•在该简单博弈中，有三种稳定集：{(x,y,0)|x,y≥0,x+y=1}{(x,0,z)|x,z≥0,x+z=1}{(0,y,z)|y,z≥0,y+z=1}•该稳定集中不包含平均分配。•接下来将考察公平如何进入合作解概念。（四）核仁•核仁具有如下意义的性质：1）每个博弈有且仅有一个核仁；2）如果核存在的话，则核仁是它的一部分。•对于I人合作博弈（，V），S为一个联盟，x=(x1,x2,…,xI)为一个收益向量（不一定为一个分配），记x(S)=iSxi，则称e(S,x)=V(S)-x(S)为S关于x的剩余。•若x为一个分配，则剩余e(S,x)反映了联盟对于分配的不满意程度。•由于的子集共有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|x∈E(V)，对一切y∈E(V)，y≠x，有(x)(y)}•定理7：对于I人合作博弈（，V），有：（1）它的核仁非空，且只包含一个元素；（2）若核C（V）非空，则必定包含核仁N（V）。核仁的求解•定义一个任意的实数ε，满足条件e(T,x)≤ε,nucleolus就是在n个博弈者可能组成的2n-1种组合中，出现最大的ε时，最小化e(T,x)所得到的解矢量x=(x1,x2,…,xn)，即•它可转化为一线性规划问题：),(maxminxTeNSXxmin..(,),steTxTNxX　　，其中　（五）夏普利值•夏普利值利用公理化方法得到合作博弈的惟一解。•其核心思想是按照参与人对联盟的贡献来分配联盟得到的总效用。•在熊、狼、狐狸瓜分猎物博弈中，夏普利值就是平均分配。承载和置换•承载：对于I人合作博弈（，V），T为一个联盟，若对任意联盟S，有V(S∩T)=V(S)，则称T为这个博弈的承载。•承载外的局中人对任何联盟都没有贡献。•置换博弈：对于I人合作博弈（，V），为上一个置换运算，对任意i人联盟S，定义博弈（，v)为这样一个新博弈（，U），使得U((S))=V(S)i[V]（i∈）应满足的公理•公理1（帕累托最优性要求）：若S为（，V）任意一个承载，则有