Ігрові методи

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

Результат чи результат гри, навіть у тому випадку, коли він не має прямої кількісної оцінки, звичайно характеризується деяким числом, наприклад, виграш +1, програш —1, нічия — 0. Гра може бути парної чи множинний (з багатьма учасниками). Найбільше повно розроблена теорія парних ігор з нульовою сумою, тобто таких ігор, при яких одна сторона виграє те, що програє інша.

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

Стратегією гравця називається сукупність правил, по яких він аналізує ситуацію і робить ходи від початку гри доїїзавершення.

Завдання пари стратегій (А, В) (своєї і супротивника) у парній грі цілком визначає її результат, тобто виграш одного і програш іншого. Гра називається кінцевої, якщо в кожного гравця мається лише кінцеве число стратегій. Результати кінцевої парної з нульовою сумою гри можна задавати матрицею, рядка і стовпці якої відповідають різним стратегіям, а її елементи — відповідні виграші однієї сторони (рівні програшам іншої). Ця матриця називається платіжною матрицею чи матрицею гри. При цьому зручно програш першої сторони ; розглядати як її негативний виграш, а виграш другий – як її негативний програш. Якщо перша сторона має т стратегій, а друга – п, те говорять, що ми маємо справу з грою т´п. Розглянемо гру від т´п з наступною матрицею.

Якщо перший гравець застосовує стратегію А_і, то другий гравець буде прагнути до того, щоб вибором відповідної стратегії звести виграш першого гравця до мінімуму. Величина цього мінімуму, що ми позначимо через a_і, дорівнює, мабуть, min a_іj.

З погляду першого гравця (при будь-яких відповідях супротивника) доцільно прагнути знайти таку стратегію, при якій а, звертається в максимум. Цей максимум, що ми позначимо a_і, називається нижньою ціною гри. Оскільки значення а обчислюється по формулі

,

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

Аналогічним образом визначається мінімальний програш (який може бути в дійсності і виграшем) для другого гравця:

Величина b називається верхньою ціною чи гри мінімаксом, Їй відповідає мінімаксна стратегія другого гравця.

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

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

Величина виграшу (бути може, негативного) першого гравця при користуванні парою оптимальних стратегій називається ціною гри і позначається в. Ціна гри укладена між нижньою і верхньою ціною гри: a £ g £ b.. Стратегії, що змішуються для одержання оптимальної стратегії, будемо називати корисними.

Вирішити гру – значить знайти пари оптимальних стратегій і ціну гри. Рішення гри володіє однією важливою властивістю:

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

При цьому, щоправда, як і при будь-яких відступах від оптимальної стратегії, що відповідає зміна стратегії супротивником може привести до збільшення його середнього виграшу. Доведено, що в гри т´п число корисних стратегій з кожної сторони не перевершує мінімального з чисел т і п.

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

Нехай, наприклад, мається гра 3 ´ 3 з наступною матрицею:

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

Значить третя стратегія свідомо не може бути корисної, і неї варто виключити з розгляду. У матриці, що залишилася, 2´3 всі елементи третього стовпця більше, ніж відповідні елементи першого стовпця. Отже, якщо другий гравець застосовує третю стратегію, то виграш його супротивника (тобто його власний програш) більше, ніж при застосуванні першої стратегії. Тому при пошуку рішення стратегія В₃ повинна бути свідомо виключена з розгляду.

Таким чином, у результаті виключення свідомо марних стратегій гра 3´3 звелася до гри 2´2 з матрицею:

Наступним кроком у пошуку рішення знаходимо нижню і верхню ціну гри:

; .

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

У нашому випадку a ¹ b, і, отже, рішення потрібно шукати серед змішаних стратегій. Розглянемо інший приклад. Нехай гра 2´3 задана матрицею:

Знаходимо нижню і верхню ціну гри:

;

У цьому випадку a = b = 1. Оскільки a £ g £ b, те ціна гри також дорівнює 1. Рішення ж гри задається парою чистих стратегій (А₂, В₃) або максимін (він же мінімакс) розташований у другому рядку і третьому стовпці.

В області чистих стратегій рішення може бути отримане безпосередньо. Якщо ж рішення потрібно шукати в області змішаних стратегій (при a ¹ b), то в загальному випадку т´п матриці ïï a_ij ïï застосовується наступний прийом. Вважаючи всі т стратегією першого гравця корисними, визначимо імовірності їхнього застосування в змішаній оптимальній стратегії (якщо якась стратегія в дійсності марна, те відповідна імовірність звернеться в нуль). Позначимо ці імовірності р₁, р₂,…р_m ціну гри (поки невідому) – g.

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

,

,

………………………………………

Введемо нові невідомі

; ;…;

