对策论运筹学讲义.ppt

《对策论运筹学讲义.ppt》由会员分享，可在线阅读，更多相关《对策论运筹学讲义.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对策论运筹学讲义现在学习的是第1页，共65页对策论或博弈论(Game Theory)是研究具有对抗和竞争性行为问题的数学理论与方法。是运筹学的重要分支学科经济学领域一般称博弈论，是经济学领域近几十年发展起来一门新兴学科对策论从理论上作严格的讨论却起始于二十世纪：1912年，德国数学家E.Zermelo证明了国际象棋的3种着法必定存在一种；1921年，法国数学家E.Borel引入了“最优策略”等概念；1928年，美籍匈牙利人J.Von Neumann证明了对策论的基本定理-最大值最小值定理；1944年，Von Neumann和O.Morgenstern合写了对策论与经济行为一书，建立起对策论的基

2、本理论，奠定了对策论研究的基础。现在学习的是第2页，共65页对策问题举例例例1 1 猜单和猜双的博弈。两个人同时出一个指头或两个指头，如果两人猜单和猜双的博弈。两个人同时出一个指头或两个指头，如果两人出的指头相同，则局中人出的指头相同，则局中人1 1从局中人从局中人2 2处赢得五元；如果出的不处赢得五元；如果出的不一样，局中人一样，局中人1 1就要支付给局中人就要支付给局中人2 2五元。两个对手都可以采取五元。两个对手都可以采取两个策略：出一个手指和出两个手指，下表是局中人两个策略：出一个手指和出两个手指，下表是局中人1 1的赢得的赢得矩阵矩阵(二指莫拉问题二指莫拉问题)策 略局中人2出1指出

3、2指局中人1出1指55出2指55局中人局中人1 1从局中人从局中人2 2该如何选择策略，已获得利益？该如何选择策略，已获得利益？现在学习的是第3页，共65页例例2 2 囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在不同的囚徒困境。两个嫌疑犯作案后被警察抓住，分别被关在不同的屋子里审讯。警察告诉他们：如果两人都坦白，各判刑屋子里审讯。警察告诉他们：如果两人都坦白，各判刑8 8年；如年；如果两人都抵赖，由于证据不充分，两人将各判刑果两人都抵赖，由于证据不充分，两人将各判刑2 2年；如果其中年；如果其中一人坦白，另一人抵赖，则坦白者立即释放，抵赖者判刑一人坦白，另一人抵赖，则坦白者立即释放，抵赖者

4、判刑1010年。年。在这个例子中两人嫌疑犯都有两种策略：坦白或抵赖。可以用在这个例子中两人嫌疑犯都有两种策略：坦白或抵赖。可以用一个矩阵表示两个嫌疑犯的策略的损益一个矩阵表示两个嫌疑犯的策略的损益策 略囚徒2坦白抵赖囚徒1坦白(8,8)(0,10)抵赖(10,0)(2,2)囚徒该如何选择策略？囚徒该如何选择策略？囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就

5、变成了（坦白，坦白）。个人理性导致了集体不理性白，坦白）。个人理性导致了集体不理性现在学习的是第4页，共65页例3 田忌与齐王赛马 战战国国时时期期，齐齐威威王王与与大大将将田田忌忌赛赛马马，双双方方约约定定：从从各各自自的的上上、中中、下下三三个个等等级级的的马马中中各各选选一一匹匹马马出出场场比比赛赛，负负者者要要付付给给胜胜者者一一千千金金。已已知知田田忌忌的的马马要要比比齐齐王王同同一一等等级级的的马马差差一一些些，但但比比齐齐王王等等级级较较低低的的马马却却要要强强一一些些。因因此此，如如用用同同等等级级的的马马对对抗抗，田田忌忌必必连连输输三三场场，失失三三千千金金无无疑疑。田田忌

6、忌的的谋谋士士孙孙膑膑给给田田忌忌出出了了个个主主意意：每每局局比比赛赛前前先先了了解解齐齐王王参参赛赛马马的的等等级级，再再采采用用下下等等马马对对齐齐王王上上等等马马、中中等等马马对对齐齐王王下下等等马马、上上等等马马对对齐齐王王中中等等马马的的策策略略。比比赛赛结结果果，田田忌忌二二胜胜一一负负，反反而而赢赢得得一一千千金金。由由此此可可见见，双双方方各各采采取取什什么么样样的的出出马马次次序序对胜负至关重要。对胜负至关重要。现在学习的是第5页，共65页“齐王赛马齐王赛马”齐王在各局势中的益损值表齐王在各局势中的益损值表(单位：千金单位：千金)齐王和田忌可以任意选择三匹马出场的顺序齐王和

