引论第二矩阵对策第三矩阵对策的求解.ppt

2019/7/25,第一节：引论 第二节：矩阵对策 第三节：矩阵对策的求解,第十一章 对策论,2019/7/25,第一节：引论,1. 内涵：对策论亦称博弈论（Game Theory），具有竞争或对抗性质的行为称为对策行为。 2. 引例 3. 对策行为的基本要素 4. 对策行为的基本假设 5. 对策行为的分类,2019/7/25,1.引例：齐王赛马,齐王：上、 中、 下 田忌：上、 中、 下,2019/7/25,1.引例：齐王赛马,齐王：上、 中、 下 田忌：上、 中、 下,2019/7/25,2.对策行为的基本要素,1. 局中人（Player）：在一个对策行为中，有权决定自己行动方案的参加者称为局中人。 2. 策略（Strategy）：一局对策中，可供局中人选择的完整的行动方案称为策略。 3. 赢得函数（Score）：一局对策中，局中人使用每一策略都会有所得失，这种得失是全体局中人所采取的一组策略的函数，称为赢得函数。 4. 局势：一局对策中，各局中人选定的策略所形成的策略组称为一个局势。,2019/7/25,3.对策行为的基本假设,对策行为总是假定每一个局中人都是“理智的”决策者，不存在利用其他局中人的决策失误来扩大自身利益的可能性或相反。,2019/7/25,4.对策行为的分类,2019/7/25,第二节：矩阵对策,1.矩阵对策的数学模型 2.矩阵对策解的问题 3.矩阵对策的混合策略 4.矩阵对策的基本定理 5.矩阵对策解的性质,2019/7/25,1.矩阵对策的数学模型,（1）矩阵对策的内涵：二人有限零和对策，即对策双方的利益是激烈对抗的。 （2）矩阵对策的数学模型： 甲：有m个策略，表示为S1=（ 1, 2, 3, m) 乙：有n个策略，表示为S2=（ 1, 2, 3, n) 当甲选定策略i 、乙选定策略j 时，就形成了一个局势（ i , j ）。可见这样的局势总共有m n个，对任意局势（ i , j ）甲的赢得值为aij，即甲的赢得矩阵为Amn=aij。因为对策是零和的，所以乙的赢得矩阵为 -Amn。,2019/7/25,1. 矩阵对策的数学模型,建立二人零和对策的模型就是要根据对实际问题的叙述，确定甲、乙两个局中人的策略集合以及相应的赢得矩阵。不难看出在“齐王赛马”的例子中，齐王的赢得矩阵为：,A =,3 1 1 1 1 -1 1 3 3 3 -1 1 1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 -1 1 3 1 1 1 1 -1 1 3,2019/7/25,1. 矩阵对策的示例1,例1 ：甲的赢得矩阵,2019/7/25,1. 矩阵对策的示例2,例2 ：从一张红牌和一张黑牌中随机抽取一张，在对乙保密的情况下拿给甲看。若甲看到的是红牌，他可以选择掷硬币或让乙猜；若甲选择掷硬币，出现正面甲赢 p 元，出现反面甲输 q 元；若让乙猜，当乙猜中是红牌时甲输 r 元，否则甲赢 s 元。若甲看到的是黑牌，他只能让乙猜，当乙猜中是黑牌时甲输 u 元，否则甲赢 t 元。试确定甲、乙各自的策略并建立赢得矩阵。,正面 1/2,2019/7/25,1. 矩阵对策的示例2,正面 1/2,若甲决定掷硬币这个策略，则乙的猜红或猜黑已无意义；若抽到黑牌，甲的掷硬币已无意义，只与乙的猜红或猜黑有关。所以，对于局势“掷硬币，猜红”甲的期望赢得为：1/2（1/2p-1/2q）+1/2t = 1/4（p-q+2t ）,2019/7/25,1. 矩阵对策的示例2,正面 1/2,2019/7/25,2. 矩阵对策解的问题,设矩阵对策G=S1，S2，A，其中： S1 =1，2，3，4， S2 = 1 ，2 ，3 ，,A =,-4 2 -6 -6 4 3 5 3 8 -1 -10 -10 -3 0 6 -3,Min,Max 3,局中人甲应选择2 ，此时不管局中人乙采取什么策略，甲的赢得均不小于3。,2019/7/25,2. 矩阵对策解的问题,设矩阵对策G=S1，S2，A，其中： S1 =1，2，3，4， S2 = 1 ，2 ， 3,A=,-4 2 -6 -6 4 3 5 3 8 -1 -10 -10 -3 0 6 -3,Min,Max 3,局中人甲应选择2 ，乙应采取2策略；结果甲赢得3，乙付出3。,Max 8 3 6 Min 3,2019/7/25,2. 矩阵对策解的问题,定义1：设矩阵对策G=S1，S2，A，其中： S1 =1，2，m， S2 = 1 ，2 ， ， n A = aijmn ；若 Max min aij = Min max aij = ai*j* 则称ai*j*为对策G的值，局势（ i* ，j* ）为G的解，i*和j*分别称为局中人的最优策略。,i,j,i,j,2019/7/25,2. 矩阵对策解的问题,由于ai*j*既是其所在行的最小值，又是其所在列的最大值，于是有： aij* ai*j* ai*j 定理1：设矩阵对策G=S1，S2，A在策略意义下有解的充分必要条件是存在着局势（ i* ，j* ）使得对于一切i与j都有aij* ai*j* ai*j成立。,2019/7/25,2. 矩阵对策解的问题,例：设矩阵对策G=S1，S2，A，赢得矩阵为：,A=,7 5 6 5 5 2 -3 9 -4 -4 6 5 7 5 5 0 1 -1 2 -1,Min,Max = 5,Max 7 5 9 5 Min = 5 i = 1, 3 ，j = 2, 4，ai*j* = 5，四个局势均为矩阵对策的解。,2019/7/25,3. 矩阵对策的混合策略,对矩阵对策G=S1，S2，A来说，局中人甲有把握的最小赢得是： v1 = max min aij 局中人乙有把握的最大损失是： v2= min max aij 当v1 = v2时，对矩阵对策有策略意义下的解；然而并非总是如此，经常是 v1 v2 （ 总有v1 v2 ），此时没有策略意义下的解。,i,j,i,j,2019/7/25,3. 矩阵对策的混合策略,A=,-4 4 -6 -6 4 3 5 3 8 -1 -10 -10 -3 0 6 -3,Min,Max 3,Max 8 4 5,Min 4,v1 = 3 v2 = 4,2019/7/25,3. 矩阵对策的混合策略,v1 = 3 v2 = 4对于两个局中人来说，不存在一个双方均可接受的平衡局势。 设矩阵对策G=S1，S2，A，其中： S1 = 1，m， S2 = 1 ， ，n A = aijmn ；则 S1* = xi 0，i=1,2, ,m; x1+ x2+ +xm = 1 S2* = yj 0，j=1,2, ,n; y1+ y2+ +yn = 1 称为局中人的混合策略。,2019/7/25,3. 矩阵对策的混合策略,对 x S1*, y S2* 称(x, y)为一个混合局势，局中人的赢得函数记成： E (x, y) =xT A y 这样便得到一个新的对策 G* = S1*, S2*, E G*称为G的混合扩充。,2019/7/25,3. 矩阵对策的混合策略,G * = S1*, S2*, E 是G=S1，S2，A的混合扩充，如果 max min E (x,y) = min max E (x,y) 记其值为VG，则VG为对策G *的值，使上式成立的混合局势（x *，y *）为G 在混合策略意义下的解， x *，y *分别称为局中人甲和乙的最优混合策略。 注：策略意义下的解不存在时，自动转向混合策略意义下的解。,x S1*,y S2*,x S1*,y S2*,2019/7/25,3. 矩阵对策的混合策略,对策矩阵G=S1，S2，A在混合策略意义下有解的充分必要条件是存在着 x * S1* ， y * S2*使（x *，y *） 为E (x,y) 的一个鞍点，即对于一切x S1* ， y S2* 有 E (x,y *) E (x *,y *) E (x *,y),2019/7/25,3. 矩阵对策的混合策略,例：对策矩阵G=S1，S2，A，其中： A = 显然G在策略意义下的解不存在，于是设x=(x1,x2)为局中人甲的混合策略， y=(y1,y2)为局中人乙的混合策略，则 S1* = xi 0，i=1,2; x1+ x2 = 1 S2* = yj 0，j=1,2; y1+ y2 = 1 局中人甲的赢得期望值是：E (x,y) =xT A y,3,6,5,4,2019/7/25,3. 矩阵对策的混合策略,例：E (x,y) =xT A y =3x1y1+6x1y2+5x2y1+4x2y2 = -4(x1-1/4)(y1-1/2)+9/2 取x *=（1/4，3/4），y *=（1/2，1/2），则 E (x,y *)= E (x *,y *) = E (x *,y) = 9/2 即有 E (x,y *) E (x *,y *) E (x *,y) 故x *和y *分别为局中人甲和乙的最优（混合）策略。,2019/7/25,4.矩阵对策的基本定理,定理1：设矩阵对策G=S1，S2，A在策略意义下有解的充分必要条件是存在着局势（ i* ，j* ）使得对于一切i与j都有aij* ai*j* ai*j成立。 定理2：对策矩阵G=S1，S2，A在混合策略意义下有解的充分必要条件是存在着 x * S1* ， y * S2*使（x *，y *） 为E (x,y) 的一个鞍点，即对于一切x S1* ， y S2* 有 E (x,y *) E (x *,y *) E (x *,y),2019/7/25,4.矩阵对策的基本定理,定理3：设 x * S1* ， y * S2*则（x *，y *） 是矩阵对策G的解的充分必要条件是对任意的i(1,2,m)和j(1,2, ,n)有 E (x,y *) E (x *,y *) E (x *,y),2019/7/25,4.矩阵对策的基本定理,定理4：设 x * S1* ， y * S2*则（x *，y *） 是矩阵对策G的解的充分必要条件是存在数v使得x * 和y * 分别是不等式组 aijxi v aijyj v xi = 1 yj= 1 xi 0 yj 0 的解，且v=VG。,i,j,(j=1,2,n),(i=1,2,m),(i=1,2,m),(j=1,2,n),2019/7/25,4.矩阵对策的基本定理,定理5：对任一矩阵对策G=S1，S2，A，一定存在混合策略意义下的解。,2019/7/25,5.矩阵对策解的性质,性质1：设（x *，y *） 是矩阵对策G=S1，S2，A的解，v=VG ，则 （1）若xi*0，则 aijyj* = v ， （2）若 aijyj* 0，则 aijxi* = v ， （4）若 aijxi* v ，则yj*=0。,2019/7/25,5.矩阵对策解的性质,性质2：矩阵对策G1=S1，S2，A1、 G2=S1，S2，A2，解集分别为T（ G1 ）和 T（ G2 ），若其中有A1=（aij）、 A2=（aij+L ），L为任一常数，则：（1） V G2= V G1+L； （2） T（ G2 ）= T（ G1 ）。,2019/7/25,5.矩阵对策解的性质,性质3：矩阵对策G1=S1，S2，A、 G2=S1，S2，A，其中为大于0的任一常数，则： （1） V G2= V G1； （2） T（ G2 ）= T（ G1 ）。,2019/7/25,5.矩阵对策解的性质,性质4：设一矩阵对策G=S1，S2，A 存在 A = - AT （称为对称对策） 则： （1） V G= 0； （2） T1 （ G ）= T2（ G），分别为局中人甲、乙的最优策略集。,2019/7/25,5.矩阵对策解的性质,性质5：设一矩阵对策G=S1，S2，A ，若在S1（或、和S2）中出现被优超的策略，那么去掉被优超的策略所形成的新的矩阵对策与原矩阵对策同解。,A =,4 0 2 3 -2 -2 1 4 -4 3 7 3 8 4 5 4 6 5 6 6 5 2 7 4 3,例11-6：,2019/7/25,第216页例11-6,由于第4行优超于第1行，第3行优超于第2行，故可去掉第1行和第2行，得到新的赢得矩阵：,A1 =,7 3 8 4 5 4 6 5 6 6 5 2 7 4 3,2019/7/25,第216页例11-6,对于A1由于第1列优超于第3列，第2列优超于第4列，1/3（第1列）+2/3(第2列)优超于第5列，故可去掉第3、4、5列，得到新的赢得矩阵：,A2 =,7 3 4 6 5 2,2019/7/25,第216页例11-6,对于A2由于第1行优超于第3行，故可去掉第3行，得到新的赢得矩阵：,A3 =,7 3 4 6,2019/7/25,第216页例11-6,对于A3易之于无鞍点存在，应用定理4求解不等式组：,7x3+4x4 v 3x3+6x4 v x3+ x4 = 1 x3, x4 0,7y1+3y2 v 4y1+6y2 v y1+ y2 = 1 y1, y2 0,2019/7/25,第216页例11-6,求得解为： x3* = 1/3， x4* = 2/3 y1* = 1/2， y2* = 1/2,于是原矩阵对策的一个解是： x* = （0，0，1/3，2/3，0）T y* = （1/2，1/2，0，0，0）T VG = 5,2019/7/25,第三节 矩阵对策的求解,1. 22对策的公式法 2. 2n 或m2对策的图解法 3. 线性方程组求解法 4. 线性规划求解法,2019/7/25,1. 22对策的公式法,所谓 22对策是指局中人的赢得矩阵为22阶矩阵，即：,如果A有鞍点，则很快就可求出各局中人的最优策略；如果A没有鞍点，则可证明各局中人的最优混合策略中的xi* ,yj*均大于零。 于是由定理6可知，为求混合策略可求解下列方程组： a11x1+ a21x2 = v a11y1+ a12y2 = v a12x1+ a22x2 = v a21y1+ a22y2 = v x1+ x2 = 1 y1+ y2 = 1,2019/7/25,2. 2n 或m2对策的图解法,例：设一矩阵对策G=S1，S2，A ，其中 S1 = 1，2， S2 = 1 ，2 ， 3,2 3 11 7 5 2,设局中人甲的混合策略为(x, 1-x)T， x0,1。过数轴上坐标为0和1的两点分别做两条垂线 和 ，垂线上点的纵坐标值分别表示局中人甲采取纯策略1，2 时，局中人乙采取各策略时的赢得值。如下图所示，当局中人甲选择每一混合策略(x, 1-x)T时，他可能的最少赢得为局中人乙选择1 ，2 ， 3时所确定的3条直线在 x 处的纵坐标值的最小值。,2019/7/25,2. 2n 或m2对策的图解法,V = 2x + 7(1-x) V = 3x + 5(1-x) V = 11x + 2(1-x) 设局中人甲的混合策略为(x, 1-x)T， x0, 1。过数轴上坐标为0和1的两个点分别做两条垂线 和 ，垂线上的点的纵坐标值分别表示局中人甲采取纯策略1，2 时，局中人乙采取各策略时的赢得值。如下图所示：,2019/7/25,甲采取混合策略最少的赢得：B1BB2B3 甲确定 x 使赢得最大，即最小最大原则,2019/7/25,x= OA, AB即为对策值VG 求解 x 及VG，解方程组： VG = 3x + 5(1-x) VG = 11x + 2(1-x) 求得 x = 3/11, VG = 49/11；所以甲的最优策略为 x* = （3/11，8/11） E(x* , 1 )=23/11 + 78/11 = 62/1149/11 E(x* , 2 )=33/11 + 58/11 = 49/11 E(x* , 3 )=113/11 + 28/11 = 49/11 所以局中人乙的最优混合策略 y* = （0, y2, y3）,2019/7/25,3y2+ 11y3 = VG = 49/11 5y2+ 2y3 = VG = 49/11 y2+ y3 = 1 求解得y* = （0, 9/11, 2/11）.,2019/7/25,例：设一矩阵对策G=S1，S2，A ，其中 S1 = 1，2 ，3， S2 = 1 ，2 2 7 A = 6 6 11 2 设乙的混合策略为 (y, 1-y)，同理有：,2019/7/25,0,1,2,6,7,11,6,2,y,A1,B1,B2,B3,乙采取混合策略最大的支付：7B1B211 乙确定 y 使支付最小，即最大最小原则,3,2,1,A2,2019/7/25,OA1 y OA2 VG = 6 2y + 7 (1-y) = 6 6y + 6 (1-y) = 6 6y + 6 (1-y) = 6 11y + 2 (1-y) = 6 求得 OA1 = 1/5, OA2 = 4/9。故局中人乙的最优混合策略为 y* = （ y, 1-y），其中 y 1/5， 4/9；而故局中人甲的最优策略显然只能是 x* = （ 0, 1, 0），即策略2 。,2019/7/25,3. 线性方程组求解法,根据定理4求解矩阵对策解（x *，y *）的问题等价于求解： aijxi v aijyj v xi = 1 yj= 1 xi 0 yj 0 又根据定理5和定理6，如果x *，y *中各分量均不为零，即可将不等式组转换为方程组：,2019/7/25,3. 线性方程组求解法,不等式组转换为方程组： aijxi= v aijyj = v xi = 1 yj= 1 xi 0 yj 0 如果这两个方程组存在非负解x *和y *，则已经求得了矩阵对策的解（x *，y *）。,2019/7/25,3. 线性方程组求解法,例：“齐王赛马”齐王的赢得矩阵为 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,2019/7/25,3. 线性方程组求解法,设： X *=（ x1， x2， x3， x4， x5， x6）T Y *=（ y1， y2， y3， y4， y5， y6）T 从矩阵A的元素来看局中人采取任何一个策略的可能性都是存在的，故可事先假设X *，Y *中各分量