9.合作博弈

第7章合作博弈COOPERATIVEGAMES熊、狼、狐狸一起抓了一只兔子，民主协商如何分配。狐狸对熊说：平均分只能各得1/3，这样吧，我们俩联合起来，平分如何？熊要答应，狼急了，于是狐狸对狼说：怎么样，我和熊联合起来可以让你什么也得不到，我可以和你合作，不过我要3/4。狼感激的点头，熊琢磨过味来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。狐狸见势不妙，对狼说：别，我给你2/3，我只要1/3。狼成了抢手货，正得意，没留神狐狸和熊又开始嘀咕起来，有再次把自己晾在一边的不妙趋势，连忙钻去继续讨价还价。结果呢？青山原不动，白云自去来如果在实际博弈问题中，具有有力的保障使局中人能够进行协商、谈判，联合选择行动，共同分享利益，我们就面对一个合作博弈问题。本章通过合作博弈模型的介绍，讨论在合作博弈中，局中人如何进行协商谈判、结成联盟及分享利益。1、纳什讨价还价问题(略）2、联盟博弈3、联盟博弈的分配4、核和稳定集5、沙普利值合作博弈的意义与构成合作博弈的意义表现在它与非合作博弈的差别上。如果协议有外在力量保证强制执行，则为合作博弈，否则为非合作博弈。非合作博弈的重点是在个体，是每个局中人该采用什么策略；强调个体理性（individualrationality）合作博弈的重点则在群体，讨论何种联盟将会形成，联盟中的成员将如何分配他们可以得到的支付；强调群体理性(grouprationality)合作：为共同的目的而一起行动需要一个描述集体理性的效用函数。描述n人合作博弈，通常假设合作博弈具有可传递效用。简单地说，该效用就像货币一样，可以在各局中人之间自由转让。（合作，人类进化之舟。）7.2具有可转移支付的联盟博弈7.2.1具有可转移支付的联盟博弈及分类具有可转移支付的人合作博弈在非合作的人博弈中，局中人之间不允许事先协商如何选择策略，不允许他们把策略结合起来，不允许局中人对得到的支付重新分配，一个局中人不能分享另一个局中人的支付，或支付是不可能转移的。本章所讨论的人合作博弈对上述问题都不加限制。局中人在选择策略时可以协商，并且局中人的支付可以相互转让，或支付是可以转移的。在具有可转移支付的人合作博弈中，局中人如何选择自己的策略已不是主要讨论的问题，我们主要讨论的问题是局中人如何分配通过合作所获得的收益或效用。nnnn联盟与特征函数设局中人集合，称的任一子集为一个联盟。为方便，把的空子集也视为一个联盟。记所有联盟构成的集类为。对，用表示联盟中的局中人通过合作所能获得的最大支付。且可认为这个值与中的局中人的行为是独立的，因而是定义于上的函数，即。定义7.2对于局中人集合的任一子集，给定集合的支付，如果满足,则称为特征函数，称为具有可转移支付的联盟博弈。若满足对，，有，则说满足超可加性。下面讨论的联盟博弈都是指具有可转移支付的联盟博弈。特征函数满足超可加性。}n,,2,1{NNNBBS)(SvSSSSN\)(SvBRBv:}n,,2,1{N)(Svv0)(v)(vvN,)(SvBTS,TS)()()(TvSvTSv)(v例7.1局中人1（卖主）要把一件物品卖掉，局中人2和3（买主）分别出价9元和10元。如果局中人1将物品卖给局中人2的要价是x元，则局中人2赢利9-x元。联盟的总收益为9元。类似，联盟的总赢利为10元。于是有。另一方面，单个局中人或者两个买主在一起都不可能赢利，即，。当三个局中人在一起交易时，局中人1显然要把物品卖给局中人3，从而v({1,2,3})=10，显然满足超可加性，于是我们建立了联盟博弈。特征函数是研究联盟博弈的基础，确定特征函数过程实际就是一个建立合作博弈模型的过程。有的问题，特征函数可以容易地得到，有的问题需要仔细分析，甚至需要一些专业知识。若对，，都有,则称满足可加性。}2,1{}3,1{10}3,1{,9}2,1{vu0}3,2{}{viv3,2,1i)(vvN,BTS,TS)()()(TvSvTSvv我们可以给出满足可加性的特征函数的例子。例7.2在某项工作中，不熟练工人可获报酬元，熟练工人可得报酬元，于是可以定义特征函数。这里表示集合中的局中人个数，以后也用这种记法。(小知识：中国参与环保组织的志愿者约30万人，美国有60%，欧洲有50%的人参与。参与环保，保护共同家园，需要我们合作，如二氧化碳排放，如如何保护森林。当前，最大的善，不是施舍，而是节约资源！)1,,2,1nabSnasbSnassv当当)1()(SS7.3联盟博弈的分配转归或分配的定义在联盟博弈中局中人通过合作，获得一定的联盟支付，联盟还要将这笔支付转归于每个局中人，联盟博弈中每个局中人从联盟中所获的支付或转归可用维向量表示，这里为局中人所得到的支付。定义7.3称向量是联盟博弈的一个转归或分配，如果满足（1），（2）。（1）式表明n个局中人的支付总和应与他们全体构成一个联盟所获的支付相等。这说明如果要使某个局中人的支付增加，必需减少其它局中人的支付。这描写了帕累托最优性，因而，称（1）为整体合理性。（2）式表明每个局中人在合作博弈中所获得的支付不应低于他“单干”所获的支付。称（2）为个体合理性。),,2,1(nin),,,(21nxxxXix),,2,1(ni),,,(21nxxxXvN,XniiNvx1)(({})ixvi分配的优超关系为了比较哪个分配好些，给出以下定义。定义7.4设有分配，及联盟,如果(1)对，(2)则称联盟为分配优于分配，记作。如果对于，存在一个联盟，使，则称优于，记为。定义中条件（1）表明，联盟中每个成员都认为分配比好。条件（2）表明分配对中成员的支付能够由联盟付出。)(,vIyxBSiiyxSi,siiSvx)(SSSSxyyxs)(,vIBTTxyx单人联盟不可能存在转归之间的占优关系实际，如果，由定义，且，于是有，这与为转归相矛盾。全联盟也不可能存在转归之间的占优关系如果，则，，。于是，这与为转归矛盾。关于某个联盟转归之间的占优关系满足下述的传递性：设，如果，，则。但由，一般不能得到的结论。XYi})({ivyiiixyiixyiv})({XNXYNniiyNv1)(iixyNi)(11NvxyniiniiYS)(,,vIZYXYXSZYSZXSZYYX,ZX7.4稳定集与核稳定集的定义定义7.5对于联盟博弈，集合称为联盟博弈的稳定集（stableset），如果以下条件成立。（1）中任意分配都不优于中的其余分配。（2）不属于中的任何分配，总可以在中找到优于的分配。稳定集定义中第1条表明在稳定集内部的任何两个分配之间不存在优超关系，称为稳定集的内稳定性，它可以防止由于联盟内部成员因利益冲突而导致联盟解体；第2条表明稳定集外的任一分配，至少被稳定集内的某个分配优超，称为稳定集的外稳定性。稳定集的概念由冯.诺依曼（V.Neumann）和摩根斯坦恩（Morgenstern）提出，也称为合作博弈的解。vN,)()(vIvSvN,)(vS)(vSx)(vSyy)(vSxMVN例7.3设有三个局中人，拟合伙开商店，每月可赢利2000元。要使商店正常营业，起码需要两人。试问，应采用怎样的方式经营，以及怎样分配利润才是合理的。这是一个联盟博弈问题。特征函数为三人利润分配是向量，满足如果联盟形成，即局中人1、2合伙，则分配是合理的。否则，局中人1要求采取分配，其中，那么局中人2将与局中人3合伙。如果局中人3也采取类似的要求，则局中人2不与任何人结盟，余下1与3各持己见。不构成分配。同样，如果结盟，是合理的分配；结盟，是合理的分配。易知是稳定集（1）x,y,z之间没有优超关系；（2）对于W之外的任何一个分配，必被中某个分配优超。3,2,1,0)(iiv.2}3,2,1{}3,1{}3,2{}2,1{vvvv),,(321xxxx2}3,2,1{321vxxx.3,2,1,0ixi}2,1{)0,1,1(x)0,1,1()1,0()1,0,1(}3,2{)1,1,0(y}3,1{)1,0,1(z},,{zyxw人们花费了近20年的时间来证明联盟博弈的存在性。但卢卡斯（Lucas，１９６９）举出了反例说明联盟博弈的稳定集可以是空的。另外，寻求稳定集至今还没有通用的方法。核的定义定义7.6人联盟博弈的所有不被优超的分配构成的集合称为核，记为。对于核中的分配，局中人不能通过重组联盟而增加支付。核的充要条件定理7.2是人联盟博弈的核中的分配的充要条件是（1）（2）对，。nvN,)(vcX),,,(21nxxxXnvN,)(1NvxniiBS)()(SvxSxSii例7.4设有三人联盟对策，其特征函数，由定理7.2易知,该博弈的核由下面不等式组确定：易知，，，。故该博弈的核其图形为单纯形内以为顶点的四边形，如图7-1所示(p201)。0}}3{}2{}1{vvv5}3,2,1{,3}3,1{,1}3,2{,4}2,1{vvvv0,,5134321321323121xxxxxxxxxxxx41x22x13x}0,,,5),,({321321321xxxxxxxxxxA)1,2,2(),0,2,3(),0,1,4(),1,0,4(}10,20,40,5),,{()(321321321xxxxxxxxxvc(5,0,0)（0,5,0）（0,0,5）(2,2,1)（3,2,0）(4,1,0)图7-1(4,0,1)例7.5污染问题沙普利（Shaplay）和舒比克（Shubik）描述了一个湖的污染模型。设有个工厂分布在某湖的沿岸，为简便起见，设问题是对称的。即每个工厂的污染程度相同。假设每个工厂每天必须在湖里抽取相同数量的清洁水，用完后将污水排入湖中。所涉及的方案和费用如下:(1)每个工厂每天必须因每个直接向湖中排放污水的工厂（包括自身）花费c美元净化它所用的水。（2）每个工厂可以安装一个过滤器，在污水排回湖中之前就将水净化。每个工厂每天的净水费用为b美元。为使问题有意义，假设。（3）个局中人可以组成一个联盟，共同决定是否采用过滤器。注意，如果决定采用过滤器，联盟之外的工厂仍会向湖中排放污水。因而联盟的特征函数值为ncbc0),,2,1(nsSSSScbscsnbscbsncscsnbssncSv))((})((,max{)(即当时，联盟决定采用过滤器，时决定不采用过滤器。设，有由定理7.2，的充要条件是满足下述不等式组由知即。由问题的对称性知，。故该联盟博弈的核为，。cbsSScbs1,2,3cbn232)5()(sssssSv)(),,(321vcxxxXX3,2,1,36666323121321ixxxxxxxxxxi621xx63321xxxx03x0ix3,2,1i123123(){(,,)6,30}icvxxxxxxx3,2,1i例7.7具有否决人的0-1规范简单联盟博弈设是一个0-1规范简单的联盟博弈，即取0与1两个值，且，，。如果局中人满足，称为具有否决权的局中人或否决人。对于，的充要条件是存在否决人。证明必要性若，但没有否决人，即对成立。对有，。于是，。这与相矛盾。因而存在否决人。充分性设的全体否决人集合为，设满足，当时，。当时，。可以证明。(联合国的安理会)vN,vN,vN,)(sv1)(Nv0})({