第十二章 对策论(运筹学讲义)

1、第十章 对策论 由“齐王赛马”引入1 1 对策论的例子2 2矩阵矩阵对策论的基本概念3 3 矩阵对策的最优纯策略矩阵对策的最优纯策略4 4矩阵对策的混合策略矩阵对策的混合策略5 5 其他类型的对策其他类型的对策对策论或博弈论(Game Theory) 是研究具有对抗和竞争性行为问题的数学理论与方法。是运筹学的重要分支学科经济学领域一般称博弈论，是经济学领域近几十年发展起来一门新兴学科对策论从理论上作严格的讨论却起始于二十世纪：1912年，德国数学家E.Zermelo证明了国际象棋的3种着法必定存在一种；1921年，法国数学家E.Borel引入了“最优策略”等概念；1928年，美籍匈牙利人J.V

2、on Neumann证明了对策论的基本定理-最大值最小值定理；1944年，Von Neumann和O.Morgenstern合写了对策论与经济行为一书，建立起对策论的基本理论，奠定了对策论研究的基础。对策问题举例例例1 1 猜单和猜双的博弈。两个人同时出一个指头或两个指头，猜单和猜双的博弈。两个人同时出一个指头或两个指头，如果两人出的指头相同，则局中人如果两人出的指头相同，则局中人1 1从局中人从局中人2 2处赢得五元；处赢得五元；如果出的不一样，局中人如果出的不一样，局中人1 1就要支付给局中人就要支付给局中人2 2五元。两个五元。两个对手都可以采取两个策略：出一个手指和出两个手指，下对手都

3、可以采取两个策略：出一个手指和出两个手指，下表是局中人表是局中人1 1的赢得矩阵的赢得矩阵( (二指莫拉问题二指莫拉问题) )策 略局中人2出1指出2指局中人1出1指55出2指55局中人局中人1 1从局中人从局中人2 2该如何选择策略，已获得利益？该如何选择策略，已获得利益？例例2 2 囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在不同的屋子里审讯。警察告诉他们：如果两人都坦白，各不同的屋子里审讯。警察告诉他们：如果两人都坦白，各判刑判刑8 8年；如果两人都抵赖，由于证据不充分，两人将各年；如果两人都抵赖，由于证据不充分，两人将各判刑判刑2 2

4、年；如果其中一人坦白，另一人抵赖，则坦白者年；如果其中一人坦白，另一人抵赖，则坦白者立即释放，抵赖者判刑立即释放，抵赖者判刑1010年。在这个例子中两人嫌疑犯都年。在这个例子中两人嫌疑犯都有两种策略：坦白或抵赖。可以用一个矩阵表示两个嫌疑有两种策略：坦白或抵赖。可以用一个矩阵表示两个嫌疑犯的策略的损益犯的策略的损益策 略囚徒2坦白抵赖囚徒1坦白(8, 8)(0, 10)抵赖(10, 0)(2, 2)囚徒该如何选择策略？囚徒该如何选择策略？囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒

5、都是理性人，他们追求自身效应的最的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性例3 田忌与齐王赛马 战国时期，齐威王与大将田忌赛马，双方约定：从各战国时期，齐威王与大将田忌赛马，双方约定：从各自的自的上、中、下三个等级上、中、下三个等级的马中各选一匹马出场比赛，负者的马中各选一匹马出场比赛，负者要付给胜者一千金。已知田忌的马要比齐王同一等级的马差要付给胜者一千金。已知田忌的马要比齐王同一等级的马差一些，但比齐王等级较低的马却要强一些。因此，如用同等一些，但比齐王等

6、级较低的马却要强一些。因此，如用同等级的马对抗，田忌必连输三场，失三千金无疑。田忌的谋士级的马对抗，田忌必连输三场，失三千金无疑。田忌的谋士孙膑给田忌出了个主意：每局比赛前先了解齐王参赛马的等孙膑给田忌出了个主意：每局比赛前先了解齐王参赛马的等级，再采用级，再采用下等马对齐王上等马下等马对齐王上等马、中等马对齐王下等马中等马对齐王下等马、上上等马对齐王中等马等马对齐王中等马的策略。比赛结果，田忌二胜一负，反而的策略。比赛结果，田忌二胜一负，反而赢得一千金。由此可见，双方各采取什么样的出马次序对胜赢得一千金。由此可见，双方各采取什么样的出马次序对胜负至关重要。负至关重要。“齐王赛马齐王赛马”齐王

