第十一讲博弈模型.ppt

第十一讲对策模型,11.1二人零和对策模型11.2进攻与撤退的选择,二人零和对策,问题一:,甲、乙两名儿童玩“石头剪子布”的游戏。石头胜剪子，剪子胜布，布胜石头。那么，甲、乙儿童如何做，使自己获胜的可能最大？,问题分析：问题中所涉及的要素,（1）游戏决定者甲、乙儿童两人；,（3）游戏的收益（支付）-胜得分为1，负得分为-1，平得分为0。,（2）游戏者的决定石头、剪子、布；,对策行为的三要素,1局中人,在一个对策行为中，有权决定自己行动方案的对策参加者，称为局中人。通常用I表示局中人的集合。如果n个局中人，则I=1，2，n。它可以是一个人，也可以是一个集团或一个自然现象。,2策略集,一局对策中，可供局中人选择的一个实际可行的完整的行动方案，称为一个策略。设i为局中人，i的所有策略构成的集合Si称为i的策略集。,3赢得函数（支付函数）,局势:在一局对策中，各局中人所选定的策略形成的策略组称为一个局势。即若设si是第i个局中人的一个策略，则n个局中人的策略组s=s1，s2，sn就是一个局势。,全体局势的集合S可用各局中人策略集的笛卡尔乘积表示，即S=S1S2Sn,赢得函数：当局势出现后，对策的结果也就确定了。也就是说，对任一局势sS，局中人i可以得到一个赢得Hi(s)。,显然，Hi(s)是局势s的函数，称之为第i局中人的赢得函数。,二人零和对策的数学模型,1二人有限零和对策：,是指有两个参加对策的局中人，每个局中人都只有有限个策略可供选择，在任一局势下，两个局中人的赢得之和总等于零。,2二人零和对策模型（矩阵对策模型）,设分别表示两个局中人，且它们的纯策略集分别为S1=1,2,m和S2=1,2,n。记局中人对任一纯局势（i,j）的赢得值为aij,并称,为局中人的赢得矩阵。,局中人的赢得矩阵为A。,通常，将矩阵对策记成G=，；S1，S2；A或G=S1，S2；A。,3局中人如何选取对自己最有利的纯策略？,局中人的“理智行为”,双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最小，从各自可能出现的最不利的情形中选择一种最为有利的情形作为决策的依据。,选择原则,局中人按最大最小原则，局中人按最小最大原则。即局中人从所有最小的赢得中选择最大的赢得的策略，局中人从所有最大的损失中选择最小的损失的策略。,解：,根据选择的原则，分析局中人的选择的策略,局中人的策略：,纯策略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）mn,若等式,成立，记VG=ai*j*。则称VG为对策G的值，称上述等式成立的纯局势（i*,j*）为G在纯策略下的解（或平衡局势），i*与j*分别称为局中人的最优纯策略。,根据定义1可知，上例中（2,2）是在纯策略下的解。对策值VG=a22=2，i*=2，j*=2。,定理的直观解释：如果ai*j*既是矩阵A=(aij)mn中第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)为一个定义在xA,yB上的实值函数，如果存在x*A,y*B,使得对一切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*和S2*分别称局中人和的混合策略集（或策略集）；xS1*，yS2*分别称为局中人和的混合策略；对xS1*，yS2*，称(x,y)为一个混合局势(或局势)。,这样得到的一个新的对策记成G*=S1*,S2*,E,称G*为对策G的混合扩充。,局中人的赢得函数记成,1纯策略与混合策略的关系,纯策略是混合策略的特例。局中人的纯策略k等价与混合策略x=(x1x2xm)S1*,其中当i=k时，xi=1，当ik时，xi=0。,混合策略x=(x1x2xm)S1*,可设想成当两个局中人多次重复进行对策G时，局中人分别采取纯策略1,2,m的频率。,定义4设G*=S1*,S2*;E是矩阵对策G=S1,S2;A的混合扩充，如果,记其值为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)的一个鞍点，即对一切xS1*,yS2*，有,2矩阵对策G在混合策略意义下解的定义,3.混合对策求解方法,下列线性规划问题的解就是局中人的最优混合策略x*,问题一求解,3.混合对策求解方法,下列线性规划问题的解就是局中人的最优混合策略y*,问题一求解,1944年6月初，盟军在诺曼底登陆成功.到8月初的形势：,背景,11.2进攻与撤退的抉择,双方应该如何决策？,问题分析与模型假设,对策参与者为两方（盟军和德军）,盟军有3种使用其预备队的行动：强化缺口，原地待命，东进；德军有2种行动：向西进攻或向东撤退.,对策双方完全理性，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多.,对策模型,对策参与者集合N=1,2(1为盟军，2为德军),盟军行动S1=1,2,3(强化缺口/原地待命/东进)；德军行动S2=1,2,(向西进攻/向东撤退),无鞍点,混合策略,盟军的混合策略集,赢得函数,S1=p=(p1,p2,p3)|,德军的混合策略集,S2=q=(q1,q2)|,局中人求解,局中人求解,1、设有一矩阵G=S1，S2；A，其中S1=1,2,3,4