对策理论谢家平学习课件

1、运筹学运筹学 Operation s Research 21.4.301 2 第第1010章章 对策理论对策理论 理解对策模型的三大要素理解对策模型的三大要素 了解矩阵对策的基本定理了解矩阵对策的基本定理 通晓纯策略和混合策略通晓纯策略和混合策略 掌握矩阵对策方程组法掌握矩阵对策方程组法 理解纳什定理和平衡偶理解纳什定理和平衡偶 掌握双矩阵对策的求解掌握双矩阵对策的求解 3 “田忌赛马” 对策论对策论（Game TheoryGame Theory），亦名），亦名“博弈论博弈论” 研究具有斗争或竞争性质现象的数学理论研究具有斗争或竞争性质现象的数学理论 第第1 1节对策论简介节对策论简介 具有具

2、有竞争或对抗性质的行为竞争或对抗性质的行为 研究对策行为中竞争各方是否存在最合理行动方案研究对策行为中竞争各方是否存在最合理行动方案, ,以及如何找以及如何找 到最合理行为方案的管理优化理论和方法到最合理行为方案的管理优化理论和方法 一个决策主体一个决策主体, ,面对不确定环境下的收益最大化行为面对不确定环境下的收益最大化行为 4 对策模型对策模型三要素三要素 n 局中人：在一个对策行为局中人：在一个对策行为( (或一局对策或一局对策) )中，有权中，有权决定自己行动方案的对策决定自己行动方案的对策参参 加者。加者。I=1,2,.,n。理性人理性人（有很好定义的偏好，在给定的约束下最大化偏好）

3、（有很好定义的偏好，在给定的约束下最大化偏好） n策略集：指一局对策中策略集：指一局对策中, ,可供局中人选择的实际、可行、完整的行动可供局中人选择的实际、可行、完整的行动方案，方案，Si n赢得函数：对任一局势赢得函数：对任一局势s, ,局中人局中人i可以得到一个赢得值可以得到一个赢得值Hi(s)。显然。显然, ,Hi(s)是局势是局势 的函数的函数, ,称为第个局中人的赢得函数称为第个局中人的赢得函数( (或支付函数或支付函数) )。 5 对策对策问题的分类问题的分类 n二二人对策，多人对策人对策，多人对策 n零和对策，非零和对策零和对策，非零和对策 n合作对策，非合作对策合作对策，非合作

4、对策 n有限对策，无限对策有限对策，无限对策 根据对策模型的数学特征：根据对策模型的数学特征： 6 第第2 2节矩阵对策节矩阵对策 一、一、矩阵对策的矩阵对策的数学模型数学模型 设局中人设局中人有个纯策略有个纯策略 , ,局中人局中人II有个纯策略有个纯策略 , ,则局中人则局中人 、的策略集分别为的策略集分别为 a1,a2,amb1,b2,bn S 1 = a1,a2,am ,S2 = b1,b2,bn 当局中人当局中人选定选定纯策略纯策略 和局中人和局中人II选定选定纯策略纯策略 后后, ,就形成了一个纯局势就形成了一个纯局势 。 可见这样的纯局势共有可见这样的纯局势共有 个。对任一纯局势

5、个。对任一纯局势 , ,记局中人记局中人的赢得值的赢得值为为 。 i a j b ij ,a b m n ij ,a b ij a 矩阵对策矩阵对策（二人有限零和对策（二人有限零和对策, ,finite two-person zero-sum game） A= a 11 a 12 a 1n a21a22a2n am 1 am 2 am n 为局中人为局中人I的赢得矩阵的赢得矩阵( (或为局中人或为局中人II的支付矩阵的支付矩阵) ) 其中：齐王的策略集: : S1= a a1, a a2, a a3, a a4, a a5, a a6 ， 田忌的策略集：S2= b b1, b b2, b b3

6、, b b4, b b5, b b6 。 下面矩阵称齐王的赢得矩阵： 8 例10-1 “田忌赛马”齐王在各局势中的益损值表（单位：千金） 1 2 3 4 5 6 a a a a a a 31111 1 311111 311111 31 1111 311111 3111 11 A = 356124 bbbbbb 当赢得矩阵A=(=(ark) )中等式 成立时，双方才有最优纯策略 并把（a ar,b bk）称为最优纯局势或对策G在纯策略下的解，又称鞍点。把其 值v 称之为对策G=S1，S2，A的值。 称G为有鞍点的对策。 10 rkij ij ij ji aaav=maxminminmax vv