7、在各局势中的益损值表齐王在各局势中的益损值表(单位：千金单位：千金)齐王和田忌可以任意选择三匹马出场的顺序齐王和田忌可以任意选择三匹马出场的顺序1 1对策论的基本概念对策模型的三个基本要素：对策模型的三个基本要素：1.1.局中人局中人( (Players) )：参与对抗的各方；：参与对抗的各方；2.2.策略集策略集(Strategices):(Strategices):局中人选择对付其它局中人的行动局中人选择对付其它局中人的行动方案称为方案称为策略策略；某局中人的所有可能策略全体称为；某局中人的所有可能策略全体称为策略集策略集3.3.一局势对策的益损值：局中人各自使用一个对策就形成了一局势对策

8、的益损值：局中人各自使用一个对策就形成了一个局势一个局势，一个局势决定了各局中人的对策结果（量化），一个局势决定了各局中人的对策结果（量化）称为该局势对策的称为该局势对策的益损值益损值。 赢得函数赢得函数(payoff function)(payoff function)：定义在局势上，取值为相应：定义在局势上，取值为相应益损值的函数益损值的函数4. 纳什均衡：纳什均衡：纳什均衡指所有局中人最优策略组成的一种局纳什均衡指所有局中人最优策略组成的一种局势，既在给定其他局中人策略的情况下，没有任何局中人势，既在给定其他局中人策略的情况下，没有任何局中人有积极性去选择其他策略有积极性去选择其他策略对

9、策的分类对策按对策方式合作对策非合作对策完全理性有限理性两人对策零和对策非零和对策多人对策结盟对策不结盟对策按对策人数静态对策完全信息静态对策不完全信息静态对策动态对策完全信息动态对策不完全信息动态对策按对策状态二人有限零和对策二人有限零和对策（又称（又称矩阵对策矩阵对策）：）： 局中人为局中人为2 2；每个局中人的策略集的策略数目都是有限的；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。局中人的益损值之和为零。 通常将矩阵对策记为通常将矩阵对策记为: : G = S1,

10、S2, A局中人甲的策略集：局中人甲的策略集： 局中人乙的策略集：局中人乙的策略集：甲的赢得矩阵：甲的赢得矩阵： 矩阵对策矩阵对策112,mS212,nS111212122212mmmmmnaaaaaaAaaaaij为局中人甲在局势 下的赢得(,)ij其中：齐王的策略集其中：齐王的策略集: : S1= 1, 2, 3, 4, 5, 6 ， 田忌的策略集：田忌的策略集： S2= 1, 2, 3, 4, 5, 6 。下面矩阵称齐王的下面矩阵称齐王的赢得矩阵赢得矩阵： 3 1 1 1 -1 1 1 3 1 1 1 -1 A= 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 1 -1 3

11、1 1 1 -1 1 1 3 “齐王赛马齐王赛马”是一个矩阵策略。是一个矩阵策略。2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略例4 甲、乙两队进行球赛，双方各可排出三种不同的阵容。设甲队为局中人，乙队为局中人，每一种阵容为一个策略，有S1 =1 , 2 , 3，S2 =1 , 2 , 3。根据 以往两队比赛的记录，甲队得分情况的赢得矩阵为415306213A问：这次比赛中，双方应 如何对阵？在如此反复对策的过程中，各局中人如果不想冒险，就应该考虑从自身可能出现的最坏情况下着眼，去选择一种尽可能好的结果，即双方都是从各自可能出现的最不利即双方都是从各自可能出现的最不利的情形选择一种最为有利的

12、情况作为决策的依据。的情形选择一种最为有利的情况作为决策的依据。这就是所谓“理智行为理智行为”。称为最小最大准则最小最大准则，按照这个各方均避免冒险的观念，就形成如下的推演过程推演过程。415306213A解 从A中可以看出，最多可得6分。于是，为得6分而选2 。但是推测会有此心理，从而选3来对付，使得非但得不到6分，反而要失去3分。当然也会料到会有此心理，从而改选3 ，以使欲得3分而反失4分。矩阵矩阵A中每行的最小元素分别为中每行的最小元素分别为1，-3，-5。 在这些最少赢得中最好的结果是在这些最少赢得中最好的结果是1 1，故，故局中人局中人会采取会采取策略策略 1 1，无论对手采取何策略

13、，无论对手采取何策略，局中人局中人至少得至少得1 1分。对于分。对于局中人局中人， 1 1， 2 2， 3 3 可能带来的最少赢得，即可能带来的最少赢得，即A中每列的中每列的最大元素，分别为最大元素，分别为6，1，4。局中人局中人会采取会采取 2 2策略，确保策略，确保局局中人中人不会超过不会超过1 1分分。 1 1和和 2 2分别称为局中人分别称为局中人、 的最优策略。由于双方必的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。然选择这一种策略，所以，这种策略又称为最优纯策略。2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略326035141AMin1356Max14

