数学建模第十讲博弈模型

第十讲对策模型10.1二人零和对策模型10.2进攻与撤退的选择10.3二人常数和对策模型10.4二人非常数和对策模型对策行为问题一:甲、乙两名儿童玩“石头—剪子—布”的游戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？问题分析：问题中所涉及的要素（1）游戏决定者—甲、乙儿童两人；（3）游戏的收益（支付）--胜得分为1，负得分为-1，平得分为0。（2）游戏者的决定—石头、剪子、布；问题二:囚徒困境甲乙两个嫌疑犯因同一罪行被逮捕,如果双方均坦白，则各获刑3年，如果双方均不坦白，则各获刑2年，如果其中一人坦白，另一人不坦白，则坦白一方宽大释放，另一方获刑5年，两个嫌疑犯各自应采取什么策略才能使自己的刑期最短。问题分析：问题中所涉及的要素（1）决定者—甲、乙嫌疑犯两人；（3）甲乙的收益（支付）--获刑年数。（2）可用的决定—坦白、不坦白；对策行为的三要素1﹒局中人在一个对策行为中，有权决定自己行动方案的对策参加者，称为局中人。通常用I表示局中人的集合。如果n个局中人，则I={1，2，…，n}。它可以是一个人，也可以是一个集团或一个自然现象。2﹒策略集一局对策中，可供局中人选择的一个实际可行的完整的行动方案，称为一个策略。设i为局中人，i的所有策略构成的集合Si称为i的策略集。3﹒赢得函数（支付函数）局势:在一局对策中，各局中人所选定的策略形成的策略组称为一个局势。即若设si是第i个局中人的一个策略，则n个局中人的策略组s={s1，s2，…，sn}就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔乘积表示，即S=S1×S2×…×Sn赢得函数：当局势出现后，对策的结果也就确定了。也就是说，对任一局势s∈S，局中人i可以得到一个赢得Hi(s)。显然，Hi(s)是局势s的函数，称之为第i局中人的赢得函数。1﹒二人有限零和对策：是指有两个参加对策的局中人，每个局中人都只有有限个策略可供选择，在任一局势下，两个局中人的赢得之和总等于零。2﹒二人零和对策模型（矩阵对策模型）设Ⅰ﹑Ⅱ分别表示两个局中人，且它们的纯策略集分别为S1={α1,α2,…,αm}和S2={β1,β2,…,βn}。记局中人Ⅰ对任一纯局势（αi,βj）的赢得值为aij,并称a11a12…a1n..….am1am2…amnA＝为局中人Ⅰ的赢得矩阵。局中人Ⅱ的赢得矩阵为﹣A。通常，将矩阵对策记成G={Ⅰ，Ⅱ；S1，S2；A}或G={S1，S2；A}。10.1二人零和对策3﹒局中人如何选取对自己最有利的纯策略？①局中人的“理智行为”双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最小，从各自可能出现的最不利的情形中选择一种最为有利的情形作为决策的依据。②选择原则局中人Ⅰ按最大最小原则，局中人Ⅱ按最小最大原则。即局中人Ⅰ从所有最小的赢得中选择最大的赢得的策略，局中人Ⅱ从所有最大的损失中选择最小的损失的策略。例设有一矩阵G={S1，S2；A}，其中S1={α1,α2,α3,α4}和S2={β1,β2,β3}局中人Ⅰ的赢得矩阵为﹣61﹣83249﹣2﹣10A=﹣306求出局中人Ⅰ﹑Ⅱ的最优策略。解：根据选择的原则，分析局中人的选择的策略⑴局中人Ⅰ的策略：纯策略α1,α2,α2,α4可能带来的最小赢得分别﹣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）m×n若等式成立，记VG=ai*j*。则称VG为对策G的值，称上述等式成立的纯局势（αi*,βj*）为G在纯策略下的解（或平衡局势），αi*与βj*分别称为局中人Ⅰ﹑Ⅱ的最优纯策略。根据定义1可知，上例中（α2,β2）是在纯策略下的解。对策值VG=a22=2，i*=2，j*=2。maxminaij=minmaxaij=ai*j*ijji定理的直观解释：如果ai*j*既是矩阵A=(aij)m×n中第i*行的最小值，又是第j*列的最大值，则ai*j*是对策的值，且(αi*,βj*)是在纯策略意义下的解。定理的对策意义：一个平衡局势(αi*,βj*)具有这样的性质，当局中人Ⅰ选择了纯策略αi*后，局中人Ⅱ为了其所失最小，只能选择βj*，否则就可能失去更多；反之，当局中人Ⅱ选择了纯策略βj*后，局中人Ⅰ为了得到最大的赢得，只能选择α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)为一个定义在x∈A,y∈B上的实值函数，如果存在x*∈A,y*∈B,使得对一切x∈A,y∈B，有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）m×n。记S1*={x∈Em|xi≥0,i=1,2,…,m,＝1i=1m∑xi}S2*={y∈En|yj≥0,j=1,2,…,n,＝1j=1n∑yj}则S1*和S2*分别称局中人Ⅰ和Ⅱ的混合策略集（或策略集）；x∈S1*，y∈S2*分别称为局中人Ⅰ和Ⅱ的混合策略；对x∈S1*，y∈S2*，称(x,y)为一个混合局势(或局势)。E(x,y)=xAyTi=1m∑j=1n∑aijxiyj=这样得到的一个新的对策记成G*={S1*,S2*,E},称G*为对策G的混合扩充。局中人Ⅰ的赢得函数记成1﹒纯策略与混合策略的关系①纯策略是混合策略的特例。局中人Ⅰ的纯策略αk等价与混合策略x=(x1﹐x2﹐…﹐xm)∈S1*,其中当i=k时，xi=1，当i≠k时，xi=0。②混合策略x=(x1﹐x2﹐…﹐xm)∈S1*,可设想成当两个局中人多次重复进行对策G时，局中人Ⅰ分别采取纯策略α1,α2,…,αm的频率。定义4﹒设G*={S1*,S2*;E}是矩阵对策G={S1,S2;A}的混合扩充，如果maxminE(x,y)x∈S1*y∈S2*=minmaxE(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*)为E(x,y)的一个鞍点，即对一切x∈S1*,y∈S2*，有2﹒矩阵对策G在混合策略意义下解的定义3.混合对策求解方法下列线性规划问题的解就是局中人Ⅰ的最优混合策略x*v1,j=1,2,…,ni=1m∑aijxi≥＝1i=1m∑xixi≥0,i=1,2,…,mmaxv1问题一求解3.混合对策求解方法下列线性规划问题的解就是局中人Ⅱ的最优混合策略y*v2,i=1,2,…,mj=1n∑aijyj≤＝1j=1n∑yjyj≥0,j=1,2,…,nminv2问题一求解•1944年6月初，盟军在诺曼底登陆成功.•到8月初的形势：背景10.2进攻与撤退的抉择双方应该如何决策？强化缺口盟军(预备队)撤退进攻德军盟军(加一)盟军(英二)盟军(美一)盟军(美三)东进原地待命问题分析与模型假设•对策参与者为两方（盟军和德军）•盟军有3种使用其预备队的行动：强化缺口，原地待命，东进；德军有2种行动：向西进攻或向东撤退.•对策双方完全理性，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多.盟军胜1场盟军败2场东进无战斗盟军胜2场原地待命无战斗盟军胜1场强化缺口向东撤退向西进攻盟军德军对策模型•对策参与者集合N={1,2}(1为盟军，2为德军)3210{}2021ijAa•盟军行动S1={α1,α2,α3}(强化缺口/原地待命/东进)；德军行动S2={β1,β2,}(向西进攻/向东撤退)无鞍点混合策略盟军的混合策略集赢得函数S1={x=(x1,x2,x3)|｝3101,1iiixx德军的混合策略集S2={y=(y1,y2)|｝2101,1iiiyy3211121(,)(,)(,)TiijjijExyxAyxayExyExy局中人Ⅰ求解局中人Ⅱ求解在晚8点至晚9点这时间段，两家电视台在竞争100万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容，电视台1可能选择的展播方式及可能得到的观众如下表10.3二人常数和对策模型电视台2电西部片连续剧喜剧片视西部片351560台连续剧4558501喜剧片381470试确定两家电视台各自的策略10.4二人非常数和对策模型囚徒困境:甲乙两个嫌疑犯因同一罪行被逮捕,如果双方均坦白，则各获刑3年，如果双方均不坦白，则各获刑2年，如果其中一人坦白，另一人不坦白，则坦白一方宽大释放，另一方获刑5年，两个嫌疑犯各自应采取什么策略才能使自己的刑期最短。双矩阵对策记成G={S1，S2；A，B}。两个局中人，的纯策略集分别为S1={α1,α2,…,αm}和S2={β1,β2,…,βn}，A、B分别为局中人Ⅰ和Ⅱ的赢得矩阵。双矩阵对策记成G={S1，S2；A，B}，A、B分别为局中人Ⅰ和Ⅱ的赢得矩阵。若存在ai*j*=minmaxaij=jibi*j*=minmaxbijij则称局势（α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*)E2(x*,y)≤E2(x*,y*)3.双矩阵混合对策求解方法下列线性规划问题的解就是局中人Ⅰ的最优混合策略x*v1,j=1,2,…,ni=1m∑bijxi≤＝1i=1m∑xixi≥0,i=1,2,…,mminv1下列线性规划问题的解就是局中人Ⅱ的最优混合策略y*v2,i=1,2,…,mj=1n∑aijyj≤＝1j=1n∑yjyj≥0,j=1,2,…,nminv21111min..(1,2,,)(1,2,,)11,0nijjjmijiimiinjjijGpqstaypimbxqjnxyxy可以合并为下列线性规划问题比赛策略：两运动队进行比赛，各有三个策略，其得分见下表，求该双对策问题的混合策略。乙运动队甲策略1策略2策略3运策略1(14,13)(13,14)(12,15)动策略2(13,14)(12,15)(12,15)队策略3(12,15)(12,15)(13,14)模型求解红黑牌游戏有两张牌，红黑各一。A先任抓一张牌看后叫赌，赌金可定3元或5元。B或认输或应赌，如认输，付给A1元；如应赌，当A抓的是红牌，B输钱，A抓的是黑牌，B赢钱，输赢钱数是A叫赌时定下的赌金数。列出A，B各自的纯策略并求最优解。