清华大学运筹学8对策论

1、第十二章 博弈论,第一节 引言 第二节 矩阵对策基本理论 第三节 矩阵对策解法 第四节 其他类型对策,1/119,第一节 引言,一、对策现象和对策论 亦称博弈论，研究对抗或竞争活动。是现代数学新分支。政治、经济、军事活动乃至一般日常生活等都有这类活动。 对弈、战略；谈判；政治较量、国际集团间的角逐等。,2/119,竞争或对抗的双方或多方为取胜而选择策略称为对策。各方为了达到自己的目的，实现自己的目标和利益，必须考虑对手各种可能的行动方案，并选用对自己最有利或最合理的方案。 对策论就是研究对策中各方是否有最合理的行动方案，以及如何选用的数学分支。,3/119,张盛开教授70年代将“齐王赛马”视为

2、矩阵对策，列出了齐王的赢得矩阵，提出了问题的解。,4/119,1938年生，山东文登人。大连轻工学院运筹所教授、所长。1962年哈师大研究生毕业后，一直从事运筹学教学与研究工作。出版现代对策论方法、对策论及其应用、矩阵对策初步等。,二、对策三要素 对策模型，须有3个基本要素。 1局中人 有权决策者称为局中人，局中人全体用I表示。若有n个局中人，则I=1，2，n。至少有两个局中人。 可以是个人、群体。利益完全一致的参加者只能视为一个局中人。 局中人不能心存侥幸，不能利用其他局中人失误扩大自身利益。,5/119,2策略 可供局中人选择、可行的完整行动方案称为策略。各局中人的策略集记为S，每一局中人

3、策略集至少应有两个策略。 “齐正赛马”，若用(上，中，下)表示以上、中、下三等马依次参赛，就是一个策略。齐王和田忌都有6个策略： (上，中，下)、(上，下，中)、(中，上，下)、 (中，下，上)、(下，中，上)、(下，上，中)。,6/119,3赢得 (支付)函数 各局中人的策略形成局势。设si是第i个局中人的一个策略，则n个局中人的策略形成的策略组 s =(s1, s2, , sn) (12.1) s就是一个局势。 若以S记全部局势，则 S=S1S2Sn (12.2),7/119,局势s形成后，局中人i的赢得或所失值用Hi(s)表示，定义域是S，称为局中人i的赢得函数。 齐王和田忌的策略集可分

4、别用S1=(1, 2, , n)和S2=(1, 2, , n)表示。 齐王任一策略i和田忌任一策略j构成局势sij。如果1=(上，中，下)，1=(上，中，下)，则在s11中，齐王赢得H1(s11)=3，田忌赢得为H2(s11)= -3，如此等等。 当局中人、策略集和赢得函数确定后，也就确定了对策模型。,8/119,三、对策举例及分类 例2 (销售竞争)假定企业I，均于0, 1期间任一时刻出售某一产品 。I和II分别在时刻x和y出售，则I的收益(赢得)函数为： c(y-x) 若xy 问两个企业各应选择什么时机出售对自己最有利? 此例中，I、II可用策略无穷多。,9/119,例3 (费用分摊)3个

5、邻城均在某河岸边，可单独建水厂，也可合建大水厂。 合建大水厂加敷设管道的费用要比分建3个小水厂总费用少。 但合建大厂方案能否实施，要看费用分摊是否合理。如果某城分摊的费用比自己单独建多，就不会接受合建方案。应如何合理分摊费用，才能使其愿意合建大水厂?,10/119,例4 (拍卖)一般先由拍卖人介绍卖品并要价，然后请竞买人报价。每一次报价都比前一次高，最后卖给出价最高者。设n个买主分别报价p1，p2，pn，设pnpn-1p2p1，只要pn略高于pn-1，第n个买主就能买到，即卖品实际上在次高价上卖出。 问：各买主不能确知他人出价时，应如何报价才能以较低价格买到卖品，最后结果又会怎样?,11/11

6、9,例5 (困境难题)警官因事拘二人，分开审讯。 法律规定，若两人都承认是自己所为，各判7年；若都不承认，且证据不足，各判1年； 若仅一人承认，认者释放，不认者判9年。 两人要权衡“认”和“不认”利弊得失。,12/119,对策的分类： (1)根据局中人个数，二人对策和多人对策； (2)根据赢得函数之和，零和与非零和对策； (3)根据是否允许局中人合作，合作和非合作对策； (4)根据局中人策略个数，有限和无限对策。 还有许多其他分类方式， 矩阵对策最简单，但体现了对策论的一般思想和方法，是研究其他对策的基础。 本章重点介绍。其他模型只简要介绍。,13/119,第二节 矩阵对策基本理论,一、矩阵对