7、kr = * ,bbaa jijiij aaa * 矩阵对策的纯策略 悲观准则 11 乙 甲 123min(aij) 1-71-8-8 2342 316-1-3-3 4-305-3 max(aij)1625 例10-2 甲方“小中取大”，乙方“大中取小” rkij ij ij ji aaav=maxminminmax=a22=2 鞍点（a a2, b b2） 对策G=S1，S2，A的值v=2 。 矩阵对策的矩阵对策的混合策略混合策略 设矩阵对策 G = S1, S2, A 。当 时，不存在最优纯策略。 例11-4 12 )(maxmin)(minmax ij ij ij ji aa 36 3

8、54 4 56 A = 12 12 maxmin,minmax ijij jjii vava vv = 11122122 11111111 11 3654 3615 14 11 4141292 Ex, yx yx yx yx y x yxyxyxy x/y/ = = = 对甲对甲（乙）（乙）给出一个选取不同策略的概率分布，以使甲给出一个选取不同策略的概率分布，以使甲（乙）（乙）在各种情况下的在各种情况下的 期望赢得最多期望赢得最多（损失最少）（损失最少）-即即混合策略。混合策略。 12概率 xi 136x1 254x2 概率 yjy1y2 14 0, 0= = y ER x ER 取取 , ,

9、则则 故故 和和 分别分别为局中人为局中人和和的最优策略的最优策略, , 对策对策值值( (局中人局中人的赢得期望值的赢得期望值) ) 。 1 43 41 21 2 * x/ , /,y/ , /=9 29 2 * E x ,y/ ,E x ,yE x,y/= 1 4 3 4 * x/ , /=1 21 2 * y/ , /= 9 2 G V/= 二阶矩阵对策的通解公式 乙 甲 12甲方概率 xi 1acx1 2bdx2 乙方概率 yjy1y2 dcba bcad dcba bd y dcba cd xdcba dy dcba dc x dcba db xydcba yxdyxcybxaxyE

10、R = = = )()( )( )1)(1 ()1 ()1 ( D bcad v D ca y D bd y D ba x D cd x cbdaD = = = = = = * * 2 * 1 * 2 * 1 )()(令 16 的值为对策 的解，为对策 ）策略，为甲、乙的最优（混合 有 Gv GYX YX YXERYXERm YXERYXERYXERv SYSX YXX XYY * * * * * * 2 * 1 * ),( , ),(minmax),(ax ),(maxmin),(min),( , = = ),(),(),( ),(max),(min),( ),(maxmin ),(minm

11、ax * * 21 2 1 * 1 * 2 * 1 * 2 * 2 * 1 YXEYXEYXE YXEYXEYXE vv YXEv YXEv SXSY SXSY SYSX = = = 二、矩阵对策的基本原理二、矩阵对策的基本原理 E x,y =a ij x i yj j i =a ij yj j x i =E i,y xi i i E x,y =a ij x i yj j i =a ij x i i yj=E x, jyj j j ijj j Ei, yay= 当局中人当局中人取纯策略取纯策略 时时, ,记其相应的赢得函数为记其相应的赢得函数为 i a iji i E x, ja x= 当局中

12、人当局中人取纯策略取纯策略 时时, ,记其相应的赢得函数为记其相应的赢得函数为 j b * E i,yE x ,yE x , j则则 是是G的解的的解的充要条件充要条件是：是： * x ,y 则则 是是G的解的充要条件是：存在数的解的充要条件是：存在数v, ,使得使得 和和 分别是不等式组分别是不等式组( () ) 和和( () )的的解解, ,且且 。 * x ,y * x * y G vV= aijxiv, j=1,n i xi=1 i xi0, i=1,m ( () ) aijyjv, i=1,m i yj=1 j yj0, j=1,n ( () ) n 矩阵对策矩阵对策及其解的性质及其

13、解的性质 l 定理定理1 1：对任一矩阵：对任一矩阵 , ,一定存在混合策略意义下的解。一定存在混合策略意义下的解。 12 GS ,S ;A= l 定理定理2 2：设：设 是矩阵对策是矩阵对策G的解的解, , ,则：则： (1) (1)若若 , ,则则 ； （2)2)若若 , ,则则 ； (3) (3)若若 , ,则则 ； (4) (4)若若 , ,则则 。 * x ,y G v V= 0 * i x * ijj j a yv= 0 * j y * iji i a xv= * ijj j a yv 0 * i x = * iji i a xv 0 * j y = 21 记矩阵对策记矩阵对策G的

