矩陣對(duì)策的基本定理

關(guān)于矩陣對(duì)策的基本定理2024/4/1022.1矩陣對(duì)策的數(shù)學(xué)模型二人有限零和對(duì)策二人零和對(duì)策就是矩陣對(duì)策,是指只有兩個(gè)參加對(duì)策的局中人,每個(gè)局中人都只有有限個(gè)策略可供選擇。在任一局勢(shì)下,兩個(gè)局中人的贏得之和總是等于零,即雙方的利益是激烈對(duì)抗的。矩陣對(duì)策的表示設(shè)局中人Ⅰ有m個(gè)純策略

1,

2,?,

m

,局中人Ⅱ有n個(gè)純策略

1,

2,?,

n

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

S1={

1,

2,?,

m}S2={

1,

2,?,

n}第2頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/103當(dāng)局中人Ⅰ選定純策略

i

和局中人Ⅱ選定純策略

j

后,就形成了一個(gè)純局勢(shì)(

i

,

j

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

i

,

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

,則稱矩陣A=(aij)m

n

為局中人I的贏得矩陣(或?yàn)榫种腥薎I的支付矩陣)，這樣，局中人II的贏得矩陣即為–A。矩陣對(duì)策常記為：G={I,II;S1,S2;A}或G={S1,S2;A}第3頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/104例齊王賽馬的贏得矩陣第4頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/105例6設(shè)有一矩陣對(duì)策G={S1,S2;A},其中S1={

1,

2,

3,

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

試分析局中人I和II分別使用什么策略最有利？又在什么局勢(shì)下對(duì)雙方都有利？第5頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/106定義1

設(shè)G={S1,S2;A}為矩陣對(duì)策。其中S1={

1,

2,?,

m

},S2={

1,

2,?,

n

},A=(aij

)m×n

若成立以下等式

則稱VG

為對(duì)策G的值,并稱使上述等式成立的純局勢(shì)(

i*,

j*)為G在純策略下的解(或平衡局勢(shì)),

i*

與

j*

分別稱為局中人Ⅰ,Ⅱ的最優(yōu)純策略。第6頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/107例7求解矩陣對(duì)策G={S1,S2;A},其中第7頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/108定理1

矩陣對(duì)策G={S1,S2;A}在純策略意義下有解的充分必要條件是:存在純局勢(shì)(

i*,

j*)使得對(duì)一切i=1,?,m,j=1,?,n,均有

aij*≤ai*j*≤ai*j證明：第8頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/109充分性（前提：對(duì)任意i,j

有aij*

ai*j*

ai*j

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

不超過(guò)i*行的最小元素，即有因此可得而對(duì)每列的最大元中的最小者及每行的最小元中的最大者有即：j*列的任一元素i*行的任一元素第9頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1010另外，對(duì)任意i,j

有，任意元素aij

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

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

，即同理，由不等式的右邊也可得從而有結(jié)合(1),(2)即可得第10頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1011必要性假設(shè)有i*,j*使上式右邊說(shuō)明ai*j*

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

是第i*行中最小元，即而對(duì)任意i

應(yīng)有同理對(duì)任意j

應(yīng)有綜上可得即第11頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1012定義2

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

A,y*

B,使得對(duì)一切x

A和y

B,有

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

則稱(x*,y*)為函數(shù)f的一個(gè)鞍點(diǎn)。矩陣對(duì)策的解與鞍點(diǎn)若將局勢(shì)矩陣視為二元函數(shù)f(x,y)的定義域，則贏得矩陣即為其值域；從而，若矩陣對(duì)策有解的充要條件是ai*j*是贏得矩陣的鞍點(diǎn)。第12頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1013例8求對(duì)策的解。設(shè)矩陣對(duì)策G={S1,S2;A},其中S1={

1,

2,

3,

4},S2={

1,

2,

3,

4},贏得矩陣為第13頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1014一般矩陣對(duì)策的解可以是不唯一的。當(dāng)解不唯一時(shí),解之間的關(guān)系具有下面兩條性質(zhì)。性質(zhì)1無(wú)差別性即若(

i1,

j1)和(

i2,

j2)是對(duì)策G的兩個(gè)解,則ai1j1=ai2j2;性質(zhì)2可交換性即若(

i1,

j1)和(

i2,

j2)是對(duì)策G的兩個(gè)解,則(

i1,

j2)和(

i2,

j1)也是解。第14頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/10152.2矩陣對(duì)策的混合策略定義3

設(shè)有矩陣對(duì)策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è)混合局勢(shì),局中人Ⅰ的贏得函數(shù)記成