7、策纯策略 二局中人各自策略均有限；任一局势，一人所得恰为另一人所失，赢得之和为零。 设局中人I有m个纯策略1, 2, , m，有n个纯策略1, 2, , n；I和II的策略集分别为S1=(1, 2, , m)和S2=(1, 2, , n) 当I和分别选定i和j后，形成纯局势(i, j)，有mn个。(i, j)，记I的赢得值为aij，称,14/119,15/119,a11 a12 a13 a1n A= a21 a22 a23 a2n am1 am2 am3 amn 为局中人I的赢得矩阵。II的赢得矩阵是- A。 当局中人、各自策略集S1和S2，以及赢得矩阵A确定后，就确定了矩阵对策模型。 记为G

8、= S1，S2；A。在“齐王赛马”的例子中，齐王的赢得矩阵为：,16/119,3 1 1 1 1 -1 1 3 1 1 -1 1 A= 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 -1 1 3 1 1 1 1 -1 1 3 局中人的问题是：如何选择对自己最有利的纯策略以使赢得最大(或所失最小)? 举例说明各局中人如何选择最有利的策略。,17/119,例6 设矩阵对策为G= S1，S2；A，其中 -6 1 -8 A= 3 2 4 9 -1 -10 -3 0 6 I的最大赢得是9，须用3。II料到了I会用3，以3对之，使I不但得不到9，反而失掉10。I也会猜到II的心，转而用4，使

9、II得不到10，反而失掉6；,如果双方都不想冒险，不心存侥幸，而是考虑到对方必然设法使自己所得最少，就应从各自可能出现的最不利情形中选择一个最有利的应对之，即所谓“理智”，是双方实际可接受并采取的一种稳妥方法。 例6中I在各纯策略下可能的最少赢得为：-8，2，-10，-3，最好结果是2。无论II用什么纯策略，I只要取2，就能保证赢得不少于2，而任何其他纯策略，都可能使赢得少于2，甚至输给对方。,18/119,II各纯策略最不利结果是：9，2，6，最好是2，只要选2，无论I取何种纯策略，所失都不超过2，而任何其他纯策略都可能使自己的所失超过2。 I和分别用2和2，方属“理智”，I如期赢得了可接受

10、的2，II也如期使I的所得不超过2，竞争促成了平衡局势(2，2)，双方均可接受，对自己都是最稳妥。,19/119,20/119,3,3,9,-10,4,6,1,-3,2,2,2,2,局中人I和分博弈过程,对一般矩阵对策，有如下定义。 定义1 设矩阵对策G= S1，S2；A，其中S1=(1, 2, , n)和S2=(1, 2, , n)，A=(aij)mn。若 max min aij =min max aij (12.5)(12.3) i j j i 成立，记其值为VG，则称VG为对策的值，使式(12.5)成立的纯局势(*i，*j)称为G在纯策略意义下的解(或平衡局势)，*i和*j 分别称为I和

11、II 的最优纯策略。,21/119,例6矩阵A中对应平衡局势(2，2) 的元素a22既在所属行最小，又在所属列最大，即 ai2a22a2j i=1, 2, 3, 4；j=1, 2, 3 (12.6)(12.4) 对于一般矩阵对策，有如下定理。 定理1 矩阵对策G= S1，S2；A在纯策略意义下有解的充要条件是存在纯局势(*i，*j)，使得对任意i和j，有 aij*ai*j*ai*j (12.7) (12.5),22/119,证明 先证充分性，由式(12.7) (12.5)，有 max aij*ai*j*min ai*j i j 而 min max aijmax aij* j i i min a

12、i*jmax min aij j i j 所以，min max aijai*j*max min aij (12.8) j i i j (12.6),23/119,另一方面，对于任意的i和j，有 min aijaijmax aij j i 所以，max min aijmin max aij (12.9) (12.7) i j j i 由(12.8) (12.6)和(12.9) (12.7)可得到： max min aij=min max aij= ai*j* i j j i 且VG= ai*j*,24/119,再证必要性。设有i*和j*，使得 min ai*j= max min aij max

13、aij*= min max aij j i j i j i 则由 max min aij=min max aij i j j i 有 max aij* = min ai*jai*j*max aij*= min ai*j i j i j 所以，对于任意的i*和j*，有 aij* max aij*ai*j*min ai*jai*j 证毕。,25/119,对任意矩阵A，称使式(12.7) (12.5)成立的ai*j*为矩阵A的鞍点。矩阵A的鞍点也称对策的鞍点。 定理1(12.7) (12.5)的含义：(*i，*j)应使得： 当I选择了*i后，II为使所失最少，只能用*j，否则会失去更多； 反之，当I

