资源描述：
《专题二：合作博弈.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、专题二：合作博弈在非合作的n人博弈中，局中人之间不允许事先协商和选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配。一个局中人不能分享另一个局中人得到的支付。讨论的n人合作博弈，对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让。在n人合作博弈中，如何选择自己的策略已不是主要讨论的问题，n人合作博弈模型主要讨论下述问题。（1）n个局中人之间是如何构成联盟的。（2）各个联盟的支付或收益有多大。（3）局中人最终在联盟中分配到多少。§1.稳定集1、联盟设局中人集合N={1,2,…..,n}，N的
2、任意子集称为联盟。注1：空子集也称为一个联盟。记所有的联盟构成的集类为B。对于SB，用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、3})=10于是建立了联盟博弈特征函数是研究联盟博弈的基础，确定特征函数的过程实际就是一个建立合作博弈的过程定义1：称向量x=(x1,x2,…xm)是联盟S={1,2,..m}的一个分配，如果它满足:(1)(整体合理性)(2)v{i},i=1,2,….,m（个体合理性）注2：的全部分配所构成的集合记为I(v)注3：满足（1）（2）的分配不唯一。定义2：设有分配x,yI(v)，及联盟SB，如果:(1)对iS,(说明分配x比y好)(2)（说明分配中给联盟成员的支付可由联盟付出）则称对联盟S，分配x优于y，记作。如果对于
4、，能找到一个联盟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元。要使商店正常营业，起码需要
5、两人。试问，应采用怎样的方式经营，以及怎样分配利润才是合理的。解：特征函数为v(i)=0,i=1,2,3.v{1,2}=v{2,3}=v{1,3}=v{1,2,3}=2三人利润分配是向量x=(x1,x2,x3)，满足x1+x2+x3=v{1,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-,
6、）不构成分配。同样，如果{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：设有三人联盟对策，其特征函数v{1}=v{2}=v{3}=0,
7、v{1,2}=4,v{2,3}=1,v{1,3}=3,v{1,2,3}=5由定理1知：这个博弈的核心由下面不等式组确定:x1+x2>=4x1+x3>=3x2+x3>=1x1+x2+x3=5xi>=0其解为A={x=(x1,x2,x3)
8、x1+x2+x3=5,xi>=0}内以(4,0,1,),(4,1,0),(3,2,0),(2,2,1)为顶点的四边形，如图：（0,0,5）0,5,03,2,0(4,1,0)(5,0,0)(4,1,0)(2,2,1)核有些联盟博弈的核可能是空的。满足非空的条件:定理：对于n人的联盟博弈，核心非空的充要条件
9、是线性规划有解：§4联盟博弈的Shapley值—n人合作博弈的另一个解设为一联盟博弈，对于给定的特征函数v可以确定出特定的分配这里,称为联盟博弈的Shapley值可以证明Shapley值是满足下述公理
