Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

11.3. Матричні ігри двох осіб

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

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

Результати (плата) за всіма можливими варіантами гри задаються спеціальними функціями, які залежать від стратегій гравців, як правило, у вигляді платіжної матриці.

Нехай — виграш гравця А;

— виграш гравця В.

Оскільки гра з нульовою сумою, то

Тоді в разі, якщо то

Отже, мета гравця А — максимізувати величину , а гравця В — мінімізувати її. Нехай тобто маємо матрицю А:

де рядки відповідають стратегіям Аі, а стовпці — стратегіям Bj.

Матриця А називається платіжною, а також матрицею гри. Елемент цієї матриці aij — це виграш гравця А, якщо він вибрав стратегію Ai, а гравець В — стратегію Bj.

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

Нехай гравець А вибрав стратегію Ai, тоді у найгіршому разі він отримає виграш, що дорівнює min aij, тобто навіть тоді, якщо гравець В і знав би стратегію гравця А. Передбачаючи таку можливість, гравець А має вибрати таку стратегію, щоб максимізувати свій мінімальний виграш, тобто

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

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

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

Якщо

,

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

Фірма виготовляє устаткування для хімічної промисловості. Експертами виробничого відділу фірми розглядаються три конструкторські варіанти устаткування: А-1, А-2, А-3. Для спрощення допустимо, що за технічними характеристиками ці три типи майже ідентичні, однак залежно від зовнішнього вигляду та зручності використання кожен тип може мати три модифікації: М-1, М-2, М-3 залежно від закупленої технології виробництва. Собівартість виготовлення устаткування наведена в табл. 11.1:

Таблиця 11.1

СОБІВАРТІСТЬ ВИГОТОВЛЕННЯ УСТАТКУВАННЯ, тис. ум. од.

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

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

Розв’язання.

Якщо виробничий відділ запропонує виготовлення устаткування типу А-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 одиниць і т. д. Можливість такого розвитку подій виникає тому, що мінімаксна та максимінна стратегії в даному разі не є стійкими. Тобто обставини, за яких обидва гравці використовують мінімаксну та максимінну стратегії, невигідні гравцям у тому разі, коли один з них змінює свою оптимальну стратегію.
Однак така нестійкість властива не всім іграм із сідловою точкою. В деяких випадках сідловій точці відповідають стійкі максимінна та мінімаксна стратегії. В такому разі відхилення від оптимальної стратегії одним з гравців спричиняє таку зміну виграшу, яка є невигідною для цього гравця, оскільки стан або не змінюється, або погіршується.

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