对策论的基本概念和策略要求

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

2、大值最小值定理；1944年，Von Neumann和合写了对策论与经济行为一书，建立起对策论的基本理论，奠定了对策论研究的基础。对策论的基本概念和策略要求对策问题举例例1 猜单和猜双的博弈。两个人同时出一个指头或两个指头，如果两人出的指头相同，则局中人1从局中人2处赢得五元；如果出的不一样，局中人1就要支付给局中人2五元。两个对手都可以采取两个策略：出一个手指和出两个手指，下表是局中人1的赢得矩阵(二指莫拉问题)策 略局中人2出1指出2指局中人1出1指55出2指55局中人1从局中人2该如何选择策略，已获得利益？对策论的基本概念和策略要求例2 囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在不同

3、的屋子里审讯。警察告诉他们：如果两人都坦白，各判刑8年；如果两人都抵赖，由于证据不充分，两人将各判刑2年；如果其中一人坦白，另一人抵赖，则坦白者立即释放，抵赖者判刑10年。在这个例子中两人嫌疑犯都有两种策略：坦白或抵赖。可以用一个矩阵表示两个嫌疑犯的策略的损益策 略囚徒2坦白抵赖囚徒1坦白(8, 8)(0, 10)抵赖(10, 0)(2, 2)囚徒该如何选择策略？囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性对策论的基本概念和策略要求例3 田忌与齐王赛马 战

4、国时期，齐威王与大将田忌赛马，双方约定：从各自的上、中、下三个等级的马中各选一匹马出场比赛，负者要付给胜者一千金。已知田忌的马要比齐王同一等级的马差一些，但比齐王等级较低的马却要强一些。因此，如用同等级的马对抗，田忌必连输三场，失三千金无疑。田忌的谋士孙膑给田忌出了个主意：每局比赛前先了解齐王参赛马的等级，再采用下等马对齐王上等马、中等马对齐王下等马、上等马对齐王中等马的策略。比赛结果，田忌二胜一负，反而赢得一千金。由此可见，双方各采取什么样的出马次序对胜负至关重要。对策论的基本概念和策略要求“齐王赛马”齐王在各局势中的益损值表(单位：千金)齐王和田忌可以任意选择三匹马出场的顺序对策论的基本概

5、念和策略要求1对策论的基本概念对策模型的三个基本要素：1.局中人(Players)：参与对抗的各方；2.策略集(Strategices):局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集3.一局势对策的益损值：局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果（量化）称为该局势对策的益损值。 赢得函数(payoff function)：定义在局势上，取值为相应益损值的函数4. 纳什均衡：纳什均衡指所有局中人最优策略组成的一种局势，既在给定其他局中人策略的情况下，没有任何局中人有积极性去选择其他策略对策论的基本概念和策略要求对策的分类对策按对

6、策方式合作对策非合作对策完全理性有限理性两人对策零和对策非零和对策多人对策结盟对策不结盟对策按对策人数静态对策完全信息静态对策不完全信息静态对策动态对策完全信息动态对策不完全信息动态对策按对策状态对策论的基本概念和策略要求二人有限零和对策（又称矩阵对策）： 局中人为2；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。 通常将矩阵对策记为: G = S1, S2, A局中人甲的策略集： 局中人乙的策略集：甲的赢得矩阵： 矩阵对策aij为局中人甲在局势 下的赢得对策论的基本概念和策略要求其中：齐王的策略集: S1= 1, 2, 3

7、, 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 1 1 1 -1 1 1 3 “齐王赛马”是一个矩阵策略。对策论的基本概念和策略要求2 矩阵对策的最优纯策略例4 甲、乙两队进行球赛，双方各可排出三种不同的阵容。设甲队为局中人，乙队为局中人，每一种阵容为一个策略，有S1 =1 , 2 , 3，S2 =1 , 2 , 3。根据 以往两队比赛的记录，甲队得分情况的赢得矩阵为问：这次比赛中，双方应 如何对阵？