7、田忌可以任意选择三匹马出场的顺序现在学习的是第6页，共65页11对策论的基本概念对策模型的三个基本要素：对策模型的三个基本要素：1.1.局中人局中人(Players)：参与对抗的各方；：参与对抗的各方；2.2.策略集策略集(Strategices):(Strategices):局中人选择对付其它局中人的行动方案称局中人选择对付其它局中人的行动方案称为为策略策略；某局中人的所有可能策略全体称为；某局中人的所有可能策略全体称为策略集策略集3.3.一局势对策的益损值：局中人各自使用一个对策就形成了一局势对策的益损值：局中人各自使用一个对策就形成了一个一个局势局势，一个局势决定了各局中人的对策结果（量

8、化）称为该，一个局势决定了各局中人的对策结果（量化）称为该局势对策的局势对策的益损值益损值。赢得函数赢得函数(payoff function)(payoff function)：定义在局势上，取值为相应：定义在局势上，取值为相应益损值益损值的函数的函数4.纳什均衡：纳什均衡：纳什均衡指所有局中人最优策略组成的一种局势，纳什均衡指所有局中人最优策略组成的一种局势，既在给定其他局中人策略的情况下，没有任何局中人有积极既在给定其他局中人策略的情况下，没有任何局中人有积极性去选择其他策略性去选择其他策略现在学习的是第7页，共65页对策的分类对策按对策方式合作对策非合作对策完全理性有限理性两人对策零和对

9、策非零和对策多人对策结盟对策不结盟对策按对策人数静态对策完全信息静态对策不完全信息静态对策动态对策完全信息动态对策不完全信息动态对策按对策状态现在学习的是第8页，共65页二人有限零和对策二人有限零和对策（又称（又称矩阵对策矩阵对策）：）：局中人为局中人为2 2；每个局中人的策略集的策略数目都是有限的；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。中人的益损值之和为零。通常将矩阵对策记为通常将矩阵对策记为:G=S1,S2,A局中人甲的策略集：局中人甲的策略集：局中人乙的策略

10、集：局中人乙的策略集：甲的赢得矩阵：甲的赢得矩阵：矩阵对策矩阵对策aij为局中人甲在局势 下的赢得现在学习的是第9页，共65页其中：齐王的策略集其中：齐王的策略集: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 1 1 1 -1 1 1 3 “齐王赛马齐王赛马”是一个矩阵策略。是一个矩阵策略。现在学习的是第10页，共65页2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略例4 甲

11、、乙两队进行球赛，双方各可排出三种不同的阵容。设甲队为局中人，乙队为局中人，每一种阵容为一个策略，有S1=1,2,3，S2=1,2,3。根据 以往两队比赛的记录，甲队得分情况的赢得矩阵为问：这次比赛中，双方应 如何对阵？现在学习的是第11页，共65页在如此反复对策的过程中，各局中人如果不想冒险，就应该考虑从自身可能出现的最坏情况下着眼，去选择一种尽可能好的结果，即双方都是从各自可能出现的最不利的情形选择一即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。种最为有利的情况作为决策的依据。这就是所谓“理智行为理智行为”。称为最小最大准则最小最大准则，按照这个各方均避免冒险

12、的观念，就形成如下的推演过程推演过程。解 从A中可以看出，最多可得6分。于是，为得6分而选2。但是推测会有此心理，从而选3来对付，使得非但得不到6分，反而要失去3分。当然也会料到会有此心理，从而改选3，以使欲得3分而反失4分。现在学习的是第12页，共65页矩阵矩阵A中每行的最小元素分别为中每行的最小元素分别为1，-3，-5。在这些最少赢得中最好的结果是在这些最少赢得中最好的结果是1 1，故，故局中人局中人会采取策略会采取策略 1 1，无，无论对手采取何策略，论对手采取何策略，局中人局中人至少得至少得1 1分。对于分。对于局中人局中人，1 1，2 2，3 3 可能带来的最少赢得，即可能带来的最少

