ЛЕКЦІЯ 7 «Теорія ігр та ігрове моделювання»

Анотація

Основні поняття теорії ігор. Оптимальний розв’язок в іграх двох осіб з нульовою сумою. Змішані стратегії. Графічний метод розв’язку ігор виду 2 × m і n × 2. Iтеративний метод Брауна-Робiнсон. Зведення задач теорії ігор до задач лінійного програмування.

 

7. 1 Основні поняття теорії ігор

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

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

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

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

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

Метою теорії гри є визначення оптимальної стратегії для кожного гравця.

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

В основу класифікації ігор покладено такі ознаки: кількість гравців, кількість стратегій, характер взаємовідносин, характер виграшів, вигляд виграшів, кількість ходів, стан інформації (табл. 7.1).

Залежно від кількості гравців існують ігри: одного гравця, двох гравців, k-гравців. Гра називається парною, якщо в ній приймають участь тільки дві сторони (дві особи). Щодо кількості стратегій ігри діляться на скінченні та нескінченні. Якщо в грі кожен із гравців має скінченне число стратегій, то вона називається скінченною. Якщо ж хоч би один із гравців має нескінченну кількість можливих стратегій, то така гра буде називатися нескінченною. За характером взаємовідносин гравців ігри поділяються на безкоаліційні, кооперативні та коаліційні. Безкоаліційними називають ігри, в яких гравці не мають права домовлятися між собою, тобто утворювати коаліції. У кооперативній грі коаліції наперед відомі.

Таблиця 7.1 – Класифікація ігор

 

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

Залежно від виду функції виграшів ігри діляться на матричні, біматричні, неперервні, випуклі, сепарабельні, типу дуелі тощо.

Відносно кількості ходів ігри поділяють на однокрокові й багатокрокові. Однокрокові ігри закінчуються після закінчення одного ходу кожного гравця. Багатокрокові ігри поділяються на позиційні, стохастичні, диференціальні, типу дуелі тощо.

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

7. 2 Оптимальний розв’язок в іграх двох осіб з нульовою сумою

Розглянемо гру, в якій беруть участь два гравці, один з яких може дотримуватися стратегії і з n своїх можливих стратегій (і=1, 2,…, n), а другий, не знаючи вибору першого, вибирає стратегію j із m своїх можливих стратегій (j =1, 2, …, m).У результаті перший гравець (A) виграє a_ij, а другий (B) програє цю величину.

Величини a_ij утворюють платіжну матрицю (матрицю гри):

 

(7.1)

 

Рядки матриці [ a_ij ] відповідають стратегіям (А₁, …, А_n) гравця А. А стовпці – стратегіям (В₁, …, В_m) гравця B. Дані стратегії називаються чистими. Будемо вважати, що при a_ij > 0 гравець А виграє, а гравець B програє величину a_ij. Якщо a_ij < 0, то навпаки, виграє гравець B_і програє гравець А.

Спочатку знайдемо найкращу із стратегій гравця А, тобто найкращу серед А₁, …, А_n з урахуванням можливих варіантів відповідей на неї гравця B. При цьому необхідно враховувати те, що на довільну стратегію А_і гравець B відповідає стратегією В_j, для якої виграш гравця А буде мінімальним. Для знаходження стратегії В_j необхідно в і -му рядку платіжної матриці знайти . При зміні стратегії гравця А одночасно будуть змінюватися відповідні їм числа α_і. Зрозуміло, що гравцеві А вигідно завжди зупинятися на такій стратегії А_і, для якої значення , або, враховуючи представлення α_і, отримаємо .

Число α називається нижньою ціною гри чимаксиміном,а відповідна йому стратегія (рядок) – максимінною.

Якщо гравець А буде дотримуватися максимінної стратегії, то йому, при довільній поведінці гравця В, у будь-якому випадку гарантований виграш, не менший α. Аналогічно можна визначити найкращу стратегію для гравця В, мета якого – привести виграш гравця А до мінімуму. Для цього гравець В прагне для кожної своєї стратегії B_j отримати максимальне значення виграшу при довільній стратегії гравця А_і, тобто він шукає значення . Проте гравець В не може розраховувати на те, що гравець А дозволить йому отримати будь-який із виграшів β_j. Єдине, на що може розраховувати гравець В, то це на те, щоб отримати виграш, який буде не меншим величини . Величина β називається верхньою ціною гри, чи мінімаксом, а відповідна йому стратегія гравця (стовпець) мінімаксною. Мінімакснастратегія – найобережніша стратегія для гравця В. Вона забезпечує йому в будь-якому випадку програш, не більший β, і відповідно виграш гравцеві А, теж не більший від β. Якщо α = β = v, то число v називається ціною гри.

