数学建模第十讲博弈模型

1、第十讲第十讲 对策模型对策模型10.1 二人零和对策模型二人零和对策模型 10.2 进攻与撤退的选择进攻与撤退的选择10.3 二人常数和对策模型二人常数和对策模型10.4 二人非常数和对策模型二人非常数和对策模型对策行为对策行为问题一问题一: 甲、乙两名儿童玩甲、乙两名儿童玩“石头石头剪子剪子布布”的游戏。石的游戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？如何做，使自己获胜的可能最大？问题分析：问题分析：问题中所涉及的要素问题中所涉及的要素 （1）游戏决定者游戏决定者甲、乙儿童两人；甲、乙儿童两人； （3）游戏

2、的收益游戏的收益（支付支付）-胜得分为胜得分为 1，负得分为负得分为-1，平得分为平得分为 0 。 （2）游戏者的决定游戏者的决定石头石头、剪子剪子、布；布；问题二问题二:囚徒困境囚徒困境 甲乙两个嫌疑犯因同一罪行被逮捕甲乙两个嫌疑犯因同一罪行被逮捕,如果双方均如果双方均坦白，则各获刑坦白，则各获刑3年，如果双方均不坦白，则各获刑年，如果双方均不坦白，则各获刑2年，如果其中一人坦白，另一人不坦白，则坦白一方年，如果其中一人坦白，另一人不坦白，则坦白一方宽大释放，另一方获刑宽大释放，另一方获刑5年，两个嫌疑犯各自应采取年，两个嫌疑犯各自应采取什么策略才能使自己的刑期最短。什么策略才能使自己的刑期

3、最短。问题分析：问题分析：问题中所涉及的要素问题中所涉及的要素 （1）决定者决定者甲、乙嫌疑犯两人；甲、乙嫌疑犯两人； （3）甲乙的收益甲乙的收益（支付支付）-获刑年数获刑年数 。 （2）可用的决定可用的决定坦白坦白、不坦白；不坦白；对策行为的三要素对策行为的三要素1局中人局中人 在一个对策行为中，有权决定自己行动方案的对在一个对策行为中，有权决定自己行动方案的对策参加者，称为策参加者，称为局中人局中人。通常用。通常用I表示局中人的集合。表示局中人的集合。如果如果n个局中人，则个局中人，则I=1，2，n。它可以是一个。它可以是一个人，也可以是一个集团或一个自然现象。人，也可以是一个集团或一个自

4、然现象。2策略集策略集 一局对策中，可供局中人选择的一个实际可行一局对策中，可供局中人选择的一个实际可行的完整的行动方案，称为一个的完整的行动方案，称为一个策略策略。设。设i为局中人，为局中人，i的所有策略构成的集合的所有策略构成的集合Si称为称为i的的策略集策略集。3赢得函数（支付函数）赢得函数（支付函数） 局势局势: 在一局对策中，各局中人所选定的策略形在一局对策中，各局中人所选定的策略形成的策略组称为一个局势。即若设成的策略组称为一个局势。即若设si是第是第i个局中人的个局中人的一个策略，则一个策略，则n个局中人的策略组个局中人的策略组s=s1， s2， sn就是一个局势。就是一个局势。

5、 全体局势的集合全体局势的集合S可用各局中人策略集的笛卡尔可用各局中人策略集的笛卡尔乘积表示，即乘积表示，即S=S1 S2 Sn 赢得函数赢得函数：当局势出现后，对策的结果也就确定：当局势出现后，对策的结果也就确定了。也就是说，对任一局势了。也就是说，对任一局势sS，局中人，局中人i可以得到可以得到一个赢得一个赢得Hi(s)。 显然，显然， Hi(s)是局势是局势s的函数，称之为第的函数，称之为第i局中人的局中人的赢得函数。赢得函数。1二人有限零和对策：二人有限零和对策： 是指有两个参加对策的局中人，是指有两个参加对策的局中人，每个局中人都只有有限个策略可供选择，在任一局势每个局中人都只有有限

6、个策略可供选择，在任一局势下，两个局中人的赢得之和总等于零。下，两个局中人的赢得之和总等于零。2二人零和对策模型（矩阵对策模型）二人零和对策模型（矩阵对策模型） 设设分别表示两个局中人，且它们的纯策略分别表示两个局中人，且它们的纯策略集分别为集分别为S1=1,2, ,m和和S2= 1, 2, , n。记局。记局中人中人对任一纯局势（对任一纯局势（ i, j ）的赢得值为）的赢得值为aij,并称并称 a11 a12 a1n . . . am1 am2 amnA为局中人为局中人的赢得矩阵。的赢得矩阵。局中人局中人的赢得矩阵为的赢得矩阵为A。 通常，将通常，将矩阵对策记成矩阵对策记成G=，；S1 ，

