第十二章-对策论(运筹学讲义)PPT课件

-,1,第十章对策论由“齐王赛马”引入,1对策论的例子2矩阵对策论的基本概念3矩阵对策的最优纯策略4矩阵对策的混合策略5其他类型的对策,-,2,对策论或博弈论(GameTheory)是研究具有对抗和竞争性行为问题的数学理论与方法。是运筹学的重要分支学科经济学领域一般称博弈论，是经济学领域近几十年发展起来一门新兴学科,对策论从理论上作严格的讨论却起始于二十世纪：1912年，德国数学家E.Zermelo证明了国际象棋的3种着法必定存在一种；1921年，法国数学家E.Borel引入了“最优策略”等概念；1928年，美籍匈牙利人J.VonNeumann证明了对策论的基本定理-最大值最小值定理；1944年，VonNeumann和O.Morgenstern合写了对策论与经济行为一书，建立起对策论的基本理论，奠定了对策论研究的基础。,-,3,对策问题举例,例1猜单和猜双的博弈。两个人同时出一个指头或两个指头，如果两人出的指头相同，则局中人1从局中人2处赢得五元；如果出的不一样，局中人1就要支付给局中人2五元。两个对手都可以采取两个策略：出一个手指和出两个手指，下表是局中人1的赢得矩阵(二指莫拉问题),局中人1从局中人2该如何选择策略，已获得利益？,-,4,例2囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在不同的屋子里审讯。警察告诉他们：如果两人都坦白，各判刑8年；如果两人都抵赖，由于证据不充分，两人将各判刑2年；如果其中一人坦白，另一人抵赖，则坦白者立即释放，抵赖者判刑10年。在这个例子中两人嫌疑犯都有两种策略：坦白或抵赖。可以用一个矩阵表示两个嫌疑犯的策略的损益,囚徒该如何选择策略？,囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性,-,5,例3田忌与齐王赛马,战国时期，齐威王与大将田忌赛马，双方约定：从各自的上、中、下三个等级的马中各选一匹马出场比赛，负者要付给胜者一千金。已知田忌的马要比齐王同一等级的马差一些，但比齐王等级较低的马却要强一些。因此，如用同等级的马对抗，田忌必连输三场，失三千金无疑。田忌的谋士孙膑给田忌出了个主意：每局比赛前先了解齐王参赛马的等级，再采用下等马对齐王上等马、中等马对齐王下等马、上等马对齐王中等马的策略。比赛结果，田忌二胜一负，反而赢得一千金。由此可见，双方各采取什么样的出马次序对胜负至关重要。,-,6,“齐王赛马”齐王在各局势中的益损值表(单位：千金),齐王和田忌可以任意选择三匹马出场的顺序,-,7,1对策论的基本概念,对策模型的三个基本要素：1.局中人(Players)：参与对抗的各方；2.策略集(Strategices):局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集3.一局势对策的益损值：局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果（量化）称为该局势对策的益损值。赢得函数(payofffunction)：定义在局势上，取值为相应益损值的函数4.纳什均衡：纳什均衡指所有局中人最优策略组成的一种局势，既在给定其他局中人策略的情况下，没有任何局中人有积极性去选择其他策略,-,8,对策的分类,对策,按对策方式,合作对策,非合作对策,完全理性,有限理性,两人对策,零和对策,非零和对策,多人对策,结盟对策,不结盟对策,按对策人数,静态对策,完全信息静态对策,不完全信息静态对策,动态对策,完全信息动态对策,不完全信息动态对策,按对策状态,-,9,二人有限零和对策（又称矩阵对策）：局中人为2；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。通常将矩阵对策记为:G=S1,S2,A局中人甲的策略集：局中人乙的策略集：甲的赢得矩阵：,矩阵对策,aij为局中人甲在局势下的赢得,-,10,其中：齐王的策略集:S1=1,2,3,4,5,6，田忌的策略集：S2=1,2,3,4,5,6。下面矩阵称齐王的赢得矩阵：3111-1113111-1A=1-13111-111311111-13111-1113,“齐王赛马”是一个矩阵策略。,-,11,2矩阵对策的最优纯策略,例4甲、乙两队进行球赛，双方各可排出三种不同的阵容。设甲队为局中人，乙队为局中人，每一种阵容为一个策略，有S1=1,2,3，S2=1,2,3。根据以往两队比赛的记录，甲队得分情况的赢得矩阵为,问：这次比赛中，双方应如何对阵？,-,12,在如此反复对策的过程中，各局中人如果不想冒险，就应该考虑从自身可能出现的最坏情况下着眼，去选择一种尽可能好的结果，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。这就是所谓“理智行为”。称为最小最大准则，按照这个各方均避免冒险的观念，就形成如下的推演过程。,解从A中可以看出，最多可得6分。于是，为得6分而选2。,但是推测会有此心理，从而选3来对付，使得非但得不到6分，反而要失去3分。,当然也会料到会有此心理，从而改选3，以使欲得3分而反失4分。,-,13,矩阵A中每行的最小元素分别为1，-3，-5。在这些最少赢得中最好的结果是1，故局中人会采取策略1，无论对手采取何策略，局中人至少得1分。对于局中人，1，2，3可能带来的最少赢得，即A中每列的最大元素，分别为6，1，4。局中人会采取2策略，确保局中人不会超过1分。1和2分别称为局中人、的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。,2矩阵对策的最优纯策略,-,14,定义1设有矩阵对策G=S1,S2;A,其中，A=aijmn，若有,则局势(i*，j*)称为G在纯策略意义下的解，也称为G的鞍点；i*、j*分别称为局中人和的最优纯策略；v称为G的值，也称对策值。,对于例4，G的解(鞍点)为(1,2)，1、2分别为、的最优策略。对策值v=10，反映优势在方(对有利)；若v0,为任一常数。则(1)(2)T(G1)=T(G2),定理9设GS1,S2;A为一矩阵对策，且A=AT为斜对称矩阵，称这样的对策为对称对策，则(1)vG=0(2)T1(G)=T2(G)其中T1(G)和T2(G)分别为局中人和的最优策略集,定理7和8可以用来简化矩阵中的元素数字，使得以后的求解更为方便。,-,34,矩阵对策的解法,1优超原则法,设有矩阵对策G=S1,S2;A,其中:A=aijmn,如果对一切j=1,n,都有即矩阵的第行元素均不小于行的元素，则称局中人的纯策略优超于纯策略；同样，若对于一切i=1,m,有，即矩阵的第列均不大于列的元素，则称局中人的纯策略优超于纯策略,-,35,当局中人的纯策略优超于纯策略时，局中人采用策略超过采用策略；当称局中人的纯策略优超于纯策时，局中人采用纯策略超过采用纯策略。在求解矩阵对策时，如果出现上述优超情况，可将矩阵A的第行删除；当的纯策略优超于纯策时，可以将矩阵A第列删除。优超原则可以缩小了A的规模，使计算简化。一般情况下，优超原理只是一种降阶技术，但如精简之后，A中的剩余元素仅有一个，则意味着已求得了对策的鞍点。,-,36,例9求解矩阵对策，其中：,解查视各列，发现可划去第1列，得,查视各行，发现可划去第3行，得,查视各行列，知已无法继续优超，故原矩阵A被简化为22规模。,-,37,二、22公式解法,设矩阵对策中的A为,若无鞍点，则X*与Y*中各分量必不为零(否则，假定，则，局中人选择纯策略1，局中人选择中最小元素对应的策略，即对策存在有鞍点)。由定理6的(3)、(4)，得,-,38,二、22公式解法,求解后，得：,(11),-,39,用22求解例5已知矩阵对策G,其中：,解G是不存在鞍点,用22求解例9,-,40,求解例7已知矩阵对策G,其中：,解利用优超原理得,用公式计算得：,矩阵对策的解：X*=(0，1/3,2/3，0)T,Y*=(1/3,2/3)TvG=53,-,41,三、2n和m2图解法,当对策双方中的某一方策略个数为2，而另一方策略个数大于2时，可以采用图解法来方便地求解这类对策问题。下面通过例子来介绍这种直观的几何方法。,用一个例子来看解法例10求解矩阵对策，其中:,解显然，G无鞍点且无优超关系。,设局中人的混合策略为X=(x1,x2)T=(x,1x)T，则按“理智行为”，期望的赢得为,1.考虑2n阶矩阵,-,42,在Oxv平面直角坐标系中，x0,1画直线段（图10-1）：,L1：v=-8x+9L2：v=7xL3：v=15x-2,-,43,于是，v=f(x)的图形就是折线CDEF。因为E点是折线的最高点，所以v=f(x*)。注意到E点是L1与L2的交点，求解,得x*=35，vG=215，的最优混合策略为X*=(3/5,2/5)T。,设局中人的最优混合策略为Y*=(y1*，y2*，y3*)T，则由定理6知,-,44,根据定理6得y3*=0。也可根据E点只与L1、L2有关且此处L3高于E点，即只与1,2有关且3不必考虑,所以,y3*=0，代入上式，可解得y1*=715，y2*=815。于是，的最优混合策略为Y*=(7/15,8/15,0)T。矩阵对策的解X*=(3/5,2/5)T,Y*=(7/15,8/15,0)TvG=215,注意：,-,45,例11求解矩阵对策，其中:,解显然，G无鞍点使用优超原理，1优超4，删去第4行，将A简化为,设局中人的混合策略为Y=(y1,y2)T=(y,1y)T，则按“理智行为”，期望的赢得为,2.考虑m2阶矩阵,-,46,在Oxv平面直角坐标系中，y0,1画直线段（图10-2）：,L1：v=6y5L2：v=8y4L3：v=5y3,v=g(y)的图形就是折线CDEF。因为E点是折线的最低点，所以v=g(y*)。注意到E点是L1与L3的交点，求解,-,47,求解,得y*=811，v=711，的最优混合策略为Y*=(8/11,3/11)T。,设局中人的最优混合策略为:X*=(x1*，x2*，x3*，0)T，y1*0,y2*0则由定理6知,-,48,矩阵对策的解：X*=(5/11,0,6/11,0)T，Y*=(8/11,3/11)T。vG=711,根据定理6得x2*=0。也可根据由于E点只与L1、L3相关,且此处L2低于E点，即只与1、3相关且2不必考虑，所以x2*=0，代入上式，可解得x1*=511，x3*=611。于是，的最优混合策略为X*=(5/11,0,6/11,0)T。,-,49,四、线性规划解法(最通用、应用最广的方法),对于前述各种方法全都失效的一般形式的矩阵对策，线性规划解法是最通用的方法，可以求解任一矩阵对策。由定理5知，求解矩阵对策可等价地转化为求解互为对偶的线性规划（P）和（D），故在问题（P）中，令。,则问题(P)的约束条件变为：,问题(P)等价与线性规划问题(),(12),乘以A第j列,-,50,四、线性规划解法(最通用、应用最广的方法),同理在问题（D）中，令,可知问题(D)等价于线性规划问题(),(13),问题()和()是互为对偶的线性规划，可用单纯形或对偶单纯形法求解，再由变换(12)和(13)，即可得到原问题的解和对策值,A第i行列乘以,-,51,例12求解矩阵对策，其中：,解易知，G无鞍点且无法优超。求解问题可化成线性规划问题,迭代后，得规划最优解：=(1/14,11/196,5/49)T，对偶规划最优解=(5/49,11/196,1/14)T，最优值z*=45196，vG=1z*=19645，X*=v=(20/45,11/45,14/45)TY*=v=(14/45,11/45,20/45)T,-,52,例：求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解，可求其混合策略。A中有负元素，可以取k=2,在A的每个元素上加2得到A如下：,4矩阵对策的混合策略,-,53,建立对G=S1，S2，A中求甲方最佳策略的线性规划如下：Minx1+x2+x3+x4+x5+x6s.t.5x1+3x2+3x3+x4+3x5+3x613x1+5x2+x3+3x4+3x5+3x613x1+3x2+5x3+3x4+3x5+x613x1+3x2+3x3+5x4+x5+3x61x1+3x2+3x3+3x4+5x5+3x613x1+x2+3x3+3x4+3x5+5x61xi0,i=1,2,6可解得解为：x1=x4=x5=0,x2=x3=x6=0.111,v=3,x1=x4=x5=0，x2=vx2=x3=x6=1/3,即X*=(0,1/3,1/3,0,0,1/3)T，所以甲的最优策略为作出策略2、3、6的概率都为0.333,而作出1、4、5的概率为0，此时VG=V2=1。,-,54,同样可以建立对策G=S1，S2，A中求乙方最佳策略的线性规划如下：Miny1+y2+y3+y4+y5+y6约束条件：5y1+3y2+3y3+3y4+y5+3y613y1+5y2+3y3+3y4+3y5+y613y1+y2+5y3+3y4+3y5+3y61y1+3y2+3y3+5y4+3y5+3y613y1+3y2+3y3+y4+5y5+3y613y1+3y2+y3+3y4+3y5+5y61yi0,i=1,2,6可解得解为：y1=y4=y5=0.111,y2=y3=y6=0,v=3,y1=y4=y5=1/3，y2=y3=y6=0，即Y*=(1/3,0,0,1/3,1/3,0)T。所以田忌的最优混合策略为作出策略1、4、5的概率都为1/3,而作出2，3，6的概率为0，此时VG=VG-k=1。,4矩阵对策的混合策略,-,55,齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3,0,0,1/3)T，Y*=(1/3,0,0,1/3,1/3,0)T，对策值VG=1。例两个局中人进行对策，规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。解：首先计算局中人甲的赢得矩阵如下表：,4-56,-34-5,2-34,1（出1）2（出2）3（出3）,3（出3）,2（出2）,1（出1）,甲的赢得甲的策略,乙的策略,-,56,即甲的赢得矩阵为A：可知无纯策略意义的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立线性规划模型如下：Minx1+x2+x3Maxy1+y2+y3S.T.8x1+3x2+10 x318y1+3y2+10y313x1+10 x2+x313y1+10y2+y3110 x1+x2+12x3110y1+y2+12y31x1,x2,x30y1,y2,y30,4矩阵对策的混合策略,-,57,得到x1=0.25,x2=0.50,x3=0.25；y1=0.25,y2=0.50,y3=0.25。即此对策的解为X*=(0.25,0.50,0.25)T，Y*=(0.25,0.50,0.25)T。VG=VG-k=0。,4矩阵对策的混合策略,-,58,例4甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有:(1)降低产品价格；(2)提高产品质量；(3)推出新产品。乙企业考虑采取的策略措施有(1)增加广告费用；(2)增设维修网点，加强售后服务；(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。,3-58,-6510,108-12,1（措施1）2（措施2）3（措施3）,3（措施3）,2（措施2）,1（措施1）,4矩阵对策的混合策略,甲的赢得甲的策略,乙的策略,-,59,解：易知此对策无纯策略意义下的解。把A的每一个元素加上12，得到A建立线性规划模型如下：Minx1+x2+x3Maxy1+y2+y3S.T.22x1+20 x2122y1+6y2+15y316x1+17x2+22x3120y1+17y2+7y3115x1+7x2+20 x3122y2+20y31x1,x2,x30y1,y2,y30得到：x1=0.027,x2=0.020,x3=0.023；y1=0.0225,y2=0.0225,y3=0.025。V=14.29。x1=0.3858,x2=0.2858,x3=0.3286；y1=0.3215,y2=0.3215,y3=0.3572。即此对策的解为X*=(0.3858,0.2858,0.3286)T,Y*=(0.3215,0.3215,0.3572)T。VG=VG-k=2.29。,4矩阵对策的混合策略,-,60,5其他类型的对策论简介,在对策论中可以根据不同方式对对策问题进行分类，通常分类的方式有（1）根据局中人的个数，分为二人对策和多人对策；（2）根据各局中人的赢得函数的代数和是否为零，可分为零和对策和非零和对策；（3）根据局中人是否合作，又可分为合作对策和非合作对策；（4）根据局中人的策略集中个数，又分为有限对策和无限对策（或连续对策）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策。本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。,-,61,5其他类型的对策论简介,一、完全信息静态对策该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为纳什均衡。下面以著名的“囚徒困境”来进一步阐述。例1“囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来判决。如图1-1所示。,-,62,5其他类型的对策论简介,图1-1囚徒困境,由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，(坦白，坦白)就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成协议。囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。,-,63,5其他类型的对策论简介,二、完全信息动态对策在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。例2某行业中只有一个垄断企业A，有一个潜在进入者企业B。B可以选择进入或不进入该行业这两种行动，而A当B进入时，可以选择默认或者报复两种行动。如果B进入后A企业报复，将造成两败俱伤的结果，但如果A默认B进入，必然对A的收益造成损失。同样的，如果B进入而A报复，则B受损，反之，将受益。把此关系用图1-2表示。,-,64,5其他类型的对策论简介,由分析可知，上例中（B选择不进入，A选择报复）和（B选择进入，A选择默许）都是纳什均衡解。但在实际中，（B选择不进入，A选择报复）这种情况是不可能出现的。因为B知道他如果进入，A只能默许，所以只有（B选择进入，A选择默许）会发生。或者说，A选择报复行动是不可置信的威胁。对策论的术语中，称（A选择默许，B选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为精炼纳什均衡。当然，如果A下定决心一定要报复B，即使自己暂时损失。这时威胁就变成了可置信的，B就会选择不进入，（B选择不进入，A选择报复）就成为精炼纳什均衡。军事交战时，“破釜沉舟”讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。,-,65,5其他类型的对策论简介,三、多人非合作对策有三个或三个以上对策方参加的对策就是“多人对策”。多人对策同样也是对策方在意识到其他对策方的存在，意识到其他对策方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人对策同样的思路和方法来研究它们，或将两人对策的结论推广到多人对策。不过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，因此，策略的相互依存关系也就更为复杂，对任一对策方的决策引起的反应也就要比两人对策复杂得多。并且，在多人对策中还有一个与两人对策有本质区别的特点，即可能存在“破坏者”。所谓破坏者即一个对策中具有下列特征的对策方：其策略选择对自身的得益没有任何影响，但却会影响其它对策方的得益，有时这种影响甚至有决定性的作用。例如有三个城市争夺某届奥运会的主办权。,-,66,5其他类型的对策论简介,多人对策可以分为合作