运筹学教学对策论.pptx

运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件对对 策策 论论Game TheoryGame Theory 第一节第一节 对策论的基本概念和分类对策论的基本概念和分类发发 展展 简简 史史1912年年E.Zermelo “关于集合论在象棋对策中的应用关于集合论在象棋对策中的应用”1921年年E.Borel 引入最优策略引入最优策略1928年年J.V.Neumann证明了一些猜想证明了一些猜想博奕论博奕论(Game Theory)也就是运筹学中的对策论。也就是运筹学中的对策论。对策思想最早产生于我国古代。对策思想最早产生于我国古代。早在两千多年前的春秋时期，孙武在早在两千多年前的春秋时期，孙武在孙子兵法孙子兵法中论述的军事思想和治国策略，就蕴育了丰富和深中论述的军事思想和治国策略，就蕴育了丰富和深刻的对策论思想。孙武的后代孙膑，为田忌谋划，刻的对策论思想。孙武的后代孙膑，为田忌谋划，巧胜齐王，这个著名的巧胜齐王，这个著名的“田忌赛马田忌赛马”，就是典型的，就是典型的对策思想的成功运用。对策思想的成功运用。产生标志产生标志作为一门学科的创立，则是以美国数学家冯作为一门学科的创立，则是以美国数学家冯.诺依曼诺依曼(John Von Neumann)和经济学家奥斯卡和经济学家奥斯卡.摩根斯坦摩根斯坦(Oskar Morgenstern)合著的合著的博奕论与经济行为博奕论与经济行为(The Game Theory and Economic Behavior)(1944)一书出版为标志，他们奠定和形成了这门学科的理一书出版为标志，他们奠定和形成了这门学科的理论与方法论基础。论与方法论基础。发展成熟发展成熟Nash均衡、经济博奕论、信息不对称对策和广义对均衡、经济博奕论、信息不对称对策和广义对策策基本概念基本概念在策略型博奕中，一个对策有以下几种基本要素：在策略型博奕中，一个对策有以下几种基本要素：一局中人一局中人(players)：即博奕的参与者，他们是博奕的决策主体。根据自己的利益即博奕的参与者，他们是博奕的决策主体。根据自己的利益要求决定自己的决策，记第要求决定自己的决策，记第i个局中人为个局中人为i，局中人集合为，局中人集合为1,2,I，即共有，即共有I个局中人。我们将某个局中人以外的其它个局中人。我们将某个局中人以外的其它局中人称为局中人称为“i的对手的对手”，记为，记为-i。对策中利益一致的参加者只能看成一个局中人，例：桥牌中对策中利益一致的参加者只能看成一个局中人，例：桥牌中的东、西两方。的东、西两方。对策论中对局中人的一个重要假设：每个局中人都是对策论中对局中人的一个重要假设：每个局中人都是“理智理智的的”，即每一个局中人都不存在侥幸心理，不存在利用其他，即每一个局中人都不存在侥幸心理，不存在利用其他局中人决策的失误来扩大自身利益的行为。局中人决策的失误来扩大自身利益的行为。在策略型博奕中，一个对策有以下几种基本要素：在策略型博奕中，一个对策有以下几种基本要素：一局中人一局中人 即指每个局中人在对策中可以选择采用的行动方即指每个局中人在对策中可以选择采用的行动方案，但这个方案必须是一个完整的行动，而不是行动案，但这个方案必须是一个完整的行动，而不是行动的某一步。每个局中人均有可供选择的多种策略。的某一步。每个局中人均有可供选择的多种策略。二策略二策略(strategies)：基本概念基本概念三支付或收益三支付或收益(payoffs):二策略二策略一局中人一局中人在策略型博奕中，一个对策有以下几种基本要素：在策略型博奕中，一个对策有以下几种基本要素：是是指指一一局局博博奕奕的的得得失失。或或者者说说是是局局中中人人从从各各种种策策略略组组合合中中获获得得的的效效用用，它它是是策策略略组组合合的的函函数数。如如果果局局中中人人得得失失的的总总和和为为零零，则则称称这这种种对对策策为为零零和和对对策策（博弈）；（博弈）；否则，称为否则，称为非零和对策非零和对策(博奕博奕)。基本概念基本概念局势：局势：一个对策中，每一个局中人所出策略形成的策一个对策中，每一个局中人所出策略形成的策略组称为一个局势。略组称为一个局势。设设si是第是第i个局中人的一个策略，则个局中人的一个策略，则n个局中人的策略个局中人的策略形成的策略组形成的策略组s=s1,s2,sn,就是一个局势。就是一个局势。全部局势的集合全部局势的集合S记为：记为：模模 型型局中人局中人 两个或两个以上两个或两个以上-决策者决策者策略集合策略集合 策略策略-决策决策 局势局势-状态状态支付函数支付函数 支付关于局势的函数支付关于局势的函数-决策依据和标准决策依据和标准 模型模型分分 类类局中人局中人 两人对策、多人对策两人对策、多人对策策略策略 有限对策、无限对策；非合作对策、合作对策有限对策、无限对策；非合作对策、合作对策支付支付 零和对策、非零和对策零和对策、非零和对策时间时间 单阶段对策、多阶段对策单阶段对策、多阶段对策对策模型众多，但占有重要地位的是二人有限零和对对策模型众多，但占有重要地位的是二人有限零和对策（矩阵对策）。它是一类最简单的对策模型，策（矩阵对策）。它是一类最简单的对策模型，它它的结果也是研究其他对策模型的基础。的结果也是研究其他对策模型的基础。第二节第二节二人有限零和对策模型二人有限零和对策模型 二人有限零和对策二人有限零和对策二人二人：参加对策的局中人有两个；：参加对策的局中人有两个；有限有限：局中人的策略集都为有限集；：局中人的策略集都为有限集；零和零和：在任一局势下，两个局中人的赢得之和总等于在任一局势下，两个局中人的赢得之和总等于0，即，即，一个局中人的所得值恰好是另一个局中人的所失值，双方的一个局中人的所得值恰好是另一个局中人的所失值，双方的利益是完全对抗的。利益是完全对抗的。设局中人设局中人I和和II的策略集分别为的策略集分别为对任一纯局势对任一纯局势，记局中人，记局中人I的赢得值为的赢得值为则则I的赢得矩阵为的赢得矩阵为例：甲、乙各出示一枚硬币，在不让对方看见的情况例：甲、乙各出示一枚硬币，在不让对方看见的情况下，将硬币放在桌子上，若两个硬币都呈正面或都下，将硬币放在桌子上，若两个硬币都呈正面或都呈反面则甲得呈反面则甲得1分，乙付出分，乙付出1分；若两个硬币一个呈分；若两个硬币一个呈正面另一个呈反面则乙得正面另一个呈反面则乙得1分，甲付出分，甲付出1分分局中人局中人：甲、乙：甲、乙甲的赢得矩阵为甲的赢得矩阵为例例（齐王与田忌赛马）（齐王与田忌赛马）这个问题中齐王和田忌各自拥有的策略为：这个问题中齐王和田忌各自拥有的策略为：S1=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)S2=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)则对应的齐王的赢得矩阵为则对应的齐王的赢得矩阵为例：甲乙两人玩猜拳游戏，游戏中双方同时分别出石例：甲乙两人玩猜拳游戏，游戏中双方同时分别出石头、布或剪刀。规则是剪刀赢布，布赢石头，石头头、布或剪刀。规则是剪刀赢布，布赢石头，石头赢剪刀，赢者得一分。若出的相同，算和局都不得赢剪刀，赢者得一分。若出的相同，算和局都不得分。试列出甲的赢得矩阵。分。试列出甲的赢得矩阵。石头布剪刀石头0-11布10-1剪刀-110第三节第三节矩阵对策的纯策略矩阵对策的纯策略例：设有一矩阵对策例：设有一矩阵对策其中其中解：对局中人解：对局中人I而言，最大赢得是而言，最大赢得是9，若想得到这个赢得，若想得到这个赢得，他要选择纯策略他要选择纯策略 ，由于局中人，由于局中人II也是理智的竞争也是理智的竞争者，他已考虑到局中人者，他已考虑到局中人I打算出打算出 的心理，则准备以的心理，则准备以 对付之，使局中人对付之，使局中人I不但得不到不但得不到9，反而失掉，反而失掉10.局中人局中人I当然也会猜到局中人当然也会猜到局中人II的心理，故而出的心理，故而出 来对付，使局中人来对付，使局中人II得不到得不到10，反而失掉，反而失掉6，如果双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然如果双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己所得最少这一点，就应该从各自可能出现的最不利会设法使自己所得最少这一点，就应该从各自可能出现的最不利的情形中选择一个最有利的情形作为决策的依据，这就是所谓的的情形中选择一个最有利的情形作为决策的依据，这就是所谓的“理智行为理智行为”，也是对策双方实际上可以接受并采取的一种稳妥方，也是对策双方实际上可以接受并采取的一种稳妥方法。法。对策双方处于完全对抗的环境中，因此，各自都采取保守态对策双方处于完全对抗的环境中，因此，各自都采取保守态度，从最坏处着眼，并力争较好的结局。所以，局中人度，从最坏处着眼，并力争较好的结局。所以，局中人A采用采用maxmin准则，局中人准则，局中人B采用采用minmax准则。准则。相应于这种准则下，对策双方采取的各自的策略称为相应于这种准则下，对策双方采取的各自的策略称为对策的解对策的解。双方采取上述策略，连续重复进行对策，其输赢的平均值称为双方采取上述策略，连续重复进行对策，其输赢的平均值称为相应对策问题的对策值相应对策问题的对策值，记为，记为v对策问题选择解的准则对策问题选择解的准则b1b2bna1c11c12c1na2c21c22c2namcm1cm2cmn设局中人设局中人A的策略有的策略有 ，局中人，局中人B的策略有的策略有 ，A的赢得矩阵为的赢得矩阵为maxmin准则准则:当当A依据此原则选择策略时，总考虑不管选哪一个策略依据此原则选择策略时，总考虑不管选哪一个策略都将得到最坏的结局。即都将得到最坏的结局。即minmax准则准则:当当B依据此原则选择策略时，总考虑不管选哪一个策略依据此原则选择策略时，总考虑不管选哪一个策略都将得到最坏的结局（最大损失）。即都将得到最坏的结局（最大损失）。即均均 衡衡 解解按照这个定义，例中的均衡解为按照这个定义，例中的均衡解为继续分析前例继续分析前例:此时的平衡局势此时的平衡局势 ，对应的值，对应的值 既是其所在既是其所在行的最小元素，又是其所在列的最大元素，即有行的最小元素，又是其所在列的最大元素，即有一般地，有如下定义和结论：一般地，有如下定义和结论：证明：证明：另一方面，对任意的另一方面，对任意的i,j，由，由由（由（1），（），（2）得）得必要性：必要性：设有设有i*,j*,使得使得则由则由有有注注以上定理的对策意义为：一个平衡局势以上定理的对策意义为：一个平衡局势 应该具应该具有这样的性质：当局中人有这样的性质：当局中人A选择了策略选择了策略 后，局后，局中人中人B为了使其损失最小，只能选择策略为了使其损失最小，只能选择策略 ，否则，否则就可能损失更多；反之，当局中人就可能损失更多；反之，当局中人B选择了策略选择了策略 后，局中人后，局中人A为了得到最大赢得也只能选择策略为了得到最大赢得也只能选择策略 否则就会赢得较少，双方的竞争在局势否则就会赢得较少，双方的竞争在局势 下达下达到了一个平衡状态。到了一个平衡状态。例例 子子例例 子子例例 求下面的矩阵对策的解求下面的矩阵对策的解解：计算解：计算此时，此时，i*=1,3;j*=2,4所以，所以，(a1,b2),(a1,b4),(a2,b2),(a2,b4)都是对策的解。都是对策的解。由以上例子知，对策的均衡解不见得唯一，当解不唯由以上例子知，对策的均衡解不见得唯一，当解不唯一时，解之间的关系有以下性质：一时，解之间的关系有以下性质：性质性质1（无差别性）若（无差别性）若 和和 是对策是对策G的两个的两个解，则解，则性质性质2（可交换性）若（可交换性）若是对策是对策G的两个解的两个解则则也是对策的解。也是对策的解。第三节第三节 优势原则优势原则和具有混和策略的矩阵对策和具有混和策略的矩阵对策对一个矩阵对策对一个矩阵对策由前面讨论知，局中人由前面讨论知，局中人I能保证的至少赢得为能保证的至少赢得为局中人局中人II能保证的至多损失为能保证的至多损失为所以，总有所以，总有当当时，对策在纯策略意义下有解时，对策在纯策略意义下有解当当时，对策在纯策略意义下没有解，此时情况时，对策在纯策略意义下没有解，此时情况如以下例中所述。如以下例中所述。例：如下是二人零和对策的支付矩阵例：如下是二人零和对策的支付矩阵b1b2a114a232分析发现：分析发现：此时若还使用纯策略，双方按照从最不利情形中选择此时若还使用纯策略，双方按照从最不利情形中选择最有利情形的原则，应分别选择最有利情形的原则，应分别选择a2和和b1,此时局中人此时局中人I的的赢得是赢得是3，比至少赢得多了，比至少赢得多了1，这是因为局中人，这是因为局中人II选择了选择了b1，才使得局中人，才使得局中人I得到了不该得到的赢得，显然局中得到了不该得到的赢得，显然局中人会考虑出人会考虑出b2,让局中人让局中人I的赢得变为的赢得变为2，而此时局中人，而此时局中人I又又会选择会选择a1，使得自己的赢得为，使得自己的赢得为4，如此下去就会出现不稳定状态。如此下去就会出现不稳定状态。解决此问题的想法很自然，既然局中人都没有最优策略解决此问题的想法很自然，既然局中人都没有最优策略可出，可否给出一个选择不同策略的概率分布，以达到可出，可否给出一个选择不同策略的概率分布，以达到一种平衡状态呢，这就是混合策略。一种平衡状态呢，这就是混合策略。定义：混和策略定义：混和策略设有矩阵对策设有矩阵对策G=S1,S2;A,其中其中记记则称则称则称则称为局中人为局中人A，B的的混和策略集混和策略集，称，称x,y为为混混和策略和策略，（，（x,y）为）为混和局势混和局势。局中人。局中人A的赢得函数为：的赢得函数为：称称为对策为对策G的的混和扩充混和扩充。定义：混和策略意义下的解定义：混和策略意义下的解设设如果如果则称则称VG为对策为对策G的的值值，称使得上式成立的混和局势，称使得上式成立的混和局势是矩阵对策是矩阵对策G=S1,S2;A的混和扩充。的混和扩充。（x*,y*）为）为G在混和策略意义下的在混和策略意义下的解（平衡局势解（平衡局势），），称称x*,y*分别为局中人分别为局中人A和和B的的最优混和策略最优混和策略。注注：当局中人：当局中人A选择混和策略选择混和策略x时，他的预期所得时，他的预期所得（按最小）是（按最小）是因此局中人因此局中人A应选取应选取使得使得同理，同理，B可保证损失的期望值可保证损失的期望值至多是至多是显然成立：显然成立：和纯策略类似，混合策略意义下同样有解存在的鞍和纯策略类似，混合策略意义下同样有解存在的鞍点型充要条件：点型充要条件：定理定理1:矩阵对策在混和策略下有解的充要条件是：存在矩阵对策在混和策略下有解的充要条件是：存在使得对任意使得对任意有有例：考虑矩阵对策例：考虑矩阵对策解：易知解：易知G在纯策略意义下无解，所以，设在纯策略意义下无解，所以，设表示局中人表示局中人I，II的混合策略，则的混合策略，则局中人局中人I的赢得的期望是的赢得的期望是取取则则所以所以分别为局中人分别为局中人I，II的最优策略。的最优策略。若记若记则则E(i,y)为局中人为局中人A取纯策略取纯策略ai时的赢得值；时的赢得值；E(x,j)为局中为局中人人B取纯策略取纯策略bj时的赢得值时的赢得值,且有且有则得到一个和定理则得到一个和定理1等价的定理等价的定理2混合策略意义下求解方法的相关理论混合策略意义下求解方法的相关理论定理定理2:则则为对策为对策G的解的充要条件的解的充要条件为：对任意的为：对任意的i=1,2,m;j=1,2,n,有有证明：设证明：设为对策为对策G的解，则由定理的解，则由定理1，成立，成立因为纯策略是混合策略的特例，所以，（因为纯策略是混合策略的特例，所以，（*）成立。）成立。反之，若（反之，若（*）成立，则）成立，则定理定理2说明：要验证说明：要验证为对策为对策G的解时，只需要的解时，只需要对上式给出的有限个（对上式给出的有限个（mn）不等式进行验证即可，）不等式进行验证即可，大大简化了验证过程。大大简化了验证过程。如此，便有了下面的等价定理定理如此，便有了下面的等价定理定理3定理定理2得证。得证。定理定理3:则则为：存在数为：存在数v，使得，使得为对策为对策G的解的充要条件的解的充要条件分别为不等式组分别为不等式组(1),(2)的解的解,且且v=VG定理定理4:任一矩阵对策任一矩阵对策G，一定存在混和策略意义下，一定存在混和策略意义下的解。的解。证明证明:由定理由定理2知，只需证明存在知，只需证明存在使得（使得（*）式成立。所以，考虑如下规划问题）式成立。所以，考虑如下规划问题易知，规划问题（易知，规划问题（P）和（）和（D）互为对偶问题，且）互为对偶问题，且分别为（分别为（P）和（）和（D）的一个可行解。由对偶定理知，）的一个可行解。由对偶定理知，他们都存在最优解，且最优目标值相等。即，存在他们都存在最优解，且最优目标值相等。即，存在和和使得对任意的使得对任意的i=1,2,m;j=1,2,n有有或或又由又由得得所以所以,(*)得证。得证。定理定理5:设设是矩阵对策是矩阵对策G的解，的解，v=VG，则，则证明证明:由由有有又因为又因为所以，当所以，当时，必有时，必有当当时，必有时，必有同理，可证（同理，可证（2），（），（4）。）。优优 超（优势原则）超（优势原则）算算 例例简简 化化简简 化化第四节第四节 混和策略的解法混和策略的解法方法方法1：图解法：图解法上例中，设上例中，设A以概率以概率x和和1-x使用策略使用策略a1和和a2对付对付B使使用纯策略用纯策略b1时，时，A的收入为的收入为对付对付B使用纯策略使用纯策略b2时，时，A的收入为的收入为按照按照maxmin原则原则混和策略意义下的混和策略意义下的maxmin值为值为va=5/2，此时，此时x=1/4为下图的为下图的B点点同理，若设局中人同理，若设局中人B以以y和和1-y的概率分别使用策略的概率分别使用策略b1,b2,可得到混和策略意义下的可得到混和策略意义下的minmax值为值为vb=5/2，此时，此时y=1/2。为下图的。为下图的D点点问题中求出的问题中求出的va=vb=5/2就是混和决策意义下的解。一就是混和决策意义下的解。一般记做般记做其中，其中，X=x1,xm，Y=y1,yn为局中人为局中人A，B使用使用各自策略的概率，满足各自策略的概率，满足注：局势平衡分析注：局势平衡分析设局中人设局中人B使用最优策略使用最优策略Y*,而局中人而局中人A使用某一个混使用某一个混和策略和策略X，此时，此时A的收入将降至折线的收入将降至折线ABC上离开上离开B的的某一点；又设局中人某一点；又设局中人A使用最优策略使用最优策略X*,而局中人而局中人B使用某一混和策略使用某一混和策略Y，此时，此时，B的损失将升高到折的损失将升高到折线线CDE上离开上离开D点的某一点。当双方都坚持使用最点的某一点。当双方都坚持使用最优混和策略时。局势得以平衡。优混和策略时。局势得以平衡。方法方法2：方程组法：方程组法由定理由定理3知，求矩阵对策的解等价于求解不等式方程知，求矩阵对策的解等价于求解不等式方程组（组（1），（），（2）。又由定理）。又由定理4和和5知，若最优策略中知，若最优策略中的的 均不为均不为0，则可将以上的两个不等式组的，则可将以上的两个不等式组的求解问题转化为下面两个方程组的求解问题：求解问题转化为下面两个方程组的求解问题：注：注：此方法要求此方法要求 均不为均不为0，所以，当最优策略，所以，当最优策略的某些分量实际为的某些分量实际为0时，以上两个方程组可能无解。时，以上两个方程组可能无解。这说明此方法在实际应用中有一定的局限性。这说明此方法在实际应用中有一定的局限性。特别：特别：对对22的矩阵，若局中人的赢得矩阵没有鞍点的矩阵，若局中人的赢得矩阵没有鞍点时，各局中人的最优策略中的时，各局中人的最优策略中的 都大于都大于0。即。即对于这种问题，是可以采用方程组法求解的。对于这种问题，是可以采用方程组法求解的。例：求解矩阵对策例：求解矩阵对策G，其中，其中A为为解：解：利用优势原则，化简矩阵：利用优势原则，化简矩阵：因为因为a4优超于优超于a1，a3优超于优超于a2，所以化简为，所以化简为又因为又因为b1优超于优超于b3，b2优超于优超于b4,b5，所以化简为，所以化简为又因为又因为a1优超于优超于a3，化简为，化简为容易看出矩阵容易看出矩阵A3没有鞍点，所以可以用方程组法解之。没有鞍点，所以可以用方程组法解之。对应的方程组为：对应的方程组为：求解，得求解，得所以，以矩阵所以，以矩阵A为赢得矩阵的对策的一个解为为赢得矩阵的对策的一个解为例例（齐王与田忌赛马）（齐王与田忌赛马）这个问题中齐王和田忌各自拥有的策略为：这个问题中齐王和田忌各自拥有的策略为：S1=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)S2=(上中下上中下),(上下中上下中),(中上下中上下),(中下上中下上),(下中上下中上),(下上中下上中)则对应的齐王的赢得矩阵为则对应的齐王的赢得矩阵为解：易知齐王的赢得矩阵没有鞍点，即没有最优纯策略解：易知齐王的赢得矩阵没有鞍点，即没有最优纯策略设齐王和田忌的最优混合策略分别为设齐王和田忌的最优混合策略分别为由于齐王和田忌对策略集中的所有策略都有可能选择，由于齐王和田忌对策略集中的所有策略都有可能选择，所以，可设所以，可设求解方程组求解方程组和和得得方法方法3：线性规划方法：线性规划方法由定理由定理4知，求解矩阵对策可等价于求解互为对偶的知，求解矩阵对策可等价于求解互为对偶的线性规划问题（线性规划问题（P）和（）和（D）。）。在问题（在问题（P）中，令）中，令则问题（则问题（P）变为）变为上述问题等价于上述问题等价于同理，若令同理，若令问题（问题（D）等价于）等价于算算 例例解得，最优策略为（解得，最优策略为（1/3，0，2/3）和（）和（1/3，0，2/3），），最优值为最优值为7/3。Nash 均衡均衡对前面所述的二人有限零和博弈，其中的均衡解就是对前面所述的二人有限零和博弈，其中的均衡解就是Nash 均衡。均衡。下面，针对一般的下面，针对一般的n人博弈，给出人博弈，给出Nash均衡的定义。均衡的定义。博弈的标准式博弈的标准式：称：称叫做博弈的标准式，叫做博弈的标准式，其中，其中，Si为第为第i个局中人的策略集；个局中人的策略集；是每个局中人选定某一策略时形成的局势；是每个局中人选定某一策略时形成的局势；是相应于该局势的第是相应于该局势的第i个局中人的支付函数；个局中人的支付函数；Nash均衡均衡：在有：在有n个局中人的标准式个局中人的标准式中，如果局势中，如果局势满足：对每一个局中人满足：对每一个局中人i，是至少不劣于他针对其他是至少不劣于他针对其他n-1个局中人所选策略个局中人所选策略的最优反应策略，则称局势的最优反应策略，则称局势是该博弈的一个是该博弈的一个Nash均衡，即对任意的均衡，即对任意的，有，有或或是最优化问题是最优化问题的解。的解。结论结论：在任何非合作有限博弈中，都至少存在一个：在任何非合作有限博弈中，都至少存在一个Nash均衡。均衡。