7、 S2；A或或G=S1 ， S2；A 。10.1 10.1 二人零和对策二人零和对策3局中人如何选取对自己最有利的纯策略？局中人如何选取对自己最有利的纯策略？局中人的局中人的“理智行为理智行为” 双方都不想冒险，都不存在侥幸心理，而是考虑双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最小，从各自可能出到对方必然会设法使自己的所得最小，从各自可能出现的最不利的情形中选择一种最为有利的情形作为决现的最不利的情形中选择一种最为有利的情形作为决策的依据。策的依据。选择原则选择原则 局中人局中人按最大最小原则，局中人按最大最小原则，局中人按最小最大按最小最大原则。即局中人原则。即

8、局中人从所有最小的赢得中选择最大的赢从所有最小的赢得中选择最大的赢得的策略，局中人得的策略，局中人从所有最大的损失中选择最小的从所有最大的损失中选择最小的损失的策略。损失的策略。例例 设有一矩阵设有一矩阵G=S1 ， S2；A，其中，其中S1=1,2, 3, 4和和S2= 1, 2, 3 局中人局中人的赢得矩阵为的赢得矩阵为6 1 8 3 2 4 9 2 10A=3 0 6求出局中人求出局中人的最优策略。的最优策略。解解：根据选择的原则，分析局中人的选择的策略根据选择的原则，分析局中人的选择的策略局中人局中人的策略：的策略： 纯策略纯策略1,2, 2, 4可能带来的最小可能带来的最小赢得分别赢

9、得分别8，2，10，3 所以，最小赢所以，最小赢得中最大的值为得中最大的值为2。因此局中人。因此局中人的策略应为的策略应为2局中人局中人的策略：的策略： 纯策略纯策略 1, 2, 3可能带来的最大可能带来的最大损失分别损失分别9，2，6 。 所以，最大损失中最小的值为所以，最大损失中最小的值为2。因此局中人因此局中人的策略应为的策略应为 2 。总之，局中人总之，局中人的最优察纯策略分别为的最优察纯策略分别为2 ， 2。4矩阵对策的解矩阵对策的解 定义定义1 设设G=S1 ， S2；A为矩阵对策，其中为矩阵对策，其中S1=1,2, ,m，S2= 1, 2, , n ， A=（aij）mn 若等式

10、若等式 成立，记成立，记VG= ai*j* 。则称。则称VG为对策为对策G的值，称上的值，称上述等式成立的纯局势（述等式成立的纯局势（ i* , j* ）为）为G在纯策略下的在纯策略下的解（或平衡局势），解（或平衡局势）， i*与与 j*分别称为局中人分别称为局中人的最优纯策略。的最优纯策略。 根据定义根据定义1可知，上例中（可知，上例中（ 2 , 2 ）是在纯策略）是在纯策略下的解。对策值下的解。对策值VG=a22=2 ，i*=2，j*=2 。max min aij=min max aij =ai*j*ijji 定理的直观解释定理的直观解释：如果：如果ai*j*既是矩阵既是矩阵A=(aij)

11、mn中中第第i*行的最小值，又是第行的最小值，又是第j*列的最大值，则列的最大值，则ai*j*是对策是对策的值，且的值，且( i* , j* )是在纯策略意义下的解。是在纯策略意义下的解。 定理的对策意义定理的对策意义：一个平衡局势：一个平衡局势( i* , j* )具有具有这样的性质，当局中人这样的性质，当局中人 选择了纯策略选择了纯策略 i* 后，局中后，局中人人为了其所失为了其所失 最小，只能选择最小，只能选择 j* ，否则就可能失，否则就可能失去更多；反之，当局中人去更多；反之，当局中人 选择了纯策略选择了纯策略 j* 后，局后，局中人中人为了得到为了得到 最大的赢得，只能选择最大的赢

12、得，只能选择 i* ，否则就，否则就会赢得更少会赢得更少 。双方在局势。双方在局势( i* , j* )下达到一个平衡下达到一个平衡状态。状态。定理定理1 矩阵对策矩阵对策G=S1 ， S2；A在纯策略意义下有解在纯策略意义下有解的充要条件是：存在纯局势（的充要条件是：存在纯局势（ i* , j* ）使得对一切）使得对一切i=1,2, ,m, j=1,2, ,n, 均有均有aij* ai*j* ai*j 。定理定理1的一个等价命题：的一个等价命题： 定义定义2 设设f(x,y)为一个定义在为一个定义在xA ,yB上的实值上的实值函数，如果存在函数，如果存在x* A,y* B,使得对一切使得对一