8、对策论的基本概念和策略要求在如此反复对策的过程中，各局中人如果不想冒险，就应该考虑从自身可能出现的最坏情况下着眼，去选择一种尽可能好的结果，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。这就是所谓“理智行为”。称为最小最大准则，按照这个各方均避免冒险的观念，就形成如下的推演过程。解 从A中可以看出，最多可得6分。于是，为得6分而选2 。但是推测会有此心理，从而选3来对付，使得非但得不到6分，反而要失去3分。当然也会料到会有此心理，从而改选3 ，以使欲得3分而反失4分。对策论的基本概念和策略要求矩阵A中每行的最小元素分别为1，-3，-5。 在这些最少赢得中最好的结果

9、是1，故局中人会采取策略1，无论对手采取何策略，局中人至少得1分。对于局中人，1，2，3可能带来的最少赢得，即A中每列的最大元素，分别为6，1，4。局中人会采取2策略，确保局中人不会超过1分。 1和2分别称为局中人、 的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。2 矩阵对策的最优纯策略Min1356Max141 2 31 23对策论的基本概念和策略要求定义1 设有矩阵对策G =S1, S2 ; A, 其中， A = ai j mn ，若有则局势 (i* ，j*) 称为G在纯策略意义下的解，也称为G的鞍点；i* 、j*分别称为局中人和的最优纯策略；v称为G的值，也称对

10、策值。 对于例4，G的解(鞍点)为 (1 ,2 )，1 、2分别为、的最优策略。对策值v = 1 0，反映优势在方(对有利)；若v 0,为任一常数。则 (1) (2) T(G1) = T(G2) 定理9 设G S1, S2; A为一矩阵对策，且A=AT为斜对称矩阵，称这样的对策为对称对策，则 (1) vG =0 (2) T1 (G) = T2 (G) 其中T1 (G) 和 T2 (G) 分别为局中人和的最优策略集定理7和8可以用来简化矩阵中的元素数字，使得以后的求解更为方便。对策论的基本概念和策略要求矩阵对策的解法 1优超原则法 设有矩阵对策G=S1, S2 ; A, 其中: A = ai j

11、 mn ,如果对一切j =1,n,都有 即矩阵的第 行元素均不小于 行的元素，则称局中人的纯策略 优超于纯策略 ；同样，若对于一切i =1,m,有 ，即矩阵的第 列均不大于 列的元素，则称局中人的纯策略 优超于纯策略 对策论的基本概念和策略要求当局中人的纯策略 优超于纯策略 时，局中人采用策略 超过采用策略 ；当称局中人的纯策略 优超于纯策 时，局中人采用纯策略 超过采用纯策略 。在求解矩阵对策时，如果出现上述优超情况，可将矩阵A的第 行删除；当的纯策略 优超于纯策 时，可以将矩阵A第 列删除。优超原则可以缩小了A的规模，使计算简化。一般情况下，优超原理只是一种降阶技术，但如精简之后，A中的剩

12、余元素仅有一个，则意味着已求得了对策的鞍点。对策论的基本概念和策略要求 例9 求解矩阵对策，其中：解 查视各列，发现可划去第1列，得查视各行，发现可划去第3行，得查视各行列，知已无法继续优超，故原矩阵A被简化为22规模。 对策论的基本概念和策略要求二、22公式解法设矩阵对策中的A为若无鞍点，则X*与Y*中各分量必不为零 (否则，假定 ，则 ，局中人选择纯策略1，局中人选择 中最小元素对应的策略，即对策存在有鞍点)。由定理6的(3)、(4)，得对策论的基本概念和策略要求二、22公式解法求解后，得：(11)对策论的基本概念和策略要求用22求解例5 已知矩阵对策G,其中：解 G是不存在鞍点用22求解

13、例9对策论的基本概念和策略要求求解例7 已知矩阵对策G,其中：解 利用优超原理得用公式计算得：矩阵对策的解 ：X* = (0，1/3, 2/3，0) T , Y* = (1/3, 2/3) T vG = 53对策论的基本概念和策略要求三、2n和m2图解法 当对策双方中的某一方策略个数为2，而另一方策略个数大于2时，可以采用图解法来方便地求解这类对策问题。下面通过例子来介绍这种直观的几何方法。用一个例子来看解法例10 求解矩阵对策，其中:解 显然，G无鞍点且无优超关系。设局中人的混合策略为X = (x1 , x2 )T = (x , 1x ) T，则按“理智行为”，期望的赢得为1.考虑2n 阶矩