新的對(duì)策記成G*={S1*,S2*,E},它是對(duì)策G的混合擴(kuò)充。第15頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1016定義4

設(shè)G*={S1*,S2*;E}是矩陣對(duì)策G={S1,S2;A}的混合擴(kuò)充,如果

記其值為VG

.則稱VG

為對(duì)策G*的值,使上式成立的混合局勢(shì)(x*,y*)稱為G在混合策略意義下的解(或簡(jiǎn)稱解),x*和y*分別稱為局中人Ⅰ和Ⅱ的最優(yōu)混合策略(或簡(jiǎn)稱最優(yōu)策略)。第16頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1017定理2

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

S1*,y*

S2*,使(x*,y*)為函數(shù)E(x,y)的一個(gè)鞍點(diǎn),即對(duì)一切x

S1*,y

S2*,有

E(x,y*)≤E(x*,y*)≤E(x*,y)第17頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/10182.3矩陣對(duì)策的基本定理兩個(gè)記號(hào):當(dāng)局中人Ⅰ取純策略

i

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

時(shí),記其相應(yīng)的贏得函數(shù)為E(x,j),于是則有第18頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1019定理3

設(shè)x*

S1*,y*

S2*,則(x*,y*)為G的解的充要條件是:對(duì)任意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)對(duì)

i,j

成立，有第19頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1020定理4

設(shè)x*

S1*,y*

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

。第20頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1021定理4的證明“”設(shè)x*S1*,y*S2*,(x*,y*)是G

的解，則由定理3，對(duì)i=1,2,…,m,j=1,2,…,n,有所以由上可知x*與y*分別是不等式組(1),(2)的解。第21頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1022“”設(shè)不等式組(1),(2)的解分別為x*與y*,則有另：所以有E(x*,y*)=v,由定理3即知對(duì)策G

有解。第22頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1023定理5

對(duì)任一矩陣對(duì)策G={S1,S2;A},一定存在混合策略意義下的解。第23頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1024定理6

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

,則

(1)若xi*>0,則(2)若yj*>0,則(3)若則xi*=0(4)若則yj*=0.第24頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1025證明：由定義有，其中xi*≥0,i=1,…,m.這說(shuō)明，m

項(xiàng)非負(fù)數(shù)之和為零，從而和式中每一項(xiàng)均為零。故當(dāng)有某項(xiàng)中的xi*>0的話，則與其對(duì)應(yīng)的項(xiàng)必有如下結(jié)果(反之亦然)：第25頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1026例如，設(shè)(x*,y*)是矩陣對(duì)策G的解,v=VG

,若有x2*>0，則有反之，若有i=3使則有x3*=0.以此類推。第26頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1027定理7

設(shè)有兩個(gè)矩陣對(duì)策

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頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1028定理8

設(shè)有兩個(gè)矩陣對(duì)策

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

A}

其中

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

(1)VG2=

VG1

(2)T(G1)=T(G2)第28頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1029定理9

設(shè)G={S1,S2;A}為—矩陣對(duì)策,且A=-AT

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

(1)VG

=0

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

其中T1(G)和T2(G)分別為局中人Ⅰ和Ⅱ的最優(yōu)策略集。第29頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1030定義5

設(shè)有矩陣對(duì)策G={S1,S2;A},其中

S1={

1,?,

m

},S2={

1,?,

n

},A=(aij

)

如果對(duì)一切j=1,?,n都有ai

j

≥ak

j

,即矩陣A的第i

行元素均大于或等于第k

行的對(duì)應(yīng)元素,則稱局中人Ⅰ的純策略

i

優(yōu)超于

k

;

同樣,若對(duì)一切i=1,?,m,都有aij

≤ail

,即矩陣A的第j

列元素均小于或等于第l

列的對(duì)應(yīng)元素,則稱局中人Ⅱ的純策略

j

優(yōu)超于

l

.第30頁(yè),共33頁(yè)，2024年2月25日，星期天2024/4/1031定理10

設(shè)G={S1,S2;A}為矩陣對(duì)策,其中

S1={

1,?,

m

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

},A=(aij

)

如果純策略

1

被其余純策略

2,?,

m

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

={S1