专题二：合作博弈.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,专题二：合作博弈,在非合作的,n,人博弈中，局中人之间不允许事先协商和选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配。一个局中人不能分享另一个局中人得到的支付。,讨论的,n,人合作博弈，对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让。在,n,人合作博弈中,，,如何选择自己的策略已不是主要讨论的问题，,n,人合作博弈模型主要讨论下述问题。,（,1,）,n,个局中人之间是如何构成联盟的。,（,2,）各个联盟的支付或收益有多大。,（,3,）局中人最终在联盟中分配到多少。,1.,稳定集,1,、,联 盟,设局中人集合,N=1,2,.,n,，,N,的任意子集称为联盟。,注,1,：空子集 也称为一个联盟。,记所有的联盟构成的集类为,B,。,对于,S B,，用,v(S),表示联盟,S,中的局中人通过合作所得到的支付。因而,v(S),可,认为定义在,R,上，取值于实数的一个函数。,2,、,联盟博弈,称,为一个联盟博弈,3,、,特征函数,称,v,为该联盟博弈的特征函数，它满足,v()=0,例,1,：局中人,1,（卖主）要把物品卖掉，局中人,2,和,3,（买主）分别出价,9,元和,10,元。如果局中人,1,将物品卖给局中人,2,的要价是,x,元，则局中人,2,赢利9-x,元。,V(1,2)=9,v(1,3)=10,v(i,)=v(2,3)=0.i=1,2,3,v(1,2,3)=10,于是建立了联盟博弈,特征函数是研究联盟博弈的基础，确定特征函数的过程实际就是一个建立合作博弈的过程,定义,1,：,称向量,x=(x1,x2,x,m,),是联盟,S=1,2,.m,的一个,分配,，如果它满足,:,(1)(,整体合理性,),(2),vi,i=1,2,.,m,（个体合理性）,注,2,：,的全部分配所构成的集合记为,I,(v),注,3,：满足（,1,）（,2,）的分配不唯一,。,定义,2,：设有分配,x,y,I,(v),，,及联盟,S B,，,如果,:,(1),对i S,(,说明分配,x,比,y,好,),(2),（,说明分配中给联盟成员的支付可由联盟付出）,则称对联盟,S,，,分配,x,优于,y,，,记作 。如果对于 ，能找到一个联盟,T,，,使,，则称 优于 ，记作,。,定义,3,：对于联盟博弈,，集合,s(V,),I,(v),称为联盟博弈,的稳定集，如果以下条件成立：,（,1,）,S,(V),中任意分配,x,都不优于,S,(V),中的其余分配。,(,说明稳定集内部任何两个分配无优超关系即内稳定性,),（,2,）不属于,S,(V),中的任何分配,y,，,总可以在,S,(V),中找到优于,y,的分配,x,。（,外稳定性）,注,4,：稳定集的概念由冯,诺依曼,(V.Neumann),和摩根斯坦,(Morgenstern),提出，也成为合作博弈的,V-N-M,解。,例,2,设有三个局中人，拟合伙开商店，每月可赢利,200,元。要使商店正常营业，起码需要两人。试问，应采用怎样的方式经营，以及怎样分配利润才是合理的。,解：特征函数为,v(i)=0,i=1,2,3.,v1,2=v2,3=v1,3=v1,2,3=2,三人利润分配是向量,x=(x1,x2,x3),，,满足,x1+x2+x3=v1,2,3=2,(x1,x2,x3)=0,如果联盟,1,，,2,形成，即局中人,1,、,2,合伙，,则分配,x=,（,1,，,1,，,0,）,是合理的。,否则局中人,1,要求采取分配（,1+,，,1-,，,0,），其中 （,0,，,1,），那么局中人,2,与局中人,3,合伙。如果局中人,3,也采取类似的要求，则局中人,2,不与任何人结盟，余下,1,与,3,各持己见。（,1+,，,1-,）不构成分配。同样，如果,2,，,3,结盟，,y=,（,0,，,1,，,1,）,是合理的分配；,1,，,3,结盟，,z=,（,1,，,0,，,1,）,是合理的分配，易知,w=x,y,z,是稳定集,（,1,）,x,y,z,之间没有优超关系,(2),对于,w,之外的任何一个分配,a=(a1,a2,a3),满足,a1+a2+a3=2,且,ai,=0,，,必被,w,中某个分配优超。,2.,核心,定义,1,：,n,人联盟博弈,的所有不被优超的分配构成的集合称为核心，记为,c(v),定理,1,：分配方案,x=(x1,x2,xn,),在,核心,c(v),中的充要条件：,(1),(2),对,例,3,：设有三人联盟对策，其特征函数,v1=v2=v3=0,v1,2=4,v2,3=1,v1,3=3,v1,2,3=5,由定理,1,知：这个博弈的核心由下面不等式组确定,:x1+x2=4,x1+x3=3,x2+x3=1,x1+x2+x3=5,xi=0,其解为,A=x=(x1,x2,x3)|x1+x2+x3=5,xi=0,内以,(4,0,1,),(4,1,0),(3,2,0),(2,2,1),为顶点的四边形，如图：,（,0,0,5,）,0,5,0,3,2,0,(4,1,0),(5,0,0),(4,1,0),(2,2,1),核,有些联盟博弈的核可能是空的。满足非空的条件,:,定理：对于,n,人的联盟博弈，核心非空的充要条件是线性规划有解：,4,联盟博弈的,Shapley,值,n,人合作博弈的另一个解,设,为一联盟博弈，对于给定的特征函数,v,可以确定出特定的分配,这里,称 为联盟博弈,的,Shapley,值,可以证明,Shapley,值,是满足下述公理的唯一向量。,A1,：,对称性公理,每个局中人,i,所得的收益 与,i,的序号无关。,A2:,有效性公理,。,A3,：,虚设人公理,。,i N,v(S i)=v(S)+v(i),A4:,聚合公理,。,说明：局中人,i,参与两个博弈，其收益等于两个博弈的收益之和,