14、1 2 3 1 2 3定义定义1 1 设有矩阵对策设有矩阵对策G =S1, S2 ; A, 其中，其中， A = ai j mn ，若有若有vaaajiijijijji*maxminminmax则局势则局势 (i* ，j*) 称为G在在纯策略意义下的解纯策略意义下的解，也称，也称为为G的的鞍点鞍点；i* 、j*分别称为局中人分别称为局中人和和的的最最优纯策略优纯策略；v称为称为G的值，也称的值，也称对策值对策值。 对于例对于例4，G的解的解(鞍点鞍点)为为 (1 ,2 )，1 、2分别为分别为、的最优策略。对策值的最优策略。对策值v = 1 0，反映优势在反映优势在方方(对对有利有利)；若；若

15、v 0,为任一常数。则为任一常数。则 (1) (2) T(G1) = T(G2) 21GGvv定理定理9 设设G S1, S2; A为一矩阵对策，且为一矩阵对策，且A=AT为斜对称为斜对称矩阵，称这样的对策为对称对策，则矩阵，称这样的对策为对称对策，则 (1) vG =0 (2) T1 (G) = T2 (G) 其中其中T1 (G) 和和 T2 (G) 分别为局中人分别为局中人和和的最优策略集的最优策略集定理定理7和和8可以可以用来简化矩阵中的元素数字，使得以后的求解用来简化矩阵中的元素数字，使得以后的求解更为方便。更为方便。n矩阵对策的解法矩阵对策的解法 1优超原则法优超原则法 设有矩阵对策

16、设有矩阵对策G=S1, S2 ; A, 其中其中: A = ai j mn ,如果对一切如果对一切j =1,n,都有都有 即矩阵的第即矩阵的第 行元素均不小于行元素均不小于 行的元素，则行的元素，则称局中人称局中人的纯策略的纯策略 优超于纯策略优超于纯策略 ；同样，若对于；同样，若对于一切一切i =1,m,有有 ，即矩阵的第即矩阵的第 列均不大于列均不大于 列的元素，则称局中人列的元素，则称局中人的纯策略的纯策略 优超于纯策略优超于纯策略 112,mS212,nS00ijkjaa0i0k0i0k00i jikaa0j0k0j0k当局中人当局中人的纯策略的纯策略 优超于纯策略优超于纯策略 时，局

17、中人时，局中人采用采用策略策略 超过采用策略超过采用策略 ；当称局中人；当称局中人的纯策略的纯策略 优优超于纯策超于纯策 时，局中人时，局中人采用纯策略采用纯策略 超过采用纯策略超过采用纯策略 。在求解矩阵对策时，如果出现上述优超情况，可将矩。在求解矩阵对策时，如果出现上述优超情况，可将矩阵阵A的第的第 行删除；当行删除；当的纯策略的纯策略 优超于纯策优超于纯策 时，时，可以将矩阵可以将矩阵A第第 列删除。列删除。优超原则可以优超原则可以缩小了缩小了A A的规模的规模，使计算简化。一般情况下，优，使计算简化。一般情况下，优超原理只是一种超原理只是一种降阶技术降阶技术，但如精简之后，但如精简之后

18、，A A中的剩余元素中的剩余元素仅有一个，则意味着已求得了对策的鞍点仅有一个，则意味着已求得了对策的鞍点。0i0k0j0k0i0k0k0j0k0j0k0k 例例9 9 求解矩阵对策，其中：求解矩阵对策，其中：586510126110A585106151061解解 查视各列，发现可划去第查视各列，发现可划去第1 1列，列，得得查视各行，发现可划去第查视各行，发现可划去第3 3行，得行，得查视各行列，知已无法继续优超，查视各行列，知已无法继续优超，故原矩阵故原矩阵A A被简化为被简化为22规模规模。 二、二、2 22 2公式解法公式解法设矩阵对策中的设矩阵对策中的A A为为11122122aaAa

19、a1*2*1*222*112*221*111xxvxaxavxaxa1*2*1*222*121*212*111yyvyayavyaya若无鞍点，则若无鞍点，则X*与与Y*中各分量必不为零中各分量必不为零 ( (否则，假定否则，假定 ，则则 ，局中人，局中人选择纯策略选择纯策略1 1，局中人，局中人选择选择 中最小元素对应的策略，即对策存在有鞍点中最小元素对应的策略，即对策存在有鞍点) )。由定理由定理6 6的的(3)、(4)，得，得*10 x *21x2122,aa二、二、2 22 2公式解法公式解法*2221111221221*11122111221221*2212111221221*112

