Моклячук М.П., Ямненко Р.Є. Лекції з теорії вибору та прийняття рішень (на укр. языке)

Подождите немного. Документ загружается.

Теорема 2.3.1. Основна теорема матричних iгор. Нехай гра визна-

чається матрицею виграшiв

A =(a

)

i=1

j=1

розмiрностi m × n.Тодi

величини

max

X∈S

min

Y ∈S

E(X,Y ); min

Y ∈S

max

X∈S

E(X,Y )

iснують i рiвнi мiж собою

max

X∈S

min

Y ∈S

E(X,Y )= min

Y ∈S

max

X∈S

E(X,Y ).

Отже, кожна матрична гра має розв’язок у змiшаних стратегiях.

Кожний гравець у матричнiй грi завжди має оптимальну стратегiю.

Лема 2.3.1. Нехай задана матриця розмiрностi

m × n

A =



... a

... ... ... ...

... a



Тодi справедливе одне з двох тверджень:

1. Iснує елемент

X =(x

,...,x

) множини S

такий, що

+ a

+ ···+ a

≥ 0,j=1,2,...,n;

2. Iснує елемент Y =(y

,...,y

) множини S

такий, що

+ a

+ ···+ a

≤ 0,i=1,2,...,m.

Доведення. Нехай

(j)

=(δ

,δ

,...,δ

),j=1,2,...,m,

де



0,i= j,

1,i= j,

−

символи Кронекера, точки простору R

, j-та координата яких дорiвнює

1, а всi iншi координати дорiвнюють нулю.

Нехай

(j)

=(a

,...,a

),j=1,2,...,n,−

точки простору R

, координати яких – це елементи j-го стовпчика ма-

трицi

A.ПозначимочерезC опуклу лiнiйну оболонку множини m + n

точок

(1)

,...,δ

(m)

(1)

,...,a

(n)

Нехай z =(0,...,0) – початок координат простору R

.Можливiдва

випадки:

z ∈ C; z ∈ C.Якщоz ∈ C,тоz є опуклою лiнiйною комбiнацiєю

точок

(1)

,...,δ

(m)

(1)

,...,a

(n)

111

Отже, iснує елемент (u

,...,u

,...,v

) множини S

n+m

такий, що

(1)

+ ···+ u

(m)

+ v

(1)

+ ···+ v

(n)

= z. (2.3.1)

З рiвняння (2.3.1) випливає, що

+ ···+ u

+ v

+ ···+ v

=0,i=1,2,...,m,

або, з урахуванням визначення дельта-символiв,

+ v

+ ···+ v

=0,i=1,2,...,m. (2.3.2)

Оскiльки

,...,u

,...,v

) ∈ S

n+m

, то u

невiд’ємнi i з рiвностi

(2.3.2) отримаємо

+ ···+ v

≤ 0,i=1,2,...,m. (2.3.3)

Зауважимо тепер, що

+ ···+ v

> 0, (2.3.4)

бо в iншому випадку

= ···= v

=0,

i, як наслiдок рiвностi (2.3.2),

=0,i=1,2,...,m.

Ацесуперечитьтому,що(u

,...,u

,...,v

) ∈ S

n+m

Покладемо

+ ···+ v

,j=1,2,...,n. (2.3.5)

З нерiвностей (2.3.3) i (2.3.4) ми маємо, що

+ ···+ y

≤ 0,i=1,2,...,m.

З рiвностей (2.3.5) випливає, що (y

,...,y

) ∈ S

. Отже умова 2) леми

виконується.

Припустимо тепер, що

z ∈ C. Тодi за теоремою про опорну гiпер-

площину iснує гiперплощина, яка мiстить

z i така, що всi точки C

розташованi в одному з вiдповiдних пiвпросторiв. Нехай рiвняння цiєї

гiперплощини

+ ···+ b

= b

m+1

Оскiльки точка z лежить на гiперплощинi, то ми маємо

0+···+ b

0=b

m+1

Отже, b

m+1

=0. Таким чином, рiвняння гiперплощини має вигляд

+ ···+ b

=0. (2.3.6)

Ми можемо вважати, що будь-яка точка множини

C задовольняє нерiв-

нiсть

+ ···+ b

> 0. (2.3.7)