Гра, для якої α = β, тобто мінімаксне значення рівне максимінному, називається грою із сідловою точкою. Для гри зі сідловою точкою розв’язок полягає у виборі максиміної й мінімаксної стратегії, що є оптимальними. “Оптимальність” тут означає, що жоден гравець не прагне змінити свою стратегію, оскільки його суперник може відповісти на це вибором іншої стратегії, яка може дати гірший результат для першого. Взагалі значення гри повинно задовільняти нерівність:

[Максиміннезначення]≤ [Значеннягри]≤ [Мінімаксне значення]

Приклад 7.1. Підприємства А та В виробляють два конкуруючих види продукції. У даний час кожний вид продукції “контролює” 50% ринку. Для покращення якості продукції підприємства планують розгорнути рекламні заходи. Якщо обидва підприємства не будуть цього робити, то стан ринку не зміниться. Обстеження ринку показує, що 50% потенційних покупців отримують інформацію через телебачення, 30% - через пресу й останні 20% - через радіомовлення.

Мета кожного підприємства – вибрати ефективні засоби реклами. Дану задачу необхідно сформулювати як гру двох осіб з нульовою сумою та знайти оптимальні стратегії.

Розв’язання. Учасниками гри є два підприємства А і В. Кожен із гравців має три стратегії використання реклами – телебачення (1), преса (2) й радіомовлення (3). Якщо обидва гравці виберуть для реклами своєї продукції однакові засоби інформації, то їхній вплив на ринок не зміниться. Припустимо, що якщо підприємство А вибрало як засіб реклами телебачення (А₁), то підприємство В може вибрати для рекламителебачення (В₁), пресу (В₂), чи радіомовлення (В₃). У результаті такого вибору вплив на ринок для А в першому випадку не зміниться, в другому й третьому відповідно збільшиться на 20% і 30%. Якщо підприємство А вибере за стратегію рекламу через пресу (А₂), то В може вибрати телебачення (В₁), пресу (В₂), чи радіомовлення. Тоді в першому випадку підприємство А втратить 20% споживачів, у третьому – попитзростена 10%. Аналогічно аналізуємо третю стратегію. Остаточно отримуємо платіжну матрицю :

 

 

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

 

Оскільки α =β = 0, то гра має сідлову точку. Оптимальними будуть стратегії А₁ для підприємства А і В₁ для В, тобто обом підприємствам слід використати для реклами телебачення, як засіб інформації.

7. 3 Змішані стратегії

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

Змішані стратегії – це математична модель можливої й гнучкої тактики гравця, при якій супротивний йому гравець не може знати наперед ситуацію, з якою йому прийдеться зіткнутись у грі, тому перед кожною партією проводиться випадковий вибір однієї з чистих стратегій з допомогою деякого механізму, який здійснює цей вибір із визначеними й наперед заданими ймовірностями. Розглянемо гру двох осіб, матриця платежів якої має розмірність n×m. Нехай гравець А має n стратегій, а гравець В – m стратегій. Позначимо через р = (р₁,р₂,…, р_n) і q = (q₁, q₂,…,q_m) вектори ймовірностей, з якими гравці А та В відповідно вибирають свої чисті стратегії. Оскільки ці стратегії за умовою гри повністю вичерпують можливі ходи гравців А і В, то вони утворюють повну групу подій.

Тому має місце:

 

(7.2)

 

Якщо a_ij – (i, j)-й елемент матриці гри, то платіжна матриця має вигляд

Відповідно до основної теореми теорії ігор кожна скінченна гра має хоч би один розв’язок, який визначає певна змішана стратегія.

 

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

 

, (7.3)

 

а гравець В вибирає стратегію В_j, яка дає

 

. (7.4)

 

Ці величини визначаються відповідно як сподівані максимінні та мінімаксні платежі. Прицьому має місце співвідношення:

 

.

 

