矩陣對策的基本定理

關于矩陣對策的基本定理第1頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/822.1矩陣對策的數(shù)學模型二人有限零和對策二人零和對策就是矩陣對策,是指只有兩個參加對策的局中人,每個局中人都只有有限個策略可供選擇。在任一局勢下,兩個局中人的贏得之和總是等于零,即雙方的利益是激烈對抗的。矩陣對策的表示設局中人Ⅰ有m個純策略1,2,?,m

,局中人Ⅱ有n個純策略1,2,?,n

,則局中人Ⅰ、Ⅱ的策略集分別為

S1={1,2,?,m}S2={1,2,?,n}第2頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/83當局中人Ⅰ選定純策略i

和局中人Ⅱ選定純策略j

后,就形成了一個純局勢(i

,j

)。這樣的純局勢可構(gòu)成m×n矩陣。對任一純局勢(i

,j),記局中人Ⅰ的贏得值為aij

,則稱矩陣A=(aij)mn

為局中人I的贏得矩陣(或為局中人II的支付矩陣)，這樣，局中人II的贏得矩陣即為–A。矩陣對策常記為：G={I,II;S1,S2;A}或G={S1,S2;A}第3頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/84例齊王賽馬的贏得矩陣第4頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/85例6設有一矩陣對策G={S1,S2;A},其中S1={1,

2,3,4},S2={β1,β2,β3}，局中人I的贏得矩陣為

試分析局中人I和II分別使用什么策略最有利？又在什么局勢下對雙方都有利？第5頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/86定義1

設G={S1,S2;A}為矩陣對策。其中S1={1,2,?,m

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

},A=(aij

)m×n

若成立以下等式

則稱VG

為對策G的值,并稱使上述等式成立的純局勢(i*,j*)為G在純策略下的解(或平衡局勢),i*

與j*

分別稱為局中人Ⅰ,Ⅱ的最優(yōu)純策略。第6頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/87例7求解矩陣對策G={S1,S2;A},其中第7頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/88定理1

矩陣對策G={S1,S2;A}在純策略意義下有解的充分必要條件是:存在純局勢(i*,j*)使得對一切i=1,?,m,j=1,?,n,均有

aij*≤ai*j*≤ai*j證明：第8頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/89充分性（前提：對任意i,j

有aij*

ai*j*ai*j

）由不等式左邊知，j*列的任一元素不超過ai*j*，從而j*列的最大元也不超過ai*j*.即：同理對不等式右邊，ai*j*不超過i*行的任一元素，從而ai*j*

不超過i*行的最小元素，即有因此可得而對每列的最大元中的最小者及每行的最小元中的最大者有即：j*列的任一元素i*行的任一元素第9頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/810另外，對任意i,j

有，任意元素aij

不小于其所在行的最小元，也不大于其所在列的最大元，即不等式左邊又說明，矩陣中每一行的最小元都不超過aij

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

，即同理，由不等式的右邊也可得從而有結(jié)合(1),(2)即可得第10頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/811必要性假設有i*,j*使上式右邊說明ai*j*

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

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

應有同理對任意j

應有綜上可得即第11頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/812定義2

設f(x,y)為一個定義在x∈A及y∈B上的實值函數(shù),如果存在x*

A,y*

B,使得對一切x

A和y

B,有

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

則稱(x*,y*)為函數(shù)f的一個鞍點。矩陣對策的解與鞍點若將局勢矩陣視為二元函數(shù)f(x,y)的定義域，則贏得矩陣即為其值域；從而，若矩陣對策有解的充要條件是ai*j*是贏得矩陣的鞍點。第12頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/813例8求對策的解。設矩陣對策G={S1,S2;A},其中S1={1,2,3,4},S2={1,2,3,4},贏得矩陣為第13頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/814一般矩陣對策的解可以是不唯一的。當解不唯一時,解之間的關系具有下面兩條性質(zhì)。性質(zhì)1無差別性即若(i1,j1)和(i2,j2)是對策G的兩個解,則ai1j1=ai2j2;性質(zhì)2可交換性即若(i1,j1)和(i2,j2)是對策G的兩個解,則(i1,j2)和(i2,j1)也是解。第14頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/8152.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)為一個混合局勢,局中人Ⅰ的贏得函數(shù)記成