14、I选择了*j后，I为了使赢得最多，只能用*i，否则会减少赢得。双方的竞争在(*i，*j)中达到了平衡。,26/119,例7 设有矩阵对策G= S1，S2；A，其中 9 8 11 8 A= 2 4 6 3 5 8 7 8 10 7 9 6 max min aij=min max aij=ai*j*=8，i*=1, 3；j*=2, 4，故 (1, 2)，(1, 4)，(3, 2)，(3, 4)都是对策的解，VG=8。 例7 (例6)表明，一般矩阵对策可有多解，多解之间有如下两种关系：,27/119,28/119,性质1 (无差别性)若(i1，j1)和(i2，j2)是对策G的两个解，则 ai1, j

15、1= ai2, j2 性质2 (可交换性)若(i1，j1)和(i2，j2)是对策G的两个解，则(i1，j2)和(i2，j1)也是对策G的两个解。 矩阵对策的值惟一，当一个局中人选择了最优纯策略后，其赢得值不依赖于对方的纯策略。,29/119,二、矩阵对策的混合策略 在G= S1，S2；A中，I至少能保证的赢得是 v1= max min aij i j II的至多所失是 v2=min max aij j i I的赢得不会多于II的所失，故有 v1v2。当v1=v2时，G在纯策略意义下有解，且VG=v1=v2。,30/119,当v14=v1,31/119,于是，当双方各根据从最不利中争最有利的原则

16、选纯策略时，应分别选2和1，I赢得5，但1对II来说非最优，会考虑2。I会改出1，以赢得6，而II可能仍取1对付I的1。 无双方都可接受的局势，即无纯策略意义下的解。,32/119,1,1,2,6,2,1,1,3,局中人I和分博弈过程,5,4,2,2,33/119,既然局中人无最优策略，但心目中是否对各个策略有所侧重呢？ 即，是否给予各个策略不同的权重呢？ 若是，各权重的分布或概率分布为何呢？ 如I给予1和2的权重分别是x和1-x，这样的权重分布称为混合策略。 同样，II也可分别以概率y，1-y选取纯策略1和2。,34/119,定义2 设有G= S1，S2；A，其中 S1=(1, 2, , m

17、)和S2=(1, 2, , n)，A=(aij)mn 记 S1*=xEm| xi0, i=1, 2, , m； xi=1 S2*=yEn| y j0, j=1, 2, , n； y j =1。 分别称为局中人I和II的混合策略集(或策略集)；对xS1*和yS2*，称x和y为混合策略(或策略)，(x, y)为混合局势(或局势)。I的赢得函数记成 E(x, y)= xTAy (12.10) (12.8) 称G*=S1*，S2*；A为对策G的混合扩充。,35/119,纯策略是混合策略的特殊情形。 混合策略x=(x1，x2，xm)T可理解为：若进行多局对策，I选用纯策略1, 2, , m的频率；若只对

18、策一次，则反映了I对各纯策略的偏爱程度。 仍设局中人理智，则I选择混合策略x 时，其预期所得(最不利情形)是min E(x, y)， yS2*,36/119,因此，I应选取xS1*，使得 v1= max min E(x, y) (12.11) (12.9) xS1* yS2* 同理，II可保证的所失期望值至多是 v2= min max E(x, y) (12.12) (12.10) yS2* xS1*,37/119,定义3 设G*=S1*，S2*；A是G=S1，S2；A的混合扩充。如果 max min E(x, y)= min max E(x, y) (12.13) xS1* yS2* yS2

19、* xS1* (12.11) 记其值为VG，则称VG为对策的值，称使(12-13) (12.11)成立的混合局势(x*, y*)为G在混合策略意义下的解(或平衡局势)，称x*和y*分别为局中人I和II的最优混合策略。 对G及G*一般都用G=S1，S2；A表示。当G无纯策略意义下的解时，讨论的自然是混合策略意义下的解。,38/119,和定理1类似，可给出G 在混合策略意义下有解的充要条件。 定理2 矩阵对策G在混合策略意义下有解的充要条件是：存在x*S1*，y*S2*，使得对任意xS1*和yS2*，有 E(x, y*)E(x*, y*)E(x*, y) (12.14) (12.12),39/11

20、9,例8 考虑矩阵对策G=S1，S2；A，其中 A= 3 6 5 4 在纯策略意义下无解，设x=(x1, x2)T，y=( y1, y2)T为I和II的混合策略，则 S1*(x1, x2)T | x1, x20，x1+ x2=1 S2*(y1, y 2)T | y1, y20，y1+ y2=1 I的赢得的数学期望是 E(x, y)=3x1y1+6x1y2+5x2y1+4x2y2 =3x1y1+6x1(1-y1)+5(1- x1)y1+4(1- x1)(1-y1) = -4(x1-1/4)(y1-1/2)+9/2,40/119,取x *=(1/4, 3/4)和y*=(1/2, 1/2)，则E(x

21、*, y*)=9/2，E(x*, y)= E(x, y*)=9/2，即有 E(x, y*)E(x*, y*)E(x*, y) x *=(1/4, 3/4)和y*=(1/2, 1/2)分别为I和II的最优策略，对策的值(I赢得的期望值)为VG=9/2。,41/119,三、矩阵对策的基本定理 在构造矩阵对策解的过程中，证明矩阵对策有解，介绍基本求解方法一一线性规划法。 以下，记 E(i, y)=aijyj (12.15) (12.13) j E(x, j)=aijxi (12.16) (12.14) i E(i, y)为 I取纯策略i时的赢得值， E(x, j)为II取纯策略j时的赢得值。,42/

