对策论(课堂讲解)2.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第,10,章 对策论（博弈论）,2,10.1,对策论概论,日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为，例如下棋、打牌、体育比赛等。,还如战争活动中的双方、在政治上国际间的谈判、各种政治力量之间的斗争、经济生活中的各国之间、各公司之间的各种经济谈判、企业为争夺市场而进行的竞争、人与自然的竞争等。这类现象称作,“,对策现象,”,。,3,1,、对策论概论,对策论（,The Game Theory),也称竞赛论或博弈论，是研究具有竞争、对抗、斗争、利益分配等方面的问题，采用数量化方法，并提供寻求最优策略的途径。,对策现象的特点：,（,1,）参加人,利益互相冲突的双方或几方；,（,2,）结 局,取决于双方或几方所选择的策略。,所有可能的结局可用数量表示。,4,例,1,：田 忌 赛 马,齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负,1000,金。,田忌在好友、著名的军事谋略家孙膑的指导下，作以下安排：,齐王上中下,田忌下上中,最终净胜一局，赢得,1000,金。,5,三局的对局形势,田忌,齐王,上中下,上下中,中上下,中下上,下上中,下中上,上中下,3,2,2,2,1,2,上下中,2,3,2,2,2,1,中上下,2,1,3,2,2,2,中下上,1,2,2,3,2,2,下上中,2,2,2,1,3,2,下中上,2,2,1,2,2,3,6,例,2,：石头、剪子、布,甲、乙两人玩,“,石头、剪子、布,”,的游戏。游戏,规定为：,第一，每人每局比赛中，只能在石头、剪子、布三种出法中选一种；,第二，在一局比赛中，石头对剪子认为石头赢，剪子对布认为剪子赢，布对石头认为布方赢，如果双方都是同一种，则认为没有输赢。,这样一局比赛中，各方是赢是输，不仅与自己所采取的出法（亦称策略）有关，而且与对方所采取的出法有关,。,规定：赢得,1,分，输负,1,分，平局,0,分,7,每局的可能结果,乙,甲,石头,剪子,布,石头,0,1,-1,剪子,-1,0,1,布,1,-1,0,8,例,3:,现代实例,案例：俾斯麦海的海空对抗,1943,年,2,月，第二次世界大战中的日本，在太平洋战区已经处于劣势。为扭转局势，日本统帅山本五十六大将统率下的一支舰队策划了一次军事行动：由集结地,南太平洋的新不列颠群岛的蜡包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守在那里的日军。,9,当盟军获悉此情报后，盟军统帅麦克阿瑟命令太平洋战区空军司令肯尼将军组织空中打击。,日本统帅山本五十六大将心里很明白：在日本舰队穿过俾斯麦海的三天航行中，不可能躲开盟军的空中打击，他要策划的是尽可能减少损失。,日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划。,10,自然条件对于双方 都是已知的。基本情况如下：从蜡包尔出发开往莱城的海上航线有南北两条。通过时间均为,3,天。,气象预报表明：未来,3,天中，北线阴雨，能见度差；而南线天气晴好，能见度好。,肯尼将军的轰炸机布置在南线的机场，侦察机全天候进行侦察,，,但有一定的搜索半径,。,11,经测算，双方均可得到如下估计：,局势,1,：盟军的侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶劣，能见度差，盟军只能实施两天的轰炸。,局势,2,：盟军的侦察机重点搜索北线，日本舰队走南线。由于发现晚，尽管盟军的轰炸机群在南线，但有效轰炸也只有两天。,12,局势,3,：盟军的侦察机重点搜索南线，而日本舰队走北线。由于发现晚、盟军的轰炸机群在南线，以及北线气候恶劣，故有效轰炸只有一天。,局势,4,：盟军的侦察机重点搜索南线，日本舰队也恰好走南线。此时日本舰队迅速被发现，盟军的轰炸机群所需航程很短，加上天气晴好，有效轰炸时间三天。,13,这场海空遭遇与对抗一定会发生，双方的统帅如何决策呢？历史的实际情况是：局势,1,成为现实。肯尼将军命令盟军的侦察机重点搜索北线；而山本五十六大将命令日本舰队取道北线航行。由于气候恶劣，能见度差，盟军飞机在一天后发现了日本舰队，基地在南线的盟军轰炸机群远程航行，实施了两天的有效轰炸，重创了日本舰队，但未能全歼。,14,对策的三要素：,局中人,：有权决定自己行为方案的对局参加者称为局中人。案例中，美日双方的决策者为局中人。当对局中局中人只有两人时，称为二人对策。,策略,：对局中一个实际可行的方案称为一个策略。案例中，美日双方各有二个策略。,支付矩阵,：当每个局中人在确定了所采取的策略后，他们就会获得相应的收益或损失，此收益或损失的值称为支付。赢得与策略之间的对应关系称为支付函数。,案例中，肯尼将军与山本五十六大将的支付函数都可以用矩阵,A,、,B,表示。,15,（日军）,北线 南线,（盟军）北线,2 2,=A,南线,1 3,（日军）,北线 南线,（盟军）北线,-2 -2,=B,南线,-1 -3,16,在本例中的每一个对局，双方的赢得的代数之和为零，这样的对策称为“有限零和二人对策”,设两个局中人为,I,，,II,，局中人,I,有,m,个策略：,1,、,2,m,；,用,S1,表示这些策略的集合：,S1=,1,、,2,m,17,同样，局中人,II,有,n,个策略：,1,、,2,。,n,；用,S2,表示这些策略的集合：,S2=,1,、,2,n,局中人,I,的赢得矩阵是：,a11 a12 a1n,a21 a22 a2n,A=,a m 1 a m 2 a m n,18,局中人,II,的赢得矩阵是,-A,把一个对策记为,G,：,G=S1,，,S2,；,A,北线,1,南线,2,北线,1,2 2,（盟军）,=A,南线,2,1 3,19,在矩阵中，盟军的最大赢得是,3,，而要得到,3,，必须选择策略,2,，而日军的目的是使盟军的赢得尽量的小，必须选择策略,1,，使盟军的赢得只有,1,。,在局中人,I,设法使自己的赢得尽可能大的同时，局中人,II,也设法使局中人,I,的赢得尽可能小。,20,所以局中人,I,应首先考虑用,所能赢得的最小，然后在这些最小赢得中选择最大。局中人,I,可以保证赢得,max min aij,i j,同样，局中人,II,可以保证局中人,I,的赢得不超过,min max aij,j i,21,案例中局中人,I,（盟军）应当选择（北线）策略,1,，这样,能保证赢得,2,。局中人,II,（日军）应当选择（北线）策略,1,使,盟军赢得不超过,2,。实际上，在（,1,，,1,）局势下，有,max min aij=min max aij,i j j i,上式蕴涵的思想是朴素自然的，可以概括为：“,从最坏处着想，去争取最好的结果”,(,对于双方都是）（请大家回忆：不确定型决策时的最大最小决策）,22,2,、对策现象的要素,对策现象的要素：,局 中 人,二人或多人，,I=1,2,n,策略集合,可供局中人选择的一个实际可行的完整的行动方案。,参加对策的每,个,局中人,i,都有自己的策略集,合：,S,i,支付函数,在一局对策中，当局势给定以后，就用一个函数来表示得失（或输赢），,用,H,i,表示局中人,i,的支付函数,对策模型：,=,I=1,2,n,S,i,H,i,(S),i,I,其中，,S=,（,s,(1),，,s,(2),，,，,s,(n),）,是一个局势。,23,说明,在对策中总是假定每一个局中人都是理智的，聪明的决策者或竞争者（即不存在利用其它局中人决策的失误，来扩大自身利益的可能性）,当局势出现后，对策结果也就确定了，即对任一局势,sS,，局中人,I,可能得到一个赢得,H,（,s,）。,一个对策模型由,局中人、策略、支付函数这,三个基本因素确定。,24,例,1,田忌赛马,齐王赛马,局中人,齐,王和田忌,策 略,上,中下三种等级的马的组合，比三次，有六组策略：,(,上，中，下,),、,(,中，上，下,),、,(,上，下，中,),、,(,中，下，上,),、,(,下，上，中,),、,(,下，中，上,),支付函数,赢,了得一千金，输了付一千金,25,田忌,齐王,上中下,上下中,中上下,中下上,下上中,下中上,上中下,3,1,1,1,-1,1,上下中,1,3,1,1,1,-1,中上下,1,-1,3,1,1,1,中下上,-1,1,1,3,1,1,下上中,1,1,1,-1,3,1,下中上,1,1,-1,1,1,3,齐王的赢得（支付）矩阵：,26,例,2,石头、剪子、布,甲的赢得矩阵：,乙,甲,石头,剪子,布,石头,0,1,-1,剪子,-1,0,1,布,1,-1,0,27,3,、对策问题的分类,对策,静态对策,动态对策,合作对策,不合作,对策,两人对策,多人对策,零和对策,非零和对策,纯策略对策,混合策略对策,有限策略对策,无限策略对策,28,10,.2,两人有限零和对策,非合作,局中人：,2,个，每个人的策略有限。,策略集：,S,1,=,1,2,m,，,S,2,=,1,2,n,支付函数：,H,1,+H,2,=0,，则,H,1,=,a,ij,，,H,2,=-,a,ij,可用矩阵表示为：,A=,（,a,ij,），,其中,行的数目表示局中人,1,的策略个数；列的数目代表局中人,2,的策略个数；用,a,ij,表示局中人,1,在局势（,i,j,）时的支付，,-,a,ij,表示局中人,2,在局势（,i,j,）时的支付。,矩阵对策：,=S,1,，,S,2,；,A,29,1,、策略选择,最稳妥的策略：,一个局中人采取各种各样策略时，最不利情况是什么，而从这些最不利的情况中，选择其中最有利的一个。即：,局中人,1,：,局中人,2,：,30,2,、对策的解,矩阵对策,=S,1,，,S,2,；,A,，如果存在局势（,i*,j*,）满足（定理,10.2.1P311),：,则称（,i*,j*,）是对策,的解。,i*,j*,分别是局中人,1,，,2,的,最优策略（也称为纯策略），,v=a,i*j*,称为对策,的值（也称为鞍点）。,31,P310,例,种菜,P,310,自然,人,1,2,3,4,5,6,1,192460,235120,278200,156360,197520,242840,2,189560,231700,273630,155620,195600,239710,3,192060,234799,277095,158235,198580,243280,4,194370,237218,280751,158475,199813,245362,5,194360,238990,281385,157835,199750,246020,32,3,、问题举例,例,1,、采购问题,局中人,采,购员和气候,策略,气,候：偏暖、正常、偏冷；采购员：秋天购煤,1000,、,1500,、,2000,吨,支付函数,秋,天购买价格为,200,元,/,吨，冬天再购买价格是,300,元,/,吨。,-20,万,-35,万,-50,万,-30,万,-30,万,-45,万,-40,万,-40,万,-40,万,气候,偏暖 正常 偏冷,1000,采购员,1500,2000,两人、有限、非合作、零和对策,33,例,2,、甲、已两企业生产同一种电子产品，两企业都想通过改革措施争取更多的市场份额。,甲企业的措施有：,（,1,）降价；（,2,）提高产品质量，处长保修期；（,3,）推出新产品。,乙企业的措施有：,（,1,）增加广告费用；（,2,）增设维修点；（,3,）改进产品性能。,假定市场份额,一定且通过预测可,知，两企业的市场,占有变动如表。试,通过对策分析，确,定两个企业各自的,最优策略。,乙,甲,1,2,3,1,10,-1,3,2,12,10,-5,3,6,8,5,34,例,3,、一个病人的症状说明他可能患,a,、,b,、,c,三种病中的一种，有两种药,A,与,B,可用。,A,的治愈率为,0.5,，,0.4,，,0.6,；,B,的治愈率为,0.7,，,0.1,，,0.8,。问医生应开哪种药才能最稳妥？,病人,医生,a,b,c,A,0.5,0.4,0.6,B,0.7,0.1,0.8,35,例,4,、甲、乙两队进行乒乓球团体赛，每队都由三名球员组成。双方可排出三种不同的阵容，每一种阵容可以看成一种策略，,根据以往的比赛记录，相应的支付矩阵为 ，那么这次比赛双方各采用哪种阵容上场最稳妥？,36,4,、具有混合策略的矩阵对策,该矩阵对策在纯策略下无解。此时，用最大最小原则来选取各自的纯策略都不会是稳定的，因为各局中人可以选取其它的纯策略来改善自己的赢得值。,37,在上述双方都不能固定采用任何一个纯策略下，必须随机地选取自己的各个纯策略，使双方捉摸不到自己使用的策略，以求得自己的期望赢得最大（或期望损失最小）。在上例中，若局中人,1,以概率,x,选用,1,以概率,1-x,选用,2,局中人,2,以概率,y,选,1,以概率,1-y,选,2,，则局中人,1,的期望赢得为,=8xy,6y,x+8,=,38,5,、矩阵对策的解,二人对策时、局中人的策略也分别只有,2,个时用上述方法求解是可以的。但碰到,n,个人的情况呢？我们有两种方法可以求解：,1,）碰到较为特殊的情形，可以进行简化求解；,2,）碰到更一般的情形，利用线性规划的对偶法求解；,39,5.1,矩阵对策的简化,实际上，能简化的矩阵都是一些比较特殊的矩阵，而且，我们马上要讲的第二种方法：线性规划方法已经包含了这种方法，而且书上也只是简单地讲了一下，一种纯策略被另一纯策略优超的情形同学们很容易看懂。另外一种一种纯策略被另外若干个纯策略的凸线性组合所优超的情形，书上没仔细讲。有兴趣的同学请参阅：南通职业大学学报,1993,年第,3,期陈斌发表的：,“,矩阵对策中纯策略可被优超的充要条件,”,一文。,40,优 超,41,算 例（书本,P314,）,42,简 化,43,简 化,44,课堂练习,45,5.2,矩阵对策的解法之二：线性规划方法,已学过的方法在解二阶矩阵时或特殊的高阶矩阵时能用，但碰到一般的高阶时就会束手无策。对此，我们可以将矩阵对策化为一对对偶规划问题进行求解。,课堂讲解（,1,、原理（,P315,）；,2,、方法（,P317,）。注意构造对偶线性规划时的两个方面：求极小对应于以列构造的大于不等式组，反之，求极大对应于以行构造的小于不等式组，然后求解）,46,例 对给定的赢得矩阵,A,A,1,=,（,aij+2,）,0 1 -1 2 3 1,A=-1 0 1 A,1=,1 2 3,1 -1 0 3 1 2,47,（,LP,）,min,（,p1+p2+p3,）,2p1+p2+3p3 1,3p1+2p2+p3 1,p1+3p2+2p3 1,pi 0,(i=1,2,3),48,(DLP)max,（,q1+q2+q3,）,2q1+3q2+q3 1,q1+2q2+3q3 1,3q1+q2+2q3 1,qj 0 (j=1,2,3),且 ,pi=qj=1/V,49,利用单纯形法可求出：,P*=,（,1/6,，,1/6,，,1/6,）,Q*=,（,1/6,，,1/6,，,1/6,）,p1+p2+p3=1/6+1/6+1/6=1/2=1/,V,V,=2,原问题的解：,X*=,V,P*=,（,1/3,，,1/3,，,1/3,）,Y*=,V,Q*=,（,1/3,，,1/3,，,1/3,）,对策值,V G*=,V,-2=0,50,10,.3,两人有限非零和对策,在许多对策问题中，对策双方的得失之和并不等于零，即局中人一方的得并不等于另一方得失，这就是两人有限非零和对策。,如两家企业竞争某种商品的市场占有率，当他们采取某些策略时，有可能产生双赢的结果。,51,1,、两人有限非零和对策的数学模型,例,1,甲、乙两家面包店在市场竞争中，各自都在考虑是否要降价，如果两家都降价，则各家可得,3,百元的利润，如果都不降价，则各家可得利润,5,百元，如果一家降价，另一家不降，则降价的一家可得利润,6,百元，不降价的一家由于剩余损坏等原因而亏损,4,百元，问双方应如何选择行动较为合理？,52,甲面包店,乙面包店,1,（降价）,2,（不降价）,1,（降价）,（,3,，,3,）,（,6,，,4,）,2,（不降价）,（,4,，,6,）,（,5,，,5,）,依题意，把上述问题表述成如下表格：,这个问题的数学模型可表示为：,问题表示,53,两人有限非零和对策的数学模型 一般形式,一般地，两人有限非零和对策的数学模型可表示为,54,随着,A,B,的确定，两人有限非零和对策也就确定，因此两人有限非零和对策又称为双矩阵对策。特别，当,A=-B,时，双矩阵对策就是矩阵对策。,在上述这个竞争对策中，两家面包店在没有互通信息非合作情况下，各自都有两种策略的选择，降价或不降价。显然，双方最好策略的选择都是降价，即（,1,，,1,）。,因为选择降价至少可以得到,3,百元的利润，如果选择不降价，则可能由于对方降价而蒙受,4,百元的损失。当然，在两店互通信息，进行合作的情况下，双方采取不降价的策略，各自都能得到,5,百元的利润。,分析,55,2,、非合作两人对策的解法,在这里所讨论的两人有限非零和对策中，假定对策双方都了解对方的纯策略集和赢得函数，但不合作，并且局中人在选择自己的策略时不知道对方的选择。,（,1,）非合作两人对策的解,纳什均衡,一般地，对于非合作两人对策,S,1,S,2,;(A,B),如果,i,*S,1,j,*S,2,分别是局中人,1,和,2,的最优纯策略，则称局势,(,i,*,j,*),是一个纳什均衡,.,56,纳什均衡指的是这样一种战略组合，,这种策略组合由所有参与人最优策略组成,。,即在给定别人策略的情况下，没有人有足够理由打破这种均衡。纳什均衡，从实质上说，是一种非合作博弈状态。,57,纳什均衡经典案例：囚徒困境（与前面两个面包店的例子类似，但这个更为著名）,假设有两个小偷,A,和,B,联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑,8,年；如果另一个犯罪嫌人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑,2,年，而坦白者有功被减刑,8,年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱,1,年。下表给出了这个博弈的支付矩阵。,58,甲,乙,坦白,抵赖,坦白,（,-8,，,-8,）,（,0,，,10,）,抵赖,（,10,，,0,）,（,-1,，,-1,）,59,关于案例，显然最好的策略是双方都抵赖，结果是大家都只被判,1,年。但是由于两人处于隔离的情况，首先应该是从心理学的角度来看，当事双方都会怀疑对方会出卖自己以求自保、其次才假设每个人都是,“,理性的经济人,”,，都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程：假如他坦白，我抵赖，得坐,10,年监狱，坦白最多才,8,年；他要是抵赖，我就可以被释放，而他会坐,10,年牢。综合以上几种情况考虑，不管他坦白与否，对我而言都是坦白了划算。两个人都会动这样的脑筋，最终，两个人都选择了坦白，结果都被判,8,年刑期。,60,基于经济学中理性经济人的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被释放就不会出现。这样两人都选择坦白的策略以及因此被判,8,年的结局，纳什均衡,”,首先对亚当,斯密的,“,看不见的手,”,的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从,“,纳什均衡,”,中引出,“,看不见的手,”,原理的一个悖论：从利己目的出发，结果损人不利己，既不利己也不利他。,因此博弈论的出现深刻地改变了经济学！,61,求解非合作两人对策的纳什均衡解的步骤,1,、在双矩阵对策（,A,B),表中，对于矩阵,A,的每列，分别找出赢得最大的数字，并在其下划一横线；,2,、在双矩阵对策（,A,B),表中，对于矩阵,B,的每行，分别找出赢得最大的数字，并在其下划一横线；,3,、如果表中某格的数字下面都被划上横线，则此格对应于两个局中人相应策略的组合就是一个（纯策略下的）纳什均衡。否则，该对策不存在纯策略下的纳什均衡。,例如：,甲面包店,乙面包店,1,（降价）,2,（不降价）,1,（降价）,（,3,，,3,）,（,6,，,4,）,2,（不降价）,（,4,，,6,）,（,5,，,5,）,62,（,2,）混合策略纳什均衡,上面所介绍的非合作两人有限对策是在纯策略下有解的对策问题，其特点是纳什均衡中的策略是每一个局中人的一个完整策略。,但是有些对策并不存在纯策略下的纳什均衡，如：,63,混合策略纳什均衡问题举例,例,2,、局中人是政府和一个流浪汉，流浪汉有两个策略：寻找工作或游荡；政府也有两个策略：救济或不救济。政府帮助流浪汉的前提是后者必须试图寻找工作；否则，前者不予帮助；而流浪汉只有在得不到救济时才会寻找工作。下表给出了对策的赢得双矩阵：,流浪汉,政府,1,（寻找工作）,2,（游荡）,1,（救济）,（,3,，,2,）,（,1,，,3,）,2,（不救济）,（,1,，,1,）,（,0,，,0,）,因此，在这个对策问题中，没有一个纯局势可以构成纯策略下的纳什均衡。为求得纳什均衡，必须对矩阵加以扩充。,64,设,A,B,分别为局中人,1,和,2,的赢得矩阵，且皆为,m,n,矩阵，局中人,1,，,2,的混合策略集为：,如果一个混合策略组合（,X*,Y*,）同时满足,则称策略组合,局势（,X*,Y*,）是一个混合策略纳什均衡。,混合策略纳什均衡问题,一般模型,65,对于上述例题，假定政府以概率,x,选择救济，以概率,1-x,选择不救济，即政府的混合策略为,(x,1-x),，流浪汉以概率,y,选择寻找工作，以概率,1-y,选择游荡，即流浪汉的混合策略为,(y,1-y),。那么政府的期望赢得函数为：,用微分求极值的方法：,这就是说，在混合策略中，流浪汉在对付给定政府的混合策略下，最优策略是以,1/5,的概率选择寻找工作，,4/5,的概率选择游荡，即,Y*=(1/5,4/5),66,同样流浪汉的期望赢得函数为：,用微分极值法求：,即在混合策略均衡中，政府在对付给定流浪汉的混合策略下，最优策略是,X*=(1/2,1/2),。,由于纳什均衡要求每个局中人的混合策略是在给定对方的混合策略下的最优选择，因此，由,x*=(1/2,1/2),和,Y*=(1/5,4/5),构成的,(x*,Y*),是唯一的纳什均衡。且此时赢得函数值为：,E,A,(X,Y)=-1/5,E,B,(X,Y)=3/2,。,