矩阵对策的基本定理

关于矩阵对策的基本定理第1页，讲稿共33页，2023年5月2日，星期三2023/7/422.1矩阵对策的数学模型二人有限零和对策二人零和对策就是矩阵对策,是指只有两个参加对策的局中人,每个局中人都只有有限个策略可供选择。在任一局势下,两个局中人的赢得之和总是等于零,即双方的利益是激烈对抗的。矩阵对策的表示设局中人Ⅰ有m个纯策略1,2,⋯,m

,局中人Ⅱ有n个纯策略1,2,⋯,n

,则局中人Ⅰ、Ⅱ的策略集分别为

S1={1,2,⋯,m}S2={1,2,⋯,n}第2页，讲稿共33页，2023年5月2日，星期三2023/7/43当局中人Ⅰ选定纯策略i

和局中人Ⅱ选定纯策略j

后,就形成了一个纯局势(i

,j

)。这样的纯局势可构成m×n矩阵。对任一纯局势(i

,j),记局中人Ⅰ的赢得值为aij

,则称矩阵A=(aij)mn

为局中人I的赢得矩阵(或为局中人II的支付矩阵)，这样，局中人II的赢得矩阵即为–A。矩阵对策常记为：G={I,II;S1,S2;A}或G={S1,S2;A}第3页，讲稿共33页，2023年5月2日，星期三2023/7/44例齐王赛马的赢得矩阵第4页，讲稿共33页，2023年5月2日，星期三2023/7/45例6设有一矩阵对策G={S1,S2;A},其中S1={1,

2,3,4},S2={β1,β2,β3}，局中人I的赢得矩阵为

试分析局中人I和II分别使用什么策略最有利？又在什么局势下对双方都有利？第5页，讲稿共33页，2023年5月2日，星期三2023/7/46定义1

设G={S1,S2;A}为矩阵对策。其中S1={1,2,⋯,m

},S2={1,2,⋯,n

},A=(aij

)m×n

若成立以下等式

则称VG

为对策G的值,并称使上述等式成立的纯局势(i*,j*)为G在纯策略下的解(或平衡局势),i*

与j*

分别称为局中人Ⅰ,Ⅱ的最优纯策略。第6页，讲稿共33页，2023年5月2日，星期三2023/7/47例7求解矩阵对策G={S1,S2;A},其中第7页，讲稿共33页，2023年5月2日，星期三2023/7/48定理1

矩阵对策G={S1,S2;A}在纯策略意义下有解的充分必要条件是:存在纯局势(i*,j*)使得对一切i=1,⋯,m,j=1,⋯,n,均有

aij*≤ai*j*≤ai*j证明：第8页，讲稿共33页，2023年5月2日，星期三2023/7/49充分性（前提：对任意i,j

有aij*

ai*j*ai*j

）由不等式左边知，j*列的任一元素不超过ai*j*，从而j*列的最大元也不超过ai*j*.即：同理对不等式右边，ai*j*不超过i*行的任一元素，从而ai*j*

不超过i*行的最小元素，即有因此可得而对每列的最大元中的最小者及每行的最小元中的最大者有即：j*列的任一元素i*行的任一元素第9页，讲稿共33页，2023年5月2日，星期三2023/7/410另外，对任意i,j

有，任意元素aij

不小于其所在行的最小元，也不大于其所在列的最大元，即不等式左边又说明，矩阵中每一行的最小元都不超过aij

，从而每一行的最小元中的最大者也不超过aij

，即同理，由不等式的右边也可得从而有结合(1),(2)即可得第10页，讲稿共33页，2023年5月2日，星期三2023/7/411必要性假设有i*,j*使上式右边说明ai*j*

是第j*列中最大元，即同理左边说明ai*j*

是第i*行中最小元，即而对任意i

应有同理对任意j

应有综上可得即第11页，讲稿共33页，2023年5月2日，星期三2023/7/412定义2

设f(x,y)为一个定义在x∈A及y∈B上的实值函数,如果存在x*

A,y*

B,使得对一切x

A和y

B,有

f(x,y*)≤f(x*,y*)≤f(x*,y)

则称(x*,y*)为函数f的一个鞍点。矩阵对策的解与鞍点若将局势矩阵视为二元函数f(x,y)的定义域，则赢得矩阵即为其值域；从而，若矩阵对策有解的充要条件是ai*j*是赢得矩阵的鞍点。第12页，讲稿共33页，2023年5月2日，星期三2023/7/413例8求对策的解。设矩阵对策G={S1,S2;A},其中S1={1,2,3,4},S2={1,2,3,4},赢得矩阵为第13页，讲稿共33页，2023年5月2日，星期三2023/7/414一般矩阵对策的解可以是不唯一的。当解不唯一时,解之间的关系具有下面两条性质。性质1无差别性即若(i1,j1)和(i2,j2)是对策G的两个解,则ai1j1=ai2j2;性质2可交换性即若(i1,j1)和(i2,j2)是对策G的两个解,则(i1,j2)和(i2,j1)也是解。第14页，讲稿共33页，2023年5月2日，星期三2023/7/4152.2矩阵对策的混合策略定义3

设有矩阵对策G={S1,S2;A},其中S1={1,2,⋯,m

},S2={1,2,⋯,n

},A=(aij

)m×n

记

则S1*和S2*分别称为局中人Ⅰ和Ⅱ的混合策略集;x

