Тема 5. Методи розв’язання матричних ігор.

1.     Оптимальні стратегії.

2.     Ігри з сідловою точкою. Чиста стратегія гравця.

3.     Розв’язок матричної гри в чистих стратегіях.

4.     Мішана стратегія гравця.

5.     Розв’язок матричної гри в мішаних стратегіях.

6.     Геометричний метод розв’язання матричної гри. Матрична гра порядку 2х2.

 

1.     Оптимальні стратегії.

Щоб розв’язати гру, слід для кожного гравця обрати стратегію, яка задовольняє умову оптимальності, тобто:

-       перший гравець повинен отримувати максимальний ВИГРАШ, коли другий дотримується своєї стратегії;

-       в той же час другий гравець повинен мати мінімальний ПРОГРАШ, якщо перший дотримується своєї стратегії.

Такі стратегії називаються оптимальними.

Оптимальні стратегії повинні також задовольняти умову стійкості, тобто будь-якому з гравців має бути невигідно відмовитися від своєї стратегії в цій грі.

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

 

2.     Ігри з сідловою точкою. Чиста стратегія гравця.

Якщо гра має сідлову точку (aij), яка задає певні стратегії гравців (стратегію Аi  гравця А і стратегію Вj гравця В), то ці стратегії і є оптимальними і розв’язком гри є набір таких стратегій (Аi;Bj).

Чистою стратегією Ai гравця А називається можливий хід, який гравець А обрав з ймовірністю 1. Це задані стратегії А1, А2, …, Аm гравця А.

 

3.   Розв’язок матричної гри в чистих стратегіях.

Нагадаємо, що ми розглядаємо:

-       парні ігри з двома гравцями, причому А – гравець, який завжди виграє, а В – гравець, який завжди програє;

-       ігри з нульовою сумою, тобто антагоністичні.

Оскільки матрична гра фактично вимагає шукати рішення в умовах невизначеності, то основною розв’язку має стати певного критерію.

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

Для першого гравця (А) – це МАКСИМІННИЙ критерій (вибір мінімального числа в кожному рядку, і далі вибирає з цих чисел максимальне – тобто максимум з мінімумів):

α = Vнц    нижня ціна гри

Для другого гравця (В) – це МІНІМАКСНИЙ критерій (вибір максимального числа в кожному стовпці, і далі вибирає з цих чисел мінімальне – тобто мінімум з максимумів):

β = Vвц    верхня ціна гри

Якщо гра має сідлову точку, то Vнц = Vвц = V  (або  α = β = V)   ціна гри.

Якщо гра має сідлову точку, то (aij), яка задає певні стратегії гравців (стратегію Аi  гравця А і стратегію Вj гравця В), то ці стратегії і є оптимальними і розв’язком гри є набір таких стратегій (Аi;Bj). Це чисті стратегії гравців – ті, які були задані в умові.

 

4.   Мішана стратегія гравця.

Якщо a ¹ b, а точніше a < b, то це означає, що не існує єдиних стратегій для першого і другого гравців для отримання оптимального результату. Тоді логіка гри вимагає «змішувати» стратегії при повторенні однакових ігор з ймовірнісними «ваговими» коефіцієнтами з метою отримати оптимальну ціну гри a < V < b, тобто підвищити виграш і знизити програш, зводячи їх значення до ціни гри. Зміст ймовірнісних «вагових» коефіцієнтів полягає у знаходженні ймовірностей вибору тієї або іншої стратегії, які утворюють вектори мішаних стратегій для кожного гравця.

Для першого гравця вектор мішаних стратегій:

p = ( p1, p2,..., pm), де pi (i =1,...,m) – ймовірність вибору першим гравцем стратегії Ai.

Для другого гравця вектор мішаних стратегій:

q = (q1, q2,..., qn), де qj (j =1,...,n) – ймовірність вибору другим гравцем стратегії Bj.

Оскільки якісь стратегії будуть обов’язково використані, вектору мішаних стратегій притаманна властивість:

p1 + p2 + ... + pm = 1    і    q1 + q2 + ... + qn = 1.

 

5.   Розв’язок матричної гри в мішаних стратегіях.

Якщо матрична гра mхn не має сідлової точки, то знаходження розв’язків є досить складною задачею, особливо при великих m та n.

Інколи задачу вдається спростити, зменшуючи кількість стратегій, тобто закреслюючи заздалегідь невигідні.

Найбільш простими випадками скінченних ігор, які можна завжди розв’язати елементарними способами, є ігри 2х2, 2´n, m´2.

 

Розглянемо гру 2х2, тобто гру двох гравців, кожен з яких має дві стратегії.

Платіжна матриця гри має розмірність 2х2:

 

А

 

а11

а12

2х2

 

a21

a22

 

Одним із способів розв’язання такої гри є аналітичний метод.

Позначимо оптимальні мішані стратегії гравців, які є розв’язком задачі і які ми маємо знайти:

 

для гравця А:

p = ( p1*, p2*), де

p1* - ймовірність, з якою гравець А вибере стратегію А1

p2* - ймовірність, з якою гравець А вибере стратегію А2

p1*+ p2*=1.

 

для гравця В:

q = (q1*, q2*), де

q1* - ймовірність, з якою гравець B вибере стратегію B1

q2* - ймовірність, з якою гравець B вибере стратегію B2

q1*+ q2* =1.

 

Для знаходження оптимальної мішаної стратегії p = ( p1*, p2*) гравця А і відповідної ціни гри V необхідно розв’язати систему рівнянь (1):

 