20、121112212211122122111221221 ,1 ,1 Gaaxaaaaaaxxaaaaaayaaaaaayyaaaaa aaavvaaaa求解后，得：求解后，得：(11)1342A用用2 22 2求解例求解例5 5 已知矩阵对策已知矩阵对策G, ,其中：其中：解解 G是不存在鞍点是不存在鞍点*1*2*1*22421,12344213112342231,1234414312344212105.123442Gxxyyv 用用2 22 2求解例求解例9 9*12231571111552222222222Gxxyyv，；，；5002.5A 求解例求解例7 7 已知矩阵对策已知矩阵对策G,

21、 ,其中：其中：解解 利用优超原理得利用优超原理得*1*21*1*212.50152.50032132.50152.500321352.512.55.52.5007.53Gxxxyyyv555002.507.5A用公式计算用公式计算得：得：矩阵对策的解矩阵对策的解 ：X* = (0，1/3, 2/3，0) T , Y* = (1/3, 2/3) T vG = 53三、三、2 2n n和和m m2 2图解法图解法 当对策双方中的当对策双方中的某一方策略个数为某一方策略个数为2 2，而另一方策略个，而另一方策略个数大于数大于2 2时，可以采用图解法来方便地求解这类对策问题。时，可以采用图解法来方便

22、地求解这类对策问题。下面通过例子来介绍这种直观的几何方法。下面通过例子来介绍这种直观的几何方法。1713902A用一个例子来看解法用一个例子来看解法例例10 10 求解矩阵对策，其中求解矩阵对策，其中: :解解 显然，显然，G G无鞍点且无优超关系。无鞍点且无优超关系。设局中人设局中人的混合策略为的混合策略为X = (x1 , x2 )T = (x , 1x ) T，则按则按“理智行为理智行为”，期望的赢得为期望的赢得为1.1.考虑考虑2n 阶矩阵阶矩阵1112121222nnaaaAaaa*21101max min,max min(, )jxYSXSvEX YE Xj 1T121222(,

23、)( ,1- )(1)()jjjjjjjaE X jxxa xaxaaxaa1010101max min9 1,7 ,132 1max min89, 7 ,152max ( )xxxvxxxxxxxxfx在在Oxv平面直角坐标系中，平面直角坐标系中，x0, 1 画直线段（图画直线段（图10-110-1）：）：L1 ： v = -8x + 9L2 ： v = 7xL3 ： v = 15x - 2图图10-110-1xvO2468101Cx*DEFL1L2L3于是，v = f (x) 的图形就是折线CDEF。因为E点是折线的最高点，所以v = f (x*)。注意到E点是L1与L2的交点，求解xvx

24、v798得x*= 35 ，vG = 215 ，的最优混合策略为X* = (3/5, 2/5)T。图图10-110-1xvO2468101Cx*DEFL1L2L3设局中人的最优混合策略为Y* = (y1*，y2*，y3*)T，则由定理6知*123*1321(1,)713521(2,)925EYyyyEYyy图图10-110-1xvO2468101Cx*DEFL1L2L3*123*1321(1,)713521(2,)925EYyyyEYyy根据定理根据定理6 6 得得y3*=0=0。也可根据。也可根据E点只与点只与L L1 1、L L2 2有关且此处有关且此处L L3 3高高于于E E点，即只与点

25、，即只与1 1, ,2 2有关且有关且3 3不必考虑不必考虑, ,所以所以, ,y3*= 0 = 0 ，代入上式，可解得代入上式，可解得 y1* = 715，y2* = 815。于是，于是，的最优混合策略为的最优混合策略为 Y* = = (7/15, 8/15, 0) T。 矩阵对策的解矩阵对策的解 X* = = (3/5, 2/5) T , Y* = = (7/15, 8/15, 0) T vG = 215注意：注意：*21(,1)(,2)5321(,3)152755E XE XE X例例11 11 求解矩阵对策，其中求解矩阵对策，其中: :解解 显然，显然，G G无鞍点使用优超原理，无鞍点

26、使用优超原理，1 1优超优超4 4，删去第删去第4 4行，将行，将A A简化为简化为设局中人设局中人的混合策略为的混合策略为Y = (y1 , y2 )T = (y , 1y ) T，则按则按“理智行为理智行为”， 期望的赢得为期望的赢得为2.2.考虑考虑m2阶矩阵阶矩阵111221221mmaaaaAaa15442305A154423A*212011220101min max,min max( ,) min max()min( )yiYSXSiiiyyivEX YE i Yaayag y在在Oxv平面直角坐标系中，平面直角坐标系中，y0, 1 画直线段（图画直线段（图10-210-2）：）：