14、阵对策论的基本概念和策略要求在Oxv平面直角坐标系中，x0, 1 画直线段（图10-1）：L1 ： v = -8x + 9L2 ： v = 7xL3 ： v = 15x - 2图10-1xvO2468101Cx*DEFL1L2L3对策论的基本概念和策略要求于是，v = f (x) 的图形就是折线CDEF。因为E点是折线的最高点，所以v = f (x*)。注意到E点是L1与L2的交点，求解得x*= 35 ，vG = 215 ，的最优混合策略为X* = (3/5, 2/5)T。图10-1xvO2468101Cx*DEFL1L2L3设局中人的最优混合策略为Y* = (y1*，y2*，y3*)T，则由

15、定理6知对策论的基本概念和策略要求图10-1xvO2468101Cx*DEFL1L2L3根据定理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) T vG = 215注意：对策论的基本概念和策略要求例11 求解矩阵对策，其中:解 显然，G无鞍点使用优超原理，1优超4，删去第4行，将A简化为设局中人的混合

16、策略为Y = (y1 , y2 )T = (y , 1y ) T，则按“理智行为”， 期望的赢得为2.考虑m2阶矩阵对策论的基本概念和策略要求在Oxv平面直角坐标系中，y0, 1 画直线段（图10-2）：L1 ： v = 6y5L2 ： v = 8y4L3 ： v = 5y 3图10-2yvO2461Fy*DECL1L2L342v = g (y) 的图形就是折线CDEF。因为E点是折线的最低点，所以 v = g (y*)。注意到E点是L1与L3的交点，求解对策论的基本概念和策略要求图10-2yvO2461Fy*DECL1L2L342求解得 y*= 811，v = 711，的最优混合策略为Y*

17、= (8/11, 3/11)T。设局中人的最优混合策略为:X* = (x1*，x2*，x3*，0 )T， y1*0 , y2*0 则由定理6知 对策论的基本概念和策略要求图10-2yvO2461Fy*DECL1L2L342矩阵对策的解： X* = (5/11, 0, 6/11, 0) T ，Y* = (8/11, 3/11)T。v G= 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

18、) T。对策论的基本概念和策略要求 四、线性规划解法 (最通用、应用最广的方法)对于前述各种方法全都失效的一般形式的矩阵对策，线性规划解法是最通用的方法，可以求解任一矩阵对策。由定理5知，求解矩阵对策可等价地转化为求解互为对偶的线性规划（P）和（D），故在问题（P）中，令。则问题(P)的约束条件变为：问题(P)等价与线性规划问题( )(12) 乘以A第j列对策论的基本概念和策略要求 四、线性规划解法 (最通用、应用最广的方法)同理在问题（D）中，令可知问题(D)等价于线性规划问题( )(13) 问题( ) 和( ) 是互为对偶的线性规划，可用单纯形或对偶单纯形法求解，再由变换(12)和(13)

19、，即可得到原问题的解和对策值 A第i行列乘以对策论的基本概念和策略要求例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对策论的基本概念和策略要求例：求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解，可求其混合策略。A中

20、有负元素，可以取k=2,在A的每个元素上加2得到A如下：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+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

21、.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中求乙方最佳策略的线性规划如下： 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 3

22、y1+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。 所以田忌的最优混合策略为作出策略1、4、5的概率都为1/3,而作出2，3，6的概率为0，此时VG=VG-k=1。4矩阵对策的混合策略对策论的基本概念和策略要求 齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3,0,0,1/3)T，Y*=(1/3,0,0,1/3,1/3,0)T，对策

23、值VG=1。例 两个局中人进行对策，规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。 解：首先计算局中人甲的赢得矩阵如下表：4-56-34-52-341（出1）2（出2）3（出3）3（出3）2（出2）1（出1）甲的赢 得甲的策略乙的策略对策论的基本概念和策略要求即甲的赢得矩阵为A： 可知无纯策略意义的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立线性规划模型如下： Min x1+x2+x3 Max y