13、赢得，即A中每列的最大元素，分别为中每列的最大元素，分别为6，1，4。局中人局中人会采取会采取 2 2策略，确保策略，确保局中人局中人不会超过不会超过1 1分分。1 1和和 2 2分别称为局中人分别称为局中人、的最优策略。由于双方必然选择的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。这一种策略，所以，这种策略又称为最优纯策略。2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略Min1356Max14 1 2 3 1 2 3现在学习的是第13页，共65页定义定义1 1 设有矩阵对策设有矩阵对策G=S1,S2;A,其中，其中，A=ai j mn，若有若有则局势则局势(i*，

14、j*)称为G在在纯策略意义下的解纯策略意义下的解，也称为，也称为G的的鞍点鞍点；i*、j*分别称为局中人分别称为局中人和和的的最优纯策略最优纯策略；v称为称为G的值，也称的值，也称对策值对策值。对于例对于例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)v

15、G=0 (2)T1(G)=T2(G)其中其中T1(G)和和 T2(G)分别为局中人分别为局中人和和的最优策略集的最优策略集定理定理7和和8可以可以用来简化矩阵中的元素数字，使得以后的求解更为用来简化矩阵中的元素数字，使得以后的求解更为方便。方便。现在学习的是第33页，共65页矩阵对策的解法矩阵对策的解法 1优超原则法优超原则法 设有矩阵对策设有矩阵对策G=S1,S2;A,其中其中:A=ai j mn,如果对一切如果对一切j=1,n,都有都有 即矩阵的第即矩阵的第 行元素均不小于行元素均不小于 行的元素，行的元素，则称局中人则称局中人的纯策略的纯策略 优超于纯策略优超于纯策略 ；同样，；同样，若

16、对于一切若对于一切i=1,m,有有 ，即矩阵的第即矩阵的第 列均不列均不大于大于 列的元素，则称局中人列的元素，则称局中人的纯策略的纯策略 优超优超于纯策略于纯策略 现在学习的是第34页，共65页当局中人当局中人的纯策略的纯策略 优超于纯策略优超于纯策略 时，局中人时，局中人采用策略采用策略 超过采用策略超过采用策略 ；当称局中人；当称局中人的的纯策略纯策略 优超于纯策优超于纯策 时，局中人时，局中人采用纯策略采用纯策略 超过采用纯策略超过采用纯策略 。在求解矩阵对策时，如果出现上述优超情况，可将矩。在求解矩阵对策时，如果出现上述优超情况，可将矩阵阵A的第的第 行删除；当行删除；当的纯策略的纯

17、策略 优超于纯策优超于纯策 时，可以将矩阵时，可以将矩阵A第第 列删除。列删除。优超原则可以优超原则可以缩小了缩小了A A的规模的规模，使计算简化。一般情况下，优超，使计算简化。一般情况下，优超原理只是一种原理只是一种降阶技术降阶技术，但如精简之后，但如精简之后，A A中的剩余元素仅中的剩余元素仅有一个，则意味着已求得了对策的鞍点有一个，则意味着已求得了对策的鞍点。现在学习的是第35页，共65页 例例9 9 求解矩阵对策，其中：求解矩阵对策，其中：解解 查视各列，发现可划去第查视各列，发现可划去第1 1列，列，得得查视各行，发现可划去第查视各行，发现可划去第3 3行，得行，得查视各行列，知已无

18、法继续优超，故查视各行列，知已无法继续优超，故原矩阵原矩阵A A被简化为被简化为22规模规模。现在学习的是第36页，共65页二、二、2222公式解法公式解法设矩阵对策中的设矩阵对策中的A A为为若无鞍点，则若无鞍点，则X*与与Y*中各分量必不为零中各分量必不为零 (否则，假定否则，假定 ，则，则 ，局中人，局中人选择纯策略选择纯策略1 1，局中人，局中人选择选择 中最小元素中最小元素对应的策略，即对策存在有鞍点对应的策略，即对策存在有鞍点)。由定理由定理6 6的的(3)、(4)，得，得现在学习的是第37页，共65页二、二、2222公式解法公式解法求解后，得：求解后，得：(11)现在学习的是第3