22、119,由式(12.15)和(12.16)，有 E(x, y)= aijxiyj =(aijyj)xi=E(i, y)xi (12.17) i j i j i (12.15) E(x, y)=aijxiyj =(aij xi) yj=E(x, j) yj (12.18) i j j i j (12.16) 用上面记号，定理2也可表达如下： 定理3 设对任意xS1*和yS2*，则(x *, y*)为G的解的充要条件是 E(i, y*)E(x*, y*)E(x*, j) (12.19) (12.17),43/119,证明 设(x *, y*)是G的解，由定理2，(12.14) (12.12)成立。

23、由于纯策略是混合策略特例，故(12.19) (12.17)成立。反之，设(12.19) (12.17)成立，由 E(x, y*)=E(i, y)xiE(x*, y*)xi =E(x*, y*) i i E(x*, y)=E(x*, j)yjE(x*, y*)yj =E(x*, y*) j j 即得(12.14) (12.12) ，证毕。 定理3说明，当验证(x *, y*)是否为G的解时，只需验证(12.19) (12.17)表示的mn个不等式，大大简化对解的验证。,44/119,定理4也是定理3的等价形式。 定理4 设x*S1*，y*S2*，则(x *, y*)为G的解的充要条件是：存在数v

24、，使x *和y*分别是不等式组(12.20) (12.18)和(12.21) (12.19)的解，且v=VG。 aijxiv (j=1, 2, , n) (12.20) (12.16) xi =1 xi0 (i=1, 2, , m) aijyjv (i=1, 2, , m) (12.21) (12.19) yj=1 yj0 (j=1, 2, , n),45/119,下面是矩阵对策的基本定理。 定理5 对任一矩阵对策G=S1，S2；A，一定存在混合策略意义下的解。 证明 由定理3，只要证明存在x*S1*，y*S2*，使(12.19) (12.17)成立。为此，考虑如下两个线性规划问题： Max

25、w (P) s.t. aijxiw (j=1, 2, , n) xi =1 xi0 (i=1, 2, , m),46/119,Min v (D) s.t. aijyjv (i=1, 2, , m) yj=1 yj0 (j=1, 2, , n) 容易验证，(P)和(D)互为对偶。且 x=(1, 0, , 0)TEm w=min a1j 是(P)的一个可行解； y=(1, 0, , 0) TEn v=max ai1 是(D)的一个可行解。,47/119,由线性规划对偶定理可知，(P)和(D)分别存在最优解(x*, w*)和(y*, v*)，且w*=v*。即存在x*S1*，y*S2*和数v*，使得对

26、任一i=1, 2, m和j=1, 2, , n，有 aijyj*v*aijxi* (12.22) (12.20) 或 E(i, y*)v*E(x*, j) (12.23) (12.21) 又由 E(x*, y*)=E(i, y*)x*iv*x*i = v* i i E(x*, y*)= E(x*, j)y*jv*y*j = v* j j 得到v*=E(x*, y*)，故由(12.23)知(12.19)成立，证毕。,48/119,定理5构造出了G的一个解，不仅证明G有解，也指出如何用线性规划方法求解。 定理6 设(x*, y*)是矩阵对策G的解，v =VG，则 (1)若x*i0，则aijyj*=

27、v。 (2)若y*j0，则aijxi*=v。 (3)若aijyj*v，则y*j=0 证明 由v = max E(x, y*) xS1*,49/119,有 v-aijyj*= max E(x, y*)- E(i, y*)0 xS1* 又因 x*i(v-aijyj*)= v -aij x*i yj*=0 x*i0，(i=1, 2, , m) 所以，当x*i0时，必有aijyj*=v；当aijyj*v时，必有x*i=0，(1)、(3)得证。同样可证(2)、(4)。 以下，记T(G)为矩阵对策G的解集，下面3个定理是关于矩阵对策解的性质的主要结果。,50/119,定理7 设G1= S1，S2，A1和G

