混合策略线性规划解法.

§3矩阵对策的混合策略若不存在va=v=vb，则局中人甲、乙两方没有最优纯策略，就要考虑如何随机地使用自己的策略，使对方捉摸不到自己使用何种策略。即使用混合策略。设矩阵对策G={S1,S2,A}。当maxminaijminmaxaijijji时，不存在最优纯策略。例：设一个赢得矩阵如下:min595A=max6策略2866imax89min8策略1j当甲取策略2，乙取策略1时，甲实际赢得8比预期的多2，乙当然不满意。考虑到甲可能取策略2这一点，乙采取策略2。若甲也分析到乙可能采取策略2这一点，取策略1，则赢得更多为9…。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即maxminaijminmaxaij。ijji一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-----即混合策略。求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等，我们这里只介绍线性规划法，其他方法略。例：设甲使用策略1的概率为X1′，使用策略2的概率为X2′，并设在最坏的情况下，甲赢得的平均值为V（未知）。59A=STEP1861)X1′+X2′=1X1′,X2′02)无论乙取何策略，甲的平均赢得应不少于V:对乙取1：5X1’+8X2’V对乙取2：9X1’+6X2’V注意V0,因为A各元素为正。STEP2作变换：X1=X1’/V;X2=X2’/V得到上述关系式变为：X1+X2=1/V(V愈大愈好）待定5X1+8X219X1+6X21X1,X20建立线性模型：minX1+X2s.t.5X1+8X21X1=0.0489X1+6X21X2=0.095X1,X20所以，V=6.993返回原问题：X1’=X1V=0.336X2’=X2V=0.664于是甲的最优混合策略为：以0.336的概率选1策略，以0.664的概率选2策略，简记为Ｘ﹡＝（0.336,0.664）T，最优值V=6.993。同样可求乙的最优混合策略：设乙使用策略1的概率为Y1′Y1′+Y2′=1设乙使用策略2的概率为Y2′Y1′,Y2′0设在最坏的情况下，甲赢得的平均值为V。这也是乙损失的平均值，越小越好。作变换：Y1=Y1’/V，Y2=Y2’/V建立线性模型：maxY1+Y2s.t.5Y1+9Y21Y1=1/148Y1+6Y21Y2=1/14Y1,Y201/V=Y1+Y2=1/7所以，V=6.993返回原问题：Y1’=Y1V=1/2Y2’=Y2V=1/2于是乙的最优混合策略为：以½的概率选1；以½的概率选2，最优值V=7。当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换：选一正数k，令矩阵中每一元素加上k得到新的正矩阵A’，其对应的矩阵对策G’={S1,S2,A’}与G={S1,S2,A}解相同，但VG=VG’–k。例1：求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解，可求其混合策略。A中有负元素，可以取k=2,在A的每个元素上加2得到A’如下：311111131111113111111311111131111113A3maxmin1minmaxijijijjiaa533133351333335331333513133353313335'A建立对G′={S1，S2，A′}中求甲方最佳策略的线性规划如下：Minx1+x2+x3+x4+x5+x6约束条件：5x1+3x2+3x3+x4+3x5+3x6≥13x1+5x2+x3+3x4+3x5+3x6≥13x1+3x2+5x3+3x4+3x5+x6≥13x1+3x2+3x3+5x4+x5+3x6≥1x1+3x2+3x3+3x4+5x5+3x6≥13x1+x2+3x3+3x4+3x5+5x6≥1xi≥0,i=1,2,…,6可解得解为：x1=x4=x5=0,x2=x3=x6=0.111,v′=3,x1′=x4′=x5′=0，x2′=x3′=x6′=1/3,即X′*=(0,1/3,1/3,0,0,1/3)T，所以甲的最优策略为作出策略2、3、6的概率都为0.333,而作出1、4、5的概率为0，此时V′G=V′=3。同样可以建立对策G′={S1，S2，A′}中求乙方最佳策略的线性规划如下：Miny1+y2+y3+y4+y5+y6约束条件：5y1+3y2+3y3+3y4+y5+3y6≤13y1+5y2+3y3+3y4+3y5+y6≤13y1+y2+5y3+3y4+3y5+3y6≤1y1+3y2+3y3+5y4+3y5+3y6≤13y1+3y2+3y3+y4+5y5+3y6≤13y1+3y2+y3+3y4+3y5+5y6≤1yi≥0,i=1,2,…,6可解得解为：y1=y4=y5=0.111,y2=y3=y6=0,v′=3,y1′=y4′=y5′=1/3，y2′=y3′=y6′=0，即Y′*=(1/3,0,0,1/3,1/3,0)T。所以田忌的最优混合策略为作出策略1、4、5的概率都为1/3,而作出2，3，6的概率为0，此时VG=VG′-k=1。齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3,0,0,1/3)T，Y*=(1/3,0,0,1/3,1/3,0)T，对策值VG=1。例2两个局中人进行对策，规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。解：首先计算局中人甲的赢得矩阵如下表：4-56-34-52-341（出1）2（出2）3（出3）3（出3）2（出2）1（出1）甲的赢得甲的策略乙的策略即甲的赢得矩阵为A：可知无纯策略意义的解，下面求其在混合策略下的解。A的各元素都加上6，得到建立线性规划模型如下：Minx1+x2+x3Maxy1+y2+y3S.T.8x1+3x2+10x3≥18y1+3y2+10y3≤13x1+10x2+x3≥13y1+10y2+y3≤110x1+x2+12x3≥110y1+y2+12y3≤1x1,x2,x3≥0y1,y2,y3≥0654543432A1211011031038'A得到x1′=0.25,x2′=0.50,x3′=0.25；y1′=0.25,y2′=0.50,y3′=0.25。即此对策的解为X*=(0.25,0.50,0.25)T，Y*=(0.25,0.50,0.25)T。VG=VG′-k=0。在对策论中可以根据不同方式对对策问题进行分类，通常分类的方式有:（1）根据局中人的个数，分为二人对策和多人对策；（2）根据各局中人的赢得函数的代数和是否为零，可分为零和对策和非零和对策；（3）根据局中人是否合作，又可分为合作对策和非合作对策；（4）根据局中人的策略集中个数，又分为有限对策和无限对策（或连续对策）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关可分为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策。本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。§4其他类型的对策论简介一、完全信息静态对策该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这种均衡就称为纳什均衡。下面以著名的“囚徒困境”来进一步阐述§4其他类型的对策论简介例1“囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来判决。如图1-1所示。坦白抵赖轻罪，轻罪重罪，无罪重罪，无罪释放，释放坦白抵赖图1-1囚徒困境由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，(坦白，坦白)就是纳什均衡解。而这个均衡是不会被打破的，即使他们在坐牢之前达成协议。囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。二、完全信息动态对策在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。例2某行业中只有一个垄断企业A，有一个潜在进入者——企业B。B可以选择进入或不进入该行业这两种行动，而A当B进入时，可以选择默认或者报复两种行动。如果B进入后A企业报复，将造成两败俱伤的结果，但如果A默认B进入，必然对A的收益造成损失。同样的，如果B进入而A报复，则B受损，反之，将受益。把此关系用图1-2表示。默许报复50,100-20,00,2000,200进入不进入图1-2A、B的行动及结果AB由分析可知，上例中（B选择不进入，A选择报复）和（B选择进入，A选择默许）都是纳什均衡解。但在实际中，（B选择不进入，A选择报复）这种情况是不可能出现的。因为B知道他如果进入，A只能默许，所以只有（B选择进入，A选择默许）会发生。或者说，A选择报复行动是不可置信的威胁。对策论的术语中，称（A选择默许，B选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为精炼纳什均衡。当然，如果A下定决心一定要报复B，即使自己暂时损失。这时威胁就变成了可置信的，B就会选择不进入，（B选择不进入，A选择报复）就成为精炼纳什均衡。军事交战时，“破釜沉舟”讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。三、多人非合作对策有三个或三个以上对策方参加的对策就是“多人对策”。多人对策同样也是对策方在意识到其他对策方的存在，意识到其他对策方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人对策同样的思路和方法来研究它们，或将两人对策的结论推广到多人对策。不过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，因此，策略的相互依存关系也就更为复杂，对任一对策方的决策引起的反应也就要比两人对策复杂得多。并且，在多人对策中还有一个与两人对策有本质区别的特点，即可能存在“破坏者”。所谓破坏者即一个对策中具有下列特征的对策方：其策略选择对自身的得益没有任何影响，但却会影响其它对策方的得益，有时这种影响甚至有决定性的作用。例如有三个城市争夺某届奥运会的主办权。四、非零和对策所谓零和对策，就是一方的收益必定是另一方的损失。这种对策的特点是不管各对策方如何决策，最后各对策方得益之和总是为零。有某些对策中，每种结果之下各对策方的得益之