Нерiвнiсть (2.3.7) повинна бути справедливою, зокрема, для точок

(1)

...,δ

(m)

множини C.Отже,

+ ···+ b

> 0,i=1,...,m. (2.3.8)

112

А це означає (вiдповiдно до визначення дельта-символiв), що

> 0,i=1,...,m. (2.3.9)

Нерiвнiсть (2.3.8) повинна бути справедливою, зокрема, для точок

(1)

...,a

(m)

множини C.Отже,

+ ···+ b

> 0,i=1,...,m. (2.3.10)

З нерiвностi (2.3.9) випливає, що

+···+b

> 0 i ми можемо визначити

+ ···+ b

,i=1,2,...,m. (2.3.11)

З виразiв (2.3.10) i (2.3.11) випливає, що

+ a

+ ···+ a

> 0,j=1,2,...,n,

iтимбiльше

+ a

+ ···+ a

≥ 0,j=1,2,...,n. (2.3.12)

Так як з виразiв (2.3.9) i (2.3.11) випливає, що

,...,x

) ∈ S

,то

нерiвнiсть (2.3.12) означає, що умова 1) леми виконується.

Доведення. Доведемо основну теорему теорiї матричних iгор.

Для кожного

Y =(y

,...,y

) функцiя E(X,Y ) є неперевна лiнiйна

функцiя вiд

X =(x

,...,x

), яка визначена на замкнутiй пiдмножинi

простору R

.Тому

max

X∈S

E(X,Y )

iснує для кожного Y ∈ S

. Далi легко переконатися в тому, що

max

X∈S

E(X,Y )

є неперервною кусково-лiнiйною функцiєю вiд Y =(y

,...,y

),якави-

значена на

.ОскiлькиS

єзамкнутапiдмножинапросторуR

,то

min

Y ∈S

max

X∈S

E(X,Y )

iснує. Аналогiчно показується, що iснує

max

X∈S

min

Y ∈S

E(X,Y ).

Якщо перша умова леми 2.3.1 виконується, то iснує елемент X =

,...,x

) множини S

такий, що

+ a

+ ···+ a

≥ 0,j=1,2,...,n.

Тодi для довiльного Y ∈ S

E(X,Y )=



j=1

+ a

+ ···+ a

) y

≥ 0. (2.3.13)

Оскiльки спiввiдношення (2.3.13) справедливе для будь-якого

Y ∈ S

то

min

Y ∈S

E(X,Y ) ≥ 0.

113

Отже,

max

X∈S

min

Y ∈S

E(X,Y ) ≥ 0. (2.3.14)

Аналогiчно показуємо, що

min

Y ∈S

max

X∈S

E(X,Y ) ≤ 0, (2.3.15)

якщо виконуєтьс умова 2) леми 2.3.1.

Оскiльки виконується або умова 1), або умова 2) леми 2.3.1, то при-

наймнi одна з двох нерiвностей, (2.3.14) чи (2.3.15), повинна виконува-

тися, i, отже, нерiвнiсть

max

X∈S

min

Y ∈S

E(X,Y ) < 0 < min

Y ∈S

max

X∈S

E(X,Y ) (2.3.16)

не може бути справедливою.

Нехай

– матриця, яку отримаємо з матрицi A при вiднiманнi k вiд

кожного елемента, тобто



− ka

− k ... a

− k

− ka

− k ... a

− k

... ... ... ...

− ka

− k ... a

− k



iнехайE

(X,Y ) – це математичне сподiвання виграшу у грi з матрицею

(X,Y )=



i=1



j=1

− k)x

= E(X,Y ) − k.

Тодi, точно так само, як ми показали, що нерiвнiсть (2.3.16) не викону-

ється для

A, ми можемо показати, що нерiвнiсть

max

X∈S

min

Y ∈S

(X,Y ) < 0 < min

Y ∈S

max

X∈S

(X,Y )

не виконується для A

. Отже, нерiвнiсть

max

X∈S

min

Y ∈S

M(X,Y ) <k<E(X,Y ) <k< min

Y ∈S

max

X∈S

M(X,Y )

неправильна для всiх чисел k. А тому не виконується нерiвнiсть

max

X∈S

min

Y ∈S

E(X,Y ) < min