28、2= S1，S2，A2，A1=(aij)，A2=(aij+L)，L为一任意常数，则 (1)VG2= VG1+L (2) T(G2)=T(G1) 定理8 设G1= S1, S2, A和G2= S1, S2, A，0，为一任意常数，则 (1) VG2=VG1， (2) T(G2)=T(G1),51/119,定理9 设G= S1, S2, A，A= -A T为斜对称矩阵（亦称对称对策)，则 (1) VG=0 (2) T(G2)=T(G1) T(G1)和T(G2)分别为I和的最优策略集。,第三节 矩阵对策解法,一、图解法 用于赢得矩阵为2n或m2阶的对策问题，简单，直观解释对策论的思想。 例9 用图解

29、法求解G= S1，S2，A， A= 2 3 11 7 5 2,52/119,53/119,解 设I混合策略为(x, 1- x)T，x0, 1。过数轴0和1分别做垂线I-I和-。纵坐标分别表示I采取纯策略2和1时，II采取各纯策略时的值(见图12-1)。 当I选定(x, 1-x)T后，可能的最少赢得为由1，2和3确定的3条直线在x处的纵坐标最小者。 对I来说，就是确定x ，使3个纵坐标最小者尽可能地大。x=OA时，纵坐标AB即为对策的值。,54/119,I,II,11,3,2,2,5,7,0,O,A,B,B1,B2,B3,1,x,1,2,3,I,II,图12-1 2n矩阵对策图解法,55/119

30、,为求x 和VG，可联立过B点两条直线的方程： 3x+5(1- x)= VG 11x+2(1- x)= VG 解得x=3/11，VG49/11。 I的最优策略为x*=(3/11, 8/11) T。 若y*=(y1*, y2*, y3*)T为II的最优策略，则 由E(x*, 1)=23/11+78/11=62/1149/11=VG和定理6知，有y1*=0。最优策略只由2和3组成。,56/119,又因x1*=3/110；x2*=8/110，由定理6，可由 3y2+11y3=49/11 5y2+ 2y3=49/11 y2+ y3=1 求得 y2*=9/11；y3*=2/11。所以，II的最优策略为

31、y*=(0, 9/11, 2/11)T。,57/119,例10用图解法求解G= S1，S2，A，其中 2 7 A= 6 6 11 2 解 设II策略为(y, 1- y)T，y0, 1。图12-2，对任一y0, 1，直线1，2和3纵坐标是取策略(y, 1- y)T时赢得。按从最不利中选最有利原则，要确定y，使三纵坐标最大者尽可能小，就是选y，使A1yA2，这时，对策值是6，,58/119,I,II,11,6,2,2,6,7,0,O,A1,B1,B2,1,x,1,2,3,I,II,图12-2 m2矩阵对策图解法,A2,59/119,由方程组 2y +7(1- y)=6 11y +2(1- y)=6

32、 解得OA1=1/5，OA2=4/5，故II最优策略是 y*=(y, 1-y)T，1/5y4/5，I的最优策略只能是(0, 1, 0) T，即取纯策略2。,60/119,二、方程组法 按定理4，(x*, y*)是不等式组(12.20) (12.18)和(12.21) (12.19)的解； 按定理5和6，若x*i和y*j均不为零，不等式组转化为方程组： aijxi=v (j=1, 2, , n) (12.24) (12.22) xi =1，xi0 (i=1, 2, , m) aijyj=v (i=1, 2, , m) (12.25) (12.23) yj=1，yj0 (j=1, 2, , n),

33、61/119,若(12.24) (12.22)和(12.25) (12.23)有解x*和y*，便求得G的解。若无解，则可视情况，将其中某些改成不等式，再试解，直至求得G的解。 因事先假定x*和y*均不为零，故当最优策略某些分量实际为零时，两方程组可能无解，因此，该法有局限性。 但22矩阵，当I赢得矩阵 A= a11 a12 a21 a22 无鞍点时，易证，各局中人最优策略中x*i和y*j均大于零。于是，由定理5，方程组,62/119,a11x1+ a21x2=v a11y1+ a12 y 2=v a12x1+ a22x2=v a21 y1+ a22 y2=v x1+ x2=1 y1+ y2=1

34、 一定有严格非负解（即两个局中人的最优策略)： x*1=(a22- a21)/(a11+ a22- a12- a21) x*2=(a11- a12)/(a11+ a22- a12- a21) y*1=(a22- a12)/(a11+ a22- a12- a21) y *2=(a11- a21)/(a11+ a22- a12- a21) v *=(a11 a22- a12a21)/(a11+ a22- a12- a21)=VG,63/119,例11求解矩阵对策G= S *1，S *2；A，其中A为： 1 2 3 4 5 1 3 4 0 3 0 2 5 0 2 5 9 3 7 3 9 5 9 4