新的對策記成G*={S1*,S2*,E},它是對策G的混合擴充。第15頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/816定義4

設G*={S1*,S2*;E}是矩陣對策G={S1,S2;A}的混合擴充,如果

記其值為VG

.則稱VG

為對策G*的值,使上式成立的混合局勢(x*,y*)稱為G在混合策略意義下的解(或簡稱解),x*和y*分別稱為局中人Ⅰ和Ⅱ的最優(yōu)混合策略(或簡稱最優(yōu)策略)。第16頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/817定理2

矩陣對策G={S1,S2;A}在混合策略意義下有解的充要條件是:存在x*

S1*,y*

S2*,使(x*,y*)為函數(shù)E(x,y)的一個鞍點,即對一切x

S1*,y

S2*,有

E(x,y*)≤E(x*,y*)≤E(x*,y)第17頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/8182.3矩陣對策的基本定理兩個記號:當局中人Ⅰ取純策略i

時,記其相應的贏得函數(shù)為E(i,y),于是當局中人Ⅱ取純策略βj

時,記其相應的贏得函數(shù)為E(x,j),于是則有第18頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/819定理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頁，2022年，5月20日，13點50分，星期五2022/11/820定理4

設x*

S1*,y*

S2*,則(x*,y*)為G的解的充要條件是:存在數(shù)v,使得x*和y*分別是不等式組(1)和(2)的解,且v=VG

。第20頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/821定理4的證明“”設x*S1*,y*S2*,(x*,y*)是G

的解，則由定理3，對i=1,2,…,m,j=1,2,…,n,有所以由上可知x*與y*分別是不等式組(1),(2)的解。第21頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/822“”設不等式組(1),(2)的解分別為x*與y*,則有另：所以有E(x*,y*)=v,由定理3即知對策G

有解。第22頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/823定理5

對任一矩陣對策G={S1,S2;A},一定存在混合策略意義下的解。第23頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/824定理6

設(x*,y*)是矩陣對策G的解,v=VG

,則

(1)若xi*>0,則(2)若yj*>0,則(3)若則xi*=0(4)若則yj*=0.第24頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/825證明：由定義有，其中xi*≥0,i=1,…,m.這說明，m

項非負數(shù)之和為零，從而和式中每一項均為零。故當有某項中的xi*>0的話，則與其對應的項必有如下結(jié)果(反之亦然)：第25頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/826例如，設(x*,y*)是矩陣對策G的解,v=VG

,若有x2*>0，則有反之，若有i=3使則有x3*=0.以此類推。第26頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/827定理7

設有兩個矩陣對策

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

其中A1=(aij

),A2=(aij+L),L為任一常數(shù),則有

(1)VG2=VG1+L

(2)T(G1)=T(G2)第27頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/828定理8

設有兩個矩陣對策

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

其中>0為任一常數(shù)。則

(1)VG2=VG1

(2)T(G1)=T(G2)第28頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/829定理9

設G={S1,S2;A}為—矩陣對策,且A=-AT

為反對稱矩陣(亦稱這種對策為對稱對策)。則

(1)VG

=0

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

其中T1(G)和T2(G)分別為局中人Ⅰ和Ⅱ的最優(yōu)策略集。第29頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/830定義5

設有矩陣對策G={S1,S2;A},其中

S1={1,?,m

},S2={1,?,n

},A=(aij

)

如果對一切j=1,?,n都有aij

≥akj

,即矩陣A的第i

行元素均大于或等于第k

行的對應元素,則稱局中人Ⅰ的純策略i

優(yōu)超于k;

同樣,若對一切i=1,?,m,都有aij≤ail,即矩陣A的第j

列元素均小于或等于第l

列的對應元素,則稱局中人Ⅱ的純策略j

優(yōu)超于l.第30頁，共33頁，2022年，5月20日，13點50分，星期五2022/11/831定理10

設G={S1,S2;A}為矩陣對策,其中

S1={1,?,m

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

},A=(aij

)

如果純策略1

被其余純策略2,?,m

中之一所優(yōu)超,由G可得到一新的矩陣對策G={S1,