博弈论模型和线性规划课件

第07章对策论模型7.1矩阵对策模型7.2双矩阵对策模型7.3n人合作对策初步（ModelsofGameTheory）1-7.1矩阵对策模型例7.1田忌赛马问题战国时期，齐国国王齐王提出要与田忌赛马，双方约定从各自的上、中、下三个等级的马中各选一匹参赛，每匹马都只能参赛一次，每一次比赛双方各出一匹马，负者要付给胜者千金。已经知道，在同等级别的马中，田忌的马不如齐王的马，而如果田忌的马比齐王的马高一等级，则田忌的马可取胜。当时，田忌手下的一个谋士给他出了一个主意：每次比赛时先让齐王牵出他要参赛的马，然后来用下马对齐王的上马，用中马对齐王的下马，用上马对齐王的中马。比赛结果，田忌二胜一负，夺得千金。2-对策模型的种类可以千差万别，但本质上都必须包括以下三个基本要素：局中人，是指参与对抗的各方，可以是一个人，也可以是一个集团。在例7.1中的齐王和田忌就是局中人。策略，是指局中人所拥有的对付其他局中人的手段、方案的集合。如例7.1中田忌共有（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、中、上）和（下、上、中）六种策略。支付函数（或收益函数），是指一局对策后各局中人的得与失，通常用正数表示局中人的得，用负数表示局中人的失。例如，在例7.1的局中人齐王的支付函数如表7-1所示。3-田忌的策略齐王的策略b1(上,中,下)b2(上,下,中)b3(中,上,下)b4(中,下,上)b5(下,中,上)b6(下,上,中)a1(上,中,下)31111-1a2(上,下,中)1311-11a3(中,上,下)1-13111a4(中,下,上)-111311a5(下,中,上)11-1131a6(下,上,中)111-113表7-1当局中人得失总和为零时，称这类对策为零和对策；否则称为非零和对策。当局中人只有两个，且对策得失总和为零，则称为二人零和对策；若得失总和为常数，则称为二人常数和对策；若得失总和是非常数，则称为二人非常数和对策。若二人对策双方的得失是用矩阵形式表示，则称支付函数为支付矩阵，相应的对策称为矩阵对策。通常，支付矩阵表示局中人A的支付函数。4-7.1.1对策的基本策略—鞍点对策例7.2设A,B两人对策，各自拥有三个策略a1,a2,a3和b1,b2,b3，局中人A的支付（收益）矩阵如表7-2所示。试求A,B各自的最优策略。b1b2b3mina11391a26575a38422max859表7-25-从直观上来看，局中人A应该出策略al，因为这样选择，他有可能得到9。但局中人B看到了这一点，他出策略b1，这样局中人A不能得到9，而只能得到1。因此，局中人A也充分认识到这一点，他应当出策略a3，这样做，就有可能得到8，而这种情况下局中人B就要出策略b3，局中人A也只能得到2。这样做下来，局中人A只能选择策略a2，而局中人B也只能选择策略b2，大家达到平衡，最后局中人A赢得的值为5，局中人B输掉的值为5。b1b2b3mina11391a26575a38422max859从上面的分析可以看出，无论局中人A选择什么策略，他赢得的值总是小于等于5，而无论局中人B选择什么策略，他输掉的值总是大于等于5，5就是支付矩阵的鞍点。6-假设局中人I有m个策略，局中人II有n个策略，分别记为为局中人I的支付矩阵，而–A为局中人II的支付矩阵，矩阵对策记为或定义7.1设是一矩阵对策，若等式（7-1）成立，则记，并称vG为对策G的值。称使式(7-1)成立的纯局势为在纯策略下的解（或平衡局势），称和分别为局中人I、II的最优纯策略。由定义7.1可知，在矩阵对策中两局中人都采取最优纯策略（如果最优纯策略存在）才是理智的行动。7-例7.3求解矩阵对策，其中解：根据矩阵A，有

Β