Якщо р_i і q_j відповідають оптимальним розв’язкам, тобто виконується строга рівність, то результуюче значення дорівнює сподіваному (оптимальному) значенню гри. Якщо p_i^* i q_j^* оптимальні розв’язки для обох гравців, то кожному елементу платіжної матриці відповідає ймовірність p_i^*q_j^*. Отже, оптимальне сподіване значення (ціна) гри, або математичне сподівання плати гравця А гравцеві В (середній виграш гравця В) знаходиться за формулою:

 

(7.5)

 

Для знаходження оптимальних стратегій в іграх двох осіб з нульовою сумою можна використати графічний метод (для ігор виду 2 × m або 2 × n), а також привести задачу до лінійного програмування.

 

7.4 Графічний метод розв’язку ігор виду 2 × m і n × 2

Розглянемо гру виду 2 × m, яка не має сідлової точки.

 

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

 

. (7.6)

 

Отримані результати представимо у вигляді табл. 7.2.

 

Таблиця. 7.2 – Стратегії гравців А та В

 

Із таблиці 7.2. випливає, що сподіваний виграш гравця А M_j(p₁) лінійно залежить від р₁ і являє собою пряму лінію.

Мета гравця В полягає в мінімізації виграшу гравця А за рахунок вибору своїх стратегій, тобто . На рис. 7.1 точка М^* означає значення M(p₁^*), яке дістали при p₁ = p₁^*. Ціна гри v=M(p₁^*). Таким чином, графічно визначається оптимальна змішана стратегія p₁ = p₁^* першого гравця і пара частих стратегій другого гравця, які в перетині утворюють точку М^* (на рис. 7.1 це відповідає ІІ і ІІІ стратегіям гравця В).

Розв’язавши систему рівнянь M_j(p₁) = v(j = 2, 3), знайдемо точне значення p₁^*. і v. Після цього, надавши q_j = 0 для тих j, для яких М_j(р₁) не утворюють точку М^*, можемо знайти значення q_j для тих j, для яких М_j(р₁) утворюють точку М^*, розв’язавши систему

 

. (7.7)

Рисунок 7.1 – Графічне визначення оптимальної змішаної стратегії p₁ = p₁^* першого гравця і пара частих стратегій другого гравця

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

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

.

За допомогою графічного методу знайти оптимальні стратегії по організації випуску продукції підприємством.

Розв’язання. Побудована гра не має сідлової точки в чистих стратегіях, тому для визначення оптимальних стратегій можна скористатися графічним методом. Стратегіями підприємства є виробництво продукції першого або другого виду. Будемо вважати підприємство першим гравцем, а природу – другим. Позначимо через р₁ імовірність використання своєї першої стратегії першим гравцем, через q(q₁, q₂, …, q₆) – змішану стратегію другого гравця. Побудуємо графіки середніх виграшів першого гравця (рис. 7.2.), для цього знайдемо M_j(p₁):

Рисунок 7.2 – Графіки середніх виграшів першого гравця

 

 

Нижня границя множини обмежень зображена на рис. 7.2 жирною лінією. Як бачимо, maxM(p1) досягається в точці М^*, що утворюється лініями М₁(р₁) і М₄(р₁). Покладемо q₂ = q ₃= q₅ = q₆ = 0. Для знаходження p₁, p₂, q₁, q₄, v необхідно розв’язати такі системи рівнянь:

Розв’язками цих систем буде:

 

Ми отримали такий оптимальний розв’язок.

Підприємству необхідно 5/12 обсягів сировини використати на виготовлення першого виду продукції, а 7/12 – для другого виду продукції. При цьому отримаємо максимальний прибуток у розмірі 6.75 млн. грн.

 

7.5 Iтеративний метод Брауна-Робiнсон

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

Розглянемо ітеративний метод, запропонований Брауном i обґрунтований Робiнсон (метод Брауна-Робiнсон).

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

У першій партії гравці P1, P2 вибирають довільно свої чисті стратегії, відповідно, i₁ та j₁. Формується m -вимiрний вектор x ¹ = (0,.., 0, 1, 0,..., 0), в якому 1 міститься на i₁ -у місці i який характеризує частоти вибору гравцем P1 своїх чистих стратегій, та n -вимiрний вектор y ¹ = (0,..., 0, 1, 0,..., 0)', де 1 розміщена на j₁ -у місці i який характеризує частоти вибору чистих стратегій гравцем P2. Нехай після s партiй маємо х^s = (x₁ , …, x_j^s, …, x_m^s) та y^s = (y₁^s, …, y_j^s, …, y_n^s) ' – вектори частот вибору чистих стратегій гравцями P1 та P2 відповідно.