14、解集为的解集为T(G), ,关于对策解集的性质有如下三个定理：关于对策解集的性质有如下三个定理： l定理定理3 3：设有两个矩阵对策：设有两个矩阵对策 其中其中 , , , ,L为为任一常数任一常数, ,则有则有 (1)(1) (2(2) ) 1121 2122 GS ,S ;A GS ,S ;A = = 1ij Aa=A 2 =aijL 21 GG VVL= 12 T GT G= l 定理定理4 4 设有两个矩阵对策设有两个矩阵对策 其中其中 为任一常数。则为任一常数。则 (1)(1) (2)(2) 112 212 GS ,S ;A GS ,S ; A = =a 0a 21 GG VV= a

15、 12 T GT G= l 定理定理5 5 设设 为为一矩阵对策一矩阵对策, ,且且 为斜对称矩阵为斜对称矩阵( (亦称对称对亦称对称对 策策) )，则，则 (1)(1) (2) ,(2) ,其中其中 和和 分别为局中人分别为局中人和和的最优策略集。的最优策略集。 12 GS ,S ;A= T AA= 2 0 G V= 12 T GT G= 1 T G 2 T G 23 n矩阵对策的矩阵对策的优超策略优超策略 l定义：设有矩阵对策定义：设有矩阵对策 , ,其中其中 , , , , 如果如果对一切对一切 都有都有 , , 则称则称局中人局中人的纯策略的纯策略 优优超于超于 ； 若若对一切对一切

16、, ,都有都有 ，则，则称局中人称局中人的纯策略的纯策略 优优超超于于 12 GS ,S ;A=S1= a1,am S2= b1,bn ij Aa= j=1,n 00 ijkj aa 0 i a i=1,m00 ijil aa 0 j b 0 l b 0 k a 24 优优超原则超原则： 设设 为为矩阵对策矩阵对策,其中其中, , , 如果如果纯策略纯策略 被被其余其余纯策略纯策略 中中之一所优之一所优超，由超，由G可可得到一个新的得到一个新的矩阵对策矩阵对策 G, ,其中：其中： 于是于是有：有： (1) (2)G中中局中人局中人的最优策略就是其的最优策略就是其在在G中中的最优策略的最优策略

17、; (3)若若G是是G中中局中人局中人的最优策略的最优策略,则则 便是便是其其在在G中中的最优策略。的最优策略。 若若 不是不是为纯策略为纯策略 中中之一所优超之一所优超,而是而是为为 的的某个凸线性组合所优超，定理的结某个凸线性组合所优超，定理的结 论仍然成立。论仍然成立。 12 GS ,S ;A= S1= a1,am S2= b1,bn ij Aa= 12 GS ,S ;A= 12 1 1 m ij mn ijj S, Aa aai,mj,n = aa = = = = GG VV = x*= 0,x2 * ,xm * T 1 aa2,am 1 aa2,ama2,am 例10-5 1/3*(

18、1) 2/3*(2) 7395973739 73 6875.564465.54 46 6088360603 30302 50592 73959 6875.54 60883 A = * * (0, 0,1/3, 2/3, 0) (1/ 2,1/ 2, 0, 0, 0) T T x y = = 27 三、矩阵对策的解法三、矩阵对策的解法 l方程组法方程组法 例例10-6：求解矩阵对策求解矩阵对策“田忌赛马田忌赛马” 解：已知齐王的赢得矩阵为解：已知齐王的赢得矩阵为 311111 131111 113111 111311 111131 111113 A = 易知易知, ,A A没有没有鞍点鞍点, ,

19、即对齐王和田忌来说都不存在最优纯策略。即对齐王和田忌来说都不存在最优纯策略。 设齐王和田忌的最优混合策略为设齐王和田忌的最优混合策略为 和和 ，从从矩阵矩阵A A的的元素来看元素来看, ,每每 个局中人选取每个纯策略的可能性都是存在的个局中人选取每个纯策略的可能性都是存在的, ,故可事先故可事先假定假定 和和 , ,于是求解线性方程组：于是求解线性方程组： 123456 T * xx ,x ,x ,x ,x ,x= 123456 T * yy ,y ,y ,y ,y ,y= 0 * i x 0 * j y 28 123456 123456 123456 123456 123456 123456