24、1+y2+y3 1+3x2+10 x3 1 8y1+3y2+10y31 3x1+10 x2+x3 1 3y1+10y2+y3 1 10 x1+x2+12x3 1 10y1+y2+12y31 x1,x2,x3 0 y1,y2,y3 0 4矩阵对策的混合策略对策论的基本概念和策略要求得到x1=0.25, x2=0.50, x3；y1=0.25, y2=0.50, y3。即此对策的解为X* =(0.25,0.50,0.25)T，Y* =(0.25,0.50,0.25)T。VG=VG-k=0。4矩阵对策的混合策略对策论的基本概念和策略要求例4 甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有

25、:(1)降低产品价格；(2)提高产品质量；(3)推出新产品。乙企业考虑采取的策略措施有(1)增加广告费用；(2)增设维修网点，加强售后服务；(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。3-58-6510108-121（措施1）2（措施2）3（措施3）3（措施3）2（措施2）1（措施1）4矩阵对策的混合策略甲的赢 得甲的策略乙的策略对策论的基本概念和策略要求解：易知此对策无纯策略意义下的解。把A的每一个元素加上12，得到A建立线性规

26、划模型如下： Min x1+x2+x3 Max y1+y2+y3 1+20 x21 22y1+6y2+15y3 1 6x1+17x2+22x3 1 20y1+17y2+7y3 1 15x1+7x2+20 x3 1 22y2+20y3 1 x1,x2,x30 y1,y2,y30得到：x1=0.027,x2=0.020,x3；y1=0.0225,y2=0.0225,y3。x1=0.3858, x2=0.2858, x3；y1=0.3215,y2=0.3215,y3。即此对策的解为 X* =(0.3858,0.2858,0.3286)T ,Y* =(0.3215,0.3215,0.3572)T。VG

27、=VG。4矩阵对策的混合策略对策论的基本概念和策略要求 5其他类型的对策论简介 在对策论中可以根据不同方式对对策问题进行分类，通常分类的方式有（1）根据局中人的个数，分为二人对策和多人对策；（2）根据各局中人的赢得函数的代数和是否为零，可分为零和对策和非零和对策；（3）根据局中人是否合作，又可分为合作对策和非合作对策；（4）根据局中人的策略集中个数，又分为有限对策和无限对策（或连续对策）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地

28、对策、凸对策、随机对策。 本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。对策论的基本概念和策略要求 5其他类型的对策论简介一、完全信息静态对策 该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。 纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为纳什均衡。下面以著名的“囚徒困境”来进一步阐述。 例1 “囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了

29、起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来判决。如图1-1所示。对策论的基本概念和策略要求 5其他类型的对策论简介坦白抵赖轻罪，轻罪重罪，无罪重罪

30、，无罪释放，释放坦白抵赖图1-1 囚徒困境 由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，(坦白，坦白)就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成协议。 囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。对策论的基本概念和策略要求 5其他类型的对策论简介二、完全信息动态对策 在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知

31、道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。 例2 某行业中只有一个垄断企业A，有一个潜在进入者企业B。B可以选择进入或不进入该行业这两种行动，而A当B进入时，可以选择默认或者报复两种行动。如果B进入后A企业报复，将造成两败俱伤的结果，但如果A默认B进入，必然对A的收益造成损失。同样的，如果B进入而A报复，则B受损，反之，将受益。把此关系用图1-2表示。默许报复50,100-20,00,2000,200进入不进入图1-2 A、B的行动及结果AB对策论的基本概念和策略要求 5其他类型的对策论简介 由分析可知，上例中（B

32、选择不进入，A选择报复）和（B选择进入，A选择默许）都是纳什均衡解。但在实际中，（B选择不进入，A选择报复）这种情况是不可能出现的。因为B知道他如果进入，A只能默许，所以只有（B选择进入，A选择默许）会发生。或者说，A选择报复行动是不可置信的威胁。对策论的术语中，称（A选择默许，B选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为精炼纳什均衡。 当然，如果A下定决心一定要报复B，即使自己暂时损失。这时威胁就变成了可置信的，B就会选择不进入，（B选择不进入，A选择报复）就成为精炼纳什均衡。 军事交战时，“破釜沉舟”讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。 对策论的基本概念和策略要求 5其他类型的对策论简介三、多人非合作对策 有三个或三个以上对策方参加