Визначаючи свій вибір i_s+1 у (s+1) -й партії, гравець P1 підраховує свій середній програш

7.6 Зведення задач теорії ігор до задач лінійного програмування

Розглянемо матричну гру n× m, задану матрицею [ a_ij ].

Позначимо через p^* = (p₁^*, p₂^*,..., p_n^*), q^* =(q₁^*, q₂^*,..., q^*_m) імовірності оптимальних змішаних стратегій відповідно першого та другого гравців, а через v - ціну гри. Без доведення сформулюємо теорему.

Теорема. Для того, щоб число v було ціною гри, а p^* і q^* - векторам иймовірностей оптимальних стратегій, необхідне й достатнє виконання системи нерівностей:

(7.8-7.9)

 

Для простоти припустимо, що v > 0. Цього завжди можна досягнути завдяки додаванню до всіх елементів матриці [ a_ij ] одного й того ж постійного числа k. Така процедура не вплине на оптимальні стратегії, а тільки збільшить ціну гри на k.

Мета першого гравця полягає в отриманні максимального виграшу, а другого – мінімального програшу. Користуючись сформульованою теоремою, задачу максимізації гарантованого виграшу першого гравця і задачу мінімізації гарантованого програшу другого гравця можна представити як пару взаємнодвоїстих задач лінійного програмування:

Завдання І гравця

(7.10)

Завдання ІІ гравця

(7.11)

 

Запишемо систему обмежень (7.10) у розширеній формі:

(7.12)

 

Поділимо праву й ліву частину нерівності на v. Отримуємо:

(7.13)

 

Зробимо заміну: . Маємо:

(7.14)

 

Відомо, що . Отже, . Звідси: .

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

Знайти Z = x₁ + x₂ +...+ x_n → min при виконанні умов

 

(7.15)

Аналогічні міркування можна провести відносно задачі другого гравця. Виконавши заміну , отримаємо наступну задачу:

Знайти F = y₁ + y₂ +...+ y_m → max при виконанні умов

 

(7.16)

 

Задача другого гравця є двоїстою до задачі першого гравця.

Процес знаходження розв’язку гри з використанням лінійного програмування складається з таких етапів:

І – побудова пари двоїстих задач лінійного програмування, еквівалентних даній матричній грі;

ІІ – знаходження оптимальних планів пари двоїстих задач;

ІІІ – знаходження розв’язку гри, використовуючи співвідношення між планами двоїстих задач і оптимальними стратегіями та ціною гри.

Приклад 7.3. Дві фірми можуть вкласти свій наявний капітал у будівництво п’яти об’єктів. Стратегія фірм: і -та стратегія полягає у фінансуванні і -го об’єкту (і = 1, 2, …,5). Враховуючи особливості вкладів й інші умови, прибуток фірми виражається за допомогою матриці А:

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

Розв’язання. Для зведення даної задачі до задачі лінійного програмування необхідно, насамперед, до кожного елементу матриці додати число k = 4 (необхідно, щоб усі елементи матриці А були додатніми). Отримуємо:

Вводимо невідомі величини х₁, х₂, …, х₅. Тоді отримуємо таку задачу лінійного програмування:

Знайти Z = x₁ + x₂ + x₃ + x₄ + x₅ → min

при виконанні умов

Розв’язком цієї задачі буде

x₁ = 0; x₂ =0; x₃ = 0.125; x₄ = 0; x₅ = 0.125.

Оскільки х₁ + х₂ + х₃ + х₄ + х₅ =1/v, то

Знаючи те, що х_i = p_i/v, отримуємо: p_i = x_i⋅ v; р₁ = 0; р₂ = 0;р₃ = 0.5; р₄ = 0; р₅ = 0.5.

Побудуємо до даної задачі двоїсту. За невідомі візьмемо y₁, y₂, y₃,:y₄, y₅. Маємо

при виконанні умов

Розв’язком цієї задачі буде

y₁ = 0; y₂ = 0,25; y₃ = 0;:y₄ = 0; y₅ = 0. Користуючись формулою y_i = q_i / v, знайдемо:

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

р = (0; 0; 0.5; 0; 0.5); q = (0; 1; 0; 0; 0), а ціна початкової гри v^* =v – 4=0.