19、8页，共65页用用2222求解例求解例5 5 已知矩阵对策已知矩阵对策G,其中：其中：解解 G是不存在鞍点是不存在鞍点用用2222求解例求解例9 9现在学习的是第39页，共65页求解例求解例7 7 已知矩阵对策已知矩阵对策G,其中：其中：解解 利用优超原理得利用优超原理得用公式计算用公式计算得：得：矩阵对策的解矩阵对策的解 ：X*=(0，1/3,2/3，0)T,Y*=(1/3,2/3)T vG=53现在学习的是第40页，共65页三、三、2n2n和和m2m2图解法图解法 当对策双方中的当对策双方中的某一方策略个数为某一方策略个数为2 2，而另一方策略个数大于，而另一方策略个数大于2 2时，可以采

20、用图解法来方便地求解这类对策问题。下面通过例子时，可以采用图解法来方便地求解这类对策问题。下面通过例子来介绍这种直观的几何方法。来介绍这种直观的几何方法。用一个例子来看解法用一个例子来看解法例例10 10 求解矩阵对策，其中求解矩阵对策，其中:解解 显然，显然，G G无鞍点且无优超关系。无鞍点且无优超关系。设局中人设局中人的混合策略为的混合策略为X=(x1,x2)T=(x,1x)T，则按则按“理智理智行为行为”，期望的赢得为期望的赢得为1.1.考虑考虑2n 阶矩阵阶矩阵现在学习的是第41页，共65页在在Oxv平面直角坐标系中，平面直角坐标系中，x0,1 画画直线段（图直线段（图10-110-1

21、）：）：L1：v=-8x+9L2：v=7xL3：v=15x-2图图10-110-1xvO2468101Cx*DEFL1L2L3现在学习的是第42页，共65页于是，v=f(x)的图形就是折线CDEF。因为E点是折线的最高点，所以v=f(x*)。注意到E点是L1与L2的交点，求解得x*=35，vG=215，的最优混合策略为X*=(3/5,2/5)T。图图10-110-1xvO2468101Cx*DEFL1L2L3设局中人的最优混合策略为Y*=(y1*，y2*，y3*)T，则由定理6知现在学习的是第43页，共65页图图10-110-1xvO2468101Cx*DEFL1L2L3根根据据定定理理6 6

22、 得得y3*=0=0。也也可可根根据据E点点只只与与L L1 1、L L2 2有有关关且且此此处处L L3 3高高于于E E点点，即即只只与与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注意：注意：现在学习的是第44页，共65页例例11 11 求解矩阵对策，其中求解矩阵对策，其中:解解 显然，显然，G G无鞍点使用优超

23、原理，无鞍点使用优超原理，1 1优超优超4 4，删去第删去第4 4行，将行，将A A简化为简化为设局中人设局中人的混合策略为的混合策略为Y=(y1,y2)T=(y,1y)T，则按则按“理智行理智行为为”，期望的赢得为期望的赢得为2.2.考虑考虑m2阶矩阵阶矩阵现在学习的是第45页，共65页在在Oxv平面直角坐标系中，平面直角坐标系中，y0,1 画直画直线段（图线段（图10-210-2）：）：L1：v=6y5L2：v=8y4L3：v=5y 3图图10-2yvO2461Fy*DECL1L2L342v=g(y)的图形就是折线CDEF。因为E点是折线的最低点，所以 v=g(y*)。注意到E点是L1与L

24、3的交点，求解现在学习的是第46页，共65页图图10-2yvO2461Fy*DECL1L2L342求解求解得得 y*=811，v=711，的最优混合策略为的最优混合策略为Y*=(8/11,3/11)T。设局中人设局中人的最优混合策略为的最优混合策略为:X*=(x1*，x2*，x3*，0)T，y1*0,y2*0 则由定理则由定理6 6知知 现在学习的是第47页，共65页图图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。也可根。也可根据据

25、由于由于E点点只与只与L1、L3相关相关,且此处且此处L2低于低于E E点，点，即只与即只与1 1、3 3相关且相关且2 2不必考虑，不必考虑，所以所以x2*=0，代入上式，可解得代入上式，可解得x1*=511，x3*=611。于是，于是，的最优混合策略为的最优混合策略为X*=(5/11,0,6/11,0)T。现在学习的是第48页，共65页 四、线性规划解法(最通用、应用最广的方法)对于前述各种方法全都对于前述各种方法全都失效失效的一般形式的矩阵对策，线性规划解的一般形式的矩阵对策，线性规划解法是最通用的方法，可以求解任一矩阵对策。法是最通用的方法，可以求解任一矩阵对策。由定理由定理5 5知，

