 |
Матрична гра з нульовою сумою
|
|
|
|
Найповніше розроблені методи розв’язування скінченої парної гри з нульовою сумою, яку й розглянемо далі. Такі ігри описують найпростіші конфліктні ситуації і теоретично більш розроблені.
Гру називають грою з нульовою сумою, якщо одна із сторін виграє все те, що програє інша, тобто сума виграшу сторін
,
де 
– дії сторін, які називають стратегіями.
Таким чином, така гра є замкненою системою, оскільки виграш однієї сторони відбувається повністю за рахунок програшу іншої.
Величина 
– це результат гри для вибраної 
-пари стратегій, яку називають наслідком гри. Ця величина показує ступінь виграшу першої сторони та програшу іншої, коли зроблено і -й хід та дано 
-ту відповідь супротивника.
Якщо стратегії 
та 
вибирають однозначно з ймовірністю, яка дорівнює одиниці, то такі стратегії називають чистими.
Розглянемо парну гру з нульовою сумою.
Нехай маємо т стратегій 
першої сторони та п стратегій 
другої сторони гри. Кожна пара стратегій (по одній з кожної сторони) та відображають конкретну -ту стратегію, яка оцінюється деякою функцією 
.
Усі наслідки гри зобразимо у вигляді платіжної матриці 
, тобто. 
. У цій матриці рядки відображують т стратегій сторони А, колонки – п стратегій сторони В:
| 
| ... | 
| |
|
| |||
| ||||
| ... | ||||
|
Величини 
платіжної матриці можна зобразити або числом, або залежністю у вигляді функції виграшу 
. Якщо 
, то виграє сторона А, якщо 
, то виграє сторона В.
При розв’язуванні матричної гри з нульовою сумою достатньо знати матрицю тільки одного гравця. Для другого гравця виграш відрізняється тільки знаком 
.
Розглянемо простий приклад гри.
Підприємство випускає три види продукції , , 
, попит на які змінюється і може набувати чотири стани , , 
та 
. Згідно з попитом задаються розміри цін одиниці кожного виду продукції у вигляді платіжної матриці :
|
|
|
|
|
|
|
| |
|
| ||||
|
| ||||
|
|
Треба знайти оптимальну поведінку однієї із сторін: при цьому перша сторона – підприємство – максимізує свій виграш, тобто робить спробу продати свій товар найдорожче, друга сторона – покупець – намагається мінімізувати свій програш, тобто купити товар найдешевше.
З отриманої матриці очевидно, що коли є попит , то краще підприємству випускати продукцію і далі 
та 
. 3 іншого боку, коли випускається продукція 
, то найдешевший товар буде при попиті або і т.д.
Розглянемо процес вибору стратегій, коли йдеться про гру з нульовою сумою. Такі задачі розв’язують за принципом мінімаксу.
Формалізація принципу мінімаксу така:
коли вибрано стратегію 
, то друга сторона В намагається зменшити свій програш
,
а тому сторона А з можливих значень 
повинна вибрати максимальне, тобто
.
Ця величина є гарантованим успіхом (виграшем) сторони А для будь-якої відповіді сторони 
її називають максиміном або нижньою межею ціни гри з боку А. Тому 
, де 
– ціна гри.
Отже, коли гравець А дотримується стратегії максиміну, то йому гарантовано успіх не менш ніж величина а.
З боку В, за аналогією, проводимо аналіз усіх 
матриці і знаходимо найбільшу небезпеку від А
,
а потім для її зменшення вибираємо найменшу величину з множини 
:
.
Ця величина вказує на найменші збитки з боку В у разі правильної гри, тобто сторона В не повинна програвати більше ніж 
(обмеження програшу). Цю величину називають мінімаксом або верхньою межею ціни гри з боку А оскільки виграти більше сторона А не може у разі правильної гри з боку В. Таким чином, має місце 
.
Узагалі маємо 
.
Розглянемо процес вибору стратегії з боку А згідно з матрицею прикладу.
|
|
|
Якщо вибрано стратегію , то, цілком зрозуміло, що з іншого боку в особі покупця, найбільш зручний попит відповідає мінімальному програшу 
,
аналогічно для маємо
,
а для
.
Значення 
– це ціни на продукцію, якщо мінімальна ціна регулювалась би попитом. Цілком очевидно, що в разі інших відповідей з боку В виграш сторони А зростає, а з боку В зменшується.
Такий вибір підсумків гри можна записати у вигляді
.
За аналогією маємо
та 
,
.
Існують ігри, в матриці підсумків яких є такий елемент, що одночасно є мінімальним серед максимальних стратегій по колонкам та максимальним серед мінімальних стратегій по рядкам. У цьому разі ситуацію називають рівноважною оскільки вибір цього елемента влаштовує обидві сторони.
Такий елемент називають сідловою точкою матриці, а саму гру – грою із сідловою точкою. Термін „сідлова точка” використовують за аналогією з конфігурацією сідла, яке скривлюється вгору за одним напрямком і вниз – за іншим (рис. 5.2).
Для такої гри 
, де
– елемент 
-ї колонки, 
;
– сідлова точка (точка рівно-ваги); 
– елемент 
- го рядка,
Рис.5.2 
.
Гра із сідловою точкою має єдиний розв’язок, який задовольняє обидві
сторони. Такий розв’язок є оптимальний, а вибрані стратегії згідно з цим розв’язком є чисті. Отже, якщо обидві сторони відповідають правильно, то розв’язок буде єдиним 
, що влаштовує обидві сторони, тобто
.
Наприклад, нехай задано таку матрицю:
 А