35、4 6 8 7 6 5 6 0 8 8 3 解 先按优超原则简化A。所谓优超。A第4行元素均大于或等于第1行对应者，对I来说，4优于1，可划掉第1行；同理划掉第2行，得新矩阵A1：,64/119,1 2 3 4 5 3 7 3 9 5 9 A1 = 4 4 6 8 7 6 5 6 0 8 8 3 对于矩阵A1，第1列优于第3列，第2列优于第4和第5列，可从A1中划掉第3、4和第5列，得到矩阵A2：,65/119,1 2 3 7 3 A2 = 4 4 6 5 6 0 对于矩阵A2，第1行优超于第3行，故可从中划掉第3行，得到矩阵A3： 1 2 A3 = 3 7 3 4 4 6,66/119,易知

36、A3无鞍点，可求方程组 7x3+ 4x4=v 7y1+3y 2=v 3x3+6x4=v 4y1+6y2=v x3+ x4=1 y1+ y2=1 的解为 x*3=1/3，x*4=2/3，y*1=1/2，y*2=1/2 以矩阵A为赢得矩阵的对策的一个解就是 x*=(0, 0, 1/3, 2/3,0)T，y*=(1/2, 1/2, 0, 0,0)T VG=5,67/119,例12 求解矩阵对策“齐王赛马”。 解 已知该矩阵A无鞍点，齐王和田忌都无最优纯策略。设二人最优混合策略分别为 x*=(x*1, x*2, x*3, x*4, x*5, x*6)T和 y*=(y*1, y*2, y*3, y*4,

37、 y*5, y*6)T。 从A的元素看，各局中人选任一策略可能性都有，故可事先假定x*i0(i=1，6)和y*j0(j=1，6)。于是，求解方程组,68/119,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,69/119,3y1+y2+y3+y4+y5-y6=v y1+3y2+y3+y4-y5+y6=v y1-y2+3y3+y4+y5+y6=v -y

38、1+y2+y3+3y4+y5+y6=v y1+y2-y3+y4+3y5+y6=v y1+y2+y3-y4+y5+3y6=v y1+y2+y3+y4+y5+y6=1 得到x*i=1/6(i=1，6)和y*j=1/6 (j=1，6)，VG=v=1，双方都以1/6的概率选取各纯策略，或者说在6个纯策略中随机地选取一个即为最优策略，最后结局应是：齐王赢的机会为5/6，赢得的期望值是1千金。,70/119,三、线性规划法 由定理5可知，求解矩阵对策可转化为求解互为对偶的(P)和(D)。故在(P)中，令(由定理7，不妨设w0)： xi = xi/w (i=1，m) (12-31) (12.29) 则(P)

39、的约束条件变成： aijxi1 (j=1, 2, , n) xi =1/w xi0 (i=1, 2, , m),71/119,故(P)等价于线性规划问题(P)： Min xi (P) s.t. aijxi1 (j=1, 2, , n) xi0 (i=1, 2, , m) 同理，令yj =yj/v (j=1，n) (12.32) (12.30) 可知(D)等价于线性规划(D)： Max yj (D) s.t. aijyj1 (i=1, 2, , m) yj0 (j=1, 2, , n) (P)和(D)互对偶，可用单纯形或对偶单纯形求解，再由(12.31) (12.29)和(12.32) (12.

40、30)求对策解。,72/119,例13 利用线性规划方法求解下述矩阵对策，其赢得矩阵为： 7 2 9 2 9 0 9 0 11 求解互为对偶的线性规划问题: Min x1+x2+x3 s.t. 7x1+2x2+9x31 (P) 2x1+9x2 1 9x1+ 11x31 x1, x2, x30,73/119,Max y1+ y2+ y3 s.t. 7y1+2y2+9y31 (D) 2y1+9y2 1 9y1+ 11y31 y1, y2, y30 线性规划解为x=(1/20, 1/10, 1/20)T，w=1/5， y=(1/20, 1/10, 1/20)T，v=1/5 对策问题发解为： VG=1

41、/w=1/v=5 x*=VGx=5(1/20, 1/10, 1/20)T= (1/4, 1/2, 1/4)T， y *=VGy=5(1/20, 1/10, 1/20)T= (1/4, 1/2, 1/4)T,第四节 其他类型对策,一、二人无限零和对策 局中人策略集如区间0, 1。G=S1，S2；H表示二人无限零和对策，S1和S2至少一个是无限集，H为局中人I的赢得函数。记 v1= max min H(i，j) iS1，jS2 v2= min max H(i，j) jS2，iS1,74/119,75/119,则v1为I的至少赢得，v2为的至多所失，有v1v2，当v1=v2时，有如下定义： 定义4

42、设G=S1，S2；H为二人无限零和对策。若存在i*S1，j*S2，使得 max min H(i，j) = min max H(i，j) iS1 jS2 jS2 iS1（12.33） （12.31） 记VG = H(i*，j*) ，VG 为对策G的值，称使上式成立的(i*，j*)为G在纯策略解，i*和j*分别称为I和最优纯策略。,76/119,定理10 (i*, j*)为G有纯策略解的充要条件：对任意iS1，jS2，有 H(i, j*)H(i*, j*)H(i*, j) （12-34）（12.32） 例14 设I、独立地从0, 1分取实数x和y，I的赢得为H(x, y)=2x2- y2。I希望越