αβ1β2β3minjaijα1-72-9-9α24353*α315-2-4-4α4-406-4maxiaij153*6，G的解为（α2,β2），α2和β2分别是局中人I和II的最优纯策略。8-从例7.3可以看出，矩阵A的元素a22既是其所在行的最小元素又是其所在列的最大元素，即。将这一事实推广到一般矩阵对策，可得如下定理。定理7.1矩阵对策在纯策略意义下有解的充分必要条件是：存在纯局势使得(7-2)为了便于对更广泛的对策情形进行分析，引进关于二元函数鞍点的概念。定义7.2设f(x,y)为一个定义在及上的实值函数，若存在，，使得(7-3)则称为函数f(x,y)的一个鞍点。9-当矩阵对策的最优解不惟一时，有如下定理。定理7.2(无差别性）若和是矩阵对策的两个解，则定理7.3(可交换性）若和是矩阵对策的两个解，则和也是矩阵对策的解。例7.4设矩阵对策，其中，，。支付矩阵A如下，试求对策的解。10-解：直接在提供的支付矩阵上计算有其中，，所以、、和四个局势都是对策的解，且vG=5。11-7.1.2无鞍点的对策策略—混合对策如果支付矩阵有鞍点，选择鞍点对策是最优的对策策略，如果支付矩阵无鞍点，则需要选择混合对策。再看例7.1，对于支付矩阵（见表7-1），有。没有纯最优策略，因此无法用定理7.1来确定最优策略。在此情况下，只能求相应的混合策略。类似于纯策略，混合策略有如下定义和定理。定义7.3设有矩阵对策，称（7-4）分别为局中人I和II的混合策略，称为一个混合局势,称为局中人I的支付函数（赢得函数）。因此,称为对策G的混合扩充。（7-5）12-定义7.4设是的混合扩充，若(7-7)则称vG为对策G的值，称使式(7-7)成立的混合局势(x*,y*)为G在混合策略下的解，称x*和y*分别为局中人I和II的最优混合策略。定理7.4矩阵对策在混合策略意义下有解的充分必要条件是：存在，使(x*,y*)为函数的一个鞍点，即(7-8)该定理说明，如果一个局中人单方面不论采取何种纯策略都不能增加自己的赢得，则该局势为对策的解；反之亦然。13-定理7.5设，则(x*,y*)是对策G的解的充要条件是存在正数v使得x*,y*

分别是不等式组和的解，且v=vG定义7.5设，，，如果对任意j=1,2,…,n有，则称局中人I的纯策略优超于纯策略。类似地，可以定义局中人II的纯策略优超于。定理7.6对任一矩阵，对策一定存在混合策略意义下的解。14-定理7.7设，如果纯策略被其余的纯策略中之一所优超,由G可得一个新矩阵对策,其中,(;)，则有（1）vG’=vG

；（2）G'

中局中人II的最优策略就是其在G

中的最优策略；（3）若是G'中局中人I的最优策略，则就是局中人I在G中的最优策略。推论：在定理7.7中，若不是为纯策略中之一所优超，而是为的某个凸线性组合所优超，定理的结论仍然成立。15-定理7.7实际上给出了一个化简支付（赢得）矩阵A的原则，称为优超原则。根据此原则，当局中人I的某纯策略被其他纯策略或纯策略的凸线性组合所优超时，可在矩阵A中划去第i行而得到一个与原对策G等价但赢得矩阵阶数较小的对策G'，而G'的求解往往比G的求解容易些，通过求解G'而得到G的解。类似地，对于局中人II来说，可以在赢得矩阵A中划去被其他列或其他列的凸线性组合所优超的那些列。16-7.1.3混合对策的线性方程组求解方法和设有矩阵对策，由定理7.6知一定存在混合策略意义下的解(x*,y*)，又由定理7.5得，(x*,y*)为G的解的充要条件是存在v使x*,y*分别为的解，且v=vG，而且可以证明：当时，x*,y*分别为

和的解。17-例7.5设赢得矩阵为A，求解此矩阵对策。解：由于第4行优超于第1行，第3行优超于第2行，故可以划掉第1行和第2行，得到新的赢得矩阵对于A1，第1列优超于第3列，第2列优超于第4列，1/3(第1列)+2/3(第2列)优超于第5列，因此去掉第3、4、5列，得到这时，第1行又优超于第3行，故从A2中划去第3行，得到18-对于A3，易知无鞍点存在，应用定理7.5，求解以下两个不等式组首先考虑满足和的非负解。求得解为，，。因此，原矩阵对策的一个解为19-练习1：求解下列矩阵对策根据赢得矩阵有所以G的解为20-练习2：求解下列矩阵对策由于第3行优超于第2行，第4行优超于第1行，故可划去第1、2行，得到新的赢得矩阵对于A1，第2列优超于第3、4、5列，得到对于A2，第1行优超于第3行，故可划去第3行，得到21-A3没有鞍点，故求解所以原矩阵对策的一个解为：22-7.1.4混合对策的线性规划求解方法设局中人I分别以的概率混合使用他的m种策略，局中人II分别以的概率混合使用他的n种策略。当I采用混合策略，II分别采用纯策略，I的赢得分别为，依据最大最小原则，应有(7-9)其中vI是局中人I的赢得值。将问题(7-9)写成线性规划问题：(7-10)即线性规划问题（7-10）的解就是局中人I采用混合策略的解。23-类似地，求局中人II的最优策略转化为求解下列线性规划问题：s.t.因此，线性规划问题(7-11)的解就是局中人II采用混合策略的解。(7-11)24-例：利用线性规划方法求解如下的矩阵对策所以A所对应的支付矩阵没有纯对策。采用线性规划方法求解其最优混合策略，求解局中人I的最优策略转化为求解以下的LP问题局中人Ⅱ25-MODEL:sets:playerI/1..6/:x;playerII/1..6/;game(playerI,playerII):A;endsetsdata:A=31111-11311-111-13111-11131111-1131111-113;enddatamax=vI;@free(vI);@for(playerII(j):@sum(playerI(i):A(i,j)*x(i))>=vI);@sum(playerI:x)=1;END程序的第16行@free(vI)表示变量vI没有非负约束，求得最优解（只保留相关部分）：*例7.6用线性规划方法求解例7.1的最优混合策略。解：对于局中人齐王，按照线性规划(7-10)写出相应的LINGO程序26-Globaloptimalsolutionfound.Objectivevalue:1.000000Totalsolveriterations:3VariableValueReducedCostVI1.0000000.000000X(1)0.33333330.000000X(2)0.0000000.000000X(3)0.0000000.000000X(4)0.33333330.000000X(5)0.0000000.000000X(6)0.33333330.000000即齐王以1/3的概率出（上、中、下）、（中、下、上）、（下、上、中）中每种策略的一种，其赢得值为1，即在公平对策时，结局是齐王赢田忌，齐王赢得为1000两黄金。对于局中人田忌的计算也会出现相同的结果。27-在此需要指出，对于一个具有鞍点的对策问题，同样也可以采用线性规划方法来进行求解。*例7.7用线性规划方法求解例7.2。解：写出的LINGO程序清单如下MODEL:sets:playerI/1..3/:x;playerII/1..3/;game(playerI,playerII):A;endsetsdata:A=139657842;enddatamax=vI;@free(vI);@for(playerII(j):@sum(playerI(i):A(i,j)*x(i))>=vI);@sum(playerI:x)=1;ENDGlobaloptimalsolutionfound.Objectivevalue:5.000000Totalsolveriterations:4VariableValueReducedCostVI5.0000000.000000X(1)0.0000002.000000X(2)1.0000000.000000X(3)0.0000001.00000028-7.2双矩阵对策模型双矩阵对策也称为二人非常数和对策。在前面介绍的常数和（零和）对策中，均包含两种情况，纯策略和混合策略。对于非常数和对策，也包含这两种策略。7.2.1纯对策问题例7.8囚徒困境问题设有两名嫌疑犯因同一桩罪行被捕，由于希望他们坦白并提供对方的犯罪证据，规定如果两人均坦白各判刑3年；如果一方坦白另一方不坦白，坦白一方从轻释放，不坦白一方判刑10年；如果两人均不坦白，由于犯罪事实很多不能成立，只能各判1年。试分析甲、乙两犯罪嫌疑人各自采用什么策略使自己的刑期最短。29-假设囚犯I与II的第一个策略都是坦白认罪，第二个策略则是拒不交代，以对它们判处监禁的年数表示他们的赢得，则它们的赢得矩阵为通常规定，双矩阵中，第一个元素是局中人I的赢得值，第二个元素是局中人II的赢得值。问题分析这是一个二人非常数和对策问题。从表面上看，两犯罪嫌疑人拒不坦白，只能被判1年徒刑，结果是最好的。但仔细分析，却无法做到这一点。因为犯罪嫌疑人I如果采用不坦白策略，他可能被判的刑期为1到10年，而犯罪嫌疑人II可能判的刑期为0到1年；而甲选择坦白，他被判的刑期为0到3年，此时，犯罪嫌疑人II可能判的刑期为3到10年。因此，犯罪嫌疑人I一定选择坦白。基于同样的道理，犯罪嫌疑人II也只能选择坦白。选择坦白是他们最好的选择，各自被判3年。30-设是局中人I和II的赢得值，则I和II采用的策略是对于一般纯对策问题，局中人I、II的支付（赢得）矩阵如表7-4所示，其中局中人I有m个策略，局中人II有n个策略，分别记为31-为局中人I的支付（赢得）矩阵，为局中人II的支付（赢得）矩阵，矩阵对策记为，或定义7.6设是一双矩阵对策，若等式(7-12)成立，则记，并称vI

为局中人I的赢得值，记，并称vII为局中人II的赢得值。称为G在纯策略下的解（或Nash平衡点），称和分别为局中人I、II的最优纯策略。32-2.纯对策问题的求解方法

例7.9夫妻爱好的争执问题由于夫妻双方的爱好不同，经常会有一些争执出现。例如一个新婚家庭中的丈夫（局中人I）业余时间爱好看足球赛（策略1），而妻子（局中人II）业余时间喜欢看电视大片（策略2）。在一段时间里，每个周末体育场都有精彩足球赛，同时电视台也正上映妻子最喜欢的每周一次的精彩大片。由于夫妇俩都希望一起度周末，但各自的喜好不同，这就发生了争执。夫妻双方究竟是一起看足球赛还是一起在家看大片，只要在一起就比分开好，对二人来说，在一起看自己喜欢的比看不喜欢的好。夫妻双方的赢得矩阵为如果两人每次选择决策都不事先商量，则这对夫妻应该如何来选择，即怎样度过周末？解：由定义7.6可知，对于策略((1,0),(1,0))或策略((0,1),(0,1))均是Nash平衡点，也就是最优解，即他们选择共同看足球，或共同看大片。33-7.2.2混合对策问题1．混合对策问题的基本概念定义7.7在对策中，若存在策略，使得(7-13)则称为G的一个非合作平衡点，记，，则称分别为局中人I、II的赢得值。定理7.8每个双矩阵对策至少存在一个非合作平衡点。定理7.9混合策略为对策的平衡点的充分必要条件是(7-14)34-VA=(14*X1*Y1+13*X1*Y2+12*X1*Y3+13*X2*Y1+12*X2*Y2+12*X2*Y3+12*X3*Y1+12*X3*Y2+13*X3*Y3);VB=(13*X1*Y1+14*X1*Y2+15*X1*Y3+14*X2*Y1+15*X2*Y2+15*X2*Y3+15*X3*Y1+15*X3*Y2+14*X3*Y3);B1B2B3A1(14,13)(13,14)(12,15)A2(13,14)(12,15)(12,15)A3(12,15)(12,15)(13,14)列出求解下列双矩阵对策混合策略的不等式组14*Y1+13*Y2+12*Y3<=VA;13*Y1+12*Y2+12*Y3<=VA;12*Y1+12*Y2+13*Y3<=VA;13*X1+14*X2+15*X3<=VB;14*X1+15*X2+15*X3<=VB;15*X1+15*X2+14*X3<=VB;X1+X2+X3=1;Y1+Y2+Y3=1;35-2.混合对策问题的求解方法由定义7.7可知，求解混合对策就是求非合作对策的平衡点。进一步由定理7.9得到，求解非合作对策的平衡点，就是求解满足不等式约束(7-14)的可行点。因此，混合对策问题的求解问题就转化为求不等式约束(7-14)的可行点，而LINGO软件可以很容易做到这一点。*例7.10有甲、乙两支游泳队举行包括三个项目的对抗赛。这两支游泳队各有一名健将级运动员（甲队为李，乙队为王），在三个项目中成绩很突出，但规则准许他们每个人分别只能参加两项比赛，而每队的其他两名运动员则可参加全部三项比赛，各运动员的成绩如表7-5所示甲队乙队赵钱李王张孙100m蝶泳54.758.252.153.656.459.8100m仰泳62.263.458.256.559.761.5100m蛙泳69.170.565.367.868.471.336-解：分别用甲1、甲2和甲3表示甲队中李姓健将不参加蝶泳、仰泳、蛙泳比赛的策略，分别用乙l、乙2和乙3表示乙队中王姓健将不参加蝶泳、仰泳、蛙泳比赛的策略。当甲队采用策略甲1，乙队采用策略乙1时，在l00m蝶泳中，甲队中赵获第一、钱获第三得6分，乙队中张获第二，得3分；在l00m仰泳中，甲队中李获第二，得3分，乙队中王获第一、张获第三，得6分；在l00m蛙泳中，甲队中李获第一，得5分，乙队中王获第二、张获第三，得4分。也就是说，对应于策略（甲1，乙1），甲、乙两队各自的得分为（14,13）。乙1乙2乙3甲1(14,13)(13,14)(12,15)甲2(13,14)(12,15)(12,15)甲3(12,15)(12,15)(13,14)甲队乙队赵钱李王张孙100m蝶泳54.758.252.153.656.459.8100m仰泳62.263.458.256.559.761.5100m蛙泳69.170.565.367.868.471.3表7-6中给出了在全部策略下各队的得分。37-按照定理7.9，求最优混合策略，就是求不等式约束(7-14)的可行解，相应的LINGO程序清单如下。MODEL:sets:optA/1..3/:x;optB/1..3/:y;AxB(optA,optB):Ca,Cb;endsetsdata:Ca=141312131212121213;Cb=131415141515151514;enddataVa=@sum(AxB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AxB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);END38-Feasiblesolutionfound.Extendedsolversteps:0Totalsolveriterations:10VariableValueVA12.50000VB14.50000X(1)0.5000000X(2)0.000000X(3)0.5000000Y(1)0.000000Y(2)0.5000000Y(3)0.5000000即甲队采用的策略是甲1、甲3方案各占50％，乙队采用的策略是乙2、乙3方案各占50％，甲队的平均得分为12.5分，乙队的平均得分为14.5分。39-当纯对策的解不惟一时，也存在混合对策的平衡点。*例7.11用混合对策方法求解例7.9。解：写出求不等式(7-14)的LINGO程序如下：MODEL:sets:optA/1..2/:x;optB/1..2/:y;AxB(optA,optB):Ca,Cb;endsetsdata:Ca=3-1-11;Cb=1-1-13;enddataVa=@sum(AxB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AxB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);END40-Feasiblesolutionfound.Extendedsolversteps:0Totalsolveriterations:8VariableValueVA0.3333333VB0.3333333X(1)0.6666667X(2)0.3333333Y(1)0.3333333Y(2)0.6666667计算得到混合对策的平衡点（(2/3,1/3),(1/3,2/3)），各自的赢得值为1/3。从上述分析来看，二人常数和对策是非常数和对策的特例，因此也可以用求解非常数和对策的方法求解常数和对策。41-例7.12两家电视台在黄金时段竞争100万电视观众收看自己的电视节目，并且电视台必须实时公布自己在下一时段的展播内容。电视台1可能选择的展播方式及可能得到的观众如表7-7所示。电视台2min西部片连续剧喜剧片电视台1西部片35156015连续剧45585045喜剧片38147014max455870例如，两家电视台都选择播放西部片，则表7-7表明，电视台1可以争得35万观众，而电视台2可以争得100-35=65万观众，即二人的常数和为100。试确定两家电视台各自的策略。表7-742-解：若完全采用二人常数和对策的方法确定最优纯策略，则由可得，电视台1选择播放连续剧，赢得45万观众，电视台2播放西部片，赢得100-45=55万观众。*如果用求解非常数和对策的方法求解以上的问题，则相应的LINGO程序清单如下：sets:optA/1..3/:x;optB/1..3/:y;AxB(optA,optB):Ca,Cb;endsetsdata:Ca=351560455850381470;Cb=658540554250628630;enddataVa=@sum(AxB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AxB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);END43-Feasiblesolutionfound.Extendedsolversteps:0Totalsolveriterations:24VariableValueVA45.00004VB55.00005X(1)0.000000X(2)1.000001X(3)0.000000Y(1)0.9999916Y(2)0.000000Y(3)0.8421006E-05即局中人I（电视台1）采用第二种策略，赢得45万观众，局中人II（电视台2）采用第一种策略，赢得55万观众，与前面计算的结果相同。44-7.3n人合作对策初步例7.13甲有一件废旧物品，对他自己来说，已无任何价值，即价值为0元。甲将此废旧物品拿到旧货市场上进行出售，有乙和丙两个买主分别出价20元和30元若购买此物品，即对乙和丙来说，此物品的价值分别是20元和30元。试建立三人合作对策，使得每人的利益最大。解：设甲、乙、丙三人的价值分别为x1,x2,x3，因此对于每个人来说，此废旧物品的价值均为0，即v{1}=v{2}=v{3}=0。如果甲与乙合作，其价值为20，甲与丙合作，其价值为30，乙与丙合作，其价值仍为0。因此有。但三人合作的总价值为30，即