«…Гра — не філософія і не релігія,це особлива дисципліна, за своїм характеромвона найближча до мистецтва..» Г. Гессе «Гра в бісер» ТЕОРІЯ ІГОР Теорія ігор вперше була систематично викладена Нейманом і Моргенштерном та оприлюднена лише 1944 року в монографії «Теорія ігор і економічної поведінки», хоча окремі результати були опубліковані ще в 20-х роках. Нейман і Моргенштерн написали оригінальну книгу, яка містила переважно економічні приклади, оскільки економічні задачі простіше за інші описати за допомогою чисел. Під час другої світової війни і одразу після неї теорією ігор серйозно зацікавились військові, які одразу побачили в ній математичний апарат для дослідження стратегічних проблем і підготовки рішень. Потім головна увага знову була звернута до економічних проблем. Нині сфера застосування теорії ігор значно розширилась. Так, у соціальних науках апарат теорії ігор застосовується у психології для аналізу торгових угод та переговорів, а також для вивчення принципів формування коаліцій тощо. 11.1. Основні поняття теорії ігор У попередніх розділах описані такі задачі математичного програмування, де рішення на основі розрахованого оптимального плану приймає лише один суб’єкт, що має чітко визначену мету. Відомо, що будь-яка економічна система не функціонує ізольовано, а на певних етапах своєї діяльності вступає в різні економічні відносини з іншими суб’єктами господарювання. Оптимальний план за наведеними вище математичними моделями визначався, виходячи з інтересів тільки однієї сторони економічних відносин, не враховуючи можливі варіанти дій інших сторін. У даному розділі розглядаються ситуації з кількома учасниками, коли значення цільової функції для кожного учасника залежить не лише від його власної поведінки, але і від дій інших суб’єктів. За умов ринкової економіки все частіше мають місце конфліктні ситуації, коли два або більше колективів (індивідуумів) мають протилежні цілі та інтереси, причому результат дії кожної із сторін залежить і від дії супротивника. Класичним прикладом конфліктної ситуації в економіці є відношення продавець — покупець (монополія — монопсонія). Складніші ситуації виникають, коли в суперечці інтересів беруть участь об’єднання чи коаліції. Зазначимо, що не завжди учасники ігрової ситуації мають протилежні цілі. Наприклад, дві фірми, які надають однакові послуги, можуть об’єднуватися з метою спільного протистояння більшому супернику. Часто однією із сторін конфлікту є природні процеси чи явища, наприклад, погода, тобто маємо гру людини з природою. Погодними умовами людина практично не може керувати, але вона має змогу пристосовуватися до її постійних змін. Безліч подібних ситуацій можна зустріти і в інших сферах людської діяльності: біології, психології, політології тощо. Теорія ігор — це математичний апарат, що розглядає конфліктні ситуації, а також ситуації спільних дій кількох учасників. Завдання теорії ігор полягає у розробленні рекомендацій щодо раціональної поведінки учасників гри. Реальні конфліктні ситуації досить складні і обтяжені великою кількістю несуттєвих чинників, що ускладнює їх аналіз, тому на практиці будують спрощені моделі конфліктних ситуацій, які називають іграми. Характерними рисами математичної моделі ігрової ситуації є наявність, по-перше, кількох учасників, яких називають гравцями, по-друге, опису можливих дій кожної із сторін, що називаються стратегіями, по-третє, визначених результатів дій для кожного гравця, що подаються функціями виграшу. Задачею кожного гравця є знаходження оптимальної стратегії, яка за умови багатократного повторення гри забезпечує даному гравцю максимально можливий середній виграш. Існує дуже багато різних ігор. Прикладом «гри» в буквальному розумінні цього слова, передусім, є спортивна, карточна гра, шахи тощо. Від реальної конфліктної ситуації гра відрізняється не лише спрощеною формою, а також наявністю певних правил, за якими мають діяти її учасники. Дослідження таких формалізованих ігор звичайно не може дати чітких рекомендацій для реальних умов, проте є найзручнішим об’єктом для вивчення конфліктних ситуацій і оцінки можливих рішень з різних поглядів. Розраховані на основі ігрових моделей оптимальні плани не визначають єдино правильне рішення за складних реальних умов, проте слугують математично обґрунтованою підставою для прийняття таких рішень. 11.2. Класифікація ігор Класифікація ігор проводиться відповідно до вибраного критерію. Ігри можуть розрізнятися залежно від кількості гравців, кількості стратегій, властивостей функцій виграшу, можливостей взаємодії між гравцями. Якщо в грі беруть участь два гравці, то така гра називається парною (грою двох осіб). Часто у грі беруть участь багато сторін, тоді гра є множинною. Залежно від кількості стратегій розрізняють скінченні та нескінченні ігри. Якщо кожен гравець має скінченну кількість стратегій, то гра — скінченна, в іншому разі — нескінченна. Якщо виграш одного гравця дорівнює програшу іншого, то маємо гру з нульовою сумою. Такі ігри характеризуються протилежними інтересами сторін, тобто ситуацією конфлікту. Інші ігри — з ненульовою сумою, виникають як за умов конфліктної поведінки гравців, так і за їх узгоджених дій. За можливості поєднання інтересів гравців та домовленості між ними про вибір стратегій можна казати про кооперативну гру, коли ж гравці не мають можливості чи не бажають координувати свої дії, то гра називається некооперативною. 11.3. Матричні ігри двох осіб Найчастіше розглядається гра з двома гравцями, в якій виграш однієї сторони дорівнює програшу іншої, а сума виграшів обох сторін дорівнює нулю, що в теорії ігор називають грою двох осіб з нульовою сумою. Подібна ситуація є типовою у практичній діяльності менеджерів, маркетологів, спеціалістів рекламних служб, які щоденно приймають рішення за умов гострої конкуренції, неповноти інформації тощо. Основною метою розв’язування задач цього класу є розроблення рекомендацій щодо вибору оптимальних стратегій конфліктуючих сторін на основі застосування методичних підходів теорії ігор. Отже, маємо два гравці А і В (гра двох осіб з нульовою сумою). Кожний гравець вибирає одну із можливих стратегій: позначимо стратегії гравця А — стратегії гравця В — . Результати (плата) за всіма можливими варіантами гри задаються спеціальними функціями, які залежать від стратегій гравців, як правило, у вигляді платіжної матриці. Нехай — виграш гравця А; — виграш гравця В. Оскільки гра з нульовою сумою, то Тоді в разі, якщо то Отже, мета гравця А — максимізувати величину , а гравця В — мінімізувати її. Нехай тобто маємо матрицю А:
де рядки відповідають стратегіям Аі, а стовпці — стратегіям Bj. Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці aij — це виграш гравця А, якщо він вибрав стратегію Ai, а гравець В — стратегію Bj. Із багатьох критеріїв, які пропонуються теорією ігор для вибирання раціональних варіантів рішень, найпоширенішим є песимістичний критерій мінімаксу-максиміну. Суть цього критерію у наступному. Нехай гравець А вибрав стратегію Ai, тоді у найгіршому разі він отримає виграш, що дорівнює min aij, тобто навіть тоді, якщо гравець В і знав би стратегію гравця А. Передбачаючи таку можливість, гравець А має вибрати таку стратегію, щоб максимізувати свій мінімальний виграш, тобто
Така стратегія гравця А позначається і має назву максимінної, а величина гарантованого виграшу цього гравця називається нижньою ціною гри. Гравець В, який програє суми у розмірі елементів платіжної матриці, навпаки має вибрати стратегію, що мінімізує його максимально можливий програш за всіма варіантами дій гравця А. Стратегія гравця В позначається через і називається мінімаксною, а величина його програшу — верхньою ціною гри, тобто
Оптимальний розв’язок цієї задачі досягається тоді, коли жодній стороні невигідно змінювати вибрану стратегію, оскільки її супротивник може у відповідь вибрати іншу стратегію, яка забезпечить йому кращий результат. Якщо , тобто, якщо то гра називається цілком визначеною. В такому разі виграш гравця А (програш гравця В) називається значенням гри і дорівнює елементу матриці . Цілком визначені ігри називаються іграми з сідловою точкою, а елемент платіжної матриці, значення якого дорівнює виграшу гравця А (програшу гравця В) і є сідловою точкою. В цій ситуації оптимальним рішенням гри для обох сторін є вибір лише однієї з можливих, так званих чистих стратегій — максимінної для гравця А та мінімаксної для гравця В, тобто якщо один із гравців притримується оптимальної стратегії, то для другого відхилення від його оптимальної стратегії не може бути вигідним. Фірма виготовляє устаткування для хімічної промисловості. Експертами виробничого відділу фірми розглядаються три конструкторські варіанти устаткування: А-1, А-2, А-3. Для спрощення допустимо, що за технічними характеристиками ці три типи майже ідентичні, однак залежно від зовнішнього вигляду та зручності використання кожен тип може мати три модифікації: М-1, М-2, М-3 залежно від закупленої технології виробництва. Собівартість виготовлення устаткування наведена в табл. 11.1: Таблиця 11.1 СОБІВАРТІСТЬ ВИГОТОВЛЕННЯ УСТАТКУВАННЯ, тис. ум. од. Тип устаткування Модифікація
М-1 М-2 М-3
А-1 10 6 5
А-2 8 7 9
А-3 7 5 8
Конфліктна ситуація виникає в зв’язку з необхідністю вибрати той тип устаткування та його модифікації, який буде затверджений економічним відділом фірми. З погляду виробництва найкращим є найдорожчий варіант, оскільки він дає змогу виробляти дорожчу та конкурентоспроможнішу продукцію, тоді як з погляду економічного відділу фірми найкращим є найдешевший варіант, який потребує найменшого відволікання коштів. Завдання експертів полягає в тому, щоб запропонувати на розгляд фінансовому відділу такий тип устаткування, який забезпечить якщо не кращий, то в усякому разі не гірший варіант співвідношення вартості та зовнішнього вигляду. Розв’язання. Якщо виробничий відділ запропонує виготовлення устаткування типу А-1, то економічний відділ настоюватиме на придбанні технології, що дає модифікацію М-3, оскільки цей варіант найдешевший. Якщо зупинитись на устаткуванні виду А-2, то скоріш за все затверджено буде М-2, і нарешті для типу А-3 — також М-2. Очевидно, що з усіх можливих варіантів розвитку подій експертам виробничого відділу необхідно настоювати на варіанті впровадження у виробництво устаткування типу А-2, оскільки це дає найбільше значення за реалізації найгірших умов — 7 тис. ум. од. Наведені міркування ілюструють максимінну стратегію, отже: , , , — нижня ціна гри. Якщо учасник відхилиться від своєї оптимальної (максимінної) стратегії і вибере першу чи третю, то зможе отримати виграш, що дорівнює лише 5. Розглянемо тепер ситуацію з погляду спеціалістів економічного відділу. Виходячи з витрат на виробництво устаткування, вибір технології, що дає змогу виготовляти модифікацію М-1, може призвести до найбільших витрат у тому разі, коли вдасться затвердити випуск устаткування типу А-1. Для технології виготовлення устаткування з модифікацією М-2 найбільші можливі витрати становлять 7 тис. ум. од. — для устаткування А-2, а з модифікацією М-3 — також для А-2. Для економістів найкращим є вибір технології, що забезпечує виготовлення устаткування модифікації другого виду, оскільки за найгірших для них умов вона дає найменші витрати — 7 тис. ум. од. Останні міркування відповідають мінімаксній стратегії, що визначає верхню ціну гри. , , , — верхня ціна гри. Якщо гравець відхилиться від своєї оптимальної (мінімаксної) стратегії, то це призведе до більших втрат. Якщо буде вибрано першу стратегію, то можливий програш дорівнюватиме 10, а якщо буде вибрано третю стратегію, то можливий програш становитиме 9. Наведена гра є парною грою із сідловою точкою. Як правило, задачі теорії ігор, що моделюють реальні ситуації, мають значну розмірність. Тому важливим моментом дослідження платіжної матриці є способи її скорочення. Скоротити матрицю можна, якщо вилучити стратегії, про які наперед відомо, що вони є невигідними або повторюють одна одну. Стратегії, яким відповідають однакові значення платіжної матриці (тобто матриця містить однакові рядки(стовпці)), називаються дублюючими. Якщо всі елементи і-го рядка (стовпця) платіжної матриці перевищують значення елементів j-го рядка (стовпця), то кажуть, що і-та стратегія гравця А (гравця В) є домінуючою над j-ою. Для спрощення розрахунків дублюючі та ті стратегії, для яких існують домінуючі, вилучають з платіжної матриці. Маємо гру гравців А і В, яка задана такою платіжною матрицею: Гравець В Гравець A . Необхідно визначити ціну гри та оптимальні стратегії гравців А і В. Розв’язання. Оптимізацію гри почнемо з визначення домінуючих стратегій для кожної із сторін, а також виключення із дальшого аналізу невигідних і дублюючих стратегій. Визначимо домінуючі стратегії. Перша стратегія гравця А домінує над третьою, оскільки всі значення його виграшів за будь-яких дій противника є не гіршими, ніж за вибору третьої стратегії, тобто всі елементи першого рядка платіжної матриці не менші, ніж відповідні елементи її третього рядка. Тому третя стратегія гірша, ніж перша і може бути виключена із платіжної матриці. Продовжуючи аналіз можливих дій гравця B, легко помітити, що його перша стратегія домінує над п’ятою, яку можна виключити як збитковішу, а тому невигідну для цього гравця. Отже, маємо таку платіжну матрицю:
За вибору гравцем А першої стратегії залежно від дій гравця В він може отримати 6, 3, 8 або 5 одиниць виграшу. Але у будь-якому разі його виграш буде не меншим від тобто незалежно від поведінки гравця В. Якщо розглянути можливі наслідки вибору гравцем А другої стратегії, то, міркуючи аналогічно, з’ясуємо, що його гарантований виграш становитиме Для третьої стратегії маємо: Отже, нижня ціна гри буде дорівнювати: а гравець А для максимізації мінімального виграшу має вибрати другу із трьох можливих стратегій. Ця стратегія є максимінною у даній грі. Гравець В, який намагається мінімізувати свій програш, вибираючи першу стратегію, може програти 6,6 або 4 одиниці. Але за будь-яких варіантів дій гравця А гравець В може програти не більше ніж Для другої стратегії маємо: для третьої — а для четвертої — Отже, верхня ціна гри становитиме: Гравцю В доцільно вибрати також другу стратегію, яка є мінімаксною у грі. Оскільки то ця гра має сідлову точку. Ціна гри дорівнює 5. Оптимальною максимінною стратегією гравця А є друга з трьох можливих стратегій його дій. Для гравця В оптимальною є також друга із чотирьох можливих. З наведеного прикладу зрозуміло, чому мінімаксна та максимінна стратегії мають назву песимістичних. Вибір оптимальної стратегії для кожного з гравців ґрунтується на припущенні, що він буде діяти за найгірших для нього умов. Зрозуміло, що в даному разі вибір такої стратегії може не влаштовувати учасників гри. Нехай гравець А вибрав другу (максимінну) стратегію і притримується її. Допустимо, що гравцеві В став відомим вибір стратегії противника, тоді йому доцільно обрати третю стратегію, за якої виграш становитиме 7 одиниць. У свою чергу гравець А також знає про зміну стратегії гравця В на третю і вибирає першу стратегію, що дає йому змогу отримати виграш у сумі 8 одиниць і т. д. Можливість такого розвитку подій виникає тому, що мінімаксна та максимінна стратегії в даному разі не є стійкими. Тобто обставини, за яких обидва гравці використовують мінімаксну та максимінну стратегії, невигідні гравцям у тому разі, коли один з них змінює свою оптимальну стратегію. Однак така нестійкість властива не всім іграм із сідловою точкою. В деяких випадках сідловій точці відповідають стійкі максимінна та мінімаксна стратегії. В такому разі відхилення від оптимальної стратегії одним з гравців спричиняє таку зміну виграшу, яка є невигідною для цього гравця, оскільки стан або не змінюється, або погіршується. Отже, в загальному випадку не можна стверджувати, що гра з сідловою точкою визначає стійкі оптимальні стратегії. 11.4. Гра зі змішаними стратегіями Скінченні ігри, як правило, не мають сідлової точки. Якщо гра не має сідлової точки, тобто і то максимінно-мінімаксні стратегії не є оптимальними, тобто кожна із сторін може покращити свій результат, вибираючи інший підхід. Оптимальний розв’язок такої гри знаходять шляхом застосування змішаних стратегій, які є певними комбінаціями початкових «чистих» стратегій. Тобто змішана стратегія передбачає використання кількох «чистих» стратегій з різною частотою. Ймовірності (або частоти) вибору кожної стратегії задаються відповідними векторами: для гравця А — вектор де для гравця В — вектор де Очевидно, що . Виявляється, що коли використовуються змішані стратегії, то для кожної скінченної гри можна знайти пару стійких оптимальних стратегій. Існування такого розв’язку визначає теорема, яку наведемо без доведення. Теорема (основна теорема теорії ігор). Кожна скінченна гра має, принаймні, один розв’язок, можливий в області змішаних стратегій. Нехай маємо скінченну матричну гру з платіжною матрицею
Оптимальні змішані стратегії гравців А і В за теоремою визначають вектори і , що дають змогу отримати виграш: . Використання оптимальної змішаної стратегії гравцем А має забезпечувати виграш на рівні, не меншому, ніж ціна гри за умови вибору гравцем В будь-яких стратегій. Математично ця умова записується так: (11.1) З другого боку, використання оптимальної змішаної стратегії гравцем В має забезпечувати за будь-яких стратегій гравця А програш, що не перевищує ціну гри (, тобто: (11.2) Ці співвідношення використовуються для знаходження розв’язку гри. Зауважимо, що в даному разі розраховані оптимальні стратегії завжди є стійкими, тобто якщо один з гравців притримується своєї оптимальної змішаної стратегії, то його виграш залишається незмінним і дорівнює ціні гри ( незалежно від того, яку із можливих змішаних стратегій вибрав інший гравець. З доведенням цього твердження можна ознайомитися в літературі [7, 8]. 11.5. Геометрична інтерпретація гри 2 ( 2 Найпростішим випадком скінченної гри є парна гра, коли у кожного учасника є дві стратегії. Вj Ai B1 B2
A1 a11 a12
A2 a21 a22
Розглянемо випадок, коли гра не має сідлової точки. Отже, . Необхідно знайти змішані стратегії та ціну гри. Позначимо шукані значення ймовірноcтей застосування «чистих» стратегій гравця А через , а для гравця В — через . Згідно з основною теоремою теорії ігор, якщо гравець А притримується своєї оптимальної стратегії, то виграш буде дорівнювати ціні гри. Отже, якщо гравець А притримуватиметься своєї оптимальної стратегії , то: (11.3) Оскільки , то . Підставивши цей вираз у систему рівнянь (11.3), отримаємо: . Розв’язавши дане рівняння відносно невідомого , маємо: , (11.4) тоді: =. (11.5) Провівши аналогічні міркування стосовно гравця В, маємо: (11.6) Оскільки , то . . Розв’язавши це рівняння відносно невідомого , маємо: , (11.7) тоді: . (11.8) Ціну гри ( знаходять, підставлючи значення (або ) в будь-яке з рівнянь (11.3) або (11.6): . (11.9) Знайти розв’язок гри з платіжною матрицею: Вj Ai B1 B2
A1 2 5
A2 4 3
Розв’язання. Переконаємося, що гра не має сідлової точки: , . Отже, ця гра не має сідлової точки. Скористаємося формулами (11.4), (11.5), (11.7), (11.8), (11.9). Маємо: ; ; ; . Ціна гри . Отже, оптимальна стратегія кожного гравця полягає в тому, щоб випадково чергувати свої «чисті» стратегії. Гравець А має використовувати першу стратегію з імовірністю , а другу — з імовірністю , а гравець В — навпаки. За цих умов середній виграш дорівнюватиме 3,5. Розв’язку гри 2 ( 2 можна дати наочну геометричну інтерпретацію. Розглянемо гру з платіжною матрицею виду: Вj Ai B1 B2
A1 a11 a12
A2 a21 a22
Відмітимо на осі абсцис відрізок довжиною, що дорівнює одиниці (рис. 11.1). Лівий кінець відрізка (точка з абсцисою х = 0) буде відповідати стратегії А1, а правий кінець (х = 1) — стратегії А2, всі проміжні точки цього відрізка відповідатимуть змішаним стратегіям гравця А, причому імовірність х1 стратегії А1 буде дорівнювати відстані від точки Р до правого кінця відрізка, а ймовірність х2 стратегії А2 — відстані до лівого кінця відрізка. Проведемо через точки А1 та А2 два перпендикуляри до осі абсцис: вісь І і вісь ІІ. На першій з них відмітимо виграш за вибору стратегії А1, а на другій — за стратегії А2. Нехай противник вибрав стратегію В1, їй відповідають на осях І та ІІ дві точки В1, причому довжина відрізка А1В1 дорівнює а11, а довжина відрізка А2В1 дорівнює а12. Аналогічно будуємо пряму В2В2, яка відповідає стратегії В2. Необхідно знайти оптимальну стратегію Х*, таку, за якої мінімальний виграш гравця А буде максимальним. Для цього виділимо жирною лінією на малюнку нижню межу виграшу за умови вибору стратегій В1 та В2, тобто ламану лінію В1МВ2. На цій межі знаходяться значення мінімального виграшу гравця А за будь-якої його змішаної стратегії. Очевидно, що найкраще з можливих мінімальних значень у нашому прикладі знаходиться в точці М, а в загальному випадку відповідає тій точці, де крива, що позначає мінімальний виграш гравця А, набуває максимального значення. Ордината цієї точки є ціною гри (. Відстань до лівого кінця відрізка х2 та відстань до правого кінця відрізка — х1 дорівнюють відповідно ймовірностям стратегій А2 та А1.
Рис. 11.1 Геометрична інтерпретація дає також змогу наочно зобразити нижню та верхню ціну гри (рис. 11.2). Для нашого прикладу нижньою ціною гри є величина відрізка А2В2, а верхньою ціною гри — А2В1.
Рис. 11.2 На цьому ж рисунку можна розглянути і геометричну інтерпретацію оптимальних стратегій противника В. Дійсно, частка стратегії В1 в оптимальній змішаній стратегії дорівнює відношенню довжини відрізка КВ2 до суми довжин відрізків КВ2 та КВ1 на осі І: . З наведених міркувань легко висновувати, що гру 2 ( 2 можна розв’язати елементарними прийомами. Аналогічно може бути розв’язана гра 2 ( n, тобто коли гравець А має лише дві стратегії, а гравець В – n. У такому разі на рисунку слід зобразити перетин n прямих, що відповідатимуть n стратегіям гравця В. Мінімальні виграші гравця А являтимуть собою також ламану лінію, максимальне значення якої і визначатиме оптимальну стратегію для гравця А (рис. 11.3).
Рис. 11.3 Можна також розв’язати і гру m ( 2, з тією різницею, що необхідно визначати не нижню величину виграшу, а верхню і знаходити не максимальне з можливих значення, а мінімальне. 11.6. Зведення матричної гри до задачі лінійного програмування Якщо гра 2 ( n або m ( 2 може бути розв’язана геометрично, то у випадку гри 3 ( n (m ( 3) геометрична інтерпретація переходить у простір, що ускладнює як її побудову, так і сприйняття. У випадку ж, коли n > 3, m > 3, геометрична інтерпретація взагалі неможлива. Для розв’язування гри m × n використовують прийом зведення її до задачі лінійного програмування. Нехай розглядається парна гра зі стратегіями для гравця А та стратегіями для гравця В і платіжною матрицею . Необхідно знайти оптимальні змішані стратегії та , де , . Знайдемо спочатку оптимальну стратегію гравця А. За основною теоремою теорії ігор така стратегія має забезпечити гравцеві виграш, не менший за ціну гри (поки що невідому величину) (, за будь-якої поведінки гравця В. Допустимо, що гравець А застосовує свою оптимальну стратегію, а гравець В — свою «чисту» j-ту стратегію Bj, тоді середній виграш гравця А дорівнюватиме: . (11.10) За цих обставин виграш має бути не меншим, ніж ціна гри. Отже, для будь-якого значення j величина виду (11.10) має бути не меншою, ніж (:
Розділивши всі обмеження на (, отримаємо:
Позначивши маємо:
. Враховуючи умову, що , отримуємо . Необхідно зробити виграш максимальним. Цього можна досягти, коли вираз набуватиме мінімального значення. Отже, врешті маємо звичайну задачу лінійного програмування. Цільова функція: (11.11) за умов: (11.12) . (11.13) Розв’язуючи цю задачу симплексним методом, знаходимо значення а також величину і значення , що є оптимальним розв’язком початкової задачі. Отже, визначено змішану оптимальну стратегію для гравця А. За аналогією можна записати задачу лінійного програмування для визначення оптимальної стратегії гравця В. З цією метою позначимо:
Маємо таку лінійну модель задачі:
за умов:
Очевидно, що задача лінійного програмування для гравця В є двоїстою до задачі гравця А, а тому оптимальний розв’язок однієї з них визначає також оптимальний розв’язок спряженої. Розглянемо приклад застосування методів лінійного програмування для знаходження оптимального розв’язку гри. Агрофірма «Зоря» розробила шість бізнес-планів (X1, X2, X3, X4, X5, X6) для їх здійснення у наступному році. Залежно від зовнішніх умов (погодного стану, ринку тощо) виділено п’ять ситуацій (Y1, Y2, Y3, Y4, Y5). Для кожного варіанта Xi бізнес-плану та зовнішньої ситуації Yj обчислені прибутки, які наведені у табл. 11.2: Таблиця 11.2 Варіант бізнес-плану Зовнішня ситуація
Y1 Y2 Y3 Y4 Y5
прибутки, тис. грн
Х1 1,0 1,5 2,0 2,7 3,2
Х2 1,2 1,4 2,5 2,9 3,1
Х3 1,3 1,6 2,4 2,8 2,1
Х4 2,1 2,4 3,0 2,7 1,8
Х5 2,4 2,9 3,4 1,9 1,5
Х6 2,6 2,7 3,1 2,3 2,0
Необхідно вибрати найкращий варіант бізнес-плану або комбінацію із розроблених планів. Розв’язання. Маємо гру, платіжною матрицею якої є відповідні елементи вищенаведеної таблиці. Легко переконуємося, що домінуючих стратегій у цій грі немає. Потім визначаємо:
а також
Отже, тобто немає сідлової точки, а це означає, що необхідно застосувати метод зведення гри до задачі лінійного програмування:
за умов:
Розв’язуємо цю задачу симплексним методом. Оптимальний розв’язок задачі: ; . Звідси отримаємо оптимальний розв’язок для початкової задачі: ; . Ціна гри . Заключні зауваження Задачі теорії ігор належать до задач прийняття рішень за умов невизначеності та ризику. Невизначеність результатів гри зумовлена кількома чинниками. По-перше, як правило, кількість можливих варіантів розвитку подій дуже велика, тому передбачити результат гри неможливо. Простою ілюстрацією такого твердження є гра в шахи. Із-за безлічі можливих комбінацій знайти оптимальний розв’язок такої гри неможливо. По-друге, значний вплив на хід та результати гри мають випадкові чинники, дію яких передбачити неможливо, наприклад, у рулетці. По-третє, джерелом невизначеності є брак інформації щодо дій противника. Крім того, невизначеність певною мірою може стосуватися також і мети, якої прагне досягти суб’єкт. Не завжди таку мету можна виразити однозначно, а тим більше одним показником. Зрозуміло, що коли початкові умови задачі містять значну кількість невизначених параметрів, то математичне дослідження не може дати чіткого обґрунтування раціонального розв’язку, однак і за відсутності повної визначеності кількісний аналіз дає наукову основу для прийняття рішень. Т. Сааті — засновник науки «Дослідження операцій» (інструментарієм якої є «Математичне програмування») писав, що «Дослідження операцій» — це таке мистецтво, яке дає погані відповіді на такі практичні запитання, на які інші методи дають ще гірші відповіді. Отже, уможливлюючи розв’язування задач за умов невизначеності, навіть якщо неможливо знайти точний оптимальний розв’язок, математичні методи, в тому числі і методи теорії ігор, являють собою допоміжний матеріал, який дає змогу в складній ситуації оцінити кожен з можливих варіантів розвитку подій, а отже, прийняти виважене рішення. Контрольні запитання Що називається конфліктною ситуацією? Що таке гра? Що таке хід гри? Дайте визначення платіжної матриці. Сформулюйте принцип мінімаксу. Дайте визначення максимінної та мінімаксної стратегій. Яка гра називається скінченною, парною? Які властивості мають оптимальні стратегії гравців? Сформулюйте основну теорему теорії ігор. У який спосіб здійснюється зведення гри до задачі лінійного програмування? Приклади та завдання для самостійної роботи Задача 11.1. Розв’язати графічно ігри. 1) ; 2) 3) 4) .
