数学建模第十讲博弈模型.ppt

第十讲第十讲 对策模型对策模型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,并称并称 a11 a12 …a1n . . … . am1 am2 …amnA＝＝为局中人为局中人Ⅰ的赢得矩阵的赢得矩阵局中人局中人Ⅱ的赢得矩阵为的赢得矩阵为﹣﹣A 通常，将通常，将矩阵对策记成矩阵对策记成G={Ⅰ，，Ⅱ；；S1 ，， S2；；A}或或G={S1 ，， S2；；A} 10.1 10.1 二人零和对策二人零和对策3﹒﹒局中人如何选取对自己最有利的纯策略？局中人如何选取对自己最有利的纯策略？①①局中人的局中人的“理智行为理智行为” 双方都不想冒险，都不存在侥幸心理，而是考虑双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最小，从各自可能出到对方必然会设法使自己的所得最小，从各自可能出现的最不利的情形中选择一种最为有利的情形作为决现的最不利的情形中选择一种最为有利的情形作为决策的依据。

策的依据②②选择原则选择原则 局中人局中人Ⅰ按最大最小原则，局中人按最大最小原则，局中人Ⅱ按最小最大原按最小最大原则即局中人则即局中人Ⅰ从所有最小的赢得中选择最大的赢得的从所有最小的赢得中选择最大的赢得的策略，局中人策略，局中人Ⅱ从所有最大的损失中选择最小的损失从所有最大的损失中选择最小的损失的策略例例 设有一矩阵设有一矩阵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可能带来的最小可能带来的最小赢得分别赢得分别﹣ ﹣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 max min aij=min max aij =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 , ＝＝1 i=1 m∑ xi}S2*={y∈∈En | yj≥0 , 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的混合扩充的混合扩充局中人局中人Ⅰ的赢得函数记成的赢得函数记成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}的混的混合扩充，如果合扩充，如果max min 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*)为为E(x,y)的一个鞍点，即对一切的一个鞍点，即对一切x∈∈ S1* ,y∈∈ S2*，有，有2﹒﹒矩阵对策矩阵对策G在混合策略意义下解的定义在混合策略意义下解的定义3.混合对策求解方法混合对策求解方法 下列线性规划问题的解就是下列线性规划问题的解就是局中人局中人Ⅰ的最优混合的最优混合策略策略x*v1 , j=1,2, …,n i=1 m∑ aijxi≥＝＝1 i=1 m∑ xixi≥0 , i=1,2, …,mmax v1 问题一求解3.混合对策求解方法混合对策求解方法 下列线性规划问题的解就是下列线性规划问题的解就是局中人局中人Ⅱ的最优混的最优混合策略合策略y*v2 , i=1,2, …,m j=1 n∑ aijyj≤＝＝1 j=1 n∑ yjyj≥0 , j=1,2, …,nmin v2 问题一求解• 1944年年6月初，盟军在诺曼底登陆成功月初，盟军在诺曼底登陆成功.• 到到8月初的形势：月初的形势： 背背景景10.2 进攻与撤退的抉择进攻与撤退的抉择双方应该如何决策双方应该如何决策 ？强强 化化缺口缺口盟军盟军(预备队预备队)撤退撤退进攻进攻德军德军盟军盟军(加一加一)盟军盟军(英二英二)盟军盟军(美一美一)盟盟军军(美美三三)东进东进原地原地待命待命问题分析与模型假设问题分析与模型假设• 对策参与者为两方（盟军和德军）对策参与者为两方（盟军和德军）• 盟军有盟军有3种使用其预备队的行动：强化缺口，原地待种使用其预备队的行动：强化缺口，原地待命，东进；德军有命，东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退.• 对策双方对策双方完全理性完全理性，目的都是使战斗中己方获得，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多的净胜场次（胜利场次减去失败场次）尽可能多. 盟盟军胜军胜1场场盟盟军败军败2场场东进东进无无战战斗斗盟盟军胜军胜2场场原地待命原地待命无无战战斗斗盟盟军胜军胜1场场强强化缺口化缺口向向东东撤退撤退向西向西进进攻攻盟盟军军德德军军对策模型对策模型• 对策参与者集合对策参与者集合N={1,2}(1为盟军，为盟军，2为德军为德军)• 盟军行动盟军行动S1={α1,α2, α3}(强化缺口强化缺口/原地待命原地待命/东进东进)；； 德军行动德军行动S2={ β 1, β 2,} (向西进攻向西进攻/向东撤退向东撤退)无鞍点无鞍点混合策略混合策略盟军的盟军的混合策略混合策略集集 赢得函数赢得函数 S1={x=(x1, x2, x3) | 　　　｝｝ 德军的德军的混合策略混合策略集集 S2={ y=(y1, y2) | 　　　　　　　　｝｝ 局中人Ⅰ求解局中人Ⅱ求解 在晚在晚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* =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*)E2 (x*,y) ≤ E2 (x*,y*)3.双矩阵混合对策求解方法双矩阵混合对策求解方法 下列线性规划问题的解就是下列线性规划问题的解就是局中人局中人Ⅰ的最优混合的最优混合策略策略x*v1 , j=1,2, …,n i=1 m∑ bijxi≤＝＝1 i=1 m∑ xixi≥0 , i=1,2, …,mmin v1  下列线性规划问题的解就是下列线性规划问题的解就是局中人局中人Ⅱ的最优混的最优混合策略合策略y*v2 , i=1,2, …,m j=1 n∑ aijyj≤＝＝1 j=1 n∑ yjyj≥0 , j=1,2, …,nmin v2  可以合并为下列线性规划问题可以合并为下列线性规划问题比赛策略：比赛策略：两运动队进行比赛，各有三个策略，其得两运动队进行比赛，各有三个策略，其得分见下表，求该双对策问题的混合策略分见下表，求该双对策问题的混合策略乙运动队乙运动队甲甲策略策略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 A先任抓一张牌看后叫赌，先任抓一张牌看后叫赌，赌金可定赌金可定3 3元或元或5 5元B B或认输或应赌，如认输，付或认输或应赌，如认输，付给给A 1A 1元；如应赌，当元；如应赌，当A A抓的是红牌，抓的是红牌，B B输钱，输钱，A A抓抓的是黑牌，的是黑牌，B B赢钱，输赢钱数是赢钱，输赢钱数是A A叫赌时定下的赌叫赌时定下的赌金数列出金数列出A A，，B B各自的纯策略并求最优解各自的纯策略并求最优解。