27、L1 ： v = 6y5L2 ： v = 8y4L3 ： v = 5y 3( )max65,84,53g yyyy图图10-2yvO2461Fy*DECL1L2L342v = g (y) 的图形就是折线CDEF。因为E点是折线的最低点，所以 v = g (y*)。注意到E点是L1与L3的交点，求解图图10-2yvO2461Fy*DECL1L2L342求解求解3556yvyv得得 y*= 811，v = 711，的最优混合策略为的最优混合策略为Y* = (8/11, 3/11)T。*123*1237(,1)42117(,2)54311E XxxxE Xxxx 设局中人设局中人的最优混合策略为的最

28、优混合策略为:X* = (x1*，x2*，x3*，0 )T， y1*0 , y2*0 则由定理则由定理6 6知知 图图10-2yvO2461Fy*DECL1L2L342矩阵对策的解：矩阵对策的解： X* = (5/11, 0, 6/11, 0) T ，Y* = (8/11, 3/11)T。v G= 711根据定理根据定理6 6 得得x2*=0=0。也可根。也可根据据由由于于E点只与点只与L1、L3相关相关, ,且此处且此处L2低于低于E E点，即只与点，即只与1 1、3 3相相关且关且2 2不必考虑，所以不必考虑，所以x2* = 0，代入上式，可解得代入上式，可解得x1* = 511，x3*

29、= 611。于是，于是，的最优混合策略为的最优混合策略为X* = (5/11, 0, 6/11, 0) T。*21832072,4411111111jnjjEYa y 四、线性规划解法 (最通用、应用最广的方法)1,2,iixximw对于前述各种方法全都对于前述各种方法全都失效失效的一般形式的矩阵对策，线性规划的一般形式的矩阵对策，线性规划解法是最通用的方法，可以求解任一矩阵对策。解法是最通用的方法，可以求解任一矩阵对策。由定理由定理5 5知，求解矩阵对策可等价地转化为求解互为对偶的线性知，求解矩阵对策可等价地转化为求解互为对偶的线性规划规划（P）和和（D），故在问题（），故在问题（P）中，令

30、）中，令。则问题则问题(P)的约束条件变为的约束条件变为：111,1,2,1 0,1,2,mijiimiiia xjnxwxim 问题问题(P)等价与线性规划问题等价与线性规划问题( )P11min (P )1,1,2,0,1,2,miimijiiixa xjnxim (12) 乘以A第j列X 四、线性规划解法 (最通用、应用最广的方法)1,2,jjyyjmv同理在问题（同理在问题（D）中，令）中，令可知问题可知问题(D)等价于等价于线性规划问题线性规划问题( )D11max (D )1,1,2,0,1,2,mjimijjjijya yimyjn (13) 问题问题( ) 和和( ) 是是互为

31、对偶的线性规划，互为对偶的线性规划，可用单纯形或对可用单纯形或对偶单纯形法求解，再由变换偶单纯形法求解，再由变换(12)和和(13)，即可得到原问题的解，即可得到原问题的解和对策值和对策值DP A第i行列乘以Y例例12 求解矩阵对策，其中：求解矩阵对策，其中：821482248A123123123123123max. 8421 2841 281 ,0zyyys tyyyyyyyyyyyy解解 易知，易知，G无鞍点且无法优超。求解问题无鞍点且无法优超。求解问题可化成线性规划问题可化成线性规划问题迭代后，得规划最优解：迭代后，得规划最优解： = (1/14, 11/196, 5/49)T，对偶规划