Щоб виключити можливість розподілу на нуль, можна завжди домогтися g > 0. Для цієї мети досить до всіх елементів матриці ïï a_ij ïï додати те саме позитивне число С і всі її елементи зробити позитивними. Легко зрозуміти, що ця операція збільшує ціну гри на C, але не змінює шуканих оптимальних стратегій.

Оскільки , то .

Розділивши ліві і праві частини нерівностей наg, одержимо нову систему нерівностей:

,

,

………………………………………

.

При зроблених припущеннях усі х_і ненегативні. Оскільки ціль оптимальної стратегії – максимізація виграшу, то при її досягненні лінійна функція

.

повинна звернутися в мінімум. Отже,оптимальна стратегія першого гравця (тобто набір ймовірностейр_і = gх_і)знаходиться в результаті мінімізації функції

при ненегативних х_і, що задовольняють системі нерівностей(41). Це є звичайна задача лінійного програмування, що може бути вирішена методами, описаними в параграфі 2 дійсної глави. У результаті її рішення знаходиться не тільки оптимальна стратегія першого гравця, але і ціна гри g.

Знаючи ціну гри, оптимальну стратегію (а₁, а₂,… а_n) другого гравця звичайно можна знаходити вже без рішення задачі лінійного програмування. Для цього вибирається п – 1 корисних стратегій першого гравця (маючи можливість змінювати місцями гравців, можна вважати, що т > п) і для кожної з них записується середній виграш, що при цьому повинний бути обов'язково дорівнює ціні гри g. Наприклад, якщо для першого гравця корисна стратегія А_і, те їй відповідає рівняння:

.

Крім того, мається ще одне рівняння

Усього маємо п рівнянь для п величин q₁, q₂,… q_n.

Для ігор 2´2 оптимальна стратегія обох гравців може бути отримана без рішення задачі лінійного програмування. При a = b це очевидно, оскільки рішенням є чисті стратегії. При a ¹ b (3 обидві стратегії першого гравця й обидві стратегії другого обов'язково будуть корисними (інакше існувало би рішення в чистих стратегіях). Тому нерівності (40) перетворюються в цьому випадку в рівності:

;

.

Оскільки р₁ + р₂.= 1, то мається достатнє число рівнянь для визначення значень усіх трьох невідомих р₁, р₂, g. Застосуємо цей прийом для рішення першого з прикладів, що розглядувались вище з матрицею . Рівняння запишемо у виді: р₁ = g; 2р₂ = g . Приєднуючи до них рівняння р₁ + р₂.= 1, одержуємо рішення:

; ; .

Отже, при випадковому чергуванні першої і другий стратегії з відносними частотами і відповідно першому гравцю забезпечений середній виграш у розмірі . Помітимо, що

цей висновок йде врозріз з інтуїцією, що підказує більш часто використовувати другу стратегію, оскільки вона має багатообіцяючий рядок виграшів: (0,2) у порівнянні з (1,0) у першій стратегії.

Для перебування оптимальної стратегії другого гравця досить (оскільки уже відома ціна гри) скласти рівняння для його середнього програшу при кожній із двох корисних стратегій першого гравця, наприклад, стратегії А₁. Величина середнього програшу (рівна ціні гри) представиться при цьому у виді . Дорівнюючиїї ціні гри одержуємо , отже, . Отже, другий гравець повинний змішувати стратегії В₁ і В₂ з частотами і , відповідно.

Описаний метод простого рішення ігри можебути узагальненийтакож на ігри 2 ´ п.

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

Розглянемо один з найпростіших прикладів. Мається ділянка землі і дві стратегії його використання. Перша стратегія А₁ полягає в тому, щоб засівати ділянка ярицею, а друга А₂ – озимої (з можливим пересіванням навесні). У природи також мається дві стратегії В₁ і В₂: перша, коли сильні морози настають після випадання снігу, а друга – до випадання (що приводить до загибелі озимих). У цій грі ціною буде грошовий доход, отриманий від реалізації врожаю (у тис. карбованців).

Задамо деяку матрицю гри (зрозуміло, на практиці вона повинна бути визначена з досвіду):

Визначимо нижню і верхню ціни гри:

;

Тому що a ¹ b, те оптимальної буде змішана стратегія. Рівняння для нашого випадку дають:

;

.

Разом з рівнянням р₁ +р₂ = g приводить до рішення:

, ; .

Оптимальна стратегія другої сторони

;

Звідки

; .

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

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

Припустимо, що ця реальна (змішана) стратегія задається ймовірностями q₁ = 0.9; q₂ = 0.1 (які можуть бути визначені з довголітніх спостережень), причому в чергуванні «поганих» і «гарних» зим немає ніякої іншої закономірності, крім цих ймовірностей. Завдання полягає в тім, щоб виробити оптимальну стратегію нашого поводження (імовірності р₁ і р₂) для забезпечення максимального середнього виграшу в цих умовах.