12.7. Дослідження ігор, заданих платіжними матрицями

Узагалі завдання розв'язку гри, якщо її матриця не містить сі-длової точки, тим складніша, чим більше значення т і п. Тому в теорії матричних ігор розглядаються способи, за допомогою яких розв'язок одних ігор зводиться до розв'язку інших, більш прос­тих (зокрема, за допомогою скорочення розмірності матриці). Скоротити розмірність матриці можна, виключивши дублюючі і свідомо невигідні домінуючі стратегії. Після цього спрощену ма­трицю перевіряють на наявність у ній сідлової точки, що дозво­ляє відразу ж визначити розв'язок і ціну гри. Якщо сідлової точ­ки немає, то переходять до визначення оптимальних змішаних стратегій.

Приклад 3


Дослідити гру, задану платіжною матрицею (див. табл. 12.3).

Розв'язання:

1) 1-й рядок домінує над 2-м і 3-м, оскільки всі її елементи відповідно не менше елементів 2-го і 3-го рядків. Тому стратегії А2 і А3 свідомо менш вигідні, ніж А1 і можуть бути виключені (гравець А ніколи не скористається цими стратегіями). Виклю­чимо  «маленькі» рядки.  У результаті  одержуємо матрицю

8   6  4  7 7 7   2  6   5   9 .

У цій матриці 1, 4 і 5-й стовпці домінують над 2-м. Оскільки стовпці характеризують стратегії гравця Б, що прагне зменшити виграш гравця А, то ці стратегії свідомо невигідні (виключимо «великі» стовпці).

Після їх виключення одержуємо матрицю

6 4 2 6'

у якій немає домінуючих стратегій.

Визначивши нижню і верхню ціни гри, одержимо

(Хі = min {6, 4} =4,

а2 = min {2, 6} = 2, звідки

а = max {4, 2} = 4.

Аналогічно:

ß1 = max {6, 2} =6,

ß2 = гпах {4, 6} = 6,

звідки

ß = min {6, 6} = 6.

Оскільки а ф ß (4 Ф 6), то гра не має сідлової точки і її розв'я­зком буде змішана стратегія (розв'язування змішаних стратегій розглянуто далі).

Приклад 4


Дослідити гру, задану платіжною матрицею П1 (див. табл. 12.4).

Знайдемо дублюючі і свідомо невигідні домінуючі стратегії.

а = max (0; 2; -1) = 2

ß = min (0; 0; -1; 4) = 4

а ф ß , сідлової точки немає.

Такий же результат одержаний після дослідження матриці Пь

 

 

1 4

і

3

і

5

щ =

3 2

4

4

 

0__1_

і

4 і

вона дорівнює

1  4 1

3 22 тах_3 4

а = 2 (З = 4

а ф р , сідлової точки немає.

Для гравця Б свідомо невигідною є стратегія В4, тобто всі зна­чення цього стовпця перевищують відповідні значення 1, 2, 3 стовпців. її можна виключити (гравець Б ніколи не скористається цією стратегією).

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

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

Таким чином, при розв'язанні гри т • п слід:

а)         перевірити, чи не містить матриця сідлової точки;

б)         якщо сідлової точки немає, то потрібно порівняти між со-
бою елементи рядків і стовпців для виключення дублюючих і
домінуючих стратегій.