多人合作对策与分配问题(精品)

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,MS-OR,*,Click to edit Master title style,多人合作对策与分配问题,管理中的数量方法,多人合作对策与分配问题,本节课的内容安排,多人合作对策与分配问题,囚徒难题与,NASH,均衡点改,考试,多人合作对策与分配问题,MS-OR,第一部分多人合作对策模型,问题引入,多人结盟对策的基本概念,多人结盟对策的解,常用解法,多人结盟对策应用案例,多人合作对策与分配问题,MS-OR,一、问题引入,例1 ：（爵士乐队对策，,A Jazz Band,Gounce,）,一位歌手（,S），,一位钢琴家（,P）,和一位鼓手（,D）,组成一个小乐队在俱乐部同台演出能得到演出费1000元，若歌手和钢琴家一起演出能得800元。而只有钢琴家和鼓手一起演出能得到650元，钢琴独奏表演能得300元，钢琴家没有其它收入。然而，歌手和鼓手在地铁中表演能挣500元，歌手独奏可以从,The,Terasses,挣200元，而鼓手单独什么也挣不到。,问题：如何在这三人爵士乐队中合理分配共同演出费1000元？,多人合作对策与分配问题,MS-OR,一、问题引入,例2： 成本分摊问题（,A Cost Game）,三个城镇,A，B，C,欲与附近的一座电站连接起来，其可能的线路及其成本如下网络图表示：,这三个镇可相互联合建设，试问如何在这三个小镇合理分摊这笔建设费？,多人合作对策与分配问题,MS-OR,二、多人结盟对策的基本概念,多人结盟对策：局中人多于二人时的对策称为多人对策。这种对策中如果局中人可以和其它局中人联合成一体统一行动与其它局中人对抗，这种对策称为多人结盟对策。,这种对策有三个基本要素:,局中人,N,1,2,n,；,结盟,S,；,特征函数,V,（,S,）,。,一般可用,表示一个多人结盟对策。,多人合作对策与分配问题,MS-OR,1、,局中人与结盟,（,1,）,N,1,2,n,表示局中人集合。,（2）结盟,S，,表示一个联盟，即一局多人对,策中，一部份局中人联合成一体像一,个“局中人”一样选择策略，这种联合,称为结盟。显然结盟,S,是局中人集合,N,的子集，,S,N,。,（3）2,n,是局中人可能形成结盟的个数。,多人合作对策与分配问题,MS-OR,2、特征函数,（1）,V,(,S,),表示当若干局中人联合成一个结盟,S,时,在这局对策中能获得的最大收益值,即当形成结盟,S,只要,S,内每一个局中人共同策略,选择相应策略结盟,S,能保证获得,而与联盟外局人采用什么策略无关。若,S,=,V,(,)=0,。,（2）,超可加性,若一个多人对策的特征函数具有下列性质,即对任意结盟,S,T,N,S,T,=,满足,V,(,S,T,),V,(,S,)+,V,(,T,).,称这个多人对策具有超可加性。如果特征函数不满足超可加性，对策中的结盟是不稳定的。,多人合作对策与分配问题,MS-OR,例1 ：（爵士乐队对策，,A Jazz Band,Gounce,）,一位歌手（,S），,一位钢琴家（,P）,和一位鼓手（,D）,组成一个小乐队在俱乐部同台演出能得到演出费1000元，若歌手和钢琴家一起演出能得800元。而只有钢琴家和鼓手一起演出能得到650元，钢琴独奏表演能得300元，钢琴家没有其它收入。然而，歌手和鼓手在地铁中表演能挣500元，歌手独奏可以从,The,Terasses,挣200元，而鼓手单独什么也挣不到。,问题：如何在这三人爵士乐队中合理分配共同演出费1000元？,多人合作对策与分配问题,MS-OR,例1 ：（爵士乐队对策，,A Jazz Band,Gounce,）,这个问题可归为一个三人合作对策，它的特征函数,V（S）,为：,很容易验证此对策是具有超可加性的。,结盟,S,S,P,D,S,P,S,D,P,D,S,P,D,V,(,S,),1000,800,500,650,200,300,0,多人合作对策与分配问题,MS-OR,例2:（产品对策,A Production Game）,从,M,1,、M,2,、M,3,、M,4,四种原材料中各取一个单位能生产1个单位的某种产品，这个产品的价格要比它的原材料成本高出1000元，现有三个人，他们拥有这四种材料情况如下表:,问：若这三人联合起来生产这种产品，他们之间该如何分配所得利润？,原材料,人,M,1,M,2,M,3,M,4,1,1/2,1/2,0,0,2,1/2,0,1,0,3,0,1/2,0,1,多人合作对策与分配问题,MS-OR,例2:（产品对策,A Production Game）,将此问题转化为三人对策，其特征函数如下：,局中人2，3，通过合作生产，但由于他们共有四种原材料只能生产1/2个单位产品，所以能挣500元。,S,1,2,3,1,2,1,3,2,3,1,2,3,V,(,S,),0,0,0,0,0,0,500,1000,多人合作对策与分配问题,MS-OR,例3：成本分摊问题（,A Cost Game）,三个城镇,A，B，C,欲与附近的一座电站连接起来，其可能的线路及其成本如下网络图表示：,这三个镇可相互联合建设，试问如何在这三个小镇合理分摊这笔建设费？,多人合作对策与分配问题,MS-OR,例3：成本分摊问题（,A Cost Game）,这个问题的合作对策对，,N,=A,B,C，,成本分摊对策的特征函数,V,(,S,),如下表第二行：,相应的，表中第三行为成本节省对策,的特征函数值,V,(,S,)，,由下式得出,S,A,B,C,A,B,A,C,B,C,A,B,C,V,(,S,),0,100,140,130,150,130,160,150,C,(,S,),0,0,0,0,90,100,110,220,多人合作对策与分配问题,MS-OR,220,90,110,100,0,0,0,150,150,130,160,100,140,130,例3：成本分摊问题（,A Cost Game）,多人合作对策与分配问题,MS-OR,3、等价性与标准化(,valence and normalization),（1）,S-,等价,设,和,是两个,n,人对策，假设存在实数,a,1,a,2,，,a,n,，,及,k,0，,并对所有,S,N,，,且,S,，,满足,则称,对于,是,S-,等价，记为 ，,K,可理解为汇率。当,a,i,0,时，可理解为对,W,对策中每个局中人应分得的红利，而当,a,i,0,时，可认为是,W,对策的局中人应交的费用，该对策中的收益值依汇率,K,而变化，同时又涉及局中人的红利或应交费。,多人合作对策与分配问题,MS-OR,3、等价性与标准化(,valence and normalization),S-,等价是在一组,n,人对策中的一种等价关系，并具有下列性质。,弹性（,Reflexivity）：,对称性：若 ，则,（若,，则,）,传递性（,Transitivity）：,若 且 则,多人合作对策与分配问题,MS-OR,3、等价性与标准化(,valence and normalization),（2）标准型,0-标准型：一个多人对策，,若满足,V,(,i,)=0，,i,N,，则称该对策为0-标准型。,0-1标准型：对策,是0-标准型，且满足,V,(,N,)=1，,则称该对策为0-1标准型。,（,，,）,型：对策，,若满足,V,(,i,)=,，,i,N,且,V,(,N,)=,、,是实数，称此对策为（,，,）,型，显然（0，1）标准型是（,，,）,型之特殊情况。,定理：每一个必要结盟得超可加性对策均能,S-,等价于一个0-1标准型对策，,且这个,S-,等价是唯一的。,多人合作对策与分配问题,MS-OR,三、多人结盟对策的解,多人结盟对策的解的概念：,多人结盟对策中，每个局中人都希望通过结盟的形式去得到更多，而对策解的问题是如何合理确定这局对策中每个局中人的分配收益，对策解一般用,X(x,1, x,2,x,n,),表示,n,个局中人的得失向量，,x,i,表示第,i,个局中人之所得。,多人合作对策与分配问题,MS-OR,1、合理分配（,Imputation）,作为一个对策的解,X,，,即在对策中对,N,隔局中人得失的合理分配，至少应满足两个条件：,（1） （个人合理性）,（2） （集体合理性）,条件（1）称为：“个人合理性”（,Individual Rationality），,表示局中人,i,所分配值,x,i,不小于特征函数中规定他至少能得到的值,V,(,i,)。,条件（2）称为“集体合理性”条件（,Group Rationality），,表示对于一个对策解，所有局中人分配得失之和应等于所有局中人联合起来形成一个大联盟时得到的收益值，也就是这局对策中的最大收益值,V,(,N,)。,多人合作对策与分配问题,MS-OR,1、合理分配（,Imputation）,我们把满足上述两种条件的分法,X,=(,x,1,x,n,),称为“合理分配”，即有,显然，作为多人结盟对策的一个解,X，,至少必须是一个合理分配，即,多人合作对策与分配问题,MS-OR,1、合理分配（,Imputation）,例4：一局对策，,N,=1,2,3，,特征函数如下：,V,(,)=0，,V,(1)=,V,(2)=,V,(3)=0,V,(1,2)=,V,(1,3)=,V,(2,3)=0,V,(1,2,3)=1,合理分配集合,而 就是其中两合理分配。,多人合作对策与分配问题,MS-OR,2、支配（,Domination）,多人结盟对策求解问题实际是在合理分配集,I,(,V,),满足,对所有局中人不可能存在一个合理分配优于另一个合理分配，即有,但是对于某一个联盟,S,，,只要满足,成立（这是可能的），则对,S,联盟而言可认为,X,分配优于,Y,分配，即得出支配概念,多人合作对策与分配问题,MS-OR,2、支配（,Domination）,定义：对于两个合理分配,X,，,Y,，,若对于某一联盟,S,，,有,（1）,（2）,则称合理分配,X,通过联盟,S,支配,Y,，,记为,解释：,条件（1）表示对于联盟,S,来讲，,X,优于,Y,。,条件（2）表示联盟,S,有足够的能力保证它的局中人,I,通过合作能获得合理分配,定义：在对策中，只要存在某一联盟,S,，,且,X,通过,S,支配,Y,，,则也称,X,支配,Y,，,记为,多人合作对策与分配问题,MS-OR,四、常用解法,稳集法,核法,Shaply,值法,值法,多目标规划方法,多人合作对策与分配问题,MS-OR,1、稳集,稳集的基本思想,是选择这样一个合理分配的集合作为对策的解，而不在这集合内的任何合理分配总能被这个集合中某个合理分配所支配，且这个集合内的合理分配互相不被支配。,定义：对于一个对策，存在一组合理分配 满足,（1） ，则,X,，,Y,互相不被支配。,（2）对任合理分配 ，则必有,则称这样一组合理分配,S,(,V,),为此对策的稳集。,稳集被看作多人结盟对策的一种形式。,多人合作对策与分配问题,MS-OR,1、稳集,例5：有一三人结盟对策，N=1,2,3，V(S),为,V,(,)=,V,(1)=,V,(2)=,V,(3)=0,V,(1,2)=,V,(1,3)=,V,(2,3)=,V,(1,2,3)= 2,很容易证明：,S,(,V,)=(1,1,0),(1,0,1),(0,1,1),是此对策的一个稳集。,多人合作对策与分配问题,MS-OR,1、稳集,（1）先验证这三个合理分配间不相互支配。,对任一个 不可能成立。,例如对 在三个分配中任两个之间不可能同时成立。,（2）设任一 的合理分配 分别讨论 的情况。,多人合作对策与分配问题,MS-OR,1、稳集,把稳集作为解，从支配角度而言是有其合理性，但必须指出对多数结盟对策可能有多个稳集，而且并不是每一个对策都一定有稳集，,Lucas,早在1968年就举出一个无稳集的10人对策例子，以后1980年,Lucas,和,Rboie,又举出一个无稳集的13人对策的例子。,多人合作对策与分配问题,MS-OR,2、核（,The Core,）,核的主要思想也是基于支配概念，即从合理分配集,I(V),中选择一组合理分配，它们对任何联盟来说都不被其他合理分配所支配，把这组合理分配，称为,“,核,”,，作为对策的一种解的形式,。,定义：对策，,若存在一组合理分配，对任何联盟,S，,满足,称这组合理分配为对策的核，并用,C,(,V,),表示，记为,多人合作对策与分配问题,MS-OR,2、核（,The Core,）,例6：对一三人对策，,N,=1,2,3，,V,(,S,),为,V,(1,2)=2，,V,(1,2,3)=1，,V,(,S,)=0,对,S,1,2,对此对策有：,（注意，此对策不是超可加的）,注：若一个对策的核,C,(,V,)=,，,则可能通过先行规划的单纯形法找到核的元素。,多人合作对策与分配问题,MS-OR,2、核（,The Core,）,并非每一个对策均有非空的核，这也是将核作为对策解的一个很大缺点，实际问题中，经济问题的对策通常是有核的，而在政治科学的一些多人对策问题常常是没有核存在，为了解决此问题，提出弱核的概。,多人合作对策与分配问题,MS-OR,2、核（,The Core,）,通过求解下列,LP,问题，求得一个非空弱核。,s.t.,称,根据合理分配、稳集、核的定义有下面关系成立，,即核必定在稳集内，稳集必定在合理分配集合内。,多人合作对策与分配问题,MS-OR,3、沙波利值（,The,Shapley,Value ）,多人结盟对策的,The,Shapley,Value,解的概念是,Shapley,在1953年提出的，这个解的概念不同于前面介绍的核和稳集的概念。用核作为对策解的思想是基于选择不被支配的合理分配去作对策的解，而稳集是基于选择能支配一切不在这个集合内的合理分配的合理分配作为对策的解，而,Shapley,则,是基于期望边际收入思想上提出的,，他从局中人角度分析在对策之前，每个局中人应该期望得到多少。,多人合作对策与分配问题,MS-OR,3、沙波利值（,The,Shapley,Value ）,在一局对策,中，如果局中人,i,所得是则首先要满足下述三条公理：对称性，全局合理性、可加性。,这三个公理确立之后，,Shapley,值由下式给出：,对于一个,n,人合作对策，,存在唯一的一个向量函数,其中，|,S,|,表示联盟,S,中人的个数，则 称为,Shapley,值。,多人合作对策与分配问题,MS-OR,3、沙波利值（,The,Shapley,Value ）,Shapely,法是一种期望边际收入思想。,表示由于局中人参加了联盟而带来的数值，即局中人,i,对联盟,S,的边际贡献，而,表示局中人参加,S,的概率。,（局中人,i,在（,n,-,s,）,个局中人前，（,s,-,i,）,个局中人之后参加,s,的概率。）,多人合作对策与分配问题,MS-OR,3、沙波利值（,The,Shapley,Value ）,例7：该对策的特征函数如下,V,(1)=,a,V,(2)=,V,(3)=,V,(2,3)=0,V,(1,2)=,b,V,(1,3)=,V,(1,2,3)=,c,求,i,(,V,)，,先把包括局中人1的联盟抄列如下：,S,=1,1,2,1,3,1,2,3,多人合作对策与分配问题,MS-OR,3、沙波利值（,The,Shapley,Value ）,多人合作对策与分配问题,MS-OR,3、沙波利值（,The,Shapley,Value ）,多人合作对策与分配问题,MS-OR,4、,值法,值法是1981年提出，它的主要思想是首先确定解,X,的一个上界 和一个下界,L,满足,然后，求出,L,点与,U,点连线与超平面 之交点，,即通过求解,得解值,多人合作对策与分配问题,MS-OR,4、,值法,多人合作对策与分配问题,MS-OR,4、,值法,2）确定下界,首先对任一,i,S,联盟，取,称为联盟,S,中局中人,i,的剩余值（,remainder），,表示当联盟中除,i,外的其他局中人均按其边界贡献（上界值）,U,K,去分配,V,(,S,),时，留给,i,的剩余值。,取,为下界向量，其中 是局中人,i,的最大可能剩余值。如果,，则必有,这里,值表示一个在“理想点”,u,和“不同意点”,(disagreement),之间的一个可行的协调,(compromise),多人合作对策与分配问题,MS-OR,4、,值法,一个多人对策,的值解有下列性质。,（1,） 个人合理性,（2,） 有效性,（3,）对称性,（4,）若 ，则,虚设局中人性质。,（5） ,平衡性质。,但应指出,值解并不总是在核内。,多人合作对策与分配问题,MS-OR,4、,值法,例8：有一三人对策，N=1,2,3,V,(,)=,V,(1)=,V,(2)=,V,(3)=0,V,(1,2)=7，,V,(1,3)=,V,(2,3)=5，,V,(,N,)=9,则上界向量,U,=(,U,1,U,2,U,3,),U,1,=,V,(1,2,3)-,V,(2,3)=4,U,2,=,V,(1,2,3)-,V,(1, 3)=4,U,=(4,4,2),U,3,=,V,(1,2,3)-,V,(1,2)=2,多人合作对策与分配问题,MS-OR,4、,值法,多人合作对策与分配问题,MS-OR,4、,值法,求解,由于这个对策的核,C,(,V,),conV,(4,3,2),(4,4,1),(3,4,2)，,而,1/3(4,3,2)+(4,4,1)+(3,4,2),刚好是这个对策核三角形顶点的重心。若用,Shapley,法求解，,X,=(10/3,10/3,7/3)，,与,值解是不同的。,多人合作对策与分配问题,MS-OR,5、多人结盟对策的多目标决策方法,前面所述的多人对策的各种解的方法，都具有各自的特点和各自的缺点，从理论上讲并不存在一个最优或最合理的解，多人结盟对策的多目标决策方法，是吸收了核解法,值法的思想，将求解问题转化为一个多目标规划，从而各种有效的多目标决策方法均能使用于多人结盟对策问题。,多人合作对策与分配问题,MS-OR,5、多人结盟对策的多目标决策方法,对一个多人对策，N=1,2,N，,若把每个局中人的收益值视为一个目标函数，则此问题可看成,n,个目标的多目标决策问题，如果我们希望它的解是在核,C（V）,中或者仅在合理分配集,I（V）,中，上述多人对策求解问题转为一个多目标规划：,多人合作对策与分配问题,MS-OR,5、多人结盟对策的多目标决策方法,多人合作对策与分配问题,MS-OR,5、多人结盟对策的多目标决策方法,对于多目标规划（,I），,当核,C,(,V,),为空集时，即无可行解时，可通过下面步骤建立一个“弱核”，然后求解此问题。,步骤1：求解多目标规划（,II），,若无可行解，取步骤2。,步骤2：求解下列,LP,问题。,然后置,，,转步骤1求解。,用此方法求得解 满足整体合理性，又在核内或至少在“弱核”内。,多人合作对策与分配问题,MS-OR,5、多人结盟对策的多目标决策方法,我们可以具体选择一个适当的多目标方法来求解，这样可形成一类方法，称之为多人合作对策的多目标方法，例如使用二次规划方法（,QP）,来求解，具体步骤如下：,（1）首先确定一个理想分配向量,U,=(,u,1,u,2,u,n,）,其中,u,i,为局中人,i,的理想分配数，可以局中人,i,在大联盟中的边际贡献值作为,u,i,，,U,i,=,V,(,N,)-,V,(,N,-,i,),（2）,求解二次规划,多人合作对策与分配问题,MS-OR,5、多人结盟对策的多目标决策方法,（3）若上述二次规划非可行解，转求下列,LP,问题。,得,*,置 转（1）,此方法可称为“,GQP”,方法，它的解是指在距离意义上离理想分配向量最近，因此是在这种意义下的最优解。,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,例9： 破产问题,一个企业破产了，它的剩余资产价值抵不上所欠下的债务总和，这时应如何处置破产企业的尚留资产，即在所有债权人之间如何合理分配这些剩余资产。这就是破产的债务处理问题。,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,对于破产的债务吃力问题可以运用多人对策模型来处理，设：,E,破产后企业剩余资产值；,Nn,个债权人集合,1,2,n,；,d,1,企业欠第,i,债权人债务数；,D,债务总数，,并有,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,然后可以建立一个多人对策模型，,其中,N,债权人（局中人）集合，,N,=1,2,n,V,Ed,特征函数,V,(,S,),V,(,S,)=,Max,(,E,-,d,(,E,-,S,), 0,=,E,-,d,(,N,-,S,),+,特征函数,V,(,S,),表示部分债权人组成联盟,S,时至少能分到的资产数，其中,d,(,S,),表示,S,联盟所拥有债务总数，即：,则,m,i,为债权人,i,最少应得的资产数。,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,很容易验证,满足超可加性。这样，一个破产后剩余资产分配问题就转化为一个对策模型,的求解问题，即要求一个合理分配方案,X,=(,x,1,x,2,x,n,),，,它至少满足,其中,x,i,是债权人分到的资产数。,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,进一步求解方程组,得 代入得,将有关数据代入，得到按,值法计算的分配方案,X,*=(13.88,24,21,31.91),多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,例10 某企业宣告破产，其剩余资产为70万元，而企业有三个债权人甲、乙、丙，他们分别拥有债权数21.5万, 33.5万, 41.2万，企业的总债务数为96.2万。问题是如何在三个债权人之间合理分配企业的剩余破产。,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,首先建立对策模型,，其中,d,1,=21.5,，,d,2,=33.5,，,d,3,=21.5,，,D=d,1,+d,2,+d,3,=96.2E=70,局中人集合,N=1,2,3,特征函数,V(S)=E-,d(N,-S),+,V(1)=70-(33.5+41.2),+,=0(=m,1,),V(2)=70-(21.5+41.2),+,=7.3(=m,2,),V(3)=70-(21.5+33.5),+,=15(=m,3,),V(1,2)=70-41.2=28.8, V(2,3)=70-21.5=48.5,V(1,3)=70-33.5=36.5, V(1,2,3)=70,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,(2),按 值法求解,首先取上界,U=(u,1, u,2, ,u,n,),，其中,u,1,=V(N)-V(N-i)=E-E-,d,i,+,然后按 值法规则计算下界向量,L=(l,1, l,2, ,l,n,),经推导以此模型有,l,i,=m,i,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,(2),按,GQP,方法计算,步骤一：首先确定理想分配响亮,U=(u,1, u,2,u,3,),，其中,u,1,=V(N)-V(2,3)=70-48.5=21.5,u,2,=V(N)-V(1,3)=70-36.5=33.5,u,3,=V(N)-V(1,2)=70-28.8=41.2,多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,步骤二，求解二次规划,min,Z,=(,x,1,-21.5),2,+(,x,2,-33.5),2,+(,x,3,-41.2),2,转化为线性规划用单纯型法求解，得分配方案,X,*,=(12.83, 24.63, 32.53),多人合作对策与分配问题,MS-OR,五、多人结盟对策应用案例,2、建设工程投资分摊问题,某项工程的投资总费用应由从这项工程建成后受益的各部门共同合理分摊，投资分摊问题是一个典型的费用分配问题，因此同样可以使用多人对策模型来处理。,例19 某大型综合水利工程建成后主要效益表面在防洪、发电、航运三方面。工程总投资费用为163.04亿元（折现费用）。经有关部门反复分析估算，防洪、发电、航运三方面等同效益的替代方案费用分别为：防洪51.03亿元，发电179.27亿元，航运24.7亿元，进一步根据工程的具体情况估算各部门的可分离费用（某部门可分离费用系指综合工程的投资总费用减去该部门不参加综合利用时此工程的投资费用），三个部门的可分离费用分别为：防洪3.53亿元，发电87.60亿元，航运14.34亿元。问如何在三个部门分摊费用。,多人合作对策与分配问题,MS-OR,第二部分囚犯难题与,NASH,均衡,Prisoners Dilemma and NASH Equilibrium,Nash,均衡点是非合作对策分析中的一个重要概念， 基于冲突分析理论中的一些概念及其,F-H,稳定性分析方法的基础上，提出一个考虑局中人二步行为的,Nash,均衡概念 。,（一）纳什均衡的概念,（二）,囚犯难题与纳什均衡的缺陷,（三）纳什均衡的改进,（四）使用,F-H,方法求解囚徒问题,多人合作对策与分配问题,MS-OR,（一）,纳什均衡的概念,1、一般非合作对策模型,可用,N，,X,i,，,u,i,来描述。其中,N,为局中人集合,X,i,表示局中人,i,的一个策略,X=,X,1,X,2,X,n,为局势，即由各个局中人选择一策略后形成的；,u,i,表示各局中人对局势的支付函数,u,i,（,X,）；,多人合作对策与分配问题,MS-OR,2、 Nash,均衡,Nash,均衡就是指这样一个局势,X,*,，,在这个局势,X,*,中每个局中人都不会单独改变自己的策略。因为在局势中，当其他局中人不改变策略而仅一个局中人单独改变策略，只能使自己的支付函数减少。这个局势,X,*,是一个僵局，用数学符号表示,（,Nash,均衡），,X,*，u(,X,*)=Max,u,i,(,X,1,X,j,X,n,),(,X,i,),u,i,(,X,*),u,i,(,X,1,X,i,X,n,),在经济学中，人们给纳什均衡是这样定义的：,“,在给定它的竞争者的行为以后，各厂商采取它能采取的最好行为,”,。,多人合作对策与分配问题,MS-OR,（二）囚犯难题与纳什均衡的缺陷,1、 Nash,均衡的缺陷,Nash,均衡描述了对策中的一种平衡。但这种平衡点并没有完全反映对策中动态意义上的均衡，实质上,Nash,均衡只是考虑局中人一步行动的均衡，它是在其他局中人均不变的前提下的结论。由于这种局限，在非合作对策分析中并不完全，甚至出现与实际不符的情况。,例如：在对策中著名的囚徒问题中若仅仅使用基于,Nash,均衡念的非合作对策(又称,Nash,对策)分析方法，由于这种分析只考虑了在其他局中人策略不变的情况下，局中人自己单方面改变略自己策略的结果，而并未考虑冲突的最终结果的影响，便导致了悖论的出现。“囚犯难题”便是典型的一个。,多人合作对策与分配问题,MS-OR,2、囚犯难题,求其,Nash,平衡解的结果(-5，-5)。可见“囚犯难题”中追求最优目标的动机和实际达到低劣结果之间的矛盾便是该悖论的焦点。追求个人的“最优”策略往往导致全局的劣等解，从而又将损害个人的利益，这就是“囚犯悖论”的社会意义。,支付,囚犯,II,供认,顽抗,囚犯,I,供认,（-5，-5）,（0，-10）,顽抗,（-10，0）,（-1，-1）,多人合作对策与分配问题,MS-OR,2、囚犯难题,使用非合作对策分析方法求其囚犯难题的,Nash,平衡解，结果囚犯、囚犯的稳定策略均为“供认”，其各自的支付为(-5，-5)，但这一结果显然劣于他们共同“顽抗”的结果(-1，-1)。可见“囚犯难题”中追求最优目标的动机和实际达到低劣结果之间的矛盾便是该悖论的焦点。这个问题还有着广泛的社会背景，追求个人的“最优”策略往往导致全局的劣等解，从而又将损害个人的利益，这就是“囚犯悖论”的社会意义。用对策分析策略分析，得出（坦白，坦白）这个平衡点。但根据定义（抗拒，抗拒）不是一个,Nash,均衡点。而显然（抗拒，抗拒）这个局势对双方均为最有利，这正是因为,Nash,均衡只是考虑一步的原故。,多人合作对策与分配问题,MS-OR,（三）,FH,冲突分析方法与二步,Nash,均衡概念,F,-,H,在冲突分析中，提出了必然制裁和相继稳定性的概念，并在此基础上了建立的平衡点概念实际上就是一种扩展的,Nash,平衡点。在,F-H,稳定性分析概念的基础上，下面提出一个考虑局中人二步行为的,Nash,均衡概念,。,1、局中人的单方移动与单方改进,用数学符号表示为：,局中人,i,，,单方改进策略，其他局中人不变，使得,而,多人合作对策与分配问题,MS-OR,（三）,FH,冲突分析方法与二步,Nash,均衡概念,2、必然制裁,对某个局中人单方改进后的局势，其它局中人又拥有一个单方改进，使得经其它局中人进一步改进后的冲突局势对该局中人而言反不如其未做单方改进时的局势，我们便称为该局中人的这个单方改进存在一个必然制裁。即,局中人,i,有一单方改进，使,X,0,X,1,，,而在局中,X,1,中其它至少有一个局中人,j,有一个单方改进，使,X,1,X,2,，,而有,称为一个必然制裁。,多人合作对策与分配问题,MS-OR,（三）,FH,冲突分析方法与二步,Nash,均衡概念,3、局势的一步稳定性,对某局中人而言，对该局势不存在单方改进，则称该局势对这个局中人具有一步稳定性。,4、局势的二步稳定性,对某局中人而言，对于该局势的每一个单方改进，其他局中人均存在必然制裁。则称该局势对这个局中人具有二步稳定性。,多人合作对策与分配问题,MS-OR,（三）,FH,冲突分析方法与二步,Nash,均衡概念,5、 二步,Nash,均衡,局势,X,*,对每个局 中 人而言都是一步，或二步稳定，则称局势,X,*,为一个二步,Nash,均衡。,实际上原,Nash,平衡点的定义是，,X,*,i,对每个局中人都是一步稳定的。,二步均衡实际上是考虑了局中人二步行动的均衡。,在这个定义下，囚徒问题中局势抗拒，抗拒也是一个二步意义,Nash,均衡点。,可以使用,FH,稳定性分析方法找出所有二步,Nash,均衡。,多人合作对策与分配问题,MS-OR,（三）,FH,冲突分析方法与二步,Nash,均衡概念,F-H,冲突分析方法则从分析局势的稳定性入手，对于冲突的一个局势，它考虑多个局中人中的一个通过离开目前方案达到更好的局势了吗?同其他局中人合作而使合作者都受益的最后方案值得吗?冲突中的其他局中人将怎样面对该局中人的移动和反移动；,F-H,冲突分析方法就是从这些方面来考查一个冲突的结果的,:,F-H,冲突分析方法的分析过程由建模和稳定性分析两部分组成，冲突分析的基本步骤及其流程图如前面所示。,多人合作对策与分配问题,MS-OR,（四）使用,F-H,方法求解囚徒问题,局中人：,囚犯,A、,囚犯,B,策略：,囚犯,A,坦白 1；抗拒0,囚犯,B,坦白 1；抗拒0,局势：,（1，1），（1，0），（0，1），（0，0）,代码：,3 1 2 0,支付：,（-5，-5）（0，-10）（-10，0）（-1，-1）,囚犯,A,局势排序：,（1，0，3，2）,囚犯,B,局势排序：,（2，0，3，1）,多人合作对策与分配问题,MS-OR,（四）使用,F-H,方法求解囚徒问题,A 1 0 10 A 0 0 1 1,B 0 0 1 1 B 1 0 1 0, ,1 0 3 2 ，A,排序 2 0 3 1 ，,B,排序,稳定性分析,A r s r u,1 0 3 2,局势排序,1 3 单方改进局势,B r s r u,2 0 3 1,局势排序,2 3 单方改进局势,稳定局势：0（0，0）；3（1，1）,多人合作对策与分配问题,MS-OR,（四）使用,F-H,方法求解囚徒问题,用常规对策分析策略分析，只能得出（坦白，坦白）这个平衡点。但根据定义（抗拒，抗拒）不是一个,Nash,均衡点。而显然（抗拒，抗拒）这个局势对双方均为最有利，这正是因为,Nash,均衡只是考虑一步的原故。应用,F-H,稳定性分析能得出（坦白，坦白）和（抗拒，抗拒）二个平衡点，在上述二步,Nash,均衡定义下，囚徒问题中局势抗拒，抗拒也是一个二步意义下的,Nash,均衡点。使用,FH,稳定性分析方法可以找出所有二步,Nash,均衡。,多人合作对策与分配问题,MS-OR,结束,Thank You !,