20、 123 3 3 3 xxxxxxv xxxxxxv xxxxxxv xxxxxxv xxxxxxv xxxxxxv xxxx = = = = = = 456 1xx = (I) 123456 123456 123456 123456 123456 123456 12 3 yyyyyyv yyyyyyv yyyyyyv yyyyyyv yyyyyyv yyyyyyv yy = = = = = = 3456 1yyyy = (II) 得到：得到： ， 故故齐王和田忌的最优混合策略齐王和田忌的最优混合策略为双方都以为双方都以1/6的概率选取每个纯策略。的概率选取每个纯策略。 xi=1/6, yj=

21、1/6, ij=1,6; v=1 l线性规划法线性规划法 a ijxi v, j=1,n i x i =1 i x i 0, i=1,m ( () ) a ij yjv, i=1,m i yj=1 j yj0, j=1,n ( () ) * 2211 maxmin( , )minmax( , ) y Sy Sx Sx S vE x yE x y = = = = = = mix x njvxa ts v i m i i m i iij ,.,2 , 1, 0 , 1 ,.,2 , 1, . . max)( 1 1 = = = = = njy y mivya ts v j n j j n j ji

22、j ,.,2 , 1, 0 , 1 ,.,2 , 1, . . min)( 1 1 0, i i x vx v = 1 min 1 ( )1 . . 00 1 max 1 ()1 . . 00 iji i i i i iji i i i i ijj j j j jijj jj jj a x zx xPa x v s t xx a y wy yDa y v s t yy = = = = ( () ) ( () ) 32 例例10-7：利用线形规划方法求解赢得矩阵利用线形规划方法求解赢得矩阵为为A的的矩阵对策矩阵对策 求求最优解及最优解及值值。 323 234 542 A = 123 Xx ,x

23、,x= 123 Yy ,y ,y= minZX = xi i=1 3 = x1 x2 x3 s.t. 3 x12 x25 x31 2 x13 x24 x31 3 x14 x22 x31 xi 0, i=1,2,3 （P) 解：解：此题无鞍点此题无鞍点, ,设局中人设局中人、局中人、局中人的混合策略分别为：的混合策略分别为： 并记对策的值为并记对策的值为V。则此问题可化为：。则此问题可化为： （D) 3 123 1 123 123 123 max( ) 3231 2341 . . 5421 0 j j j Z Yyyyy yyy yyy st yyy y = = 解得 123 123 32 0

24、16 16 23 0 1616 5 16 Xx ,x ,x, Yy ,y ,y, , Z XZ Y = = = 即原问题的解为：即原问题的解为： 123 123 16 5 3 2 0 5 5 23 0 55 v X*x ,x ,x, Y*y ,y ,y, , = = = 15 (), 16 j i ij y x Z Xxy vvv =由 35 第第3 3节节 双矩阵对策双矩阵对策 n 双矩阵对策（二人有限非零和对策）的双矩阵对策（二人有限非零和对策）的数学模型数学模型 局中人局中人I选择选择 , ,局中人局中人II选择选择 , ,则对策局势为则对策局势为 , , 与与这个局势相应的局中人这个局

25、势相应的局中人I的收入的收入为为aij, ,局中人局中人II的收入不再的收入不再是是- -aij, ,而是而是bij, ,记记作作 ( (aij, , bij) )。 对对这种对策这种对策, ,通常通常用用G=I, II; S1, S2; A, B表示表示, ,其中其中 A=aij, , B=bij分别分别是局中人是局中人I与与II的的支付矩阵。支付矩阵。 1i Sa 2j Sb , ij ab 囚徒B 坦白 抵赖 坦白 囚徒A 抵赖 （囚徒A ，囚徒B） 囚徒困境 n双矩阵对策的解法双矩阵对策的解法 l平衡偶平衡偶 在非零和对策中在非零和对策中, ,设设EI=(X,Y)与与EII=(X,Y)

26、分别是局中人分别是局中人I与与II的收入的收入, ,这里这里 XS1,YS2为任意策略。为任意策略。 如果存在一对策略如果存在一对策略X*S1,Y*S2使得使得 EI=(X,Y*) EI=(X*,Y*), EI=(X*,Y) EI=(X*,Y*) 对任意的对任意的XS1,YS2均成立均成立, ,则称策略则称策略(X*,Y*)为双矩阵对策为双矩阵对策G的一个平衡偶的一个平衡偶 l纳什定理纳什定理：（：（美国科学家美国科学家纳什纳什,1951,1951年年） 任何具有有限个纯策略的二人对策任何具有有限个纯策略的二人对策( (包括零和对策与非零和对策包括零和对策与非零和对策),),至少有一至少有一

