Тема 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 – а21∙p1 = а12∙р1 + а22 – а22∙p1
Доданки з р1
перенесемо у ліву частину, а вільні члени – у праву частину:
а11∙р1 +
а22∙p1 – а21∙p1 – а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 необхідно розв’язати систему рівнянь:
а11∙q1 + а12∙q2 = V перше рівняння пов’язане з програшем
гравця В проти стратегії А1
а21∙q1 + а22∙q2 = 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.