S1*和y

S2*分别称为局中人Ⅰ和Ⅱ的混合策略,称(x,y)为一个混合局势,局中人Ⅰ的赢得函数记成

新的对策记成G*={S1*,S2*,E},它是对策G的混合扩充。第15页，讲稿共33页，2023年5月2日，星期三2023/7/416定义4

设G*={S1*,S2*;E}是矩阵对策G={S1,S2;A}的混合扩充,如果

记其值为VG

.则称VG

为对策G*的值,使上式成立的混合局势(x*,y*)称为G在混合策略意义下的解(或简称解),x*和y*分别称为局中人Ⅰ和Ⅱ的最优混合策略(或简称最优策略)。第16页，讲稿共33页，2023年5月2日，星期三2023/7/417定理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)第17页，讲稿共33页，2023年5月2日，星期三2023/7/4182.3矩阵对策的基本定理两个记号:当局中人Ⅰ取纯策略i

时,记其相应的赢得函数为E(i,y),于是当局中人Ⅱ取纯策略βj

时,记其相应的赢得函数为E(x,j),于是则有第18页，讲稿共33页，2023年5月2日，星期三2023/7/419定理3

设x*

S1*,y*

S2*,则(x*,y*)为G的解的充要条件是:对任意i=1,…,m

和j=1,…,n

有

E(i,y*)≤E(x*,y*)≤E(x*,j)证明：必要性：由定理2有:E(x,y*)≤E(x*,y*)≤E(x*,y)，又纯策略只是混合策略特殊情形，所以有

E(i,y*)≤E(x*,y*)≤E(x*,j)充分性：由E(i,y*)≤E(x*,y*)≤E(x*,j)对i,j

成立，有第19页，讲稿共33页，2023年5月2日，星期三2023/7/420定理4

设x*

S1*,y*

S2*,则(x*,y*)为G的解的充要条件是:存在数v,使得x*和y*分别是不等式组(1)和(2)的解,且v=VG

。第20页，讲稿共33页，2023年5月2日，星期三2023/7/421定理4的证明“”设x*S1*,y*S2*,(x*,y*)是G

的解，则由定理3，对i=1,2,…,m,j=1,2,…,n,有所以由上可知x*与y*分别是不等式组(1),(2)的解。第21页，讲稿共33页，2023年5月2日，星期三2023/7/422“”设不等式组(1),(2)的解分别为x*与y*,则有另：所以有E(x*,y*)=v,由定理3即知对策G

有解。第22页，讲稿共33页，2023年5月2日，星期三2023/7/423定理5

对任一矩阵对策G={S1,S2;A},一定存在混合策略意义下的解。第23页，讲稿共33页，2023年5月2日，星期三2023/7/424定理6

设(x*,y*)是矩阵对策G的解,v=VG

,则

(1)若xi*>0,则(2)若yj*>0,则(3)若则xi*=0(4)若则yj*=0.第24页，讲稿共33页，2023年5月2日，星期三2023/7/425证明：由定义有，其中xi*≥0,i=1,…,m.这说明，m

项非负数之和为零，从而和式中每一项均为零。故当有某项中的xi*>0的话，则与其对应的项必有如下结果(反之亦然)：第25页，讲稿共33页，2023年5月2日，星期三2023/7/426例如，设(x*,y*)是矩阵对策G的解,v=VG

,若有x2*>0，则有反之，若有i=3使则有x3*=0.以此类推。第26页，讲稿共33页，2023年5月2日，星期三2023/7/427定理7

设有两个矩阵对策

G1={S1,S2;A1}G2={S1,S2;A2}

其中A1=(aij

),A2=(aij+L),L为任一常数,则有

(1)VG2=VG1+L

(2)T(G1)=T(G2)第27页，讲稿共33页，2023年5月2日，星期三2023/7/428定理8

设有两个矩阵对策

G1={S1,S2;A}G2={S1,S2;A}

其中>0为任一常数。则

(1)VG2=VG1

(2)T(G1)=T(G2)第28页，讲稿共33页，2023年5月2日，星期三2023/7/429定理9

设G={S1,S2;A}为—矩阵对策,且A=-AT

为反对称矩阵(亦称这种对策为对称对策)。则

(1)VG

=0

(2)T1(G)=T2(G)

其中T1(G)和T2(G)分别为局中人Ⅰ和Ⅱ的最优策略集。第29页，讲稿共33页，2023年5月2日，星期三2023/7/430定义5

设有矩阵对策G={S1,S2;A},其中

S1={1,⋯,m

},S2={1,⋯,n

},A=(aij

)

如果对一切j=1,⋯,n都有aij

≥akj

,即矩阵A的第i

行元素均大于或等于第k

行的对应元素,则称局中人Ⅰ的纯策略i

优超于k;

同样,若对一切i=1,⋯,m,都有aij≤ail,即矩阵A的第j

列元素均小于或等于第l

列的对应元素,则称局中人Ⅱ的纯策略j

优超于l.第30页，讲稿共33页，2023年5月2日，星期三2023/7/431定理10

设G={S1,S2;A}为矩阵对策,其中

S1={1,⋯,m

},S2={β1,⋯,βn

},A=(aij

)

如果纯策略1

被其余纯策略2,⋯,m

中之一所优超,由G可得到一新的矩阵对策G={S1,S