43、大越好，II希望越小越好。图12-3是H(x, y)等值线。 不难看出平衡局势为(1, 1)，即i*=1，j*=1分别为I和II最优纯策略，VG=1。可验证，对(i*，j*) =(1, 1)，式(12-34) （12.32）成立。,77/119,y,0,1,x,H(x, y)=1,图12-3,1,H(x, y)1,H(x, y)1,78/119,由矩阵对策知，(12.33) (12.31)一般不成立，即G=S1，S2；H无纯策略解。 同矩阵对策引入混合策略类似，也可定义无限对策混合策略： I和II的混合策略x和y 分别为S1和S2上的概率分布(或分布函数)，混合策略集记为X和Y。若x，y表示纯

44、策略，FX(x)，FY(y)表示混合策略X，Y的分布，则I的赢得函数可有4种形式：,79/119,H(x，y)以及 H(X, y)S1 H(x, y)dFX(x) H(x, Y)S2 H(x, y)dFY(y) H(X, Y)S1S2 H(x, y)dFX(x)dFY(y) 定义5 若有 sup inf H(X, Y)=inf sup H(X, Y)=VG (12-35) (12.33) X Y Y X 称VG为G的值，使上式成立的(X*，Y*)为G的解，X*和Y*分别为I和最优策略。,80/119,定理11 (X*, Y*)为对策G=S1，S2；H的解的克要条件是：对任意XX，YY，有 H(

45、X, Y*)H(X*, Y*)H(X*, Y) (12.36) 当S1=S2=0, 1且H(x, y)为连续函数时，称这样的对策为连续对策。对连续对策而言，局中人I、II的混合策略即为0, 1区间上的分布函数。记0, 1区间上的分布函数的集合为D，则有 H(X, Y) 0 1 0 1 (, )()(),81/119,对连续对策，记 v1= max min H(X, Y) XD，YD v2= min max H(X, Y) YD，XD 下面是关于连续对策的基本定理。 定理12 对任何连续对策，一定有v1= v2。（证明略去）,82/119,例15 (生产能力分配问题)某公司甲、乙两厂，分处A，B

46、两市。设总产能1个单位，两市对产品总需求也是1个单位。若A市需求x，则B的需求虽为1-x，只要A厂生产能力为x，就能供需平衡。但现在不知A市确切需求x，若安排A厂产能为y，则会使供需失衡。失衡程度可用表示为： max , 1 1 公司目标是选择y，使得 max max , 1 1 (12.37) 0 x1 达到极小。,83/119,如果以市场需求为一方，公司为另一方，则以上问题可化为连续对策问题，其中 S1= S2=0, 1，H(x, y)= max , 1 1 对策的解是：最优纯策略是y*=1/2，即两厂各生产一半；需求方最优混合策略是：分别以0.5的概率取0和1，即需求要么都在A市，要么全

47、在B市满足，两种情况概率相等。 对策的值为VG=2，即当公司和市场均选择各自最优策略时，两市需求大于供给的平均程度为2(求解过程较复杂，略)。,84/119,二、多人非合作对策 多人对策各局中人赢得函数之和不一定为0， 非合作对策，指不许局中人事先交换任何有关策略选择的信息，不许有任何约定，矩阵对策就是一种非合作对策。 一般非合作对策模型如下： (1)局中人集合：I=1，2，n)； (2)每个局中人的策略集：S1，S2，Sn； (3)局势：s=(s1，s2，sn)S1S2Sn； (4)局中人i的赢得函数记为Hi(s)，一般说来，Hi(s)0。n人非合作对策一般用符号G=I，Si，Hi表示。,8

48、5/119,为讨论n人非合作对策平衡局势，引入记号： s|s0i =(s1，s2，si-1，s0i，si+1，sn) (12.38) (12.36) 意思是：在局势s=(s1，s2，sn)中，局中人i将自己的策略由si换成s0i其他局中人策略不变而得到的一个新局势。如果存在局势s，使得对任意s0iS i，有 Hi(s)Hi(s|s0i) 则称局势s对局中人i有利，也就是说，若局势s 对局中人i有利，则不论局中人i将如何改变自己的策略，都不会得到比在局势s中更多的赢得。显然，在非合作时，每个局中人都力图选择对自己最有利的局势。,86/119,定义6 如果局势s对所有的局中人都有利，即对任意iI，