27、个平衡偶个平衡偶 38 例例10-810-8：智猪博弈智猪博弈 笼子里面有两只猪笼子里面有两只猪, ,一只大一只小一只大一只小。笼子。笼子很长很长, ,一头有一个踏板一头有一个踏板, ,另一头是饲料的另一头是饲料的 出口和食槽出口和食槽。每。每踩一下踏板踩一下踏板, ,在远离踏板的猪圈一边的投食口就会落下少量的食在远离踏板的猪圈一边的投食口就会落下少量的食 物物。如果。如果有一只猪去踩踏板有一只猪去踩踏板, ,另一只猪就有机会抢先吃到另一边落下的食物另一只猪就有机会抢先吃到另一边落下的食物。按。按 一下按钮会有一下按钮会有1010个单位的猪食进槽个单位的猪食进槽, ,但是谁按按钮就会首先付出但

28、是谁按按钮就会首先付出2 2个单位的成本个单位的成本。 若若大猪先到槽边大猪先到槽边, ,大小猪吃到食物的比例是大小猪吃到食物的比例是9191；若大小猪同时到槽边进食；若大小猪同时到槽边进食, ,它们它们 吃到食物的比例是吃到食物的比例是7373；若小猪先到槽边；若小猪先到槽边, ,它们吃到食物的比例是它们吃到食物的比例是6464。如表。如表 102102所示所示, ,那么那么, ,在两头猪都有智慧的前提下在两头猪都有智慧的前提下, ,最终结果是什么呢？最终结果是什么呢？ 智猪博弈双矩阵：智猪博弈双矩阵： 小猪小猪 按按等待等待 大猪大猪 按按（5,1）（4,4） 等待等待（9，-1）（0,0

29、） 解: : 以智猪博弈为例, ,说明纯策略下的纳什均衡的求取。 (1)(1)当小猪选择按按钮时, ,如果大猪也选择按按钮, ,大猪的赢得是5 5；如果大猪选择等待, ,大猪的赢得是9,9,所以在 第一列的9 9下面划线； (2)(2)当小猪选择等待时, ,如果大猪选择按按钮, ,大猪的赢得是4 4；如果大猪也选择等待, ,大猪的赢得是0,0,所以在第 二列的第一个分量4 4下面划线； (3)(3)当大猪选择按按钮时, ,如果小猪选择按按钮, ,小猪的赢得是1 1；如果小猪选择等待, ,小猪的赢得是4,4,所以在第 一行的第二个分量的4 4下面划线； (4)(4)当大猪选择等待时, ,如果小猪

30、选择按按钮, ,小猪的赢得是-1-1；如果小猪选择等待, ,小猪的赢得是0,0,所以在第 二行的第二个分量0 0下面划线 小猪小猪 按按等待等待 大猪大猪 按按（5,1）（4,4） 等待等待（9，-1）（0,0） 因此, ,本例中存在唯一的纯策略纳什平衡偶(4,4),(4,4),即大猪按按钮, ,小猪选择等待是唯一可能出现的结局。 作作 业业 3（2） 4 5（1） 6（1） 7 11122122 11111111 11 3654 3615 14 11 4141292 Ex, yx yx yx yx y x yxyxyxy x/y/ = = = 对甲对甲（乙）（乙）给出一个选取不同策略的概率分

31、布，以使甲给出一个选取不同策略的概率分布，以使甲（乙）（乙）在各种情况下的在各种情况下的 期望赢得最多期望赢得最多（损失最少）（损失最少）-即即混合策略。混合策略。 12概率 xi 136x1 254x2 概率 yjy1y2 42 n矩阵对策的矩阵对策的优超策略优超策略 l定义：设有矩阵对策定义：设有矩阵对策 , ,其中其中 , , , , 如果如果对一切对一切 都有都有 , , 则称则称局中人局中人的纯策略的纯策略 优优超于超于 ； 若若对一切对一切 , ,都有都有 ，则，则称局中人称局中人的纯策略的纯策略 优优超超于于 12 GS ,S ;A=S1= a1,am S2= b1,bn ij Aa= j=1,n 00 ijkj aa 0 i a i=