26、求解矩阵对策可等价地转化为求解互为对偶的线性规划知，求解矩阵对策可等价地转化为求解互为对偶的线性规划（P）和和（D），故在问题（），故在问题（P）中，令）中，令。则问题则问题(P)的约束条件变为的约束条件变为：问题问题(P)等价与线性规划问题等价与线性规划问题()(12)乘以A第j列现在学习的是第49页，共65页 四、线性规划解法(最通用、应用最广的方法)同理在问题（同理在问题（D）中，令）中，令可知问题可知问题(D)等价于等价于线性规划问题线性规划问题()(13)问题问题()和和()是是互为对偶的线性规划，互为对偶的线性规划，可用单纯形或对可用单纯形或对偶单纯形法求解，再由变换偶单纯形法求解

27、，再由变换(12)和和(13)，即可得到原问题的解，即可得到原问题的解和对策值和对策值 A第i行列乘以现在学习的是第50页，共65页例例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

28、/45)T现在学习的是第51页，共65页例：求解例：求解“齐王赛马齐王赛马”问题。问题。已知齐王的赢得矩阵已知齐王的赢得矩阵A A求得求得故不存在纯策略问题下的解，可求其混合策略。故不存在纯策略问题下的解，可求其混合策略。A A中有负元素，可以取中有负元素，可以取k=2,k=2,在在A A的每个元素上加的每个元素上加2 2得到得到A A如下：如下：44矩阵对策的混合策略矩阵对策的混合策略现在学习的是第52页，共65页 建立对建立对G=S1，S2，A中求甲方最佳策略的线性规划如下：中求甲方最佳策略的线性规划如下：Min x1+x2+x3+x4+x5+x6 s.t.5x1+3x2+3x3+x4+3

29、x5+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.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

30、、4、5 的概率为的概率为0，此时，此时VG=V2=1。现在学习的是第53页，共65页 同样可以建立对策同样可以建立对策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 3y1+3y2+3y3+y4+5y5+3y6 1 3y1+3y2+y3+3y4+3y5+5y6 1 yi0,i=1,2,6 可解得解为

31、：可解得解为：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。44矩阵对策的混合策略矩阵对策的混合策略现在学习的是第54页，共65页 齐王赛马问题的对策最优解可简记为齐王赛马问题的对策最优解可简记为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/

32、3,0,0,1/3,1/3,0)(1/3,0,0,1/3,1/3,0)T T，对策值，对策值V VG G=1=1。例例 两个局中人进行对策，规则是两人互相独立的各自从两个局中人进行对策，规则是两人互相独立的各自从1 1、2 2、3 3这三个数字这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。乙以数量为此和数

33、的报酬。试求出其最优策略。解：首先计算局中人甲的赢得矩阵如下表：解：首先计算局中人甲的赢得矩阵如下表：4-56-34-52-34 1 1（出（出1 1）2 2（出（出2 2）3 3（出（出3 3）3 3（出（出3 3）2 2（出（出2 2）1 1（出（出1 1）甲的赢甲的赢 得得甲的策略甲的策略乙的策略乙的策略现在学习的是第55页，共65页即甲的赢得矩阵为即甲的赢得矩阵为A A：可知无纯策略意义的解，下面求其在混合策略下的解。可知无纯策略意义的解，下面求其在混合策略下的解。A A的各元素都加上的各元素都加上6 6，得到，得到建立线性规划模型如下：建立线性规划模型如下：Min xMin x1 1

34、+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+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 44矩阵对策的混合策

35、略矩阵对策的混合策略现在学习的是第56页，共65页得到得到x x1 1=0.25,x=0.25,x2 2=0.50,x=0.50,x3 3=0.25=0.25；y 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。44矩阵对策的混合策略矩阵对策的混合策略现在学习的是第57页，共65页例例4 4 甲乙两个企业生产