13、切xA ,yB， 有有f(x,y*) f(x*,y*) f(x*,y) , 则称则称(x*,y*) 为函数为函数f(x,y)的一个鞍点。的一个鞍点。 定理定理1的等价命题：矩阵对策的等价命题：矩阵对策G在纯策略意义下有在纯策略意义下有解，且解，且VG=ai*j*的充要条件是：的充要条件是： ai*j*是矩阵是矩阵A的一个鞍的一个鞍点点(也称为对策的鞍点也称为对策的鞍点)。矩阵对策的混合策略矩阵对策的混合策略定义定义3 设设G=S1 ， S2；A为矩阵对策，其中为矩阵对策，其中S1=1,2, ,m，S2= 1, 2, , n ，A=（aij）mn 。记记S1*=xEm | xi0 , i=1,2

14、, ,m , 1 i=1 m xiS2*=yEn | yj0 , j=1,2, ,n , 1 j=1 n yj则则S1*和和 S2*分别称局中人分别称局中人和和的混合策略集（或策的混合策略集（或策略集）；略集）； x S1*， y S2*分别称为局中人分别称为局中人和和的的混合策略；对混合策略；对x S1*， y S2*，称，称(x,y)为一个混合为一个混合局势局势(或局势或局势)。E(x,y)=xAyT i=1 m j=1 n aijxiyj=这样得到的一个新的对策记成这样得到的一个新的对策记成G*=S1*, S2*,E,称称G*为对策为对策G的混合扩充。的混合扩充。局中人局中人的赢得函数记

15、成的赢得函数记成1纯策略与混合策略的关系纯策略与混合策略的关系纯策略是混合策略的特例。局中人纯策略是混合策略的特例。局中人的纯策略的纯策略k等价与混合策略等价与混合策略x=(x1 x2 xm) S1*,其中当其中当i=k时，时，xi =1，当，当ik时，时，xi =0 。混合策略混合策略x=(x1 x2 xm) S1*,可设想成当可设想成当两个局中人多次重复进行对策两个局中人多次重复进行对策G时，局中人时，局中人分别分别采取纯策略采取纯策略1,2, ,m的频率。的频率。定义定义4设设G*=S1*, S2*;E是矩阵对策是矩阵对策G=S1, S2;A的的混合扩充，如果混合扩充，如果max min

16、 E(x,y)x S1*y S2* = min max E(x,y)y S2*x S1*记其值为记其值为VG 。则称。则称VG为为G*的值，称满足上述等式的的值，称满足上述等式的混合局势混合局势(x*,y*)为为G在混合策略意义下的解在混合策略意义下的解(或简称解或简称解)，x*和和y*分别称为局中人分别称为局中人和和的最优混合策略的最优混合策略(或简称或简称最优解最优解)。E(x,y*) E(x*,y*) E(x*,y)定理定理2 矩阵对策矩阵对策G= S1, S2;A 在混合策略意义下有解在混合策略意义下有解的充要条件是：存在的充要条件是：存在x* S1* ,y* S2*,使使(x*,y*

17、)为为E(x,y)的一个鞍点，即对一切的一个鞍点，即对一切x S1* ,y S2*，有，有2矩阵对策矩阵对策G在混合策略意义下解的定义在混合策略意义下解的定义3.混合对策求解方法混合对策求解方法 下列线性规划问题的解就是下列线性规划问题的解就是局中人局中人的最优混的最优混合策略合策略x*v1 , j=1,2, ,n i=1 m aijxi1 i=1 m xixi0 , i=1,2, ,mmax v1 问题一求解3.混合对策求解方法混合对策求解方法 下列线性规划问题的解就是下列线性规划问题的解就是局中人局中人的最优混的最优混合策略合策略y*v2 , i=1,2, ,m j=1 n aijyj1

18、j=1 n yjyj0 , j=1,2, ,nmin v2 问题一求解 1944年年6月初，盟军在诺曼底登陆成功月初，盟军在诺曼底登陆成功. 到到8月初的形势：月初的形势： 背背景景10.2 进攻与撤退的抉择进攻与撤退的抉择双方应该如何决策双方应该如何决策 ？强 化强 化缺口缺口盟军盟军(预备队预备队)撤退撤退进攻进攻德军德军盟军盟军(加一加一)盟军盟军(英二英二)盟军盟军(美一美一)盟 军盟 军(美三美三)东进东进原地原地待命待命问题分析与模型假设问题分析与模型假设 对策参与者为两方（盟军和德军）对策参与者为两方（盟军和德军） 盟军有盟军有3种使用其预备队的行动：强化缺口，原地待种使用其预备