49、有s0iS i，有 Hi(s)Hi(s|s0i) (12.39) (12.37) 则称s 为非合作对策G的平衡局势(或平衡点)。 当G为二人零和对策时，上述定义为：(i*，j*)为平衡局势的充要条件是：对任意i，j，有 aij*ai*j*ai*j (12.40) (12.38) 与上面关于矩阵对策平衡局势的定义一致。,87/119,由矩阵对策知，n人非合作对策不一定有纯策略意义平衡局势，需要考虑局中人混合策略。对每个局中人策略集S i，令S i*为定义在S i 上的混合策略集(即S i上所有概率分布的集合)，xi表示局中人i的一个混合策略，x=(x1，xn)为一个混合局势， x|zi =( x

50、1，x2，xi-1，zi，xi+1，xn) 表示局中人i在局势x中，将自己策略由xi换成zi 而得到的新混合局势。 记Ei(x)为局中人i在x 中赢得期望值，则有以下n人非合作对策解的定义。,88/119,定义7 若iI，有ziS*i，Ei(x|zi)Ei(x) 则称x为n人非合作对策的平衡局势(或平衡点)。 n人非合作对策已有非常重要结论： 定理13 (Nash定理) n人非合作对策混合平衡局势一定存在。 对于二人有限非零和对策(双矩阵对策)，Nash 定理如下：存在x*S*1，y*S*2，使得 E1(x*, y*)=x*TAy*xTAy*=E1(x, y*) xS*1 (12.41) (1

51、2.39) E2(x*, y*)=x*TBy*x*TBy=E2(x*, y) yS*2 (12.42) (12.40),89/119,John Forbes Nash, Jr. (born June 13, 1928) is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the factors that govern chance and events inside

52、 complex systems in daily life. Serving as a Senior Research Mathematician at Princeton University during the latter part of his life, he shared the 1994 Nobel Memorial Prize in Economic Sciences with game theorists Reinhard Selten and John Harsanyi.,90/119,91/119,2002年8月27日访问清华,92/119,双矩阵以及一般n人非合作对

53、策平衡点远未解决。对于22阶双矩阵对策，有如下结果：局中人赢得矩阵分别为： A= a11 a12 B= b11 b12 a21 a22 b21 b22 局中人I和的混合策略为(x,1- x)和(y, 1-y)，由式(12.41) (12.39)和(12.42) (12.40) ，局势(x, y)是平衡点的充要条件是 E1(x, y) E1(1, y) (12.43) (12.41) E1(x, y) E1(0, y) (12.44) (12.42) E2(x, y) E2(x, 1) (12.45) (12.43) E2(x, y) E2(x, 0) (12.46) (12.44),93/11

54、9,由式(12-43) (12-41)和(12-44) (12-42) ，有 Q(1-x)y-q(1-x)0 (12.47) (12-45) Qxy- qx0 (12.48) (12-46) Q=a11+ a22- a21- a12，q= a22- a12，求解，得到 (1)当Q=0，q=0时，0 x1 0yl (2)当Q=0，q0时，x=0 0y1 (3)当Q=0，q0时，x=1 0y1 (4)当Q0时，记q/Q=，有 x=0 y 0x1 y= x=1 y,94/119,类似，由(12.45) (12.43) 和(12.46) (12.44) ，有 R(1- y)x -r(1- y)0 (1

55、2.49) (12.47) Rxy- ry0 (12.50) (12.48) R=b11+ b 22- b 21- b 12，r= b 22- b 12，求解，得到 (1)当R=0，r=0时，0 x1 0yl (2)当R=0，r 0时， y=0 0 x1 (3)当R=0，r 0时， y=1 0 x1 (4)当R0时，记r/R=，有 y=0 x 0y1 x= y=1 x,95/119,例16 求解22阶双矩阵对策，其中 A= 2 -1 B= 1 -1 -1 1 -1 2 Q=50, q=2, =2/5 R=50, r=3, =3/5 将这些结果代入双矩阵对策解的公式，得到 x=0 y2/5 0x

56、1 y=2/5 （12.51） （12.49） x=1 y2/5 y=0 x3/5 0y1 x=3/5 （12.52） （12.50） y=1 x3/5,96/119,解上面不等式，得到3个平衡点： (x，y)=(0，0)，(3/5，2/5)，(1，1) 该解在图12.4中分别以粗线和虚线表示，3个交点即为3个平衡点。 由 E1(x, y)= 5xy-2(x+y)+1， E2(x, y)=5xy-3(x+y)+2 可得 E1(3/5, 2/5)= E2(3/5, 2/5)=1/5 E1(0, 0)=1，E1(1, 1)=2 E2(0, 0)=2，E2(1, 1)=1,97/119,图12-4,y,x,1,1,2/5,3/5,在(0，0)和(1，1)处，两局中人期望收益都优于(3/5，2/5)。 但是个非合作对策，选择策略前不许协商，两局中人无法保证平衡局势(0，0)或(1，1)。 尽管有3个平衡点，但都难以令人信