36、同一种电子产品，甲企业可以采取的策略措施有甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有:(1)(1)降低产品降低产品价格；价格；(2)(2)提高产品质量；提高产品质量；(3)(3)推出新产品。乙企业考虑采取的策略措施有推出新产品。乙企业考虑采取的策略措施有(1)(1)增增加广告费用；加广告费用；(2)(2)增设维修网点，加强售后服务；增设维修网点，加强售后服务；(3)(3)改进产品性能。由于甲乙两个改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的

37、措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。试求出这两个企业各自的最优策略。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）44矩阵对策的混合策略矩阵对策的混合策略甲的赢甲的赢 得得甲的策略甲的策略乙的策略乙的策略现在学习的是第58页，共65页解：解：易知此对策无纯策略意义下的解。把易知此对策无纯策略意义下的解。把A A的每一个元素加上

38、的每一个元素加上1212，得到，得到A A建立线性规划模型如下：建立线性规划模型如下：Min xMin x1 1+x+x2 2+x+x3 3 Max yMax y1 1+y+y2 2+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

39、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.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.

40、3572。即此对策的解为即此对策的解为 X X*=(0.3858,0.2858,0.3286)=(0.3858,0.2858,0.3286)T T,Y,Y*=(0.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。44矩阵对策的混合策略矩阵对策的混合策略现在学习的是第59页，共65页 55其他类型的对策论简介其他类型的对策论简介 在对策论中可以根据不同方式对对策问题进行分类，通常分类的在对策论中可以根据不同方式对对策问题进行分类，通常分类的方式有（方式有（1）根据局中人的个数，分为二人对策和多人对

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

42、为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策。对策、随机对策。本节只对对策论中非合作对策的完全信息对策、多人非合作对策、本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。非零和对策作一个简单的叙述性介绍。现在学习的是第60页，共65页 55其他类型的对策论简介其他类型的对策论简介一、完全信息静态对策一、完全信息静

43、态对策 该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为纳什均纳什均衡衡。下面以著名的。下面

44、以著名的“囚徒困境囚徒困境”来进一步阐述。来进一步阐述。例例1“1“囚徒困境囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵

45、赖的话，就都会被释放，同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来

46、判决。如图来判决。如图1-11-1所示。所示。现在学习的是第61页，共65页 55其他类型的对策论简介其他类型的对策论简介坦白坦白抵赖抵赖轻罪，轻罪轻罪，轻罪重罪，无罪重罪，无罪重罪，无罪重罪，无罪释放，释放释放，释放坦白坦白抵赖抵赖图图1-1 1-1 囚徒困境囚徒困境 由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，(坦白，坦白，坦白坦白)就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成协议。协议。囚徒困境反映了个人理性和集体理性

47、的矛盾。对于双方，（抵赖，抵赖）囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。果就变成了（坦白，坦白）。个人理性导致了集体不理性。现在学习的是第62页，共65页 55其他类型的对策论简介其他类型的对策论简介二、完全信息动态对策二、完全信息动态对策 在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存

48、在先后顺序，后行的一方会参考先行者的策略而采取行些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。策问题。例例2 2 某行业中只有一个垄断企业某行业中只有一个垄断企业A A，有一个潜在进入者，有一个潜在进入者企业企业B B。B B可以选择进入或不可以选择进入或不进入该行业这两种行动，而进入该行业这两种行动，而A

49、 A当当B B进入时，可以选择默认或者报复两种行动。如果进入时，可以选择默认或者报复两种行动。如果B B进入后进入后A A企业报复，将造成两败俱伤的结果，但如果企业报复，将造成两败俱伤的结果，但如果A A默认默认B B进入，必然对进入，必然对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的行动及结

50、果的行动及结果A AB B现在学习的是第63页，共65页 55其他类型的对策论简介其他类型的对策论简介 由分析可知，上例中（由分析可知，上例中（B B选择不进入，选择不进入，A A选择报复）和（选择报复）和（B B选择进选择进入，入，A A选择默许）都是纳什均衡解。但在实际中，（选择默许）都是纳什均衡解。但在实际中，（B B选择不进入，选择不进入，A A选择报复）这种情况是不可能出现的。因为选择报复）这种情况是不可能出现的。因为B B知道他如果进入，知道他如果进入，A A只能默许，所以只有（只能默许，所以只有（B B选择进入，选择进入，A A选择默许）会发生。或者说，选择默许）会发生。或者说，