19、队的行动：强化缺口，原地待命，东进；德军有命，东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退. 对策双方对策双方完全理性完全理性，目的都是使战斗中己方获得，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多的净胜场次（胜利场次减去失败场次）尽可能多. 盟军胜盟军胜1场场盟军败盟军败2场场东进东进无战斗无战斗盟军胜盟军胜2场场原地待命原地待命无战斗无战斗盟军胜盟军胜1场场强化缺口强化缺口向东撤退向东撤退向西进攻向西进攻盟军盟军德军德军对策模型对策模型 对策参与者集合对策参与者集合N=1,2(1为盟军，为盟军，2为德军为德军)3 2102021ijAa 盟军行动

20、盟军行动S1=1,2, 3(强化缺口强化缺口/原地待命原地待命/东进东进)； 德军行动德军行动S2= 1, 2, (向西进攻向西进攻/向东撤退向东撤退)无鞍点无鞍点混合策略混合策略盟军的盟军的混合策略混合策略集集 赢得函数赢得函数 S1=x=(x1, x2, x3) | 3101,1iiixx德军的德军的混合策略混合策略集集 S2= y=(y1, y2) | 2101,1iiiyy3211121( , )( , )( , )TiijjijE x yxAyxa yE x yE x y 局中人求解局中人求解 在晚在晚8点至晚点至晚9点这时间段点这时间段，两家电视台在竞争两家电视台在竞争100万电视

21、观众收看自己的电视节目，并且电视台必须万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容，电视台实时公布自己在下一时段的展播内容，电视台1可能选可能选择的展播方式及可能得到的观众如下表择的展播方式及可能得到的观众如下表10.3二人常数和对策模型二人常数和对策模型电视台电视台2电电西部片西部片连续剧连续剧喜剧片喜剧片视视西部片西部片351560台台连续剧连续剧4558501喜剧片喜剧片381470试确定两家电视台各自的策略试确定两家电视台各自的策略10.4二人非常数和对策模型二人非常数和对策模型 囚徒困境囚徒困境:甲乙两个嫌疑犯因同一罪行被逮捕甲乙两个嫌疑犯因同一罪行被

22、逮捕,如如果双方均坦白，则各获刑果双方均坦白，则各获刑3年，如果双方均不坦白，年，如果双方均不坦白，则各获刑则各获刑2年，如果其中一人坦白，另一人不坦白，年，如果其中一人坦白，另一人不坦白，则坦白一方宽大释放，另一方获刑则坦白一方宽大释放，另一方获刑5年，两个嫌疑犯年，两个嫌疑犯各自应采取什么策略才能使自己的刑期最短。各自应采取什么策略才能使自己的刑期最短。 双矩阵对策记成双矩阵对策记成G=S1 ， S2；A，B 。两个局中。两个局中人，的纯策略集分别为人，的纯策略集分别为S1=1,2, ,m和和S2= 1, 2, , n，A、B分别为局中人分别为局中人和和的赢得矩阵。的赢得矩阵。 双矩阵对策

23、记成双矩阵对策记成G=S1 ， S2；A，B ，A、B分分别为局中人别为局中人和和的赢得矩阵。的赢得矩阵。若存在若存在ai*j* =min max aij =jibi*j* =min max bijij则称局势（则称局势（ i* , j* ）为）为G在纯策略意义下的解在纯策略意义下的解（或称纳什均衡点），（或称纳什均衡点）， i*与与 j*分别称为局中人分别称为局中人的最优纯策略。的最优纯策略。1双矩阵对策纯策略意义下的解双矩阵对策纯策略意义下的解2双矩阵对策双矩阵对策G在混合策略意义下的解在混合策略意义下的解 设设G*=S1*, S2*;E1,E2是矩阵对策是矩阵对策G=S1, S2;A,B的混合扩充，如果存在的混合扩充，如果存在x* S1* ,y* S2*,使得对一切使得对一切x S1* ,y S2*，有，有则称混合局势则称混合局势(x*,y*)为为G在混合策略意义下的解在混合策略意义下的解(也称也称双矩阵对策的纳什均衡点双矩阵对策的纳什均衡点)。E1 (x,y*) E1 (x*,y*)E