12.8. Елементарні прийоми розв'язування ігор 2 * 2 і 2 * п

Найбільш простою є гра, у якій кожний із гравців має 2 стра­тегії. Розглянемо платіжну матрицю П:

 

 

Ві

_в1

 

 

 

4

а21

а22

Якщо сідлової точки немає, то розв'язанням гри є змішані стратегії.

у — ІУі>У2)

Теорема:

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

Відповідно до цієї теореми, застосування оптимальної страте­гії х = (х1, х2) забезпечує для гравця А одержання виграшу V при будь-яких стратегіях для гравця Б.

Оптимальна стратегія для гравця Б теж є змішаною. Тому як­що гравець А застосовує свою оптимальну стратегію, то при цьому гравець Б може використовувати одну з чистих стратегій і величина виграшу гравця А залишиться незмінною. Запишемо систему рівнянь:

аіцХі + а2іХ2=

Оскільки сума ймовірностей дорівнює 1, то

хі + х2 = 1.

Розв'язавши систему, одержимо:

х  =      а22 ~ а21        ,

Хі — ,

аііі І аа22 а2і

а^іі І аа22   аіі2 а^2і Підставляючи х1 і х2 у систему рівнянь, одержимо:

Це оптимальна стратегія для гравця А.

Аналогічно можна знайти оптимальну стратегію для гравця Б. Запишемо систему рівнянь:

«11 Уі + аі2 У 2 = V «21 Уі + «22 """2 — V

Оскільки сума ймовірностей дорівнює 1, то

Уі + У2 = і.

Розв'язавши систему, одержимо:

у\ — ■■ а\\\ і а^22   а\\2 а^2\

.           а\\ ~ а2\          

у 2 — ■

а\\\ і аа22   а\\2   аа2\

Приклад 5

п

Знайти розв'язок гри, заданої матрицею.

|\ 3|

2 \

Розв'язання. Маємо а = 1, Р = 2; матриця не має сідлової точ­ки. За формулами для гравця А:

а«2і   аа 22

1 - 2 1

Х1 —  —        — .

«21 + «22 - «12 - «21      1 + 1 - 3 - 2 3

«1і       1  3 2

Х2 —  —        — ,

«11 + «22 - «12 - «21    1 +1 - 3 - 2 3

знайдемо оптимальну стратегію для гравця А.

Підставляючи Х1 і 00, Х2 у систему рівнянь, одержимо ціну гри:

«ііі ««22     ««12 ««21

1x1 - 3 х 2 5 «11 + «22 - «12 - «21   1 +1 - 3 - 2 3 Аналогічно можна знайти оптимальну стратегію для гравця Б.

«22  - «12        1 - 3 2

У1 —  22—    —        ——;

«21 + «22 - «12 - «21   1 +1 - 3 - 2 3

У2 —  «11 - «21         —        1 - 2        — і

«11 + «22 - «12 - «21   1 +1 - 3 - 2 3 Таким чином, оптимальні стратегії і ціна гри:


хо

у

опт

_ 5

У _ 3.


 

V

ґ


 

2

з;з

\

з;з


12.9. Графічний метод розв'язування ігор 2 * 2

Розв'язок гри (2 • 2) можна знайти графічно (див. рис. 12.1).

На осі абсцис відкладемо відрізок одиничної довжини. Ліва точка X = 0 відповідає стратегії А1, а права — стратегії А2. Про­міжні точки відповідають певним змішаним стратегіям, де Хі = 1 - X, а Х2 = X.

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

«11 і «21.


Подпись:  (Ві)а„

(В2)аі2


№)а22

|(В0а21  1¥


х*


х


 


Аі


А2


 

Рис. 12.1. Геометрична інтерпретація гри

Відкладемо ці точки на прямих А1 і А2. З'єднаємо точки В1В1 і В2В2. На перетині цих прямих вийде точка М, що відповідає змі­шаній стратегії. Ординати точок, що лежать на ламаній В2МВ1 характеризують мінімальний виграш для гравця А при викорис­танні будь-якої змішаної стратегії X.

Дотримуючись принципу максиміна, одержимо, що оптима­льний розв'язок гри _визначає т. М, у якій мінімальний виграш досягає максимуму. їй відповідає на осі абсцис оптимальна стра­тегія X*, а ордината дорівнює ціні гри V. За ціною гри відразу знаходиться оптимальна стратегія для гравця Б:

\ацУ1* +СІ21У2* = 1 І у1 + у 2 = 1 Ламана В2МВ1 — нижня ціна гри.

Якщо матриця гри має сідлову точку, то одержимо такі різно­види графічного зображення гри (див. рис. 12.2—12.4).


Подпись:

Розв'язком для гравця А є чиста стратегія А2, а для гравця Б — чиста стратегія В2. Нижньою ціною гри буде ламана ВіМВ2. Максимальне значення ламаної досягається в т. В2 стратегії А2, тоді X* = (0, 1), У* = (1, 0).

Гра має сідлову точку а22 = V, що дорівнює ціні гри.

Розглянемо інший випадок гри із сідловою точкою (див. рис. 12.3).

Тут розв'язок гри відповідає точці В1 і задається векторами X* = (0,1)

У * = (1,0).


Подпись:

В2 В1


В1

V


0


х


 


А1


А2


 

Рис. 12.4. Графічне зображення гри із сідловою точкою

Графічна інтерпретація дозволяє розв'язувати ігри з матрицею 2 • р чи д • 2.

Якщо матриця (2 • р), значить треба побудуватир прямих.


Приклад 6

Знайти графічним методом розв'язок гри, заданий матрицею

П

3

min 2  -1 -1 5   3 _ max    5 3


Розв'язок (рис. 12.5)

а = 3 (З = 3

а=р=V=3

Розв'язком для гравця Б є чиста стратегія В2. Ціна гри V = 3.

Приклад 7


Знайти графічним методом розв'язок гри, заданий матрицею.

Розв'язок гри з матрицею (2 • 2) можна знайти графічно за до­помогою таких побудов.

На осі абсцис відкладемо відрізок, довжина якого дорівнює одиниці. Лівий кінець відрізка (точка х = 0) відповідає стратегії А1, правий — стратегії А2. Проміжні точки х відповідають певним змішаним стратегіям (х1, х2), де х1 = 1 - х, х2 = х.

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

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

В1В1.


Якщо гравець А застосовує змішану стратегію, то його вигра­шу відповідає точка М, що лежить на цій прямій (рис. 12.6).


Аналогічно можна побудувати пряму В2В2, що відповідає стратегії В2 гравця Б (рис. 12.7). Ламана В1КВ2 є нижньою ме­жею виграшу, одержуваного гравцем А. Точка К, у якій він мак­симальний, визначає ціну гри і її розв'язок.

Для знаходження оптимальної стратегії гравця Б скористаємо­ся формулою:

с£-\ і а/т^   с&л п о/п і           2 * 2   3 * 3

V =      П_22   п_п— =          = _2,5 ,

00^11 і а22   0^12   а21    2 і 2   3 3

одержуємо значенняу\ і в2, які дорівнюють:

,           «22 ~ «\2                     = А5.

а\\\ і ««22   а\\2 ««2\

у2 _ —«j^-^— = 05.

«\\\ і ««22   «\2   ««2\