Y ∈S

max

X∈S

E(X,Y ).

Тому справедлива нерiвнiсть

max

X∈S

min

Y ∈S

E(X,Y ) ≥ min

Y ∈S

max

X∈S

E(X,Y ).

З iншого боку за теоремою 2.2.1

max

X∈S

min

Y ∈S

E(X,Y ) ≤ min

Y ∈S

max

X∈S

E(X,Y ).

Азначить,

max

X∈S

min

Y ∈S

E(X,Y )= min

Y ∈S

max

X∈S

E(X,Y ).

Це i завершує доведення теореми.

114

2.4. ВЛАСТИВОСТI ОПТИМАЛЬНИХ СТРАТЕГIЙ ГРИ

Теорема 2.4.1. Нехай v –дiйснечислотаX

∗

, Y

∗

– елементи множин

та S

вiдповiдно. Для того, щоб v було цiною гри, а X

∗

, Y

∗

були оптимальними стратегiями першого та другого гравцiв гри з

матрицею

A =(a

)

i=1

j=1

, необхiдно i достатньо, щоб для всiх i :1≤

i ≤ m

,тадлявсiхj :1≤ j ≤ n, виконувались нерiвностi

(i,Y

∗

) ≤ v ≤ E(X

∗

,j).

Тут через E(i,Y ) позначено виграш першого гравця за умови, що вiн

застосовує свою чисту

i-ту стратегiю, а другий гравець застосовує

стратегiю

Y : E(i,Y )=



j=1

. Аналогiчно E(X,j)=



i=1

Доведення. Необхiднiсть умови випливає безпосередньо з визначення

сiдлової точки. З iншого боку, якщо умова виконується, то для будь-

якого елементу

X =(x

,...,x

) множини S



i=1

E(i,Y

∗

≤



i=1

= v.

Отже,

(X,Y

∗

) ≤ v. (2.4.1)

Аналогiчно, для будь-якого елементу

Y =(y

,...,y

) множини S

v ≤ E(X

∗

,Y ). (2.4.2)

З нерiвностей (2.4.1) i (2.4.2) при замiнi

X на X

∗

та Y на Y

∗

маємо

∗

) ≤ v ≤ E(X

∗

). (2.4.3)

Азначить,

∗

)=v.

З нерiвностей (2.4.1), (2.4.2), (2.4.3) матимемо для всiх X ∈ S

та всiх

Y ∈ S

E(X,Y

∗

) ≤ E(X

∗

) ≤ E(X

∗

,Y ).

Отже, (X

∗

) єсiдловоюточкоюфункуцiїE(X,Y ),аv єцiноюгри.

Теорема 2.4.2. Нехай (X

∗

) – розв’язок гри з матрицею A розмiр-

ностi

m × n.Тодi

max

1≤i≤m

E(i,Y

∗

)= min

1≤j≤n