а11р1 + а21р2 = V перше рівняння пов’язане з виграшем гравця А проти стратегії В1

а12р1 + а22р2 = V друге рівняння пов’язане з виграшем гравця А проти стратегії В2      (1)

p1+ p2 =1

 

Оскільки праві частини перших двох рівнянь однакові, то прирівняємо ліві частини цих рівнянь і підставимо туди вираз для p2 з третього рівняння. Отримаємо:

 

а11р1 + а21р2 = а12р1 + а22р2

p2 =1 – p1

 

а11р1 + а21∙(1 – p1) = а12р1 + а22∙(1 – p1)

розкриваємо дужки:

а11р1 + а21а21p1 = а12р1 + а22а22p1

Доданки з р1 перенесемо у ліву частину, а вільні члени – у праву частину:

а11р1 + а22p1а21p1а12р1 = а22а21

винесемо р1 за дужки:

р1 ∙ (а11 + а22а21а12) = а22а21

звідки маємо розв’язки системи рівнянь (оптимальні мішані стратегії гравця А):

р1 *= (а22а21) / (а11 + а22а21а12)                                                          (2)

p2 *=1 – p1 = (а11а12) / (а11 + а22а21а12)                                              (3)

і ціну гри:

V = (а11 а22а12 а21) / (а11 + а22а21а12)                                                  (4)

Аналогічно для знаходження оптимальної мішаної стратегії q = (q1*, q2*) гравця B і відповідної ціни гри V необхідно розв’язати систему рівнянь:

 

а11q1 + а12q2 = V перше рівняння пов’язане з програшем гравця В проти стратегії А1

а21q1 + а22q2 = V перше рівняння пов’язане з програшем гравця В проти стратегії А2

q1+ q2 =1

 

q1 *= (а22а12) / (а11 + а22а21а12)                                                          (5)

q2 *=1 – q1 = (а11а21) / (а11 + а22а21а12)                                              (6)

Ціна гри V є спільною для обох гравців.

 

6.   Геометричний метод розв’язання матричної гри. Матрична гра порядку 2х2.

Розглянемо гру 2х2.

Для знаходження ймовірностей (p1, p2) і ціни гри V в прямокутній системі координат в точках x = 0, x =1 осі ОХ відбудуємо перпендикуляри і позначимо їх A1 і A2 – відповідно до стратегій гравця А.

На перпендикулярах A1 і A2 будемо відкладати виграші гравця А, які відповідають цим чистим стратегіям.

Зобразимо стратегію B1: на прямій A1 відкладемо a11 , а на прямій A2 відкладемо a21 . З'єднаємо ці точки і отримаємо пряму B1B1 (рис.1).

Рис. 1. Графічна інтерпретація стратегії В1

Аналогічно зобразимо стратегію B2, відклавши на прямій A1 значення a12, а на прямій A2 - значення a22, отримаємо пряму B2B2 (рис. 2).

Рис. 2. Графічна інтерпретація гри 2´2 для гравця А

 

Кожній точці на відрізку [0; 1] відповідає мішана стратегія гравця А, причому p2 – відстань від цієї точки до нуля, а p1 – відстань від цієї точки до точки 1 (рис. 2).

При р1 = 0 гравець А застосовує свою другу чисту стратегію (A2). Якщо при цьому гравець В застосовує свою першу чисту стратегію, то виграш гравця А дорівнює а21, а якщо гравець В застосовує свою другу чисту стратегію, то виграш гравця А дорівнює а22.

При р1 =1 гравець А застосовує свою першу чисту стратегію (A1). Якщо при цьому гравець В застосовує свою першу чисту стратегію, то виграш гравця А дорівнює а11, а при застосуванні гравцем В другої чистої стратегіїа12.

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

Точка М перетину відрізків прямих B1B1 і B2B2 і визначає як оптимальну ціну гри V, так і оптимальні ймовірності p1 і p2 = 1 – p1, які відповідають оптимальній мішаній стратегії гравця А, тобто дає розв’язок системи рівнянь (1). Ламана B2MB1 (на рис. 2 виділено напівжирним) визначає мінімальні можливі середні виграші гравця А при використанні ним своїх мішаних стратегій. Найвища точка M(x;y) ламаної B2MB1визначає найкращий середній виграш гравця А з усіх мінімальних, вона відповідає оптимальній мішаній стратегії гравця А, при цьому:

p1* = 1 - х, p2* = x, V = y.

Таким чином, задача зводиться до знаходження координат точки M(x;y), яка є точкою перетину прямих B1B1 і B2B2. Для знаходження рівнянь цих прямих у загальне рівняння прямої у=ax+b слід підставити координати точок, через які вона проходить.

Пряму B1B1 визначають точки B1(0;а11) і B1(1;а12), а пряму B2B2 - точки B2(0;а12) і B2(1;а22).

 

Для гравця В оптимальна мішана стратегія знаходиться аналогічно, але точка М визначається як найнижча точка верхньої ламаної A1МА2напівжирна ламана на рис. 3.

Рис. 3. Графічна інтерпретація гри 2х2 для гравця В

 

Координати точки M(x;y) знаходимо, як координати точки перетину прямих A1A1 і А2А2, компоненти оптимальної мішаної стратегії q = (q1*, q2*) гравця В і ціну гри V можна знайти за такими формулами:

 

q1* = 1 - х, q2* = x , V = y.