| 
|
| 
| 
|
|
| ||||
|
| ||||
|
| -1 |
Максимін для неї
,
а мінімакс
.
Таким чином, 
, тобто існує сідлова точка, яка відповідає стратегіям та (елемент 
). Вибір іншої стратегії призведе до гірших результатів сторони, яка відхилиться від сідлової точки.
Мішані стратегії
Якщо немає сідлової точки 
, то з’являється невизначеність у виборі стратегії з наявної сукупності чистих стратегій. При багаторазовому повторенні гри інтерес відповідає середньому виграшу усієї гри, а не виграш
у кожній її партії. Такий виграш можна знайти при користуванні мішаною стратегією, за допомогою якої знаходять вибір чистих стратегій.
Мішана стратегія – це сукупність імовірностей вибору чистих стратегій, тобто це вектор
|
|
|
,
де 
і 
Наведене випливає з того, що чисті стратегії є несумісними подіями, які складають повну групу елементарних подій. Тому тільки одна подія може бути вибрана при створенні конкретної ситуації в процесі гри.
Мішану стратегію з боку В можна зобразити аналогічно:
,
де 
і 
Зауважимо, що іноді не всі чисті стратегії беруть участь у розв’язуванні задачі. Чисті стратегії, які увійшли в мішану стратегію з відмінними від нуля ймовірностями, називають активними.
Оскільки сума ймовірностей чистих стратегій дорівнює одиниці, то будь-яку чисту стратегію можна вважати мішаною з імовірністю одиниця, а інші чисті стратегії прирівняти до нуля.
При цьому мішана стратегія
,
де 
, тобто четверта чиста стратегія одночасно є мішаною.
Розглянемо таку теорему: якщо одна із сторін дотримується оптимальної стратегії, то її виграш ставить не менше ціни гри незалежно від того, які рішення приймає друга сторона.
Формально ця теорема розуміється так.
Якщо сторона А використовує мішану стратегію
,
то в разі будь-якої відповіді з боку В виграш не повинен бути меншим від значення , тобто
.
Аналогічно для сторони В: якщо використовується мішана стратегія , програш у разі будь-якої відповіді з боку А не повинен перевищувати значення , тобто
.
Таким чином, для знаходження оптимальної мішаної стратегії необхідно та достатньо виконати нерівності всіх співвідношень розглянутої теореми.
Часто при застосуванні мішаних стратегій користуються механізмом випадкових чисел для вибору чистих стратегій.
У складних іграх іноді застосовують засоби, які спрощують ці ігри. Такі засоби дають змогу зменшити розміри матриці (тобто зменшується кількість стратегій):
– виключення дублюючих рядків, якщо вони існують;
– виключення явно невигідних рядків чи колонок порівняно з іншими домінуючими стратегіями.
Рядок вважається невигідною стратегією сторони А, якщо всі його елементи менші за відповідні елементи іншого домінуючого рядка.
Колонка є невигідною стратегією сторони В, якщо всі її елементи перевищують відповідні елементи іншої домінуючої колонки.
|
|
|
Замість заданих чистих стратегій уводяться об’єднані стратегії, які дорівнюють середньозваженим значенням чистих стратегій. При цьому припускається, що об’єднані чисті стратегії чергуються випадково з однаковою ймовірністю.
|
|
|