E(X

∗

,j)=E(X

∗

Доведення. За попередньою теоремою для всiх 1 ≤ j ≤ n має мiсце

нерiвнiсть

v ≤ E(X

∗

,j),

115

де v –цiнагри.Тодi

v ≤ min

1≤j≤n

E(X

∗

,j).

Якщо

v< min

1≤j≤n

E(X

∗

,j),

то для всiх 1 ≤ j ≤ n

E(X

∗

,j).

Тодi

v<E(X

∗

Ацесуперечитьтому,щоv цiна гри. Отже,

v =min

1≤j≤n

E(X

∗

,j).

Аналогiчно показується, що

v =max

1≤i≤m

E(i,Y

∗

Наступна теорема часто виявляється дуже корисною при вiдшуканнi

розв’язкiв гри.

Теорема 2.4.3. Нехай

∗

=(x

∗

,...,x

∗

), Y

∗

=(y

∗

,...,y

∗

) – розв’язок

гри з матрицею

A розмiрностi m ×n i нехай цiна гри дорiвнює v.Тодi

для будь-якого

i, при якому E(i,Y

∗

) <v,маємiсцерiвнiстьx

∗

=0,а

для будь-якого

j, при якому E(X

∗

,j) >v,маємiсцерiвнiстьy

∗

=0.

Доведення. Припустимо, що для деякого

E(i

∗

) <v

i x

∗

=0. Тодi ми маємо, що

∗

<vx

∗

Оскiльки для i = i

E(i,Y

∗

) ≤ v,

то

(i,Y

∗

≤ vx

∗

Отже, матимемо



i=1

E(i,Y

∗



i=1

∗

) <v,

що суперечить умовi, що v – це цiна гри. Друга частина теореми дово-

диться аналогiчно.

116

Теорема 2.4.4. Нехай E – математичне сподiвання виграшу першо-

го гравця у грi з матрицею

A розмiрностi m × n iнехайX

∗

, Y

∗

–

елементи множин

та S

вiдповiдно. Тодi мають мiсце наступнi

еквiвалентнi твердження:

∗

є оптимальною стратегiєю першого гравця, а Y

∗

єопти-

мальною стратегiєю другого гравця.

2. Якщо

X – це довiльний елемент множини S

,аY – довiльний

елемент множини

,то

(X,Y

∗

) ≤ E(X

∗

) ≤ E(X

∗

,Y ).

3. Якщо i та j – це будь-якi цiлi числа, такi, що 1 ≤ i ≤ m,

1 ≤ j ≤ n,то

(i,Y

∗

) ≤ E(X

∗

) ≤ E(X

∗

,j).

2.5. СПРОЩЕННЯ МАТРИЧНИХ IГОР

Означення 2.5.1. Вектор a =(a

,...,a

) домiнує вектор b =(b

, ...,b

якщо

≥ b

для всiх 1 ≤ i ≤ n.Якщоa

для всiх 1 ≤ i ≤

, то говорять, що вектор a =(a

,...,a

) строго домiнує вектор b =

,...,b

Означення 2.5.2.Розширеннястратегiї



=(x

,...,x

) ∈ S

на i-ому

мiсцi – це вектор

X =(x

,...,x

i−1

,0,x

,...,x

) ∈ S

n+1

Теорема 2.5.1. Нехай

G –гразматрицеюA.Нехайi-й рядок матри-

цi

A домiнує деяка опукла лiнiйна комбiнацiя iнших рядкiв матрицi

A.НехайграG



зматрицеюA



, яка отримана iз матрицi A пiсля

виключення

i-го рядка. Тодi цiна гри G



дорiвнює цiнi гри G.Опти-

мальна стратегiя другого гравця у грi



єоптимальноюстратегiєю

другого гравця у грi

G.ЯкщоX



–оптимальнастратегiяпершого

гравця у грi



i X – це розширення X



на i-тому мiсцi, то X бу-

де оптимальною стратегiєю першого гравця у грi

G.Далi,якщоi-й

рядок матрицi

A строго домiнує деяка опукла лiнiйна комбiнацiя iн-

ших рядкiв, то будь-який розв’язок гри

G можна отримати вказаним

способом iз розв’язку гри



Доведення. Нехай задана матриця порядку

m × n

A =



... a

... ... ... ...

... a



117

Можна припустити, що останнiй рядок матрицi A перевищує опукла

лiнiйна комбiнацiя iнших рядкiв. Тому iснує елемент

z =(z

,...,z

m−1

)

множини S

m−1

такий, що

≤

m−1



i=1

,j=1,2,...,n. (2.5.1)

Нехай

v –цiнагриG



i w =(w

,...,w

m−1

) –оптимальнастратегiя

першого гравця у грi



,аy =(y

,...,y

) – оптимальна стратегiя гравця

другого гравця у грi



. Тодi за теоремою 2.4.1



j=1

≤ v, i =1,2,...,m− 1; (2.5.2)

v ≤

m−1



i=1

,j=1,2,...,n. (2.5.3)

Для доведення першої частини теореми досить показати, що

v єта-

кож цiна гри

G, y =(y

,...,y

) – оптимальна стратегiя гравця другого

гравця у грi

G,iw =(w

,...,w

m−1

,0) – оптимальна стратегiя першого

гравця у грi

З попереднiх теорем випливає, що для цього потрiбно довести спра-

ведливiсть наступних нерiвностей:



j=1

≤ v, i =1,2,...,m; (2.5.4)

v ≤

m−1



i=1

+ a

0,j=1,2,...,n. (2.5.5)

Нерiвнiсть (2.5.5) – це очевидний наслiдок нерiвностi (2.5.3). Тому до-

сить довести нерiвнiсть (2.5.4). Отже, користуючись нерiвнiстю (2.5.2),

досить показати, що



j=1

≤ v. (2.5.6)

З нерiвностей (2.5.1), (2.5.2) маємо



j=1

≤



j=1

m−1



i=1

≤

m−1



i=1



j=1

≤

m−1



i=1

= v,

що i доводить справедливiсть теореми. Для доведення другої частини

теореми зауважимо, що якщо у жодному зi спiввiдношень (2.5.1) немає

118

рiвностi, то



j=1



j=1

m−1



i=1

≤ v.

Отже, за теоремою 2.4.3 кожна оптимальна стратегiя першого гравця

буде мати нульову

m-ту компоненту.

Доведення наступної теореми аналогiчне.

Теорема 2.5.2. Нехай

G –гразматрицеюA.Нехайj-й стовпчик ма-

трицi

A домiнує деяку опуклу лiнiйну комбiнацiю iнших стовпчикiв

матрицi

A.НехайG



–гразматрицеюA



, яка отримана iз матрицi

A пiсля виключення j-го стопчика. Тодi цiна гри G



дорiвнює цiнi гри

G. Оптимальна стратегiя першого гравця у грi G



єоптимальною

стратегiєю першого гравця у грi

G.ЯкщоY



–оптимальнастрате-

гiя другого гравця у грi



i Y – це розширення Y



на j-тому мiсцi, то

Y буде оптимальною стратегiєю другого гравця у грi G.Далi,якщо

j-й стовпчик матрицi A строго домiнує деяку опуклу лiнiйну комбi-

нацiю iнших рядкiв, то будь-який розв’язок гри

G можна отримати

вказаним способом iз розв’язку гри



Наведемо приклад застосування цих теорем.

Приклад 2.5.1. Нехай гра задана матрицею



3240

3424

4240

0408



Оскiльки третiй рядок матрицi домiнує перший, то, викреслюючи пер-

шийрядок,миодержуємо:



3424

4240

0408



У новiй матрицi перший стовпець домiнує третiй; викреслюючи перший

стовпець, ми одержуємо:



424

240

408



У цiй матрицi нiякий рядок (i нiякий стовпець) не домiнує iншi рядки

(i стовпцi). Але перший стовпець домiнує опуклу лiнiйну комбiнацiю

другого i третього стовпцiв, тому що

4 >

× 2+

× 2,

119

× 4+

× 0,

× 0+

× 8.

Тому ми виключаємо перший стовпець i одержуємо:



У свою чергу в цiй матрицi опукла лiнiйна комбiнацiя другого i третього

рядкiв домiнує перший рядок

× 4+

× 0,

× 0+

× 8.

Таким чином, наша матриця приведена до матрицi



Цiна гри з цiєю матрицею дорiвнює

, а оптимальна стратегiя для першо-

го гравця (i для другого гравця) буде

(

). Отже, оскiльки ми одержали

матрицю

2 × 2 зматрицi4 × 4,викреслюючипершiдварядкиiпершi

два стовпчики, то приходимо до висновку, що оптимальна стратегiя для

першого гравця (i для другого гравця) у початковiй грi є

(0,0,

Зауваження. Iз доведених теорем випливає, що коли ми викреслюємо

рядок (чи стовпець), який домiнується строго, то ми одержуємо матри-

цю, що приводить до точно такої системи розв’язкiв, яку б ми отримали,

розв’язавшипочатковугру.Однакценевiрноутомувипадку,колиспiв-

вiдношення переваги не є строгим; у цьому випадку ми можемо втратити

деякi з розв’язкiв початкової гри.

Приклад 2.5.2. Як приклад розглянемо гру з матрицею виграшiв



00 0

01−1

0 −11



Легко переконатися в тому, що будь-який елемент множини S

вигляду

(a,b,b) буде оптимальною стратегiєю для першого гравця. З iншого боку,

якщо ми викреслимо перший рядок (який домiнує, але не строго, опу-

кла лiнiйна комбiнацiя двох iнших рядкiв) i потiм викреслимо перший

стовпець,томиодержимоматрицю



1 −1

−11



120