32、最优解对偶规划最优解 = (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*Y*X*X*Y例：求解例：求解“齐王赛马齐王赛马”问题。问题。已知齐王的赢得矩阵已知齐王的赢得矩阵A A求得求得故不存在纯策略问题下的解，可求其混合策略。故不存在纯策略问题下的解，可求其混合策略。A A中有负元素，可以取中有负元素，可以取k=2,k=2,在在A A的每个元素上加的每个元素上加2 2得到得到AA如下：如下：311111

33、131111113111111311111131111113A3maxmin1minmaxijijijjiaa533133351333335331333513133353313335A4 4矩阵对策的混合策略矩阵对策的混合策略 建立对建立对G=S1，S2，A中求甲方最佳策略的线性规划如下：中求甲方最佳策略的线性规划如下： Min x1+x2+x3+x4+x5+x6 s.t. 5x1+3x2+3x3+x4+3x5+3x6 1 3x1+5x2+x3+3x4+3x5+3x6 1 3x1+3x2+5x3+3x4+3x5+x6 1 3x1+3x2+3x3+5x4+x5+3x6 1 x1+3x2+3x3+

34、3x4+5x5+3x6 1 3x1+x2+3x3+3x4+3x5+5x6 1 xi 0, 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。 同样可以建立对策同样可以建立对策G=S1，S2，A中求乙方最佳策略的线性规划如下：中求乙方最佳策略的线性规

35、划如下： Min y1+y2+y3+y4+y5+y6 约束条件：约束条件： 5y1+3y2+3y3+3y4+y5+3y6 1 3y1+5y2+3y3+3y4+3y5+y6 1 3y1+y2+5y3+3y4+3y5+3y6 1 y1+3y2+3y3+5y4+3y5+3y6 1 3y1+3y2+3y3+y4+5y5+3y6 1 3y1+3y2+y3+3y4+3y5+5y6 1 yi0,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。

36、 所以田忌的最优混合策略为作出策略所以田忌的最优混合策略为作出策略 1、 4、 5的概率都为的概率都为1/3,而作出而作出 2， 3， 6的概率为的概率为0，此时，此时VG=VG-k=1。4 4矩阵对策的混合策略矩阵对策的混合策略 齐王赛马问题的对策最优解可简记为齐王赛马问题的对策最优解可简记为X X* *= =(0,1/3,1/3,0,0,1/3)(0,1/3,1/3,0,0,1/3)T T，Y Y* *= =(1/3,0,0,1/3,1/3,0)(1/3,0,0,1/3,1/3,0)T T，对策值，对策值V VG G=1=1。例例 两个局中人进行对策，规则是两人互相独立的各自从两个局中人进

37、行对策，规则是两人互相独立的各自从1 1、2 2、3 3这三个这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。略。 解：首先计算局中人甲的赢得矩阵如下表：解：首先计算局中人甲的赢得矩阵如下表：4-56-34-52-34 1 1（出（出1 1） 2 2（出（出2 2）

38、 3 3（出（出3 3） 3 3（出（出3 3） 2 2（出（出2 2） 1 1（出（出1 1）甲的赢甲的赢 得得甲的策略甲的策略乙的策略乙的策略即甲的赢得矩阵为即甲的赢得矩阵为A A： 可知无纯策略意义的解，下面求其在混合策略下的解。可知无纯策略意义的解，下面求其在混合策略下的解。A A的各元素都加上的各元素都加上6 6，得到，得到建立线性规划模型如下：建立线性规划模型如下： Min xMin x1 1+x+x2 2+x+x3 3 Max yMax y1 1+y+y2 2+y+y3 3 S.T.8xS.T.8x1 1+3x+3x2 2+10 x+10 x3 3 1 8y1 8y1 1+3y+

39、3y2 2+10y+10y3 311 3x 3x1 1+10 x+10 x2 2+x+x3 3 1 3y1 3y1 1+10y+10y2 2+y+y3 3 11 10 x 10 x1 1+x+x2 2+12x+12x3 3 1 10y1 10y1 1+y+y2 2+12y+12y3 311 x x1 1,x,x2 2,x,x3 3 0 y0 y1 1,y,y2 2,y,y3 3 00 654543432A1211011031038A4 4矩阵对策的混合策略矩阵对策的混合策略得到得到x x1 1=0.25, x=0.25, x2 2=0.50, x=0.50, x3 3=0.25=0.25；y

40、y1 1=0.25, y=0.25, y2 2=0.50, y=0.50, y3 3=0.25=0.25。即此对策的解为即此对策的解为X X* * =(0.25,0.50,0.25)=(0.25,0.50,0.25)T T，Y Y* * =(0.25,0.50,0.25)=(0.25,0.50,0.25)T T。V VG G=V=VG G-k=0-k=0。4 4矩阵对策的混合策略矩阵对策的混合策略例例4 4 甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有有: :(1)(1)降低产品价格；降低产品价格；(2)(2)提高产品质量；

41、提高产品质量；(3)(3)推出新产品。乙企业考虑推出新产品。乙企业考虑采取的策略措施有采取的策略措施有(1)(1)增加广告费用；增加广告费用；(2)(2)增设维修网点，加强售后服务；增设维修网点，加强售后服务；(3)(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的

42、最优策略。企业各自的最优策略。3-58-6510108-12 1 1（措施（措施1 1） 2 2（措施（措施2 2） 3 3（措施（措施3 3） 3 3（措施（措施3 3） 2 2（措施（措施2 2） 1 1（措施（措施1 1）4 4矩阵对策的混合策略矩阵对策的混合策略甲的赢甲的赢 得得甲的策略甲的策略乙的策略乙的策略解：解：易知此对策无纯策略意义下的解。把易知此对策无纯策略意义下的解。把A A的每一个元素加上的每一个元素加上1212，得到，得到A A建立线性规划模型如下：建立线性规划模型如下： Min xMin x1 1+x+x2 2+x+x3 3 Max yMax y1 1+y+y2 2+

43、y+y3 3 S.T.22xS.T.22x1 1+20 x+20 x2 21 22y1 22y1 1+6y+6y2 2+15y+15y3 3 11 6x 6x1 1+17x+17x2 2+22x+22x3 3 1 20y1 20y1 1+17y+17y2 2+7y+7y3 3 11 15x 15x1 1+7x+7x2 2+20 x+20 x3 3 1 22y1 22y2 2+20y+20y3 3 11 x x1 1,x,x2 2,x,x3 30 y0 y1 1,y,y2 2,y,y3 300得到：得到：x x1 1=0.027,x=0.027,x2 2=0.020,x=0.020,x3 3=0

44、.023=0.023；y y1 1=0.0225,y=0.0225,y2 2=0.0225,y=0.0225,y3 3=0.025=0.025。V=14.29V=14.29。x x1 1=0.3858, x=0.3858, x2 2=0.2858, x=0.2858, x3 3=0.3286=0.3286；y y1 1=0.3215,y=0.3215,y2 2=0.3215,y=0.3215,y3 3=0.3572=0.3572。即此对策的解为即此对策的解为 X X* * =(0.3858,0.2858,0.3286)=(0.3858,0.2858,0.3286)T T ,Y,Y* * =(0

45、.3215,0.3215,0.3572)=(0.3215,0.3215,0.3572)T T。V VG G=V=VG G-k=2.29-k=2.29。202207172015622A4 4矩阵对策的混合策略矩阵对策的混合策略 5 5其他类型的对策论简介其他类型的对策论简介 在对策论中可以根据不同方式对对策问题进行分类，通在对策论中可以根据不同方式对对策问题进行分类，通常分类的方式有（常分类的方式有（1）根据局中人的个数，分为二人对策和多）根据局中人的个数，分为二人对策和多人对策；（人对策；（2）根据各局中人的赢得函数的代数和是否为零，）根据各局中人的赢得函数的代数和是否为零，可分为零和对策和非

46、零和对策；（可分为零和对策和非零和对策；（3）根据局中人是否合作，）根据局中人是否合作，又可分为合作对策和非合作对策；（又可分为合作对策和非合作对策；（4）根据局中人的策略集）根据局中人的策略集中个数，又分为有限对策和无限对策（或连续对策）；（中个数，又分为有限对策和无限对策（或连续对策）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态对策、完全信息动态对策、非完全信息可分为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数静态对策及非完全信息动态对策；也可以根据对

47、策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策。凸对策、随机对策。 本节只对对策论中非合作对策的完全信息对策、多人非本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。合作对策、非零和对策作一个简单的叙述性介绍。 5 5其他类型的对策论简介其他类型的对策论简介一、完全信息静态对策一、完全信息静态对策 该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前

48、行动息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。者采取了什么行动方案。 纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为这种均衡就称为纳什均衡纳什均衡。下面以著名的。下面以著名的“囚徒困境囚徒困境”来进一步阐述。来进一步阐述。 例例1 “1 “囚徒困境囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被说的是两个囚犯的故事。这两个囚徒一起做

49、坏事，结果被警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警

50、方也明白这一点，所以他们就给了这两个囚犯一点儿警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来判决。如图都会被按照轻罪来判决。如图1-11-1所示。所示。 5 5其他类型的对策论简介其他类型的对策论简介坦白坦白抵赖抵赖轻罪，轻罪轻罪，轻罪重罪，无罪重罪，无罪重罪，无罪重罪，无罪释放

51、，释放释放，释放坦白坦白抵赖抵赖图图1-1 1-1 囚徒困境囚徒困境 由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，是固定的，( (坦白，坦白坦白，坦白) )就是纳什均衡解。而这个均衡是不会被打破的，就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成协议。即使他们在坐牢之前达成协议。 囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效抵赖）的结果是最好的，但因为每个囚徒都是理性人

52、，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。性。 5 5其他类型的对策论简介其他类型的对策论简介二、完全信息动态对策二、完全信息动态对策 在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动

53、，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。为完全信息动态对策问题。 例例2 2 某行业中只有一个垄断企业某行业中只有一个垄断企业A A，有一个潜在进入者，有一个潜在进入者企业企业B B。B B可以选可以选择进入或不进入该行业这两种行动，而择进入或不进入该行业这两种行动，而A A当当B B进入时，可以选择默认或者报复两种进入时，可以选择默认或者报复两种行动。如果行动。如果B B进入后进入后A A企业报复，将造成两败俱伤的结果，但如果企业报复，将造成两败俱伤的结果，但如果A A默认默认B B

54、进入，必进入，必然对然对A A的收益造成损失。同样的，如果的收益造成损失。同样的，如果B B进入而进入而A A报复，则报复，则B B受损，反之，将受益。受损，反之，将受益。把此关系用图把此关系用图1-21-2表示。表示。默许默许报复报复50,10050,100-20,0-20,00,2000,2000,2000,200进入进入不进入不进入图图1-2 A1-2 A、B B的行动及结果的行动及结果A AB B 5 5其他类型的对策论简介其他类型的对策论简介 由分析可知，上例中（由分析可知，上例中（B B选择不进入，选择不进入，A A选择报复）和（选择报复）和（B B选择进入，选择进入，A A选择默

55、许）都是纳什均衡解。但在实际中，（选择默许）都是纳什均衡解。但在实际中，（B B选择不进入，选择不进入，A A选择报复）这种情况是不可能出现的。因为选择报复）这种情况是不可能出现的。因为B B知道他如果进入，知道他如果进入，A A只能默许，所以只有（只能默许，所以只有（B B选择进入，选择进入，A A选择选择默许）会发生。或者说，默许）会发生。或者说，A A选择报复行动是不可置信的威胁。选择报复行动是不可置信的威胁。对策论的术语中，称（对策论的术语中，称（A A选择默许，选择默许，B B选择进入）为精炼纳什选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均均衡。当只当参与

56、人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为衡，这个纳什均衡才称为精炼纳什均衡精炼纳什均衡。 当然，如果当然，如果A A下定决心一定要报复下定决心一定要报复B B，即使自己暂时损失。，即使自己暂时损失。这时威胁就变成了可置信的，这时威胁就变成了可置信的，B B就会选择不进入，（就会选择不进入，（B B选择不选择不进入，进入，A A选择报复）就成为精炼纳什均衡。选择报复）就成为精炼纳什均衡。 军事交战时，军事交战时，“破釜沉舟破釜沉舟”讲的就是一种可置信威胁。讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。实际企业经营中也有很多类似的例子。 5 5其他类型的对策论简介其他

57、类型的对策论简介三、多人非合作对策三、多人非合作对策 有三个或三个以上对策方参加的对策就是有三个或三个以上对策方参加的对策就是“多人对策多人对策” ” 。多人对策。多人对策同样也是对策方在意识到其他对策方的存在，意识到其他对策方对自己同样也是对策方在意识到其他对策方的存在，意识到其他对策方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人它们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人对策同样的思路和方法来研究它们，或将两人对策的结论推

58、广到多人对对策同样的思路和方法来研究它们，或将两人对策的结论推广到多人对策。不过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，策。不过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，因此，策略的相互依存关系也就更为复杂，对任一对策方的决策引起的因此，策略的相互依存关系也就更为复杂，对任一对策方的决策引起的反应也就要比两人对策复杂得多。并且，在多人对策中还有一个与两人反应也就要比两人对策复杂得多。并且，在多人对策中还有一个与两人对策有本质区别的特点，即可能存在对策有本质区别的特点，即可能存在“破坏者破坏者”。所谓破坏者即一个对。所谓破坏者即一个对策中具有下列特征的对策方：其策略选择对自身的得益没有任何影响，策中具有下列特征的对策方：其策略选择对自身的得益没有任何影响，但却会影响其它对策方的得益，有时这种影响甚至有决定性的作用。例但却会影响其它对策方的得益，有时这种影响甚至有决定性的作用。例如有三个城市争夺某届奥运会的主办权。如有三个城市争夺某届奥运会的主办权。 5 5其他类型的对策论简介其他类型的对策论简介 多人对策可以分为合作的和非合作的。非合作对策顾名多人对策可以分为合作的和非合作的。非合作对策顾名思义，就是局中人之间不存在合作，即各局中人在采取行动思义，就是局中人之间不存在合作，即各局中人在采取行动之前，没有事前的交流和约定，