12.5. Графічне розв'язання матричних ігор розміру 2*п, т*2

магниевый скраб beletage

Графічний метод можна застосовувати до матричних ігор, в яких хоча б один з гравців має тільки дві стратегії.

S°A =

Розглянемо гру розміром 2 X n , в якій гравець А має дві чисті стратегії A0, A2, гравець В - п чистих стратегій В0, В2, ..., Вп. Вважаємо, що гра не має сідлової точки. Позначимо р0 - ймовірність застосування гравцем А стратегії A1 , р2 - ймовірність застосування гравцем А стратегії A2, причому р2 = 0 - р0 ; q0 - ймовірність застосування гравцем В стратегії B1 , q2 - ймовірність застосування

гравцем В стратегії B2 і т.д., qn - ймовірність застосування гравцем

n

В стратегії Bn, причому qj _1.

Платіжна матриця цієї гри представлена в табл. 12.11:

Таблиця 12.11 Платіжна матриця гри розміром 2 X n

 

B1

B2

• • •

B„

q1

q2

• • •

qn

4

Р1

an

a12

• • •

a1n

4

Р2

a21

a22

• • •

a2n

Якщо гра не має сідлової точки, то за основною теоремою теорії ігор вона має хоча б одне оптимальне рішення, яке визначаєтьсяv Р

so _

SB _

парою змішаних стратегій SA _

2

РО;

B

B1 B2

qO qo

А А

Середній виграш гравця А, якщо він використовує свою

O А1 А2

оптимальну стратегію SA _ o 0 , а гравець В - чисту

v p1 p2 у

стратегію B1 (що відповідає першому стовпцю платіжної матриці (табл. 12.11), дорівнює: a11 p°° + a21 p20. Оскільки р2 _ 1 _ р1 , то маємо

anр° + a2lp° _ anp0^ + 021(1 _ p1°) _ (an _ 021)Р1° + 021.

Аналогічно знайдемо очікувані середні виграші гравця А, якщо гравець В використовує чисті стратегії B2, B3,..., Bn, які представимо утабл. 12.12.

Таблиця 12.12

Чисті стратегії гравця В

Очікувані виграші гравця А

Bi

Ці - a2l)Рі" + a21

B2

(аі2 - «22)Рі" + «22

 

 

Bn

K - a2n )Рі" + a2n

З таблиці 12.12 видно, що очікуваний виграш гравця А лінійно залежить від р" . Побудуємо вирази очікуваних виграшів гравця А.

Гравцю А слід обирати таки стратегії, щоб максимізувати свій мінімальний очікуваний виграш. Тому оптимальна стратегія гравця А визначається як точка перетину прямих, що максимізують його мінімальний очікуваний виграш.

Аналогічно знаходимо оптимальну стратегію гравця В. Вона визначається як точка перетину прямих, що мінімізують його максимальний очікуваний програш.

