第三节矩阵对策课件.ppt

1、精品课程运筹学3.1 矩阵对策的数学模型矩阵对策的数学模型 3.2 矩阵对策的纯策略纳什均衡矩阵对策的纯策略纳什均衡 3.3 混合策略矩阵对策混合策略矩阵对策 3.4 矩阵对策纳什均衡存在定理矩阵对策纳什均衡存在定理 3.5 优超及矩阵对策的求解优超及矩阵对策的求解 精品课程运筹学第三节 矩阵对策 矩阵对策的研究可追朔到冯.诺依曼和摩根斯坦。矩阵对策是二人的零和对策。零和对策，是指在对策中，一方的收益必定是另一方的损失，某些对策方的赢肯定是来源于其他对策方的输,如“齐王赛马”。零和对策各对策之间的利益总是相对立,为了在对策中占据上风，不能让对手猜出自己将选择的策略。精品课程运筹学第三节 矩阵对

2、策3.1 矩阵对策的数学模型矩阵对策的数学模型 设、表示两个局中人，并设局中人有 个纯策略 ，局中人有 个纯策略 ，局中人、的策略集分别为：=局中人、所构成的策略组合共有 个，记局中人在策略()下的得益为 ，则在每个策略的赢得可用一个矩阵表示mm,21nn,211Sm,212Sn,21nmji,ija精品课程运筹学第三节 矩阵对策 称 为局中人的赢得矩阵(或为的支付矩阵)，由于对策为零和的，故局中人的赢得矩阵为-。（8.3.1)记 （8.3.2）这就是矩阵对策的基本表示。AAAmnmmnnaaaaaaaaa212222111211ASSG;,21精品课程运筹学第三节 矩阵对策例8.3.1石头、

3、剪子、布对策的矩阵表示 策略1代表出石头，策略2、3依次代表出剪子、布。=3.2 矩阵对策的纯策略纳什均衡矩阵对策的纯策略纳什均衡例8.3.2 给出下面的矩阵对策 ，其中 =，=，判断并求纯策略纳什均衡。A011101110ASSG;,211S4321,2S321,精品课程运筹学第三节 矩阵对策 矩阵为 =双方都考虑到不能去冒风险，对方会设法使它方得到最小收入，所以自己应当从最坏的情形入手，去争取最好的结果。对局中人I来说，各方案中最坏的结果：A中每一行的最小数分别是：一8，2，一10，一3。其中最好的的结果又是2。于是，局中人I出 参加对策，至少可以保证收入不会少于2；同样道理，A60310

4、194238152精品课程运筹学第三节 矩阵对策n 对局中人来说，各方案最坏的结果中最好的结果(输得最小)是2。于是，局人出 参与对策，那么它最多输2，局势(，)能使双方同时满意。定义8.3.1 在矩阵对策 中，式中 =，=，=。若等式 =(8.3.3)成立，记 ，称此为对策 的值。222ASSG;,211Sm,212Sn,21Anmija)(ijjinaixmamijijxaanmim*jia*jiGaV G精品课程运筹学第三节 矩阵对策 称使(8.3.3)成立策略组合（）为该对策的纯策略纳什均衡。一般地来说，下面不等式是成立的 (8.3.4)当两者相等时，矩阵对策有纯策略纳什均衡。例8.3

5、.3设矩阵对策 ，如下所示，求其纳什均衡。*,jiijjinaixmamijijxaanmimASSG;,21A精品课程运筹学第三节 矩阵对策 =可以看出，局中人选择方案 、局中人选择 或 是最优纯策略。从例8.3.3看出，中元素 、在该行是最小的、而在该列又是最大的。定理8.3.1矩阵对策 在纯策略定义下有纳什均衡的充要条件是：存在策略组合 A4320676813415636324A32a34aASSG;,21精品课程运筹学第三节 矩阵对策 使得对一切 均有 n （8.3.5)定义8.3.2 设 为一个定义在 及 上的实值函数，如果存在 ，使得对一切 和 ，有n (8.3.6)n则称 为函数

