对策论PPT讲稿.ppt

第1页，共32页，编辑于2022年，星期六齐王的赢得矩阵或益损值矩阵田忌的策略齐齐王王的的策策略略上中下上中下上下中上下中中上下中上下中下上中下上下中上下中上下上中下上中上 上 中 中 下 下中 下 上 下 中 上下 中 下 上 上 中 3 1 1 1 1 1 3 1 1 1 1 1 1 3 1 1 11 1 1 3 1 1 1 1 1 1 3 1 1 1 1 1 1 3 局势分析田忌整体上处于劣势，赢的概率只有1/6。田忌是否有机会赢得比赛？双方如何选择自己的策略是致关重要的双方如何选择自己的策略是致关重要的“田忌赛马田忌赛马”对策模型对策模型第2页，共32页，编辑于2022年，星期六其中：齐王的策略集其中：齐王的策略集: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 在齐王赛马的例子中在齐王赛马的例子中:第3页，共32页，编辑于2022年，星期六二人有限零和对策二人有限零和对策（又称（又称矩阵对策矩阵对策）：）：局中人为局中人为2 2；每个局中人的策略集的策略数目都是；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。同一局势的两个局中人的益损值之和为零。通常将矩阵对策记为通常将矩阵对策记为:G=S1,S2,A S1：甲的策略集；：甲的策略集；S2：乙的策略集；：乙的策略集；A：甲的赢得矩阵。甲的赢得矩阵。“田忌赛马田忌赛马”是一个矩阵策略。是一个矩阵策略。第4页，共32页，编辑于2022年，星期六 例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得赛共赛三局，规定每局胜者得1 1分，输者得分，输者得-1-1分，可知三赛三胜得分，可知三赛三胜得3 3分，三分，三赛二胜得赛二胜得1 1分，三赛一胜得分，三赛一胜得-1-1分，三赛三负得分，三赛三负得-3-3分。甲队的策略集为分。甲队的策略集为S S1 1=1 1，2 2，3 3，乙队的策略集为，乙队的策略集为S S2 2=1 1，2 2，3 3。根据以往比赛的资。根据以往比赛的资料，有甲队的赢得矩阵为料，有甲队的赢得矩阵为A A，如下所示，如下所示，纵向为纵向为 1 1 2 2 、3 3 请问这次比赛各队采用哪种阵容上场最为稳妥请问这次比赛各队采用哪种阵容上场最为稳妥?矩阵对策的最优纯策略矩阵对策的最优纯策略第5页，共32页，编辑于2022年，星期六矩阵矩阵A A中每行的最小元素分别为中每行的最小元素分别为1 1，-3-3，-1-1。在这些最少赢得中最好的结果是在这些最少赢得中最好的结果是1 1，故甲队会采取策略，故甲队会采取策略 1 1，无论对手采取何策略，无论对手采取何策略，甲队至少得甲队至少得1 1分。对于乙队，分。对于乙队，1 1，2 2，3 3 可能带来的最少赢得，即可能带来的最少赢得，即A A中每列的最中每列的最大元素，分别为大元素，分别为3 3，1 1，3 3。乙队会采取。乙队会采取 2 2策略，确保甲队不会超过策略，确保甲队不会超过1 1分。分。1 1和和 2 2分别称为局中人甲队、乙队的最优策略。由于双方必然选择这一种分别称为局中人甲队、乙队的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为策略，所以，这种策略又称为最优纯策略最优纯策略。这种最优纯策略只有当赢得矩阵这种最优纯策略只有当赢得矩阵A=A=（a aijij）中）中等式等式 先对列取大，再对最大值取小先对列取大，再对最大值取小成立时，双方才有最优纯策略，并把（成立时，双方才有最优纯策略，并把（1 1,2 2）称为对策）称为对策G G在纯策略下的解，又称在纯策略下的解，又称（1 1,2 2）为对策）为对策G G的的鞍点鞍点。把其值。把其值V V称之为对策称之为对策G=SG=S1 1，S S2 2，AA的值。的值。第6页，共32页，编辑于2022年，星期六X XY Y马鞍面马鞍面z=f(x,y)鞍点鞍点Z Z第7页，共32页，编辑于2022年，星期六 例例 某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗季气温条件下要消耗1515吨煤，在较暖和较冷的天气下要消耗吨煤，在较暖和较冷的天气下要消耗1010吨和吨和2020吨。吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为候条件下每吨煤价分别为1010元、元、1515元、元、2020元。又设秋季时煤炭价格为每吨元。又设秋季时煤炭价格为每吨1010元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？单位的支出最少？解：局中人解：局中人I I为采购员，局中人为采购员，局中人IIII为大自然，采购员有三个策略，买为大自然，采购员有三个策略，买1010吨、吨、1515吨、吨、2020吨。分别记为吨。分别记为 1 1，2 2，3 3。大自然也有三个策略：暖、正常、冷，。大自然也有三个策略：暖、正常、冷，分别记为分别记为 1 1，2 2，3 3。第8页，共32页，编辑于2022年，星期六赢得矩阵如下：赢得矩阵如下：在此表上计算，有在此表上计算，有 得得故（故（3 3，3 3）为对策）为对策G G的解，的解，V VG G=-200=-200。1231(10吨）-100-175-3002(15吨）-150-150-2503(20吨）-200-200-200123min1(10吨）-100-175-300-3002(15吨）-150-150-250-2503(20吨）-200-200-200-200*max-100-150-200*第9页，共32页，编辑于2022年，星期六n该对策的值该对策的值(即齐王的期望赢得值即齐王的期望赢得值)为为VG=1VG=1。这与我们的设想相符，即。这与我们的设想相符，即双方都以双方都以1/61/6的概率选取每个纯策略，或者说每个纯策略被选取的机会的概率选取每个纯策略，或者说每个纯策略被选取的机会应是均等的，则总的结局应该是：齐王有应是均等的，则总的结局应该是：齐王有5/65/6的机会赢田忌，赢得的期的机会赢田忌，赢得的期望值是望值是1 1千金。千金。n但如果齐王在每出一匹马前将自己的选择告诉了对方，这实际上但如果齐王在每出一匹马前将自己的选择告诉了对方，这实际上等于公开了自己的策略，如齐王选取出马次序为等于公开了自己的策略，如齐王选取出马次序为(上，中，下上，中，下)，则，则田忌根据谋士的建议便以田忌根据谋士的建议便以(下，上，中下，上，中)对之，结果田忌反而可得千金。对之，结果田忌反而可得千金。n因此，在矩阵对策不存在鞍点时，竞争的双方在开局前均应对自己的因此，在矩阵对策不存在鞍点时，竞争的双方在开局前均应对自己的策略策略(实际上是纯策略实际上是纯策略)加以保密，否则不保密的一方是要吃亏的。加以保密，否则不保密的一方是要吃亏的。田忌赛马矩阵策略分析第10页，共32页，编辑于2022年，星期六 设矩阵对策设矩阵对策 G=S1,S2,A。当当max min aij min max aij i j j I时，不存在最优纯策略。时，不存在最优纯策略。例：设一个赢得矩阵如下例：设一个赢得矩阵如下:min min 5 9 5 5 9 5 A=max 6 =max 6 策略策略 2 8 6 6 8 6 6 i i max 8 9 max 8 9 min 8 min 8 策略策略 1 j j 矩阵对策的混合策略矩阵对策的混合策略第11页，共32页，编辑于2022年，星期六 当甲取当甲取策略策略 2 2，乙取，乙取策略策略 1 1时，时，甲实际赢得甲实际赢得8比预期的多比预期的多2 2，乙当然乙当然不满意。考虑到甲可能取不满意。考虑到甲可能取策略策略 2 2这一点，乙采取策略这一点，乙采取策略 2 2。若甲也分析到。若甲也分析到乙乙可能采取策略可能采取策略 2 2这一点，取策略这一点，取策略 1 1，则赢得更多为则赢得更多为9 9 。此时，对两个局。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即乙没有执行上述原则的共同基础，即 max min aij min max aij。i j j i 一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）（乙）在各种情况下的平均赢得（损失）最多（最少）-即即混合策略混合策略。第12页，共32页，编辑于2022年，星期六 例：设甲使用策略例：设甲使用策略 1 1的概率为的概率为X1 1，使用策略，使用策略 2 2的概率为的概率为X2 ，并设在，并设在最坏的情况下，甲赢得的平均值为最坏的情况下，甲赢得的平均值为V（未知）。（未知）。5 9 A=STEP 1 8 6 1)1)X1+X2=1 X1,X2 0 第13页，共32页，编辑于2022年，星期六2)2)无论乙取何策略，甲的平均赢得应不少于无论乙取何策略，甲的平均赢得应不少于V:V:对乙取对乙取 1 1：5X5X1 1+8X+8X2 2 V V对乙取对乙取 2 2：9X9X1 1+6X+6X2 2 V V注意注意 V0,V0,因为因为A A各元素为正各元素为正。STEP 2 STEP 2 作变换：作变换：X X1 1=X=X1 1/V;X/V;X2 2=X=X2 2/V/V得到上述关系式变为：得到上述关系式变为：X X1 1+X+X2 2=1/V (V=1/V (V愈大愈好）待定愈大愈好）待定 5X5X1 1+8X+8X2 2 1 1 9X 9X1 1+6X+6X2 2 1 1 X X1 1,X,X2 2 0 0第14页，共32页，编辑于2022年，星期六建立线性模型：建立线性模型：min Xmin X1 1+X+X2 2（v v越大越好）越大越好）s.t.5Xs.t.5X1 1+8X+8X2 2 1 1 X X1 1=1/21=1/21 9 9X X1 1+6X+6X2 2 1 1 X X2 2=2/21=2/21 X X1 1,X,X2 2 0 1/V=0 1/V=X X1 1+X+X2 2=1/7=1/7 所以，所以，V=7 V=7 返回原问题：返回原问题：X X1 1=X X1 1V=1/3V=1/3 X X2 2=X X2 2V=2/3V=2/3于是甲的最优混合策略为：于是甲的最优混合策略为：以以1/31/3的概率选的概率选 1 1，以以2/32/3的概率选的概率选 2 2，最优值，最优值V=7V=7。第15页，共32页，编辑于2022年，星期六矩阵对策的解法(1)22(1)22矩阵对策的线性方程组法矩阵对策的线性方程组法 所谓所谓2222矩阵对策矩阵对策是指局中人是指局中人的赢得矩阵为的赢得矩阵为2222阶的，即阶的，即 A=A=a11 a12a11 a12 a21 a22 a21 a22 如果此对策有纯策略意义下的解，则很容易求解；如果没有如果此对策有纯策略意义下的解，则很容易求解；如果没有纯策略意义下的解，则为求出各局中人的最优混合策略可求解下纯策略意义下的解，则为求出各局中人的最优混合策略可求解下列方程组：列方程组：a a11x x1a a21x x2v av a11y y1a a12y y2v v a a12x x1a a22x x2v av a21y y1a a22y y2v v y y1y y21 x1 x1x x21 1当没有纯策略意义下的解时，方程组一定有严格非负解，即为各局中人的当没有纯策略意义下的解时，方程组一定有严格非负解，即为各局中人的最优混合策略。最优混合策略。第16页，共32页，编辑于2022年，星期六(2)2)线性规划法线性规划法 当对策的值大于当对策的值大于0 0时时,可利用线可利用线性规划法求解矩阵对策。构造两个线性性规划法求解矩阵对策。构造两个线性规划问题规划问题 min z min zxxi i a aijx xi1 (j=1,2,1 (j=1,2,n),n)i x xi0 (i=1,2,0 (i=1,2,m),m)max w max wyyj j a aijy yj1 (i=1,2,1 (i=1,2,m),m)j y yj0 (j=1,2,0 (j=1,2,n),n)不难验证，这两个线性规不难验证，这两个线性规划问题互为对偶问题。当它划问题互为对偶问题。当它们取得最优解时必然有相同们取得最优解时必然有相同的目标值。的目标值。设上述线性规划设上述线性规划问题的解为问题的解为x、y、z，则矩阵对则矩阵对策的解为：策的解为：对策的值对策的值 VG=1/z 局中人局中人的最优策略的最优策略 x*=VG x 局中人局中人的最优策略的最优策略 y*=VGy第17页，共32页，编辑于2022年，星期六两人有限非零和对策两人有限零和对策,对策的双方利益完全相反,但在现实生活的对策过程中经常出现一个局中人的所得并不一定等于另一局中人的所失.对于每一局势,两局中人的赢得之和不一定为零,这就是两人非零和对策.许多经济活动过程中的对策模型,很多是非零和的.下面简介两人有限非零和对策的数学模型及其解法.第18页，共32页，编辑于2022年，星期六例 甲、乙两家面包店在市场竞争中,各自都在考虑是否要降价,如果两家都降价,则各家可得3百元的利润；如果都不降价,则各家可得利润5百元；如果一家降价,另一家不降,是降价的一家可得利润6百元,不降价的一家由于剩余损坏等原因而亏损4百元.问双方应如何选择行动较为合理？第19页，共32页，编辑于2022年，星期六乙面包店甲面包店nb 1(降价)b 2(不降价)a 1(降价)(3,3)(6,-4)a 2(不降价)(-4,6)(5,5)36-45A=.3-465,B=双矩阵对策 第20页，共32页，编辑于2022年，星期六在这个对策中,两家面包店在没有互通信息非合作情况下,各自都有两种策略的选择,降价或不降价.显然,双方最好策略的选择都是降价,即(a 1,b 1).因为选择降价至少可得到3百元利润,如果选择不降价,则可能由于对方降价而蒙受4百元的损失.当然,在两店互通信息,进行合作的情况下,双方采取不降价的策略,各自都能从合作中多得2百元.第21页，共32页，编辑于2022年，星期六对策论的典型例子之二囚徒困境（1950年，塔克）甲乙两个嫌犯受到指控，但除非至少一个招认，否则警方不能将二两个嫌犯受到指控，但除非至少一个招认，否则警方不能将二人判有罪。警察把二人分别带到不同的房间，告之后果：人判有罪。警察把二人分别带到不同的房间，告之后果：如果二人均不坦白，将被判入狱如果二人均不坦白，将被判入狱1 1年。年。如果双方均坦白，将被判入狱如果双方均坦白，将被判入狱6 6年。年。如果一方招认，另一方不招，招认一方马上释放，另一方判入狱如果一方招认，另一方不招，招认一方马上释放，另一方判入狱9 9年。年。囚徒甲囚徒乙沉默招认沉默1，19，0招认0，96，6第22页，共32页，编辑于2022年，星期六关于案例，显然最好的策略是双方都抵赖，结果是大家都只被判1年。但是由于两人处于隔离的情况，首先应该是从心理学的角度来看，当事双方都会怀疑对方会出卖自己以求自保、其次才是亚当斯密的理论，假设每个人都是“理性的经济人”，都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程：假如他坦白，我抵赖，得坐9年监狱，坦白最多才6年；他要是抵赖，我就可以被释放，而他会坐9年牢。综合以上几种情况考虑，不管他坦白与否，对我而言都是坦白了划算。两个人都会动这样的脑筋，最终，两个人都选择了坦白，结果都被判6年刑期。第23页，共32页，编辑于2022年，星期六基于经济学中Rational agent的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被释放就不会出现。这样两人都选择坦白的策略以及因此被判6年的结局，纳什均衡”首先对亚当斯密的“看不见的手”的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论:从利己目的出发,结果损人不利己,既不利己也不利他。因为它不能满足人类的理性要求。囚徒困境所反映出的深刻问题是，人类的个人理性有时能导致集体的非理性聪明的人类会因自己的聪明而作茧自缚。第24页，共32页，编辑于2022年，星期六第25页，共32页，编辑于2022年，星期六第26页，共32页，编辑于2022年，星期六重复删除严格占劣策略的缺点：重复删除严格占劣策略的缺点：1.需要假定需要假定“参与者都是理性的参与者都是理性的”是公共知识是公共知识2.不可能总是存在严格占优策略不可能总是存在严格占优策略第27页，共32页，编辑于2022年，星期六第28页，共32页，编辑于2022年，星期六第29页，共32页，编辑于2022年，星期六第30页，共32页，编辑于2022年，星期六二维静态博弈 假设某两临近甲乙两村，道路不通，经济不好发展，若修路，需花费10万（一起修各出5万），修好后获得经济收益8万，那么损益矩阵如下：甲乙 修 不修 修 (-5+8,-5+8)(-10+8,8)不修 (8,-10+8)(0,0)也就是 甲乙 修 不修 修 (3,3)(-2,8)不修 (8,-2)(0,0)显然单独修谁修谁受损，再不允许沟通的情况下，俩村就会一直僵持下去 第31页，共32页，编辑于2022年，星期六练习例例 设赢得矩阵为A3，求解这个矩阵对策。参考答案：矩阵对策的一个解为第32页，共32页，编辑于2022年，星期六