Тема 4. Матричні ігри.
1. Антагоністичні
ігри або ігри з нульовою сумою.
2. Матричні ігри.
Матрична парна гра. Платіжна функція гри.
3. Принцип
мінімаксу (максиміну). Нижня ціна гри. Верхня ціна гри. Мінімаксна та
максимінна стратегії.
4. Сідлова точка. Ціна гри.
5. Спрощення
платіжної матриці.
1. Антагоністичні ігри або ігри з нульовою сумою.
Математичне
визначення поняття антагоністичності
означає рівність за величиною і протилежність за знаком функцій виграшу
гравців.
Антагоністичні ігри – це гри з
двома гравцями, які мають прямо протилежні інтереси.
Прикладами таких ігор є деякі (але не всі)
військові операції, спортивні і салонні ігри, а в економіці – прийняття ділових
рішень в умовах конкуренції.
В
антагоністичних іграх, за визначенням, неможливі будь-які переговори і угоди між
гравцями. Дійсно, якщо в результаті будь-яких переговорів або домовленостей
один із гравців зумів би збільшити свій виграш на деяку величину, то виграш
іншого гравця зменшився б на таку ж величину, тобто для нього такі домовленості
були б невигідними.
Сума виграшів
обох гравців в антагоністичних іграх стала в будь-якій ситуації і зазвичай
можна вважати, що вона рівна НУЛЮ.
Тому антагоністичні ігри також називають іграми двох осіб з нульовою сумою (іноді
– нульовими іграми).
Гра з нульовою сумою – це гра, в
якій виграш одного гравця дорівнює програшу іншого гравця.
2. Матричні ігри. Матрична парна гра. Платіжна функція
гри.
Розглянемо
антагоністичну парну скінченну матричну гру з нульовою сумою, в якій два гравці
А
і В.
Інтереси гравців А і В прямо протилежні: один гравець виграє те, що програє другий.
Такий підхід дозволяє вказувати тільки виграш одного гравця.
Домовимося,
що гравець А прагне збільшити свій виграш, а гравець В – зменшити свій
програш.
Нехай гравець А
має m
стратегій (A1,А2,...,Аm), а гравець В
має
n стратегій (В1,В2,...,Bn).
В результаті
застосування гравцем А стратегії Аi і гравцем В стратегії Вj однозначно визначається результат гри – це сума, яку виграє гравець А
і програє гравець В.
Гру вважають
заданою, якщо відомі всі значення aij,
які записують у вигляді матриці, яку називають платіжною матрицею, і яку представлено в табл. 1. Це матрична гра,
яка має розмірність mxn.
Таблиця
1. Платіжна матриця гри розмірності mxn
|
В1 |
В2 |
… |
Вn |
А1 |
а11 |
а12 |
… |
а1n |
А2 |
a21 |
a22 |
… |
a2n |
… |
… |
… |
… |
… |
Аm |
am1 |
am2 |
… |
amn |
Рядки таблиці відповідають стратегія гравця А,
а стовпчики – стратегіям гравця В.
Платіжну матрицю гри також
можна представити у вигляді матриці:
а11 |
а12 |
… |
а1n |
a21 |
a22 |
… |
a2n |
… |
… |
… |
… |
am1 |
am2 |
… |
amn |
Платіжна матриця – це табличний запис функції виграшу
матричної гри.
Партія в
матричній грі реалізується так: гравець А вибирає один з рядків платіжної
матриці (одну зі своїх стратегій). Гравець В, не знаючи вибору гравця А,
вибирає один зі стовпчиків платіжної матриці (одну зі своїх стратегій). Елемент
матиці, який стоїть
на перетині вибраних рядка
і стовпця, визначає водночас виграш гравця А і програш гравця В.
Ціль гравців полягає у виборі таких стратегій, при застосуванні
яких гравець А має максимальний виграш, а гравець В мінімальний програш.
В теорії ігор
виходять з того, що кожний гравець вважає свого пробника розумним (раціональним) і таким, що прагне завадити йому отримати найкращий результат.
Гра називається зведеною до нормальної форми, якщо вона записана у
вигляді матриці. Будь-яка скінченна гра може бути зведена до нормальної форми.
Щоб розв'язати гру, потрібно вказати оптимальні стратегії для кожного гравця.
3. Принцип мінімаксу (максиміну). Нижня ціна гри.
Верхня ціна гри. Мінімаксна та максимінна стратегії.
Визначимо найкращу стратегію
гравця А з урахуванням всіх можливих відповідей на неї гравця В.
При цьому слід розраховувати на те, що на будь-яку стратегію Аі гравця А гравець В
відповість стратегією Вj, для якої виграш гравця А
виявиться мінімальним, оскільки гравець В прямує зашкодити гравцю А.
Алгоритм знаходження максиміну (мінімаксу):
Крок 1.
В рядку
платіжної матриці, що відповідає стратегії Аi, знайти мінімальне з чисел aij:
αi = min aij
j=1,n
j
Це гарантований
виграш гравця А при застосуванні стратегії Аi. Причому найменший з виграшів.
Очевидно, що
гравцю А вигідно вибрати таку стратегію Аi, для якої значення гарантованого виграшу було б найбільшим.
Крок 2.
Серед всіх чисел
αi вибрати найбільше число α
α = max
αi = max min aij j=1,n
i=1,m.
i i j
яке називається НИЖНЬОЮ ціною гри або максиміном Vнц.
Максимін – це максимальний виграш, який гравець А
може собі гарантувати у грі проти розумного (раціонального) противника.
Якщо гравець А
буде дотримуватись максимінної стратегії, то йому для будь-якої розумної
(раціональної) поведінки гравця В гарантовано виграш, не менший ніж α.
Стратегія, яка відповідає максиміну, називається максимінною.
Крок 3.
В стовпчику
платіжної матриці, що відповідає стратегії Вj, знайти макс. з чисел aij:
βj = max aij
i=1,m.
i
Це гарантований
програш гравця В при застосуванні стратегії Вj. Причому найгірший з програшів.
Очевидно, що
гравець В намагатиметься мінімізувати виграш гравця А,
тобто він буде вибирати стратегію, яка дає йому найменший програш.
Крок 4.
Серед всіх чисел
βj вибрати найменше число β
β = min
βj = min max aij j=1,n
i=1,m.
j j i
яке називається ВЕРХНЬОЮ ціною гри або мінімаксом Vвц.
Мінімакс – це мінімальний програш, який гравець В може собі дозволити у грі проти
розумного (раціонального) противника.
Якщо гравець А
буде дотримуватись найбільш обережної з усіх стратегій – мінімаксної - то йому
в будь-якому випадку забезпечено програш, не більший ніж β.
Стратегія, яка відповідає мінімаксу, називається мінімаксною.
Принцип мінімаксу. В теорії ігор принцип обережності, який рекомендує
гравцям дотримання максимінної і мінімаксної стратегій, називається принцип
мінімаксу. Він випливає з припущення про обережність гравців, тобто з бажання
розв'язати конфліктну ситуацію найкращим чином для всіх учасників конфлікту.
4. Сідлова точка. Ціна гри.
Якщо
верхня і нижня ціни гри співпадають, то загальне значення Vнц = Vвц = V називається чистою ціною гри або ціною гри, а така гра називається грою з сідловою точкою.
Ціна гри V дорівнює елементу платіжної
матриці (aij).
Елемент (aij) є одночасно мінімальним у рядку i платіжної
матриці, максимальним в стовпці j платіжної матриці і називається сідловою точкою.
5. Спрощення платіжної матриці.
Правила спрощення (скорочення розмірності) платіжної матриці:
- виключення однакових рядків
чи стовпчиків – якщо в платіжній матриці є дублюючі стратегії, тобто однакові рядки (стовпчики), то всі однакові (крім одного) рядки (стовпчики) викреслюються;
- виключення більших стовпчиків – викреслюються стовпчики, всі елементи яких не менше відповідних елементів будь-якого іншого стовпчика, тобто
позбавляємось стовпчиків, які відповідають стратегіям другого гравця, які
заздалегідь дають не менші програші при будь-якій відповіді першого гравця, ніж
будь-яка інша стратегія;
- виключення менших рядків – викреслюються рядки, всі
елементи яких не перевищують відповідних
елементів будь-якого іншого рядка, тобто позбавляємось рядків, які відповідають
стратегіям першого гравця, які заздалегідь дають не більші виграші при
будь-якій відповіді другого гравця, ніж будь-яка інша стратегія.