第13章对策论

第13章对策论重庆三峡学院关文忠教学目标与要求【教学目标】1.理解下列基本概念：矩阵对策，矩阵对策三要素，最优纯策略与最优混合策略，鞍点和对策值2.算法要求：(1)会用“超优原则”和“最大最小”原则求矩阵对策的最优纯策略(2)会用“线性规划”方法求矩阵对策的最优混合策略(3)了解纯策略和混合策略的纳什均衡求取。【知识结构】对策论基本概念：三要素，分类二人零和纯策略：超优原则、maxmin和minmax原则二人零和混合策略：图解法（2行或2列收益矩阵）LP方法（一般情况）纳什均衡（非零和）：纯策略（划线法）混合策略（LP方法）本章主要内容13.1对策论的基本概念13.1.1对策模型的基本要素13.1.2对策问题的分类13.2矩阵对策的纯策略13.2.1优超原则13.2.2最大最小原则13.3矩阵对策的混合策略13.3.1混合策略的概念13.3.2图解法13.3.3线性规划法13.4纳什均衡13.4.1纯策略纳什均衡的划线法13.4.2混合策略纳什均衡的LP方法13.4应用举例案例13-1市场竞争策略案例13-2对抗赛项目确定本章小结13.1.1对策模型的基本要素1．局中人局中人(players)是指参与竞争的各方，每方必须有独立的决策能力和承担风险的能力。(如:田忌、齐王）2．策略集在对策问题中，局中人为了应对其他局中人的行动而采取的方案和手段称为该局中人的一个策略(strategy)。3．赢得及赢得函数局中人采用不同策略对策时，各方总是有得或有失，统称赢得(payoff)或得益。(上中下)(上下中)(中上下)(中下上)(下上中)(下中上)(上中下)3，-31，-11，-11，-1-1，11，-1(上下中)1，-13，-31，-11，-11，-1-1，1(中上下)1，-1-1，13，-31，-11，-11，-1(中下上)-1，11，-11，-13，-31，-11，-1(下上中)1，-11，-11，-1-1，13，-31，-1(下中上)1，-11，-1-1，11，-11，-13，-312345612345613.1.2对策问题的分类对策论合作对策非合作对策静态对策动态对策二人对策多人对策零和对策常和对策变和对策局中人之间是否允许合作？策略选择是否与时间有关？局中人多寡？赢得值代数和是否为0？13.1.2对策问题的分类13.2矩阵对策的纯策略为求出对策模型的解，首先需要对双方的对策条件作如下的假设。(1)对策双方的行为是理智的，对策略的选择不存在任何侥幸心理。(2)局中人选取策略的目标是收益最大或损失最小。(3)局中人同时选取各自的行动策略，且不知道对方选取哪一个策略。(4)对策中的有关规定和要求，局中人是知道的。13.2.1超优原则1．对若恒有则称超优于,rsrjsjaars2．对若恒有则称超优于,hkihikaahk64546.512037551.5491330804213A【例13.2】第3行优超于第2行，第1行优超于第5行12345113464546.5551.54913308A134123465451.54130A第1列优超于第5列，第4列优超于第2列第1行优于2、3行12331645A最优纯策略（α1,β2）【例13.3】某地区有甲、乙两家企业生产同种产品，采取相同的价格出售，为了提高市场份额，均采取做广告的方式扩大自己的销售量。甲和乙均有三种广告策略。甲企业所占的市场份额增加的百分数如下面矩阵A所示。123123314561423Amin16max13min1max51413.2.2最大最小原则111111minminmaxmaxnnrsmmmnhkaaaaaaA,rshkaa如果则该值所对应的策略为最优纯策略2344642543322324Amin45max224min2max634234最优纯策略(,)【例13.4】13.3.1混合策略的概念【例13.5】猜硬币游戏：甲、乙两个儿童玩猜硬币游戏，甲手中拿着一枚硬币，把硬币盖在桌子上，让儿童乙猜是正面向上还是反面向上。如若猜对甲给乙1元钱，猜错乙给甲1元钱。猜硬币游戏属于矩阵对策，儿童甲的策略有出正面向上(α1)和出反面向上(α2)，儿童乙的策略有猜正面向上(β1)和猜反面向上(β2)。1111Amin1max11min1max11minmaxminmaxijijjjiiaa13.3.1混合策略的概念设甲出正面(α1)的概率x,出反面(α2)的概率1-x;乙猜正面(β1)的概率y,猜反面(β2)的概率1-y。则乙两个策略的期望值分别为:11(1)(1)21Exxx2(1)1(1)12Exxx12,0.5EEx令可得(1)当x0.5时，，理性的儿童乙会选择猜反面;(2)当x0.5时，，理性的儿童乙会选择猜正面;(3)当x=0.5时，，儿童乙不论采取何种策略，平均赢得都是零。12EE12EE120EE00.51yx10.5乙的策略00.51yx10.5同理甲的策略00.51yx10.5最优混合策略13.3.1混合策略的概念21111111nnmmmnSSaaaaA1nyy1mxx*2*1SS111minminnjjjnmjjjayay甲各方案最小期望赢得**2111maxminmnijijYSXSijaxy甲至少期望赢得111maxmaxmmiiiniiiaxax乙各方案最大损失**2111minmaxmnijijYSXSijaxy乙最多期望损失2211maxmin(,)minmax(,),YSYSXSXSEE最优混合策略为时的解XYXYXY由于甲乙都是理智的，故混合扩充：设有矩阵对策12,,GSSA***12,,GSSE混合扩充13.3.1混合策略的概念12,,GSS矩阵对策A***12,,GSSE11,...,mS甲的策略集ijmnAa赢得矩阵21,...,nS乙的策略集iix设局中人甲使用策略的概率为同理可定义局中人乙的混合策略与混合策略集.11(,...,),1,0mTmiiimxxxxx则维概率向量称为甲的一个混合策略*111(,...,)|1,0mTmiiimSxxxxx则维称称为甲的混合策略集当甲采取混合策略x,乙采取混合策略y,则称(x,y)为一个混合局势.表示一个混合策略矩阵对策及G的一个混合扩充.13.3.2图解法图解法求解矩阵对策，一般适用于赢得矩阵为或的对策问题，对于和都较大的对策问题就不适用了。下面通过例子来说明这种方法。解设甲的混合策略为x,(1-x),x∈[0,1],则乙分别使用β1,β2,β3时,甲赢得值:112233:27(1)75:35(1)52:112(1)92vxxxvxxxvxxx01xx*72β153β2211β3步骤:(1)绘制x数轴,标出x取值范围[0,1](2)x取0和1,确定三条直线端点,绘制三条甲赢得值直线(3)由于乙是理智的,甲的赢得值只能是最小的(粗线所示)(4)甲只能在最小中取最大,对应的策略为,最优对策值为V*=49/1112,,GSSA2311752A112,S2123,,S【例13.7】求解矩阵对策，其中*38(,)1111X13.3.2图解法01xx*72β153β2211β32311752A从图还可以看出局中人乙的最优混合策略为β2β3的组合.故β1的概率为0.设β2,β3的概率为y,(1-y).由效率矩阵:可知,当甲使用α1,α2,时,乙的损失值为:由于甲是理智的,故乙取最大损失(粗线)乙会在最大损失中找出最小,即乙最优混合策略为:1324:311(1)118:52(1)23vyyyvyyy01yy*3α11152α2y分别取0和1,绘制图形如下:*92(0,,)1111Y13.3.3线性规划法111111nnmmmnyyxaaxaaA**2111maxminmnijijYSXSijaxyV甲至少期望赢得111minnjjjnmjjjayay乙采取策略组合y1,…,yn时,是从利己主义出发的,会使自己的期望损失最小(也即甲的赢得最小)甲会使用某种策略组合x1,…,xm,使得在最小赢得的概率组合尽可能地大.因此有:1,2,,101,2,,ijjjjjjayVimyyjn≤≥1minmaxVV乙的目标是期望损失最小:或11,:,:njjjjyyyVV令:则于是有1max11,2,,01,2,,njjijjjjyayimyjn≤≥13.3.3线性规划法111111nnmmmnyyxaaxaaA乙会使用某种策略组合y1,…,yn,使得最大损失的某种概率组合尽可能地小.因此有:1maxminVV甲标赢得最大:或的目是期望11,:,:miiiixxxVV令:则于是有1min11,2,,01,2,,miiijiiixaxjnxim≥≥111maxmmiiiniiiaxax**2111minmaxmnijijYSXSijaxyV同理,甲采取策略组合x1,…,xm时,也是从利己主义出发的,会使自己的期望赢得最大(也即乙的损失最大)1,2,,101,2,,ijiiiiiaxVjnxxim≥≥1min11,2,,01,2,,miiijiiixaxjnxim≥≥综上所述,二人零和对策可以表述成一对对偶规划:1max11,2,,01,2,,njjijjjjyayimyjn≤≥【例13.7】7292909011A123123123123min72912901..9011101,2,3iwxxxxxxxxxstxxxxi≥≥≥≥123123123123max72912901..9011101,2,3jzyyyyyyyyystyyyyj≤≤≤≥*(1/20,1/10,1/20)16/80Yw*(1/20,1/10,1/20)16/80Xz80/165V**5(1/20,1/10,1/20)(1/4,1/2,1/4)XVX**5(1/20,1/10,1/20)(1/4,1/2,1/4)YVY解写出一对对偶模型解得:求得最优混合局势:13.4纳什均衡13.4纳什均衡李四张三坦白1抵赖2坦白1抵赖2(-5,-5)(-10,-0.25)(-0.25,-10)(-1,-1)表示成赢得矩阵:如果某情况下无一参与者可以独自行动而增加收益，则此策略组合被称为纳什均衡点。“纳什均衡”，也叫非合作均衡，由诺贝尔经济学奖获得者——美国普林斯顿大学约翰·纳什提出。“纳什均衡”描述的就是一种非合作博弈均衡，在现实中非合作的情况要比合作情况普遍。所以“纳什均衡”是对冯·诺依曼和摩根斯坦的合作博弈