6、 的一个鞍点。矩阵对策的最优解有下列性质：),(*ji,1,1njmijijiijaaa*),(yxfAxByByAx*,AxBy),(*yxf),(*yxf),(*yxf),(*yxf精品课程运筹学第三节 矩阵对策（1）（无差别性）如（）与（）是对策的两个解，则（2）（可交换性）如（）与（）是对策的两个解，则（）与（）也为最优解。3.3 混合策略矩阵对策混合策略矩阵对策定义8.3.3 设有矩阵对策 ，其中 =，=，=。记11,ji22,ji2211jijiaa11,ji22,ji21,ji12,jiASSG;,211Sm,212Sn,21Anmija)(精品课程运筹学第三节 矩阵对策 =称

7、和 分别为局中人I、的混合策略集；和 ，称（）为局中人I、的混合局势，局中人I的赢得函数记为n =(8.3.7)n这样得到的新对策记为 =，称为对策 的混合扩充。*1SmiiimxmixEx11,2,1,0*2SnjjjnynjyEy11,2,1,0*1S*2Sx*1Sy*2Syx,),(yxEAyxjiijijyxa*GESS;,*2*1G精品课程运筹学第三节 矩阵对策n 纯策略是混合策略的特例，局中人以纯策略 等价于第 分量取1其余取0。定义8.3.4 设 =为 的混合扩充，如果：=(8.3.9)记其值为 ，则称 为对策 的值，称使(8.3.9)式成立的混合局势()为 在混合策略意义下的解

8、(或简称解)，和 分别称为局中人I和II的最优混合策略(或称最优策略)。kk*GESS;,*2*1ASSG;,21),(minmax*2*1yxESySx),(maxmin*1*2yxESxSyGVGV*G*,yxG*x*y精品课程运筹学第三节 矩阵对策 定理8.3.2 矩阵对策 在混合策略意义下的有解的充要条件是：存在 和 使（）为 的一个鞍点。即 (8.3.10)其中 是任意的。例8.3.4 考虑矩阵对策 ，其中 =纯策略意义下解不存在，混合策略意义下的解 ASSG;,21*x*1S*y*2S*,yx),(yxE),(*yxE),(*yxE),(*yxE*2*1,SySxASSG;,21A

9、 2341精品课程运筹学第三节 矩阵对策设 局中人I的赢得期望 =-8（+取 ，有 =则 和 分别为局中人的最优策略.1,0,),(212121*1xxxxxxS*1Sx1,0,),(212121*2yyyyyyS*2Sy),(yxEAyx)(431851yx47)8/3,8/5(*x)4/1,4/3(*y),(*yxE),(*yxE),(*yxE47)8/3,8/5(*x)4/1,4/3(*y精品课程运筹学第三节 矩阵对策 局中人I采用纯策略 而局中人II采用混合策略 ，相应赢得记为 ,有 =(8.3.11)类似的，II采用纯策略时 局中人1采用混合策略 ，相应赢得记为 ，于是 =(8.3.

10、12)定理8.3.3 设 ，则（）是对策的纳什均衡的充要条件是 对 ，有 （8.3.13)iy),(yiE),(yiEjjijyajx),(jxE),(yxEjjiijiyxaiijjijxya)(iixyiE),(*x*1S*y*2S*,yxnjmi,2,1,2,1),(*yiE),(*yxE),(*jxE精品课程运筹学第三节 矩阵对策 下面是定理8.3.3的等价形式。定理8.3.4设 ，则（）是对策 的纳什均衡的充要条件是：存在实数 ，使得 ，为下列不等式组的解 （I）(8.3.16)（II）(8.3.17)*x*1S*y*2S*,yxG*x*y01,2,1,iiiiiijxxnjxa01

11、,2,1,jjjjjijyymiya精品课程运筹学第三节 矩阵对策 此处不证明的介绍矩阵对策的基本定理:定理8.3.5 任一矩阵对策 ，一定存在混合意义下的解。下面是矩阵对策及其纳什均衡的若干性质 定理8.3.6设（）是矩阵对策 的纳什均衡，则（1）若 ，则 （2）若 ，则 ASSG;,21*,yxGGVV*ix*iyjjijya*iiijxa*VV精品课程运筹学第三节 矩阵对策（3）若 ，则 .（4）若 ，则 如果记矩阵对策 的解集为 ，则下面是关于阵对策解集的主要结果：定理8.3.7设两矩阵对策 与 ，为任意常数则（）（）jjijya*iiijxa*VV*ix*jyG)(GT1211;,A

12、SSG 2212;,ASSG ijaA 1laAij2llVVGG21)(1GT)(2GT精品课程运筹学第三节 矩阵对策定理8.3.8设两矩阵对策 与 ，为一常数则 （）（）定理8.3.9设 为矩阵对策，且 ，则（）（）式中 与 分别为局中人I、的最优策略集.1211;,ASSG ASSG;,212011GGVV)(1GT)(2GTASSG;,21 AA01GV)(1GT)(1GT)(2GT)(2GT精品课程运筹学第三节 矩阵对策3.5 优超及矩阵对策的求解优超及矩阵对策的求解定义8.3.5设有矩阵对策 ，其中=，=，=。若 对 有则称局中人I的纯策略 优于纯策略 ；同样地，若对 有 则称局中

13、人的纯策略 优于纯策略 。定理8.3.10 设有矩阵对策 ，其中 =，=，=。ASSG;,211Sm,212Sn,21Anmija)(nj,2,1jijiaa212i1imi,2,121ijijaa2j1jASSG;,211Sm,212Sn,21Anmija)(精品课程运筹学第三节 矩阵对策如果纯策略 被 中任一所优超，则可由 导出一个新矩阵对策：，式中 =，。于是有（1）（2）中局中人的最优策略与其在 中的最优策略相同。（3）当 是 中局中人I的最优策略，则 为其在中的最优解。1m,2G21;,ASSG1Sm,32nmijaA)1()(jiijaa)1(1.2.1minj,2,1GGVV G

14、G),(*3*2mxxxG),0(*3*2*mxxxx精品课程运筹学第三节 矩阵对策矩阵对策的求解方法：1.优超原则法例8.3.5矩阵对策的赢得矩阵如下，求其纳什均衡 =局中人I的策略 被 优超，将矩阵的第一行划去；局中人的策略 被 优超，划去第一列；又因为得到的3阶矩阵的元素满足第一列大于A80402434324304231313精品课程运筹学第三节 矩阵对策或等于1/2倍的2、3列之和，划去第一列，又将第一行划去得2 2矩阵 ，即求最优解 。2.和 矩阵对策的图解法8024),0,0(),0,0(5253*5154*yxn22m132图8.3.1efdoacbx1xPQAB精品课程运筹学第

15、三节 矩阵对策上面以 矩阵对策为例说明其图解法，此处 =。3.线形方程组法根据前面定理可将其转为以下方程组：与方程组非负解 ，则便得到一个纳什均衡（)；有负分量时，可视具体情况，32AfedcbaiiijijxnjVxa1,2,1,jijjjijxmiVya1,2,1,*,yx*,yx精品课程运筹学第三节 矩阵对策将某些等式变为不等式，继续直至求出其解。例8.3.6 求解“齐王赛马”的纳什均衡。解：齐王的赢得矩阵为 =由于无鞍点，对齐王和田忌来说不存在最优纯策略。解方程组得：；，。最优混合策略为双方都以16的概率选取每个纯策略，总的结局应该是：齐王有56的机会赢田忌，赢得的期望值是1千金。还有

16、开局前应对A311111131111113111111311111131111113)6,2,1(,1*ixi)6,2,1(,1*iyi1V精品课程运筹学第三节 矩阵对策自己开局前均应对自己的策略(实际上实施的纯策略)加以保密。4.线性规划解法 对矩阵对策来说，其求解可构造出一组互为对偶的线性规划问题，而这组对偶规划都有可行解，可借助线性规划方法求解。（1）与（2）01.2,1,iiiiiijxxnjVxa01,2,1,jjjjjijyymiVya精品课程运筹学第三节 矩阵对策其中 =就是对策的值。例8.3.7利用线性规划方法求解得益阵的矩阵对策的纳什均衡。解之 (0.36,0.49,0.15)(0.37,0.35,0.28）3.39),(minmax*2*1yxEVSySx),(maxmin81*2yxESxSyA1075274836*x*yV