10-矩阵对策

第10章GamesTheory矩阵对策——对策论的第一扇大门第10章矩阵对策210.1基本概念10.2特殊方法10.3线性规划法第10章矩阵对策第10章矩阵对策310.1基本概念10.1.1引言一、对策现象及其三个要素对策：就是竞争或斗争中的决策。对策现象的三个要素：局中人、策略、得失。（1）局中人：参与对策并有切身利益关系与决策权的个人或集体。假设：局中人都是聪明的。（2）策略：每个局中人为了自身利益所能采取的对付其他局中人的办法或措施，称为该局中人的策略。一个策略应是在一局对策中，从始至终采取的所有行动的一套完整方案。（3）得失：一局对策的结果，诸如胜负、名次、损益、效用，等等,统称为得失。第10章矩阵对策410.1基本概念例1田忌赛马（1）局中人：田忌、齐王；（2）策略：3匹马参赛的顺序：（上，中，下），（上，下，中）（中，下，上），（中，上，下）（下，上，中），（下，中，上）策略集：每个局中人所有策略构成的集合。局势：（（下，上，中），（上，中，下））（3）得失：一局千金。二、对策的分类局中人数：二人对策多人对策策略数：有限对策无限对策得失总和：零和对策非零和对策第10章矩阵对策510.1基本概念二、对策的分类（续）•按相互关系：•平等对策•主从对策协商对策对抗对策结盟对策不结盟对策•多人对策联合对策合作对策•按数学模型：矩阵对策、树图对策、微分对策。第10章矩阵对策610.1基本概念三、矩阵对策的基本模型在二人有限零和对策中，设以甲方、乙方表示两个局中人，以S1={α1,α2,···,αm}S2={β1,β2,···,βn}分别表示甲方、乙方的策略集，其中：αi(i=1,2,···,m)——甲方的策略βj(j=1,2,···,n)——乙方的策略第10章矩阵对策710.1基本概念则S1与S2构成m×n个局势(αi,βj),i=1,2,···,m;j=1,2,···,n令aij——甲方关于局势(αi,βj)的赢得则所有aij构成一个矩阵A=(aij)m×n称为甲方的赢得矩阵。由于甲、乙双方得失总和恒为零，所以A还可称为乙方的损失矩阵，而–A即乙方的赢得矩阵。第10章矩阵对策810.1基本概念由此可见，在二人有限零和对策中，给定一个局中人的赢得矩阵，则另一个局中人的赢得矩阵也就唯一确定了，而且双方的策略数目也就唯一确定了。这意味着二人有限零和对策总可以由一个局中人的赢得矩阵来刻画，故称这种对策为矩阵对策。其基本模型记为G={S1,S2,A}其中A=(aij)m×n规定为甲方的赢得矩阵。第10章矩阵对策910.1基本概念例1田忌赛马设以S1={α1,α2,α3,α4,α5,α6}表示田忌的策略集，其中：α1=(上、中、下)，α2=(上、下、中)α3=(中、下、上)，α4=(中、上、下)α5=(下、上、中)，α6=(下、中、上)以S2={β1,β2,β3,β4,β5,β6}表示齐王的策略集，其中：β1=(上、中、下),β2=(上、下、中)β3=(中、下、上)，β4=(中、上、下)β5=(下、上、中)，β6=(下、中、上)第10章矩阵对策1010.1基本概念则田忌的赢得矩阵为：β1β2β3β4β5β6α1-3-11-1-1-1α2-1-3-11-1-1α3-1-1-3-11-1α4-1-1-1-3-11α51-1-1-1-3-1α6-11-1-1-1-3A=第10章矩阵对策1110.1基本概念10.1.2纯策略一、鞍点例2设有对策G={S1,S2,A},其中:β1β2β3β4α17-8-23α23612α392-3-5A=-81-5(max)minaij9613maxaij(min)111(α2,β3)为最优纯局势。坏中求好第10章矩阵对策1210.1基本概念设有对策G={S1,S2,A},其中S1={α1,α2,…,αm},S2={β1,β2,…,βn}A=(aij)m×n如果A中存在一个元素ark，满足:ark=maxminaij=minmaxaijijji则把ark所对应的局势(αr,βk)称为对策G的解或鞍点,分别称αr——甲方的最优纯策略，记为α*=αrβk——乙方的最优纯策略，记为β*=βkark——对策G的值，记为v即v=maxminaij=minmaxaij=arkiijj(11-2)第10章矩阵对策1310.1基本概念二、鞍点属性定理1对策G={S1,S2,A}在纯策略意义下有解的充要条件是：矩阵A中存在一个元素ark，它对一切i、j都满足：上式意味着：ark是它所在行的诸元素中的最小者,同时又是它所在列的诸元素中的最大者。(11-3)aik≤ark≤arj,i=1,2,···,m;j=1,2,···,n第10章矩阵对策1410.1基本概念最优纯策略具有下述性质：(1)若甲方采用α*=αr,则他的赢得至少是v,即便事先公开这一点,乙方也无法利用这一信息使甲方的赢得比v更少。(2)若乙方采用β*=βk,则他的损失至多是v,即便事先公开这一点,甲方也无法利用这一信息使乙方的损失比v更多。第10章矩阵对策1510.1基本概念例3求解对策G={S1,S2,A},其中:(max)(max)(min)(min)解4363-220-65343A=4363-220-653435363β1β2β3β43-63α1α2α3A=jminaijimaxaij3333第10章矩阵对策1610.1基本概念10.1.3混合策略一、矩阵对策的解如前所述,有些矩阵对策在纯策略下无解。那么在这种情况下，双方应如何决策呢？例4已知对策G={S1,S2,A},其中:S1={α1,α2},S2={β1,β2}A=7436第10章矩阵对策1710.1基本概念局中人甲的期望赢得为:E(x,y)=∑aijP(αiβj)=∑∑aijP(αi)P(βj)=7xy+4x(1-y)+3(1-x)y+6(1-x)(1-y)=6xy-3y-2x+6X=(x1,x2)T=(x,1-x)TY=(y1,y2)T=(y,1-y)TX*=(1/2,1/2)TY*=(1/3,2/3)TE(X*,Y*)=5-2(x-1/2)+5=6(x-1/2)(y-1/3)+5x=1/21-x=1/2y=1/31-y=2/3=6y(x-1/2)P(βj)7436α1α2P(αi)β1β2aijβjαix1-xy1-y第10章矩阵对策1810.1基本概念(1)把S1上的概率分布X=(x1,x2,···,xm)T称为甲方的混合策略,把S2上的概率分布Y=(y1,y2,···,yn)T称为乙方的混合策略，称(X,Y)为对策G的一个混合局势。(2)称数学期望i=1j=1mnE(X,Y)=∑∑aijxiyj=XTAY为甲方的期望赢得，简称为甲的赢得,同时又称为乙方的损失,而-E(X,Y)为乙方的赢得。第10章矩阵对策1910.1基本概念(3)记S1*={X=(x1,x2,···,xm)T|xi≥0，i=1,2,···,m,∑xi=1}——甲方的混合策略集，S2*={Y=(y1,y2,···,yn)T|yj≥0，j=1,2,···,n,∑yj=1}——乙方的混合策略集，G*={S1*,S2*,E}——G={S1,S2,A}的混合扩充。第10章矩阵对策2010.1基本概念(4)若有X*∈S1*,Y*∈S2*,使XXYYE(X*,Y*)=maxminE(X,Y)=minmaxE(X,Y)XXYYv*=maxminE(X,Y)=minmaxE(X,Y)=E(X*,Y*)则这样，对策在纯策略意义下的解(α*,β*)就成为(X*,Y*)的一种特殊情况。X*——甲方的最优混合策略Y*——乙方的最优混合策略简称最优策略；而(X*,Y*)——对策G在混合策略意义下的解E(X*,Y*)——对策G的值，记为v*，即如例2:X*=(0,1,0)TαY*=(0,0,1,0)Tβ23第10章矩阵对策2110.1基本概念二、基本定理定理2混合局势(X*,Y*)是矩阵对策G的解的充要条件是：对一切X∈S1*和Y∈S2*,都有E(X,Y*)≤E(X*,Y*)≤E(X*,Y)定理3若存在实数v0以及X*∈S1*,Y*∈S2*，则(X*,Y*)是G的解，且v*=v0的充要条件是：对任意i∈I和j∈J，都有E(ei,Y*)≤v0≤E(X*,ej)第10章矩阵对策2210.1基本概念推论设v*是对策G={S1,S2,A}的值，则方程组的解X*=(x1*,x2*,…,xm*)T是甲方的最优策略;而的解Y*=(y1*,y2*,…,yn*)T是乙方的最优策略;∑aijxi≥v*,j=1,2,…,ni=1m∑xi=1j=1nxi≥0,i=1,2,…,m(Ⅰ)∑aijyj≤v*,i=1,2,…,mi=1m∑yj=1j=1nyj≥0,j=1,2,…,n(Ⅱ)第10章矩阵对策23定理4若(X*,Y*)是矩阵对策G的解,v*是G的值,则对每一个i∈I或j∈J,都有(1)若xi*0,则∑aijyj*=v*(2)若yj*0,则∑aijxi*=v*(3)若∑aijyj*v*,则xi*=0(4)若∑aijxi*v*,则yi*=0定理5矩阵对策的基本定理任何矩阵对策G={S1,S2,A}在混合策略意义下一定有解。10.1基本概念第10章矩阵对策2410.2特殊方法10.2.1矩阵对策的特殊解法如前所述，矩阵对策总能用线性规划求解，但求解较繁.而有些特殊的矩阵对策可能有一些更简单的特殊解法。一、特殊不等式方程组解法例5甲、乙二人一起玩“锤子、剪子、袱子”的游戏，每人都可从{锤、剪、袱}中选择一个出法(纯策略)从而构成一个纯局势。该游戏规定：锤胜剪,剪胜袱,袱胜锤。又若规定：胜则得1分,负则得-1分，平手时双方各得0分,则甲方的赢得矩阵为：第10章矩阵对策25-x2+x3≥v*x1-x3≥v*-x1+x2≥v*x1+x2+x3=1x1,x2,x3≥010.2特殊方法A=(Ⅰ)(Ⅱ)y2-y3≤v*-y1+y3≤v*y1-y2≤v*y1+y2+y3=1y1,y2,y3≥0x1x2x301-1-1011-10y1y2y3锤剪袱锤剪袱第10章矩阵对策2610.2特殊方法每组的前三式相加131313131313X*=(,,)T,Y*=(,,)T-x2+x3≥v*x1-x3≥v*-x1+x2≥v*x1+x2+x3=1x1,x2,x3≥0(Ⅰ)000再结合x1+x2+x3=1y1+y2+y3=1得0≥3v*0≤3v*v*=0由每组前三式有x1≤x2≤x3≤x1y1≤y2≤y3≤y1则x1=x2=x3y1=y2=y3(Ⅱ)y2-y3≤v*-y1+y3≤v*y1-y2≤v*y1+y2+y3=1y1,y2,y3≥0000第10章矩阵对策2710.2特殊方法二、取等式试解法例6求解田忌赛马的对策问题-3x1-x2-x3-x4+x5-x6=v*①-x1-3x2-x3-x4-x5+x6=v*②x1-x2-3x3-x4-x5-x6=v*③-x1+x2-x3-3x4-x5-x6=v*④-x1-x2+x3-x4-3x5-x6=v*⑤-x1-x2-x3+x4-x5-3x6=v*⑥x1+x2+x3+x4+x5+x6=1⑦x1,x2,x3,x4,x5,x6≥0(Ⅰ)-1-1-1-1-1-1第10章矩阵对策2810.2特殊方法①～⑥相加得-6(x1+x2+x3+x4+x5+x6)=6v*结合⑦式x1+x2+x3+x4+x5+x6=1⑦得v*=-1代入①～⑥,分别与⑦相加,得x1=x3=x5x2=x4=x6有X*(λ)=(λ,1-λ,λ,1-λ,λ,1-λ)T/3,λ∈[0,1]类似有Y*(μ)=(μ,1-μ,μ,1-μ,μ,1-μ)T/3,μ∈[0,1]第10章矩阵对策2910.2特殊方法三、无鞍点的二阶矩阵对策的通解公式y1y2x1x2β1β2α1α2abcdA=D=(a+d)-(b+c)x1*=d-cDx2*=a-bDy1*=y2*=d-bDa-cDv*=ad-bcD(8a)(8b)(8c)(8d)第10章矩阵对策3010.2特殊方法例4A=7436D=(a+d)-(b+c)=(7+6