数学建模_对策论

1、2022-1-171GAME THEORY对对 策策 论论第第?章章2022-1-17Game theory26 矩阵对策矩阵对策6.1 引言引言6.2 对策论的基本概念对策论的基本概念6.3 矩阵对策的概念及模型矩阵对策的概念及模型6.4 矩阵对策的纯策略解（鞍点解）矩阵对策的纯策略解（鞍点解）6.5 矩阵对策的混合策略解（矩阵对策的混合策略解（mixed strategic solution）6.6 矩阵对策的解法矩阵对策的解法2022-1-17Game theory36.1.1 何谓对策论（何谓对策论（Game Theory）？）？6.1.2 对策的例子对策的例子6.1.3 对策论的诞生

2、与发展简况对策论的诞生与发展简况6.1 引引 言言2022-1-17Game theory46.1.1 何谓对策论何谓对策论(Game Theory)？( 定义：对策论亦称竞赛论或博弈论，是研究具有斗争或竞争性质现象的数学理论和方法。 囚徒困境局中人2坦白不坦白局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)2022-1-17Game theory5(齐王赛马(决斗问题：神雕侠侣中武林盟主大会6.1.2 对策的例子对策的例子朱子柳霍 都郭 靖达尔巴郝大通金轮法王2022-1-17Game theory66.1.3 对策论的诞生与发展简况对策论的诞生与发展简况早期工作早

3、期工作F1912年E.Zermelo 关于集合论在象棋对策中的应用F 1921年E.Borel 引入最优策略F 1928年J.V.Neumann证明了一些猜想2022-1-17Game theory76.1.3 对策论的诞生与发展简况对策论的诞生与发展简况产生标志产生标志 1944年J.V.Neumann和O.Morgenstern”对策论与经济行为” （Theory of Games and Economic Behavior）发展成熟发展成熟 Nash均衡、经济博奕论、信息不对称对策和广义对策2022-1-17Game theory86.2 对策论的基本概念对策论的基本概念(6.2.1 局

4、中人（局中人（Player）(6.2.2 策略（策略（Strategy）(6.2.3 支付与支付函数支付与支付函数2022-1-17Game theory96.2.1 局中人（局中人（Player）1、局中人：在一场竞争或斗争中的决策者称为该局对策的局中人 通常，一局对策具有两个或两个以上-决策者，一般用I表示局中人集合：,.,2 , 1nI 2022-1-17Game theory106.2.1 局中人（局中人（Player）2、对策分类：依据局中人的数量，可将对策分为有限对策无限对策(n2)对策无限零和对策无限非零和对策有限零和对策有限非零和对策2022-1-17Game theory11

5、6.2.2 策略（策略（Strategy）1、 策略与策略与策略集F局中人指导自己自始至终如何行动的一个方案，称为策略(Strategy)F由所有策略构成的集合，称为策略集(StrategySet)2022-1-17Game theory126.2.2 策略（策略（Strategy）niSi,.,2 , 1; 2、策略集的元素：对于局中人i,iI，都有自己的策略集Si,通常每一局中人的策略集中至少应包括两个策略对于例4的包、剪、锤游戏。假设有两个局中人I=甲，乙，甲的策略集为S甲=(包)、(剪)、(锤)=a1、a2、a3;乙的策略集为S乙=(包)、(剪)、(锤) =b1、b2、b3;2022-

6、1-17Game theory136.2.3 支付与支付函数支付与支付函数1、局势：各局中人所选定的策略形成的策略组2、策略组 若si是第i个局中人的一个策略，则n个局中人的策略组 s=(s1,s2,sn) 就是一个局势局势。2022-1-17Game theory146.2.3 支付与支付函数支付与支付函数例如，对于包、剪、锤游戏。假设有两个局中人I=甲，乙，甲的策略集为S甲=(包)、(剪)、(锤)=(a1)、(a2)、(a3);乙的策略集为S乙=(包)、(剪)、(锤) =(b1)、(b2)、(b3); 则甲的一个策略ai，和乙的一个策略bj就构成一个局势sij.2022-1-17Game

7、theory156.2.3 支付与支付函数支付与支付函数3、赢得（支付）：、赢得（支付）：当每个局中人所采取的策略确定后，他们就会得到相应的收益或损失，称为局中人的支付（Payoff）。 若甲的一个策略a3(锤)，乙的一个策略b2(剪)，则构成一个局势s32 。在局势s32下，甲的支付为：1),(231f乙的支付1),(232f2022-1-17Game theory166.2.3 支付与支付函数支付与支付函数4、支付（赢得）函数：、支付（赢得）函数：不同的策略会导致不同的支付，因此，支付是策略(准确的说应该是局势准确的说应该是局势)的函数，称为支付函数(payoff function)。对于

8、例4，两人的支付函数分别记为： ),(1f212,),(SSf和1),(131f1),(132f例如，对于策略a3, b12022-1-17Game theory176.2.3 支付与支付函数支付与支付函数5、零和对策和非零和对策 根据各局中人支付的代数和是否为0，将对策分为零和对策和非零和对策(non-zero-sum games)。 若在任一局对策中，全体局中人支付的总和为0，则该对策称为零和对策，否则称为非零和对策(non-zero-sum games)。 对于前例，显然为零和对策，因为2121),(, 0),(),(SSff2022-1-17Game theory186.2.3 支付与

9、支付函数支付与支付函数6、对策分类 根据局中人的数目和支付函数代数和有限对策n人对策(n2)对策合作对策非合作对策2022-1-17Game theory196.3 矩阵对策的概念及模型矩阵对策的概念及模型1、定义：两个人零和对策称为矩阵对策矩阵对策 例，“包、剪、锤”游戏中，甲、乙双方各有三种不同的策略，分别为：,3211S,3212S2022-1-17Game theory206.3 矩阵对策的概念及模型矩阵对策的概念及模型甲的支付情况如下表 1 (包)2(剪)3(锤)1 (包)0-112 (剪)10-13(锤)-110乙的策略甲的支付甲的策略表6.12022-1-17Game theor

10、y216.3 矩阵对策的概念及模型矩阵对策的概念及模型齐王赛马 1234561 (上中下)31111-12 (上下中)1311-113(中上下)1-131114(中下上)-1113115(下中上)11-11316(下上中)111-113田忌策略齐王赢得齐王策略上中下上下中中上下中下上下中上下上中2022-1-17Game theory226.3 矩阵对策的概念及模型矩阵对策的概念及模型表6.1中的数字用矩阵的形式表示011101110AA称为甲的支付矩阵。显然，乙的支付矩阵为-A。因此，该对策可记为： ,21ASSG 2022-1-17Game theory236.3 矩阵对策的概念及模型矩阵

11、对策的概念及模型(2、矩阵对策的模型F一般地，若局中人 ，的策略集分别为：,211mS,212nSF为了与后面的概念区分开来，我们称i为的纯策略， j为的纯策略纯策略，对于纯策略i, j构成的策略偶(i, j)称为纯局势纯局势。 2022-1-17Game theory246.3 矩阵对策的概念及模型矩阵对策的概念及模型nmijmnmmnnaaaaaaaaaA)(212222111211(若的支付矩阵为： ij表示局势(i,j)下，局中人的支付,则矩阵对策可记为G=S1,S2,A：即矩阵对策模型。 2022-1-17Game theory256.4 矩阵对策的纯策略解矩阵对策的纯策略解6.4.

12、1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程6.4.2 矩阵对策的纯策略解理论基础矩阵对策的纯策略解理论基础6.4.3 矩阵对策的纯策略解性质矩阵对策的纯策略解性质2022-1-17Game theory26例5 设二人零和对策 G=S1, S2, A，其中 6.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程,43211S,3212S而且局中的支付矩阵为： 71228018635726A两位局中人都想自己的支付最大化。2022-1-17Game theory276.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程 这里我们认为局中人都是理智的，从矩阵A进行

13、逻辑推理可知： 如果局中人采取3作策略，虽有可能获得最大支付18，但是,局中人分析到的这种心理，就会采取3策略，使不仅得不到最大值18，反而取得很坏的结果-8； 同样，局中人为了得到最大支付+12(即局中人的支付-12)，会采取 2作为策略,但局中人也会猜到的这种心理,而采取 2作策略，这样局中人只能得到-3。2022-1-17Game theory286.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程从以上的分析可以看出，局中人选取最优策略时应该考虑到也是十分理智与精明的，的策略是要以支付最少为目的，所以不能存在任何侥幸心理。局中人也应作同样的考虑。 对于局中人来说，应该是从最

14、坏处着想对于局中人来说，应该是从最坏处着想向最好处努力。向最好处努力。2022-1-17Game theory296.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程对局中人来讲，各策略的最坏结果分别为：min-6,2,-7=-7 min5,3,6=3min18,0,-8=-8min-2,-12,7=-12这些最坏的情况中，最好的结果是：max-7,3,-8,-12=32022-1-17Game theory306.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程同样，对局中人而言，各策略的最坏的结果分别为：max-6,5,18,-2=18max2,3,0,-12=3m

15、ax-7,6,-18,7=7在这些最坏的情况中，最好的结果（损失最小）是min18,3,7=32022-1-17Game theory316.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程1231-62-7-7253633180-8-84-2-127-121837ijjminijimax2022-1-17Game theory326.4.1 矩阵对策的纯策略解例解过程矩阵对策的纯策略解例解过程课堂练习:求解对策 G=S1,S2,A已知：282703212728A2022-1-17Game theory33定义1 对于矩阵对策G=S1,S2,A,如果存在纯局势 6.4.2 矩阵对策

16、的纯策略解理论基础矩阵对策的纯策略解理论基础),(jijijiij*则称局势 为对策G在纯策略中的解。亦称其为G的鞍点(saddle point): ),(*ji(列中最大，行中最小)使得对任意j=1, ，n,及任意i=1, m有： 2022-1-17Game theory346.4.2 矩阵对策的纯策略解理论基础矩阵对策的纯策略解理论基础*jiGV 分别称为局中人，的最优纯策略。 称 为对策G的值(value)，记为*,ji*jiGV2022-1-17Game theory356.4.2 矩阵对策的纯策略解理论基础矩阵对策的纯策略解理论基础*)max(min)min(maxjiijijijj

17、i(定理1 矩阵对策G=S1,S2,A存在最优纯策略的充分必要条件为：2022-1-17Game theory366.4.2 矩阵对策的纯策略解理论基础矩阵对策的纯策略解理论基础,43211S,43212S31013676934316868A求对G的解和值。例6 已知 G=S1,S2,A，其中, 2022-1-17Game theory376.4.2 矩阵对策的纯策略解理论基础矩阵对策的纯策略解理论基础12341868662134-3-33967664-31103-3961066ijjminijimax解：根据A可得2022-1-17Game theory386.4.2 矩阵对策的纯策略解理论

18、基础矩阵对策的纯策略解理论基础由于： 6)max(min)min(maxijijijji四个局势均为G的鞍点，且 6GV故知： ),(21),(23),(41),(432022-1-17Game theory396.4.3 矩阵对策的纯策略解性质矩阵对策的纯策略解性质从上例可知，对策的解可以是不唯一的，但对策的值是唯一的。对策解不唯一时，应满足下面两条性质：1. 无差别性无差别性：若 ),(11ji与 ),(22ji是矩阵对策G的两个解，则2211jiji即对策值相等，它们在矩阵中的元素相同。2022-1-17Game theory406.4.3 矩阵对策的纯策略解性质矩阵对策的纯策略解性质2

19、. 可交换性可交换性：若 ),(11ji与 ),(22ji是矩阵对策G的两个解,则),(21ji与 ),(12ji也是对策的解。 2022-1-17Game theory416.4.3 矩阵对策的纯策略解性质矩阵对策的纯策略解性质是不是每一个矩阵对策都有纯策略解（鞍点）？12310-11-1210-1-13-110-1111ijjminijimax答案是否定的。)max(min)min(maxijijijji2022-1-17Game theory426.5 矩阵对策的混合策略解矩阵对策的混合策略解6.5.1 混合策略与混合扩充（混合策略与混合扩充（mixed strategic soluti

20、on）6.5.2 解的基本定理解的基本定理2022-1-17Game theory436.5.1 混合策略与混合扩充混合策略与混合扩充121363254456ijjminijimax2, 4)min(max*1ivijji1, 5)max(min*2jvijij121245vv1、问题提出 2022-1-17Game theory446.5.1 混合策略与混合扩充混合策略与混合扩充该对策问题表明不存在使对立双方达到平衡的局势，因此，局中人采取任何一种纯策略，都有一定的风险。所以，在这种情况下，局中人必须隐瞒自己选取策略的意图。 2022-1-17Game theory456.5.1 混合策略与

21、混合扩充混合策略与混合扩充2、问题处理方案设计这时我们可以设想局中人随机地选取纯策略来进行对策。即在一局对策中，局中人以概率 ) 10(iixx来选取纯策略 mii, 2 , 1,其中的 mxxx,21满足 0, 11imiixx于是得到一个m维的概率概率向量 ),(21mxxxX2022-1-17Game theory466.5.1 混合策略与混合扩充混合策略与混合扩充同样对于局中人,有相应的一个n维的概率向量 ),(21nyyyY满足 njyyjnjj, 2 , 1, 0, 11yj表示局中人选取纯策略j的概率。2022-1-17Game theory476.5.1 混合策略与混合扩充混合

22、策略与混合扩充3、混合策略概念引入定义:若给定一个矩阵对策G=S1,S2,A ,其中,211mS,212nSnmijA)(则我们把纯策略集对应的概率向量： ),(21mxxxX0ixmixmii, 2 , 1, 110jynj, 2 , 111njjy),(21nyyyY与 分别称作局中人、的混合策略，(X,Y)称为一个混合局势。 2022-1-17Game theory486.5.1 混合策略与混合扩充混合策略与混合扩充如果局中人选取的策略为 ),(21mxxxX局中人选取 ),(21nyyyY由于两局中人分别选取策略 ji,的事件可以看成使相互独立4、混合策略的局中人支付 如果局中人选取的

23、策略为 2022-1-17Game theory496.5.1 混合策略与混合扩充混合策略与混合扩充YAXyxYXETjminjiij11),(就是局中人的支付值。 所以局势(i，j)出现的概率是xiyj。从而知局中人支付ij的概率是xiyj。于是，数学期望值： 2022-1-17Game theory506.5.1 混合策略与混合扩充混合策略与混合扩充令： 1;, 1, 0| ),(11*1miiimxmixxxXS1;, 1, 0| ),(11*2njjjnynjyyyYS,| ),(*2*1SYSXYXEE则称 ,*2*1*ESSG 为G的混合扩充混合扩充。 5、混合扩充2022-1-1

24、7Game theory516.5.1 混合策略与混合扩充混合策略与混合扩充定义定义2 如果存在 ,*1*SX *2*SY ,满足:对任意 *1SX 及 *2SY 均有： ),(),(),(*YXEYXEYXE则称 ),(*YX为G（在混合策略下的）解解. *,YX分别称为局中人、的最优最优(混合)策略策略. ),(*YXE称为对策G（在混合意义下的）值值，记为 *GV2022-1-17Game theory526.5.1 混合策略与混合扩充混合策略与混合扩充例例7 设 ,21ASSG ,其中 ,211S,212S2431A求它的解及值。解：显然该问题无鞍点解。设局中人、 的混合策略分别为：

25、X=(x1,x2),Y=(y1,y2).则1, 0,| ),(212121*1xxxxxxS1, 0,| ),(212121*2yyyyyyS2022-1-17Game theory536.5.1 混合策略与混合扩充混合策略与混合扩充则局中人支付的数学期望为：2212211121212431),(yxyxyxyxyxYXEjijiij25)41)(21(411yx2241111yxyx2022-1-17Game theory546.5.1 混合策略与混合扩充混合策略与混合扩充可见:当 ),21,21(*X),43,41(*Y25),(*YXE2121*212214213211),(yyyyYX

26、E25)(2525252121yyyy2022-1-17Game theory556.5.1 混合策略与混合扩充混合策略与混合扩充432414433411),(2211*xxxxYXE25)(254104102121xxxx),(),(*YXEYXE显然 ),(),(),(*YXEYXEYXE2022-1-17Game theory566.5.1 混合策略与混合扩充混合策略与混合扩充由定义1知： ),21,21(*X)43,41(*Y分别是局中人、的的最优策略，且 25*GV2022-1-17Game theory576.5.2 解的基本定理解的基本定理定理2 (基本定理) 任意一个矩阵对策

27、,21ASSG 其中 ,211mS,212nSnmijA)(一定有解(在混合策略意义下),且如果G的值是V,则以下两组不等式的解是局中人,的最优策略: 2022-1-17Game theory586.5.2 解的基本定理解的基本定理njVximiij, 111, 101miiixmix（11-1）miVyjnjij, 111, 101njjjynjy（11-2）2022-1-17Game theory596.5.2 解的基本定理解的基本定理（1）若 , 0*ix则 njjijVy1*（G的值） （2）若 , 0*jy则 miiijVx1*（4）若 miiijVx1*,则 0*jy（3）若 nj

28、jijVy1*,则 0*ix可用例7验证定理3 若 是对策G(同前)的最优混合局势,则对某一个i或j来说：),(*YX2022-1-17Game theory606.5.2 解的基本定理解的基本定理y1y2yn12nx11a11a12a1nV1x22a21a22a2nV2 xmmam1am2amnVm V1V2VnYAXyxYXEVTjminjiij11),(VV2022-1-17Game theory616.6 矩阵对策的解法矩阵对策的解法6.6.1 图解法图解法6.6.2 优势法优势法6.6.3 简化计算法简化计算法6.6.4 线性规划解法线性规划解法2022-1-17Game theor

29、y626.6.1 图解法图解法例例8 已知： ,21ASSG 其中 ,211S,212S1020355A求矩阵对策的解和值。 2022-1-17Game theory63解: 设局中人 的混合策略为 (x,1-x)T,x0,1。对局中人而言，他的最少可能收入为局中人选取1，2所确定的两条直线(定理3知): 6.6.1 图解法图解法V1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10 因为x1和x2一定大于0在x处的纵坐标中的最小者. 局中人用“最大最小”原则选取自己的策略,即:)2510,1520(minmax10 xxx2022-1-17Game theory6

30、4D点为极值点,D点坐标为： )4116,41(D即 41x4116v的最优混合策略为： )43,41(*XED(1/4,16 )VV1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10 xF从上图可以看出： )2510,1520(min10 xxx就是折线EDF. 2022-1-17Game theory656.6.1 图解法图解法同理，对局中人而言有 V=5y+35(1-y)=35-30y V=20y+10(1-y)=10+10y最小最大点为: )4116,85(G85y4116v即 的最优解为 ：)83,85(*Y对策值为： 4116v2022-1-17Gam

31、e theory666.6.1 图解法图解法FG(5/8,16 )HYV=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y2022-1-17Game theory676.6.1 图解法图解法课堂练习：求解下列矩阵对策，已知赢得矩阵为：211220A2022-1-17Game theory686.6.1 图解法图解法例例9 已知： ,21ASSG 其中 ,211S,43212S06145132A求对策的解和值。 解：显然无鞍点，作混合扩充： ,1 , 0| )1 ,(*1xxxS,1; 4 , 1, 0| ),(414321*2jjjyjyyyyyS2022-1-17G

32、ame theory696.6.1 图解法图解法对局中人而言，若选取 4321,时，的最小可能收入为以下四条直线在x处纵坐标中的最小者 v=2x+4(1-x)=4-2x (1)v=3x+(1-x)=2x+1 (2)v=x+6(1-x)=-5x+6 (3)v=5x (4)2022-1-17Game theory706.6.1 图解法图解法从图上可以看出 B点坐标即为所求的极值点. AB(2)(3)(1)(4)B点坐标为:)717,75(717,75*vx即 的最优解为 )72,75(*X2022-1-17Game theory716.6.1 图解法图解法同理可得： v=2y1+3y2+y3+5y

33、4 (5) v=4y1+y2+6y3 (6)由上节的定理3求出的最优解 将 分别代入方程(1)(4)得：75x2022-1-17Game theory726.6.1 图解法图解法0*1y0*4y0*2y0*3y定理定理3的的(4)定理定理3的的(2)定理定理3的的(2)定理定理3的的(4)vxvxvxvx71772556755651752127177187104242022-1-17Game theory736.6.1 图解法图解法代入(5)、(6)得： 7173*3*2vyy7176*3*2vyy解之得：72,75*3*2yy故的最优策略为)0 ,72,75, 0(*Y2022-1-17Ga

34、me theory746.6.2 优势法优势法对于一般的矩阵对策 ,21ASSG 其中 ,211mS,212nSnmijA)(定义定义3 若对固定的i、k有nj, 2 , 1若对固定的j和l，有 ilijmi, 2 , 1则称ijki优超，记为则称优超，记为jlljkjij2022-1-17Game theory756.6.2 优势法优势法(1) GGVV定理定理4 设G中的某个 0i被其余的 miiii1 ,0之一优超, 由G可得 ,21ASSG ，其中 njmiiiSijijmii, 1;, 1,0111100nmijaA)1()(于是有 (2) G中局中人的最优策略就是G中的最优策略；2

35、022-1-17Game theory766.6.2 优势法优势法若 ),(11100miixxxx是在 G中的最优解，则 ), 0 ,(11100miixxxx为在G中的最优解. (3) 2022-1-17Game theory776.6.2 优势法优势法例10 已知某矩阵对策G的支付矩阵为： 3880667864959379520503043A求解这个矩阵对策。 2022-1-17Game theory786.6.2 优势法优势法解：显然无鞍点，由于A的阶数为 , 55图解法失效。由定义可知 ,1423由定理1可将该问题简化为:3880667864959371A38806678649593

36、79520503043A2022-1-17Game theory796.6.2 优势法优势法64373A可用图解法求得最优解和值分别为： )32,31(*3X)21,21(*3Y53GV0664372A1A324252由又可看出：2A31从又可看出：，因此得： 2022-1-17Game theory806.6.2 优势法优势法即可得到对策G的解为： )0 ,32,31, 0 , 0(*X)0 , 0 , 0 ,21,21(*Y值为V=5。2022-1-17Game theory816.6.3 简化计算法简化计算法定理5 若矩阵对策 )(,1211nmijASSG)(,2212nmijdASS

37、G其中d为常数，则G1与G2有相同的解，且对策的值相差一个常数d，即： dVVGG122022-1-17Game theory826.6.3 简化计算法简化计算法推论1 若矩阵对策 )(,1211nmijASSG)(,2212nmijkASSG其中k0为常数，则G1与G2有相同的解,且12GGkVV2022-1-17Game theory836.6.3 简化计算法简化计算法例11 已知某矩阵对策G的支付矩阵如下： 1800120012003600A解：由推论1可取 6001k得同解矩阵：32261A2022-1-17Game theory846.6.3 简化计算法简化计算法由定理1可取d=-2

38、，简化为： 10042A由 v=4x+0(1-x) =4x v=0 x+1(1-x)=1-x则)54,51(*2X由 v=4y+0(1-y) =4y v=0y+1(1-y)=1-y则)54,51(*2Y542GV2022-1-17Game theory856.6.3 简化计算法简化计算法原问题的解为：)54,51(*X)54,51(*Y1680)254(600)2(6002GGVV2022-1-17Game theory866.6.4 线性规划解法线性规划解法考虑一般的问题： 其中 ,21ASSG ,211mS,212nS其混合扩充为： ),(,11*2*1*jminjiijyxyxESSG2022-1-17Game theory876.6.4 线性规划解法线性规划解法当局中人选定任一混合策略时便确定了n个数：),(21mxxxXnjximiij, 2 , 11因为局中人的支付期望值为：jinjmiijjnjijmiijminjiijyxyxyxyxEV)()(