第15章 对策论ppt课件.ppt

经济与管理学院 何宜军,第15章 对策论,管理运筹学,第一节 对策论的基本概念 第二节 矩阵对策的最优纯策略 第三节 矩阵对策的混合策略 第四节 其他类型的对策论简介,提纲,齐王赛马,齐王与大将田忌商议赛马，双方约定：各自出上、中、下三种等级的马各一匹。每轮举行三场对抗赛。输者每输一场要付给胜者黄金一千两。由于田忌的马比齐王同等级的马都要略逊一筹，而在头一轮的比赛中，双方都是用同等级的马进行对抗，所以齐王很快赢了全部三场，得到了三千两黄金。鉴于第一次赛马的惨败，所以当齐王满面春风地再次邀请田忌赛马时，田忌感到很为难。一方面君王旨意不好违背，另一方面自己对这种必败的比赛失去了信心。田忌的军师孙膑是颇有才能的军事家，他得知后，便替田忌出了一个主意：用自己的下等马和国王的上等马比赛，而用自己的上等马和国王的中等马比赛，中等马和国王的下等马比赛。比赛开始，第一场国王的马以极大的优势取得了胜利。国王没有料到田忌的马竟然如此不堪一击，为此俯仰大笑，得意不已。但美景不长，在二、三场中田忌的马都取得了胜利。这一轮国王不但没赢，反而输了一千金。可笑的是，齐王输了钱还弄不清自己是怎样输的呢！,1 对策论的基本概念,对策模型的三个基本要素：1.局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集；3.一局势对策的益损值：局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果（量化）称为该局势对策的益损值。,“齐王赛马”齐王在各局势中的益损值表（单位：千金）,1 对策论的基本概念,其中：齐王的策略集: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,1 对策论的基本概念,二人有限零和对策（又称矩阵对策）：局中人为2；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。通常将矩阵对策记为:G=S1,S2,A S1：甲的策略集；S2：乙的策略集；A：甲的赢得矩阵。“齐王赛马”是一个二人有限零和矩阵对策。,1 对策论的基本概念,在甲方的赢得矩阵中：A=aijmni 行代表甲方策略 i=1,2,m；j 行代表乙方策略 j=1,2,n；aij 代表甲方取策略 i，乙方取策略 j，这一局势下甲方的益损值。此时乙方的益损值为-aij（零和性质）。在考虑各方采用的策略时，必须注意一个前提，就是双方都是理智的，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。,2 矩阵对策的最优纯策略,例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1=1，2，3，乙队的策略集为S2=1，2，3。根据以往比赛的资料，有甲队的赢得矩阵为A，如下所示，请问这次比赛各队采用哪种阵容上场最为稳妥?,2 矩阵对策的最优纯策略,矩阵A中每行的最小元素分别为1，-3，-1。在这些最少赢得中最好的结果是1，故甲队会采取策略1，无论对手采取何策略，甲队至少得1分。对于乙队，1，2，3可能带来的最少赢得，即A中每列的最大元素，分别为3，1，3。乙队会采取2策略，确保甲队不会超过最坏的结果1分。1和2分别称为局中人甲队、乙队的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。这种最优纯策略只有当赢得矩阵A=（aij）中等式 成立时，双方才有最优纯策略，并把（1,2）称为对策G在纯策略下的解，又称（1,2）为对策G的鞍点。把其值V称之为对策G=S1，S2，A的值。,2 矩阵对策的最优纯策略,例2 某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗15吨煤，在较暖和较冷的天气下要消耗10吨和20吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元。又设冬季时煤炭价格为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？解：局中人I为采购员，局中人II为大自然，采购员有三个策略，买10吨、15吨、20吨。分别记为1，2，3。大自然也有三个策略：暖、正常、冷，分别记为1，2，3。,2 矩阵对策的最优纯策略,赢得矩阵如下：在此表上计算，有 得故（3，3）为对策G的解，VG=-200。,2 矩阵对策的最优纯策略,设矩阵对策 G=S1,S2,A。当 时，不存在最优纯策略。例：设一个赢得矩阵如下:min 5 9 5 A=8 6 6 max 8 9,3 矩阵对策的混合策略,当甲取策略2，乙取策略1时，甲实际赢得8比预期的多2，乙当然不满意。考虑到甲可能取策略2这一点，乙采取策略2。若甲也分析到乙可能采取策略2这一点，取策略1，则赢得更多为9。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即 max min aij min max aij。i j j i 一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-即混合策略。,3 矩阵对策的混合策略,求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等，我们这里只介绍线性规划法，其他方法略。例：设甲使用策略1的概率为X1，使用策略2的概率为X2，并设在最坏的情况下，甲赢得的平均值为V（未知）。5 9 A=STEP 1 8 6 1)X1+X2=1 X1,X20,3 矩阵对策的混合策略,2)无论乙取何策略，甲的平均赢得应不少于V:对乙取1：5X1+8X2 V对乙取2：9X1+6X2 V注意 V0,因为A各元素为正。STEP 2 作变换：X1=X1/V;X2=X2/V得到上述关系式变为：X1+X2=1/V(V愈大愈好）待定 5X1+8X21 9X1+6X21 X1,X20,3 矩阵对策的混合策略,建立甲的线性模型：min X1+X2 s.t.5X1+8X21 X1=1/21 9X1+6X21 X2=2/21 X1,X20 1/V=X1+X2=1/7 所以，V=7 返回原问题：X1=X1V=1/3 X2=X2V=2/3于是甲的最优混合策略为：以1/3的概率选1，以2/3的概率选2，最优值V=7。,3 矩阵对策的混合策略,同样可求乙的最优混合策略：设乙使用策略1的概率为Y1 Y1+Y2=1设乙使用策略2的概率为Y2 Y1,Y20 设在最坏的情况下，甲赢得的平均值为V。这也是乙损失的平均值，越小越好。作变换：Y1=Y1/V，Y2=Y2/V 建立乙的线性模型：max Y1+Y2 s.t.5Y1+9Y21 Y1=1/14 8Y1+6Y21 Y2=1/14 Y1,Y20 1/V=Y1+Y2=1/7 所以，V=7,3 矩阵对策的混合策略,返回原问题：Y1=Y1V=1/2 Y2=Y2V=1/2于是乙的最优混合策略为：以 的概率选1；以 的概率选2，最优值 V=7。当赢得矩阵中有非正元素时，V0 的条件不一定成立，可以作下列变换：选一正数 k，令矩阵中每一元素加上 k 得到新的正矩阵A，其对应的矩阵对策G=S1,S2,A 与 G=S1,S2,A 解相同，但VG=VG k。,3 矩阵对策的混合策略,例：求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解，可求其混合策略。A中有负元素，可以取k=2,在A的每个元素上加2得到A如下：,3 矩阵对策的混合策略,建立对G=S1，S2，A中求甲方最佳策略的线性规划如下：Min x1+x2+x3+x4+x5+x6 约束条件：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.111,v=3,x1=x4=x5=0，x2=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=V=3。,3 矩阵对策的混合策略,同样可以建立对策G=S1，S2，A中求乙方最佳策略的线性规划如下：Max 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。所以田忌的最优混合策略为作出策略1、4、5的概率都为1/3,而作出2，3，6的概率为0，此时VG=VG-k=1。,3 矩阵对策的混合策略,齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3,0,0,1/3)T，Y*=(1/3,0,0,1/3,1/3,0)T，对策值VG=1。例3 两个局中人进行对策，规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。解：首先计算局中人甲的赢得矩阵如下表：,4-56,-34-5,2-34,1（出1）2（出2）3（出3）,3（出3）,2（出2）,1（出1）,甲的赢 得甲的策略,乙的策略,3 矩阵对策的混合策略,即甲的赢得矩阵为A：可知无纯策略意义的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立线性规划模型如下：Min x1+x2+x3 Max y1+y2+y3 S.T.8x1+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,3 矩阵对策的混合策略,得到x1=0.25,x2=0.50,x3=0.25；y1=0.25,y2=0.50,y3=0.25。即此对策的解为X*=(0.25,0.50,0.25)T，Y*=(0.25,0.50,0.25)T。VG=VG-k=0。,3 矩阵对策的混合策略,例4 甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有:(1)降低产品价格；(2)提高产品质量；(3)推出新产品。乙企业考虑采取的策略措施有(1)增加广告费用；(2)增设维修网点，加强售后服务；(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。,3-58,-6510,108-12,1（措施1）2（措施2）3（措施3）,3（措施3）,2（措施2）,1（措施1）,甲的赢 得甲的策略,乙的策略,3 矩阵对策的混合策略,解：易知此对策无纯策略意义下的解。把A的每一个元素加上12，得到A建立线性规划模型如下：Min x1+x2+x3 Max y1+y2+y3 S.T.22x1+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=0.023；y1=0.0225,y2=0.0225,y3=0.025。V=14.29。x1=0.3858,x2=0.2858,x3=0.3286；y1=0.3215,y2=0.3215,y3=0.3572。即此对策的解为 X*=(0.3858,0.2858,0.3286)T,Y*=(0.3215,0.3215,0.3572)T。VG=VG-k=2.29。,3 矩阵对策的混合策略,【优超原则】假设矩阵对策 G=S1,S2,A 甲方赢得矩阵 A=aijmn若存在两行（列），s 行（列）的各元素均优于 t 行（列）的元素，即asjatj j=1,2 n(ais ait i=1,2 m)称甲方策略s优超于t(s优超于t)。优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。如此得到阶数较小的赢得矩阵A，其对应的矩阵对策G=S1,S2,A 与 G=S1,S2,A 等价，即解相同。,3 矩阵对策的混合策略,例.设甲方的益损值，赢得矩阵为 3 2 0 3 0 被第3、4行所优超 5 0 2 5 9 被第3行所优超A=7 3 9 5 9 4 6 8 7 5.5 6 0 8 8 3得到 7 3 9 5 9 被第1列所优超A1=4 6 8 7 5.5 被第2列所优超 6 0 8 8 3,3 矩阵对策的混合策略,行划去小的行,列划去大的列,得到 7 3 9 A2=4 6 5.5 6 0 3 被第1行所优超得到 7 3 9 被第1列所优超 A3=4 6 5.5 7 3最终得到 A4=4 6,3 矩阵对策的混合策略,行划去小的行,列划去大的列,对A4计算，用线性规划方法得到：（注意：余下的策略为3，4，1，2）甲：X*=(0，0，1/15，2/15，0)T V=5 X*=(0，0，1/3，2/3，0)T 乙：Y*=(1/10，1/10，0，0，0)T V=5 Y*=(1/2，1/2，0，0，0)T。【注意】利用优超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；线性规划求解时有可能是多解问题。,3 矩阵对策的混合策略,4 其他类型的对策论简介,在对策论中可以根据不同方式对对策问题进行分类，通常分类的方式有（1）根据局中人的个数，分为二人对策和多人对策；（2）根据各局中人的赢得函数的代数和是否为零，可分为零和对策和非零和对策；（3）根据局中人是否合作，又可分为合作对策和非合作对策；（4）根据局中人的策略集中个数，又分为有限对策和无限对策（或连续对策）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策。本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。,一、完全信息静态对策 该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为纳什均衡。下面以著名的“囚徒困境”来进一步阐述。,4 其他类型的对策论简介,一、完全信息静态对策 例1“囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来判决。如图1-1所示。,4 其他类型的对策论简介,图1-1 囚徒困境,由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，(坦白，坦白)就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成协议。囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。,4 其他类型的对策论简介,二、完全信息动态对策 在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。,4 其他类型的对策论简介,二、完全信息动态对策 例2 某行业中只有一个垄断企业A，有一个潜在进入者企业B。B可以选择进入或不进入该行业这两种行动，而A当B进入时，可以选择默认或者报复两种行动。如果B进入后A企业报复，将造成两败俱伤的结果，但如果A默认B进入，必然对A的收益造成损失。同样的，如果B进入而A报复，则B受损，反之，将受益。把此关系用图1-2表示。,4 其他类型的对策论简介,由分析可知，上例中（B选择不进入，A选择报复）和（B选择进入，A选择默许）都是纳什均衡解。但在实际中，（B选择不进入，A选择报复）这种情况是不可能出现的。因为B知道他如果进入，A只能默许，所以只有（B选择进入，A选择默许）会发生。或者说，A选择报复行动是不可置信的威胁。对策论的术语中，称（A选择默许，B选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为精炼纳什均衡。当然，如果A下定决心一定要报复B，即使自己暂时损失。这时威胁就变成了可置信的，B就会选择不进入，（B选择不进入，A选择报复）就成为精炼纳什均衡。军事交战时，“破釜沉舟”讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。,4 其他类型的对策论简介,三、多人非合作对策 有三个或三个以上对策方参加的对策就是“多人对策”。多人对策同样也是对策方在意识到其他对策方的存在，意识到其他对策方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人对策同样的思路和方法来研究它们，或将两人对策的结论推广到多人对策。不过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，因此，策略的相互依存关系也就更为复杂，对任一对策方的决策引起的反应也就要比两人对策复杂得多。并且，在多人对策中还有一个与两人对策有本质区别的特点，即可能存在“破坏者”。所谓破坏者即一个对策中具有下列特征的对策方：其策略选择对自身的得益没有任何影响，但却会影响其它对策方的得益，有时这种影响甚至有决定性的作用。例如有三个城市争夺某届奥运会的主办权。,4 其他类型的对策论简介,多人对策可以分为合作的和非合作的。非合作对策顾名思义，就是局中人之间不存在合作，即各局中人在采取行动之前，没有事前的交流和约定，在其行为发生相互作用时，也不会达成任何有约束力的协议。每个局中人都选择于已最有利的策略以使效用水平最大化。然而，在非合作对策中，双方的利益也并非是完全冲突的，即对一个局中人有利的局势并不一定对其他局中人一定不利，故多人非合作对策不一定是零和对策。如同矩阵对策中纯策略意义下的解有时不存在一样，有些非合作对策也不存在纯策略纳什均衡。在这种情况下，局中人就必须考虑混合策略。,4 其他类型的对策论简介,四、非零和对策 所谓零和对策，就是一方的收益必定是另一方的损失。这种对策的特点是不管各对策方如何决策，最后各对策方得益之和总是为零。有某些对策中，每种结果之下各对策方的得益之和不等于0，但总是等于一个非零常数，就称之为“常和对策”。当然，可以将零和对策本身看作是常和对策的特例。“零和对策”和“常和对策”之外的所有对策都可被称为“非零和对策”。非零和对策即意味着在不同策略组合（结果）下各对策方的得益之和一般是不相同的。如前述囚徒困境就是典型的非零和对策。应该说，非零和对策是最一般的对策类型，而常和对策和零和对策都是它的特例。在非零和对策中，存在着总得益较大的策略组合和总得益较小的策略组合之间的区别，这也就意味着在对策方之间存在着互相配合，争取较大的总得益和个人得益的可能性。两人零和对策是完全对抗性的，总得益为0，其解法可能性根据矩阵对策予以求解，但在非零和对策下，矩阵对策求解法已经不适用了，下面用例子予以说明。,4 其他类型的对策论简介,例3 甲乙两公司生产同一产品，均想以登广告扩大产品销售，每家公司都有“登”与“不登”两种策略，双方的得益矩阵如下。,我们根据得益矩阵来分析。从甲公司立场上看，登有利，不管乙公司如何，保证赢利至少是3，最多是9。如果不登，可能要蒙受损失2。从乙公司的立场上看，同样理由，还是登广告好。但是，这是从理智行为出发的策略，是以彼此不能合作为前提的。上述两公司均采取登广告的策略是稳定的结局。可是，如果彼此能够合作，而都不登广告，免去了广告费，反而各自的赢利要多。在彼此不能合作的情况下，如果甲不登，恰好乙登，甲只好出现败局，这是非理智的策略，带有危险性。因此，非零和对策常常不易获得最理想的答案。对于三个以上的多人零和对策，互相利害关系更加复杂。,4 其他类型的对策论简介,谢谢大家,就到这里吧！,