多人合作对策与分配问题.ppt

管理中的数量方法,多人合作对策与分配问题,MS-OR,多人合作对策与分配问题,本节课的内容安排,多人合作对策与分配问题,囚徒难题与NASH均衡点改,考试,MS-OR,多人合作对策与分配问题,第一部分多人合作对策模型,问题引入,多人结盟对策的基本概念,多人结盟对策的解,常用解法,多人结盟对策应用案例,MS-OR,多人合作对策与分配问题,一、问题引入,例1：（爵士乐队对策，AJazzBandGounce）一位歌手（S），一位钢琴家（P）和一位鼓手（D）组成一个小乐队在俱乐部同台演出能得到演出费1000元，若歌手和钢琴家一起演出能得800元。而只有钢琴家和鼓手一起演出能得到650元，钢琴独奏表演能得300元，钢琴家没有其它收入。然而，歌手和鼓手在地铁中表演能挣500元，歌手独奏可以从TheTerasses挣200元，而鼓手单独什么也挣不到。问题：如何在这三人爵士乐队中合理分配共同演出费1000元？,MS-OR,多人合作对策与分配问题,一、问题引入,例2：成本分摊问题（ACostGame）三个城镇A，B，C欲与附近的一座电站连接起来，其可能的线路及其成本如下网络图表示：这三个镇可相互联合建设，试问如何在这三个小镇合理分摊这笔建设费？,MS-OR,多人合作对策与分配问题,二、多人结盟对策的基本概念,多人结盟对策：局中人多于二人时的对策称为多人对策。这种对策中如果局中人可以和其它局中人联合成一体统一行动与其它局中人对抗，这种对策称为多人结盟对策。这种对策有三个基本要素:局中人N1,2,n；结盟S；特征函数V（S）。一般可用表示一个多人结盟对策。,MS-OR,多人合作对策与分配问题,1、局中人与结盟,（1）N1,2,n表示局中人集合。（2）结盟S，表示一个联盟，即一局多人对策中，一部份局中人联合成一体像一个“局中人”一样选择策略，这种联合称为结盟。显然结盟S是局中人集合N的子集，SN。（3）2n是局中人可能形成结盟的个数。,MS-OR,多人合作对策与分配问题,2、特征函数,（1）V(S)表示当若干局中人联合成一个结盟S时,在这局对策中能获得的最大收益值,即当形成结盟S,只要S内每一个局中人共同策略,选择相应策略结盟S能保证获得,而与联盟外局人采用什么策略无关。若S=,V()=0。（2）超可加性若一个多人对策的特征函数具有下列性质,即对任意结盟S,TN,ST=,满足V(ST)V(S)+V(T).称这个多人对策具有超可加性。如果特征函数不满足超可加性，对策中的结盟是不稳定的。,MS-OR,多人合作对策与分配问题,例1：（爵士乐队对策，AJazzBandGounce）,一位歌手（S），一位钢琴家（P）和一位鼓手（D）组成一个小乐队在俱乐部同台演出能得到演出费1000元，若歌手和钢琴家一起演出能得800元。而只有钢琴家和鼓手一起演出能得到650元，钢琴独奏表演能得300元，钢琴家没有其它收入。然而，歌手和鼓手在地铁中表演能挣500元，歌手独奏可以从TheTerasses挣200元，而鼓手单独什么也挣不到。问题：如何在这三人爵士乐队中合理分配共同演出费1000元？,MS-OR,多人合作对策与分配问题,例1：（爵士乐队对策，AJazzBandGounce）,这个问题可归为一个三人合作对策，它的特征函数V（S）为：很容易验证此对策是具有超可加性的。,MS-OR,多人合作对策与分配问题,例2:（产品对策AProductionGame）,从M1、M2、M3、M4四种原材料中各取一个单位能生产1个单位的某种产品，这个产品的价格要比它的原材料成本高出1000元，现有三个人，他们拥有这四种材料情况如下表:问：若这三人联合起来生产这种产品，他们之间该如何分配所得利润？,MS-OR,多人合作对策与分配问题,例2:（产品对策AProductionGame）,将此问题转化为三人对策，其特征函数如下：局中人2，3，通过合作生产，但由于他们共有四种原材料只能生产1/2个单位产品，所以能挣500元。,MS-OR,多人合作对策与分配问题,例3：成本分摊问题（ACostGame）,三个城镇A，B，C欲与附近的一座电站连接起来，其可能的线路及其成本如下网络图表示：这三个镇可相互联合建设，试问如何在这三个小镇合理分摊这笔建设费？,MS-OR,多人合作对策与分配问题,例3：成本分摊问题（ACostGame）,这个问题的合作对策对，N=A,B,C，成本分摊对策的特征函数V(S)如下表第二行：相应的，表中第三行为成本节省对策的特征函数值V(S)，由下式得出,MS-OR,多人合作对策与分配问题,例3：成本分摊问题（ACostGame）,MS-OR,多人合作对策与分配问题,3、等价性与标准化(valenceandnormalization),（1）S-等价设和是两个n人对策，假设存在实数a1,a2,，an，及k0，并对所有SN，且S，满足则称对于是S-等价，记为，K可理解为汇率。当ai0时，可理解为对W对策中每个局中人应分得的红利，而当aiE=70局中人集合N=1,2,3特征函数V(S)=E-d(N-S)+V(1)=70-(33.5+41.2)+=0(=m1)V(2)=70-(21.5+41.2)+=7.3(=m2)V(3)=70-(21.5+33.5)+=15(=m3)V(1,2)=70-41.2=28.8,V(2,3)=70-21.5=48.5V(1,3)=70-33.5=36.5,V(1,2,3)=70,MS-OR,多人合作对策与分配问题,五、多人结盟对策应用案例,MS-OR,多人合作对策与分配问题,五、多人结盟对策应用案例,(2)按值法求解首先取上界U=(u1,u2,un)，其中u1=V(N)-V(N-i)=E-E-di+然后按值法规则计算下界向量L=(l1,l2,ln),经推导以此模型有li=mi,MS-OR,多人合作对策与分配问题,五、多人结盟对策应用案例,(2)按GQP方法计算步骤一：首先确定理想分配响亮U=(u1,u2,u3)，其中u1=V(N)-V(2,3)=70-48.5=21.5u2=V(N)-V(1,3)=70-36.5=33.5u3=V(N)-V(1,2)=70-28.8=41.2,MS-OR,多人合作对策与分配问题,五、多人结盟对策应用案例,步骤二，求解二次规划minZ=(x1-21.5)2+(x2-33.5)2+(x3-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均衡,PrisonersDilemmaandNASHEquilibriumNash均衡点是非合作对策分析中的一个重要概念，基于冲突分析理论中的一些概念及其F-H稳定性分析方法的基础上，提出一个考虑局中人二步行为的Nash均衡概念。（一）纳什均衡的概念（二）囚犯难题与纳什均衡的缺陷（三）纳什均衡的改进（四）使用F-H方法求解囚徒问题,MS-OR,多人合作对策与分配问题,（一）纳什均衡的概念,1、一般非合作对策模型可用N，Xi，ui来描述。其中N为局中人集合Xi表示局中人i的一个策略X=X1,X2,Xn为局势，即由各个局中人选择一策略后形成的；ui表示各局中人对局势的支付函数ui（X）；,MS-OR,多人合作对策与分配问题,2、Nash均衡,Nash均衡就是指这样一个局势X*，在这个局势X*中每个局中人都不会单独改变自己的策略。因为在局势中，当其他局中人不改变策略而仅一个局中人单独改变策略，只能使自己的支付函数减少。这个局势X*是一个僵局，用数学符号表示（Nash均衡），X*，u(X*)=Maxui(X1XjXn)(Xi)ui(X*)ui(X1XiXn)在经济学中，人们给纳什均衡是这样定义的：“在给定它的竞争者的行为以后，各厂商采取它能采取的最好行为”。,MS-OR,多人合作对策与分配问题,（二）囚犯难题与纳什均衡的缺陷,1、Nash均衡的缺陷Nash均衡描述了对策中的一种平衡。但这种平衡点并没有完全反映对策中动态意义上的均衡，实质上Nash均衡只是考虑局中人一步行动的均衡，它是在其他局中人均不变的前提下的结论。由于这种局限，在非合作对策分析中并不完全，甚至出现与实际不符的情况。例如：在对策中著名的囚徒问题中若仅仅使用基于Nash均衡念的非合作对策(又称Nash对策)分析方法，由于这种分析只考虑了在其他局中人策略不变的情况下，局中人自己单方面改变略自己策略的结果，而并未考虑冲突的最终结果的影响，便导致了悖论的出现。“囚犯难题”便是典型的一个。,MS-OR,多人合作对策与分配问题,2、囚犯难题,求其Nash平衡解的结果(-5，-5)。可见“囚犯难题”中追求最优目标的动机和实际达到低劣结果之间的矛盾便是该悖论的焦点。追求个人的“最优”策略往往导致全局的劣等解，从而又将损害个人的利益，这就是“囚犯悖论”的社会意义。,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有一单方改进，使X0X1，而在局中X1中其它至少有一个局中人j有一个单方改进，使X1X2，而有称为一个必然制裁。,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）代码：3120支付：（-5，-5）（0，-10）（-10，0）（-1，-1）囚犯A局势排序：（1，0，3，2）囚犯B局势排序：（2，0，3，1）,MS-OR,多人合作对策与分配问题,（四）使用F-H方法求解囚徒问题,A1010A0011B0011B10101032，A排序2031，B排序稳定性分析Arsru1032局势排序13单方