Приклад 12.6. Знайти графічно рішення гри, яку задано (9 6 7 4 2^

платіжною матрицею

, а гравцем В - чистої для

^ 1 2 4 5 8у Розв'язання.. Знайдемо середні виграші гравцяА при використанні

ним змішаної стратегії SA =

V Рі Р2 У

Очікувані виграші гравця А

кожної зі стратегій гравця А. Результати представимо у табл. 12.13.

Таблиця 12.13

Очікувані виграші гравця А

Чисті стратегії гравця В

Очікувані виграші гравця А

B

(9 _ 1) Р1 +1 _ 8 Р1 +1

B2

(6 _ 2) p1 + 2 _ 4 p1 + 2

B3

(7 _ 4) p + 4 _ 3 Р1 + 4

B4

(3 _ 5) p1 + 5 __2 p1 + 5

B5

(2 _ 8) р + 8 __6 р + 8

На осі абсцис відкладемо відрізок, довжина якого дорівнює одиниці. Лівий кінець відрізка відповідає стратегії A1, правий - стратегії A2. Проміжні точки осі абсцис відповідають певним

А1 А2

,Р1 Р2у

змішаним стратегіям SA _

, де р2 _1_ р1 . На кінцях

вибраного відрізку проведемо прямі, на яких будемо відкладати виграш при відповідних чистих стратегіях (рис. 12.6).

З теорії ігрових моделей відомо, що слід взяти нижню огибаючу всіх прямих, що відповідають стратегіям гравця А, яку на рис 12.1 показано жирною ломаною. На цій ломаній, яка завжди обернена опуклістю вверх, знаходимо найбільше значення, яке й буде ціною гри або значенням гри для змішаних стратегій.

Найбільший виграш матиме гравець А, якщо від обере змішану стратегію, що відповідатиме застосуванню гравцем В суміші стратегій B2 і B4. Для знаходження оптимальної стратегії гравця А і ціни гри слід розв'язати систему рівнянь (12.18):

4 p + 2 = v,

-2 p + 5 = v,        (12.18)

Рі + Р2 = 1

1 1

SA =

Розв'язуючи систему (12.18) отримаємо, що p1 =— , p2 = — і v = 4 . Звідки оптимальна стратегія гравця А буде такою

4

4

1

і

2

2

Для знаходження оптимальної стратегії гравця В можна скористатися відомим результатом з теорії: оптимальна стратегія гравця В будується на двох чистих стратегіях, тобто гра 2 X n може бути зведена до гри 2 X 2 .

При використанні графічного метода видно які зі стратегій гравця В відпадають (тобто їх ймовірності дорівнюють нулю: q1 = q3 = q5 = 0 ), а які використовуються з ймовірностями q2 і q4, причому q2 + q4 = 1.

(12.19)

З рис. 12.1 видно, що стратегії B1, B3 і B5 не використовуються, тому гру, що розглядається можна звести до матричної гри розміром 2 X 2 , яку представлено платіжною матрицею

'6 4Л 2 5

Для гравця В середній програш дорівнює ціни грі v _ 4 і система для знаходження його оптимальної стратегії має вигляд:

6q2 + 4q4 _ 4, <2q2 + 5q4 _ 4,      (12.20)

Qi + Qt _ 11 2

Розв'язуючи систему (12.20) отримаємо, що q2 _ — , q4 _ — , тоді

о 1 о 2 о

з з

B2 Вз В4 В5Л

оптимальна стратегія гравця В буде SB _

Розглянемо гру розміром m X 2 , в якій гравець А має т чистих стратегій A1, A2,..., Am , а гравець В - дві чисті стратегії В1, В2. Вважаємо, що гра не має сідлової точки. Позначимо р1 - ймовірність застосування гравцем А стратегії A1 , р2 - ймовірність застосування гравцем А стратегії A2 і т.д., рт - ймовірність

m

застосування гравцем А стратегії Am , причому ^ p _ 1; q1 i _1

ймовірність застосування гравцем В стратегії В1 , q2 - ймовірність

застосування гравцем В стратегії В2, причому q2 _ 1 — q1 . Платіжну матрицю цієї гри представлено в табл. 12.14:

Таблиця 12.14

Платіжна матриця гри розміром т X 2

 

В1

В2

q1

q2

4

Р1

an

a12

A2

Р2

a21

a22

 

 

 

 

Am

Pm

ami

am2

Якщо гра не має сідлової точки, то за основною теоремою теорії ігор вона має хоча б одне оптимальне рішення, яке визначаєтьсяРП

S0 = sb =

парою змішаних стратегій SA =

B1 B2

qO qO

A1 A2 Р Рі

, а гравець А - чисту стратегію

Середній виграш гравця В, якщо він використовує свою

B, B-,

оптимальну стратегію SBo =

\qi q2

Очікувані виграші гравця В

А1 (що відповідає першому рядку платіжної матриці (табл. 12.14), дорівнює: anqO + a12q2 . Оскільки q2 = 1 — q1 , то маємо

аіЖ + a2iq2o = anqi0 + ai2(1—) = (an — a2i)q° + aL

Аналогічно знайдемо очікувані середні виграші гравця В, якщо гравець А використовує чисті стратегії A2, A3,..., Am , які представимо у табл. 12.15.

Таблиця 12.15

Чисті стратегії гравцяА

Очікувані виграші гравця В

A

(aii— ai2)q° + ai2

A

(a2i — an )q[ + an

 

 

Am

(ami — am 2)q° + am 2

З таблиці 12.15 видно, що очікуваний виграш гравця А лінійно залежить від qO . Побудуємо вирази очікуваних виграшів гравця А.

Гравцю В слід обирати таки стратегії, щоб мінімізувати свій максимальний очікуваний програш. Тому оптимальна стратегія гравця В визначається як точка перетину прямих, що мінімізують його максимальний очікуваний програш.

Аналогічно знаходимо оптимальну стратегію гравця А. Вона визначається як точка перетину прямих, що максимізують його мінімальний очікуваний виграш.

7

6

а гравцем А - чистої для

Приклад 12.7. Знайти графічно рішення гри, яку задано

платіжною матрицею

Розв'язання. Знайдемо середні виграші гравця В при використанні

'В1 В2Л

ним змішаної стратегії S°„ =

V Q1 q2 J

кожної зі стратегій гравця В. Результати представимо у табл. 12.16.

Таблиця 12.16

Очікувані виграші гравця В

Чисті стратегії гравцяА

Очікувані виграші гравця В

А

(8 - 1)q1 +1 = 7q1 +1

А

(7 - 4)q1 + 4 = 3q1 + 4

Аз

(6 - 5)q1 + 5 = q1 + 5

А4

(2 - 8)q1 + 8 = -6q1 + 8

змішаним стратегіям SB =

На осі абсцис відкладемо відрізок, довжина якого дорівнює одиниці. Лівий кінець відрізка відповідає стратегії B1, правий - стратегії B2. Проміжні точки осі абсцис відповідають певним

B, B,

. На кінцях вбраного відрізку

Л ?2

проведемо прямі, на яких будемо відкладати виграш при відповідних чистих стратегіях (рис. 12.2).

З теорії ігрових моделей відомо, що слід взяти верхню огибаючу всіх прямих, що відповідають стратегіям гравця В, яку на рис 12.7 показано жирною ломаною. На цій ломаній, яка завжди обернена опуклістю вниз, знаходимо найменше значення, яке й буде ціною гри або значенням гри для змішаних стратегій.

(12.21)

Найменший програш матиме гравець В, якщо від обере змішану стратегію, що відповідатиме застосуванню гравцем А суміші стратегій А3 і А4. Для знаходження оптимальної стратегії гравця В і ціни гри слід розв'язати систему рівнянь (12.21):

q+5 = v, -6q1 + 8 = v,

3

q+q = і4

Розв'язуючи систему (12.21) отримаємо, що q1 = —, q2 = —

38

і v = —, тому оптимальна стратегія гравця В буде такою

B1 B2

So = sb =

Для знаходження оптимальної стратегії гравця А можна скористаємося відомим результатом з теорії: оптимальна стратегія гравця В будується на двох чистих стратегіях, тобто гра m X 2 може бути зведена до гри 2 X 2 .

При використанні графічного метода видно які зі стратегій гравця А відпадають (тобто їх ймовірності дорівнюють нулю: p1 = p2 = 0 ), а які використовуються з ймовірностями p3 і p4, причому p3 + p4 = 1 .

З рис. 12.2 видно, що стратегії A1, A2 не використовуються, тому гру, що розглядається, можна звести до матричної гри розміром 2 X 2 , яку представлено платіжною матрицею

(12.22)

5 6Ч 8 2,

38 .

Для гравця А середній виграш дорівнює ціни грі v = — і система для знаходження його оптимальної стратегії має вигляд:

(12.23)

38

Р2 + 8 Р4 = у>

38

Р2 + 2 Р4 = у> Р2 + Р4 = 1.

6 1

А1 А2 А3 А4

0 0 6 1 7 7.

Розв'язуючи систему (12.23) отримаємо, що р3 = —, р4 =— , тому

оптимальна стратегія гравця А буде такою S°A =