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

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

,

.

Теорема: У матричній грі нижня чиста ціна гри не перевищує верхньої чистої ціни гри, тобто
.

Визначення:Якщо для чистих стратегій ,гравцівA і відповідно має місце рівність
, то пару чистих стратегій ( ,) називають сідловою точкою матричної гри, елемент матриці, що стоїть на перетині i-го рядка та j-го стовпця – сідловим елементом платіжної матриці, а число
- Чистою ціною гри.

Приклад:Знайти нижню та верхню чисті ціни, встановити наявність сідлових точок матричної гри

.

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

У даному випадкумаємо одну сідлову точку(А 1 ; В 2), а сідловий елемент дорівнює 5. Цей елемент є найменшим у 1-му рядку та найбільшим у 2-му стовпці. Відхилення гравця А від максимінної стратегії А 1 веде до зменшення його виграшу, а відхилення гравця від мінімаксної стратегії В 2 веде до збільшення його програшу. Іншими словами, якщо в матричній грі є сідловий елемент, то найкращими для гравців є їх мінімаксні стратегії. І ці чисті стратегії, що утворюють сідлову точку та виділяють у матриці гри сідловий елемент a 12 =5, є оптимальні чисті стратегії і відповідно гравців А та В.

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

Визначення:Змішаною стратегією першого (другого) гравця називається вектор
, де
і
(
, де
і
).

Вектор p(q) означає можливість застосування i-ї чистої стратегії першим гравцем (j-ї чистої стратегії другим гравцем).

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

.

Визначення:Функція f(р, q) називається платіжною функцією гри з матрицею
.

Визначення:Стратегії
,
називаються оптимальними, якщо для довільних стратегій
,
виконується умова

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

Сукупність оптимальних стратегій та ціни гри складає рішення гри.

5. ТЕОРІЯ ІГР І СТАТИСТИЧНИХ РІШЕНЬ

5.1. Матрична гра з нульовою сумою

Економіко-математичне моделювання здійснюється в умовах:

Визначеності;

Невизначеність.

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

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

Моделювання в умовах невизначеності відповідає повній відсутності деяких необхідних даних (теорія ігор).

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

Теоретично ігор оперують такими основними поняттями:

Стратегія;

Функція виграшу.

Ходом називатимемо вибір та здійснення гравцем одного з передбачених правилами гри дій.

Стратегія - це технологія вибору варіанта дій при кожному ході в залежності від ситуації, що склалася.

Функція виграшу служить для визначення величини платежу гравця, що програв виграв.

У матричній грі функція виграшу подається у вигляді платіжної матриці :

де - величина платежу гравцю I, що вибрав хід, від гравця II, який вибрав хід.

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

Процес "ігри в матричну гру" представляється так:

Задається платіжна матриця;

Гравець I незалежно від гравця II вибирає один із рядків цієї матриці, наприклад, -ий;

Гравець II незалежно від гравця I вибирає один із стовпців цієї матриці, наприклад, - ий;

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

Антагоністичну парну гру з платіжною матрицею називатимемо грою.

приклад

Розглянемо гру.

Задано платіжну матрицю:

.

Нехай гравець I незалежно від гравця II вибирає 3-й рядок цієї матриці, а гравець II незалежно від гравця I вибирає 2-ий стовпець цієї матриці:

Тоді гравець I отримає 9 одиниць від гравця ІІ.

5.2. Оптимальна чиста стратегія у матричній грі

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

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

.

Гравець II міркує аналогічно і може напевно забезпечити мінімальний програш:

.

Завжди справедлива нерівність:

Величину називають нижньою ціною гри .

Величину називають верхньою ціною гри .

Оптимальні стратегії і називаються чистими якщо для них виконуються рівності:

,

.

Величину називають чистою ціною гри якщо .

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

Для сідлової точки виконуються умови:

тобто елемент є найменшим у рядку та найбільшим у стовпці.

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

Чиста стратегія гравця I може бути представлена ​​впорядкованим набором чисел (вектором), в якому всі числа дорівнюють нулю, крім числа, що стоїть на місці, що дорівнює одиниці.

Чиста стратегія гравця II може бути представлена ​​впорядкованим набором чисел (вектором), в якому всі числа дорівнюють нулю, крім числа, що стоїть на місці, що дорівнює одиниці.

приклад

.

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

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

Гравець II міркує аналогічно і вибере в якості ходу перший стовпець:

Таким чином, є сідлова точка платіжної матриці:

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

5.3. Оптимальна змішана стратегія у матричній грі

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

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

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

1) для, тобто ймовірність вибору кожного рядка платіжної матриці невід'ємна;

2), тобто. вибір кожного з рядків платіжної матриці в сукупності представляє повну групу подій.

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

Величина платежу гравцю I, який вибрав змішану стратегію

від гравця II, який вибрав змішану стратегію

,

є середньою величиною

.

Оптимальними називають змішані стратегії

і ,

якщо для будь-яких довільних змішаних стратегій і виконується умова:

т. е. за оптимальної змішаної стратегії виграш гравця I найбільший, а програш гравця II найменший.

Якщо платіжної матриці немає сідлової точки, то

,

тобто існує позитивна різниця ( нерозподілена різниця )

- ³ 0,

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

приклад

Розглянемо гру, задану платіжною матрицею:

.

Визначимо, чи є сідлова точка:

, .

Виявляється, що в платіжній матриці немає сідлової точки і нерозподілена різниця дорівнює:

.

5.4. Знаходження оптимальних змішаних стратегій

для ігор 2×2

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

Нехай ймовірність вибору гравцем I першого рядка платіжної матриці

дорівнює. Тоді ймовірність вибору другого рядка дорівнює.

Нехай ймовірність вибору гравцем ІІ першого стовпця дорівнює. Тоді ймовірність вибору другого стовпця дорівнює.

Розмір платежу гравцю I гравцем II дорівнює:

Екстремальна величина виграшу гравця I та програшу гравця II відповідає умовам:

;

.

Таким чином, оптимальні змішані стратегії гравців І та ІІ відповідно рівні:

5.5. Геометричне рішення ігор 2×n

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

Основні етапи знаходження рішення гри зводяться до наступного.

На площині введемо систему координат. На осі відкладемо відрізок. З лівого та правого кінців цього відрізка проведемо перпендикуляри.

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

такими виграшами гравця I при виборі стратегії будуть і, а при виборі стратегії будуть і.

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

Знаходимо оптимальну змішану стратегію гравця I

,

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

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

Таким чином, гра зводиться до гри і оптимальною змішаною стратегією гравця II у прикладі, що розглядається

,

де ймовірність знаходиться так само, як у грі:

5.6. Рішення ігорm× n

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

Нехай задана платіжна матриця розмірності:

.

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

Для кожного вибраного ходу гравцем II виграш гравця I визначається залежностями:

Розділимо обидві частини нерівностей і введемо нові позначення:

Рівність

Набуде вигляду:

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

при обмеженнях

Аналогічно будується завдання для гравця II як подвійне:

при обмеженнях

Вирішуючи завдання симплекс-методом, отримуємо:

,

5.7. Особливості вирішення матричних ігор

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

Чи можна спростити платіжну матрицю;

Чи має платіжна матриця сідлову точку.

Розглянемо можливість спрощення платіжної матриці:

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

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

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

приклад

Дано платіжну матрицю:

.

Спрощення платіжної матриці:

Наявність сідлової точки:

5.8. Гра з природою

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

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

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

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

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

приклад

Матриця виграшів:

.

Матриця ризиків:

Можливі дві постановки задачі про вибір рішення у матричній грі з природою :

Максимізація виграшу;

Мінімізація ризику.

Завдання прийняття рішень може бути поставлене для однієї з двох умов:

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

- в умовах невизначеності коли така функція розподілу ймовірностей невідома.

5.9. Розв'язання задач теорії статистичних рішень

в умовах ризику

При прийнятті рішень в умовах ризику гравцеві I відомі ймовірності настання станів природи.

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

.

При вирішенні цього завдання з матрицею ризику отримуємо таке саме рішення, що відповідає мінімального середнього ризику :

.

5.10. Розв'язання задач теорії статистичних рішень

в умовах невизначеності

При ухваленні рішень в умовах невизначеності можна скористатися такими критеріями :

Максимінним критерієм Вальда;

Критерієм мінімального ризикуСевіджа;

Критерієм песимізму – оптимізму Гурвіца;

Принципом недостатньої основи Лапласа.

Розглянемо максимальний критерій Вальда .

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

.

Розглянемо критерій мінімального ризику Севіджа .

Аналогічний попередній підхід з позиції крайнього песимізму для матриці ризику:

.

Розглянемо критерій песимізму - оптимізму Гурвіца .

Пропонується можливість не керуватися ні крайнім песимізмом, ні крайнім оптимізмом:

де ступінь песимізму;

при - крайній оптимізм,

при – крайній песимізм.

Розглянемо принцип недостатньої основи Лапласа .

Вважається, що всі стани природи рівноймовірні:

,

.

Висновки з п'ятого розділу

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

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

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

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

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

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

Запитання для самоперевірки

Як визначаються основні поняття теорії ігор: хід, стратегія та функція виграшу?

У вигляді чого видається в матричній грі функція виграшу?

Чому матричну гру називають із нульовою сумою?

Як видається процес гри в матричну гру?

Яка гра називається грою m×n?

Яка стратегія матричної гри називається оптимальною?

Яка оптимальна стратегія матричної гри називається чистою?

Що означає сідлова точка платіжної матриці?

Яка оптимальна стратегія матричної гри називається змішаною?

Як видається змішана стратегія гравця?

Що таке величина платежу гравцю I від гравця II, який вибрав змішані стратегії?

Які змішані стратегії називають оптимальними?

Що означає нерозподілена різниця?

За допомогою якого методу є оптимальні змішані стратегії для ігор 2×2?

Яким чином є оптимальні змішані стратегії для ігор 2×n?

За допомогою якого методу є оптимальні змішані стратегії для ігор m×n?

У чому полягають особливості розв'язання матричних ігор?

Що означає спрощення платіжної матриці та за яких умов воно може бути здійснено?

Яку матричну гру легко вирішувати, коли платіжна матриця має чи не має сідлову точку?

Які завдання теорії ігор належать до задач теорії статистичних рішень?

Як платіжна матриця перетворюється на матрицю ризиків?

Які дві постановки задачі про вибір рішень можливі у матричній грі з природою?

Для яких двох умов можуть бути поставлені завдання ухвалення рішень у матричній грі з природою?

Яку стратегію доцільно вибрати гравцю I під час вирішення завдання теорії статистичних рішень за умов ризику?

Якими критеріями прийняття рішень можна скористатися під час вирішення завдань теорії статистичних рішень за умов невизначеності?

Приклади розв'язання задач

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

Позначимо задану матрицю через і введемо змінні. Будемо також використовувати матрицю (вектор). Тоді і, тобто.

Розраховується зворотна матриця:

Знаходяться значення:

.

Розраховуються ймовірності:

Визначається середній прибуток від реалізації:

.

2. Фірма «Фармацевт» - виробник медикаментів та біомедичних виробів у регіоні. Відомо, що пік попиту на деякі лікарські препарати посідає літній період(Препарати серцево-судинної групи, анальгетики), на інші – на осінній та весняний періоди (антиінфекційні, протикашльові).

Витрати 1 ум. од. продукції за вересень-жовтень склали: по першій групі (препарати серцево-судинні та анальгетики) - 20 р.; по другій групі (антиінфекційні, протикашльові препарати) – 15 гр.

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

У зв'язку з можливими змінами погоди ставиться завдання – визначити стратегію фірми у випуску продукції, що забезпечує максимальний прибуток від реалізації за ціною продажу 40 грн. за 1 ум. од. продукції першої групи та 30 р. - Другої групи.

РІШЕННЯ. Фірма має дві стратегії:

Цього року буде теплою погодою;

Погода буде холодною.

Якщо фірма прийме стратегію і насправді буде тепла погода (стратегія природи), то випущена продукція (3050 ум. од. препаратів першої групи та 1100 ум. од. другої групи) буде повністю реалізована і дохід становитиме

3050×(40-20)+1100×(30-15)=77500 нар.

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

1525×(40-20)+1100×(30-15)-20×()=16500 нар.

Аналогічно, якщо форма прийме стратегію і насправді буде холодна погода, то дохід становитиме

1525×(40-20)+3690×(30-15)=85850 нар.

За теплої погоди дохід становитиме

1525×(40-20)+1100×(30-15)-() ×15=8150 нар.

Розглядаючи фірму та погоду як два гравці, отримаємо платіжну матрицю

,

Ціна гри лежить у діапазоні

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

Знайдемо рішення гри.

Позначимо ймовірність застосування фірмою стратегії через, стратегії через, причому. Вирішуючи гру графічно методом, отримаємо , при цьому ціна гри нар.

Оптимальний план виробництва лікарських препаратів становитиме

Таким чином, фірмі доцільно виробляти протягом вересня та жовтня 2379 р. ум. од. препаратів першої групи та 2239,6 ум. од. препаратів другої групи, тоді за будь-якої погоди вона отримає дохід не менше 46986 р.

У разі невизначеності, якщо неможливо фірмі використовувати змішану стратегію (договори коїться з іншими організаціями), визначення оптимальної стратегії фірми використовуємо такі критерії:

Критерій Вальде:

Критерій Гурвіца: для визначеності приймемо, тоді для стратегії фірми

для стратегії

фірмі доцільно використовувати стратегію.

Критерій Севіджа. Максимальний елемент у першому стовпці – 77500, у другому стовпці – 85850.

Елементи матриці ризиків перебувають з виразу

,

звідки , ,

Матриця ризиків має вигляд

,

доцільно використовувати стратегію чи .

Отже, фірмі доцільно застосовувати стратегію чи .

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

При відомому розподілі ймовірностей різних станів природи критерієм прийняття рішення є максимум математичного очікування на виграш.

Нехай відомо для завдання, що ймовірності теплої і холодної погоди рівні і становлять 0,5, тоді оптимальна стратегія фірми визначається так:

Фірмі доцільно використовувати стратегію чи .

Завдання для самостійної роботи

1. Підприємство може випускати три види продукції (А, Б та В), отримуючи при цьому прибуток, що залежить від попиту. Попит у свою чергу може приймати один із чотирьох станів (I, II, III та IV). У наступній матриці елементи характеризують прибуток, який отримає підприємство при випуску продукції -ой стані попиту:

Математичні методи та моделі в економіці

Матричні ігри

Вступ

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

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

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

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

Гра в чистих стратегіях

Розглянемо гру з двома гравцями Аі Ст.Припустимо, що гравець Амає mстратегій А 1, А 2, …, А m, а гравець Умає nстратегій B 1, B 2, …, B n.Вважатимемо, що вибір гравцем Астратегії А i ,а гравцем Устратегії B jоднозначно визначає результат гри, тобто. виграш a ijгравця Ата виграш b ijгравця Ст.Тут i=1,2,…,m, j=1,2,…,n.

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

b ij =-a ij

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

Кожній парі стратегій А іі B jвідповідає виграш a ijгравця А.Усі ці виграші зручно записувати у вигляді так званої платіжної матриці

Рядки цієї матриці відповідають стратегіям гравця. А,а стовпці – стратегіям гравця Ст.Загалом така гра називається (m×n)-грою.

приклад 1.Два гравці Аі Укидають монету. Якщо сторони монети збігаються, то виграє А, тобто. гравець Уплатить гравцеві Адеяку суму, рівну 1, і якщо збігаються, то виграє гравець, тобто. навпаки, гравець Аплатить гравцеві Уцю ж суму , рівну 1. Сформувати платіжну матрицю.

Рішення.За умовою завдання

Хоча я закінчив фізико-технічний факультет, у вузі мені не читали теорію ігор. Але, оскільки я в студентські рокибагато грав спочатку у преферанс, а потім у бридж, теорія ігор мене цікавила, і я освоїв невеликий підручник. А нещодавно читач сайту Михайло вирішив завдання на теорію ігор. Зрозумівши, що завдання мені не дається, вирішив освіжити в пам'яті мої знання з теорії ігор. Пропоную вам невелику книгу - популярний виклад елементів теорії ігор та деяких способів вирішення матричних ігор. Вона майже не містить доказів та ілюструє основні положення теорії прикладами. Книгу написала математик та популяризатор науки Олена Сергіївна Вентцель. Декілька поколінь радянських інженерів навчалися за її підручником «Теорія ймовірностей». Олена Сергіївна також написала кілька літературних творів під псевдонімом І. Грекова.

Олена Вентцель. Елементи теорії ігор. - М.: Фізматгіз, 1961. - 68 с.

завантажити короткий конспекту форматі або

§ 1. Предмет теорії ігор. Основні поняття

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

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

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

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

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

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

Почнемо виклад елементарної теорії ігор із формулювання деяких основних понять. Розглядатимемо парну гру, в якій беруть участь два гравці А і В з протилежними інтересами. Під «грою» розумітимемо захід, що складається з низки дій сторін А і В. Щоб гра могла бути піддана математичному аналізу, повинні бути точно сформульовані правила гри. Під "правилами гри" розуміється система умов, що регламентує можливі варіанти дій обох сторін, обсяг інформації кожної сторони про поведінку іншої, послідовність чергування "ходів" (окремих рішень, прийнятих у процесі гри), а також результат або результат гри, до якого наводить дана сукупність ходів. Цей результат (виграш або програш) не завжди має кількісний вираз, але зазвичай можна, встановивши деяку шкалу виміру, виразити його певним числом. Наприклад, у шахівниці виграшу можна умовно приписати значення +1, програшу –1, нічиєї 0.

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

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

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

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

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

Деякі ігри можуть складатися тільки з випадкових ходів (так звані чисто азартні ігри) або лише з особистих ходів (шахи, шашки). Більшість карткових ігорналежить до ігор змішаного типу, тобто. містить як випадкові, і особисті ходи.

Ігри класифікуються не лише за характером ходів (особисті, випадкові), а й за характером та за обсягом інформації, доступною кожному гравцю щодо дій іншого. Особливий клас ігор становлять звані «ігри з повною інформацією». Гра з повною інформацією називається гра, в якій кожен гравець при кожному особистому ході знає результати всіх попередніх ходів, як особистих, так і випадкових. Прикладами ігор з повною інформацією можуть бути шахи, шашки, а також відома гра «хрестики та нуліки».

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

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

Гравець, який вибрав стратегію, може тепер не брати участь у грі особисто, а замінити свою участь списком правил, які за нього застосовуватиме будь-яка незацікавлена ​​особа (суддя). Стратегія може бути задана машині-автомату у вигляді певної програми. Саме так нині грають у шахи ЕОМ. Щоб поняття «стратегії» мало сенс, потрібна наявність у грі особистих ходів; в іграх, які з одних випадкових ходів, стратегії відсутні.

Залежно від кількості можливих стратегій гри діляться на «кінцеві» та «нескінченні». Кінцевою називається гра, в якій кожен гравець має лише кінцеве число стратегій. Кінцева гра, в якій гравець має mстратегій, а гравець В - nстратегій називається грою mxn.

Розглянемо гру mxn двох гравців А та В («ми» та «противник»). Позначатимемо наші стратегії A 1 , А 2 , …, А m стратегії противника B 1 , В 2 , …, В n . Нехай кожна сторона вибрала певну стратегію; для нас це буде Ai, для противника Bj. Якщо гра складається з особистих ходів, то вибір стратегій A i , B j однозначно визначає результат гри - наш виграш. Позначимо його а ij. Якщо гра містить, крім особистих, випадкові ходи, виграш при парі стратегій A i , B j є величина випадкова, яка залежить від результатів всіх випадкових ходів. І тут природною оцінкою очікуваного виграшу є його середнє значення (математичне очікування). Ми позначатимемо одним і тим же знаком як сам виграш (у грі без випадкових ходів), так і його середнє значення (у грі з випадковими ходами).

Нехай нам відомі значення а ij виграшу (або середнього виграшу) за кожної пари стратегій. Значення можна записати як прямокутної таблиці (матриці), рядки якої відповідають нашим стратегіям (A i), а стовпці - стратегіям противника (B j). Така таблиця називається платіжною матрицею чи просто матрицею гри. Матриця гри mxn представлена ​​на рис. 1.

Мал. 1. Матриця mxn

Скорочено ми позначатимемо матрицю гри ‖а ij ‖. Розглянемо кілька простих прикладів ігор.

приклад 1.Два гравці A і В, не дивлячись один на одного, кладуть на стіл по монеті вгору гербом або решкою, на власний розсуд. Якщо гравці вибрали однакові сторони (в обох герб або в обох решках), то гравець А забирає обидві монети; інакше їх забирає гравець В. Потрібно проаналізувати гру та скласти її матрицю. Рішення. Гра складається тільки з двох ходів: наш хід і хід супротивника, обидва особисті. Гра не належить до ігор з повною інформацією, тому що в момент ходу гравець, що його виконує, не знає, що зробив інший. Так як у кожного з гравців є тільки один особистий хід, то стратегія гравця є вибіром при цьому єдиному особистому ході.

У нас дві стратегії: А 1 – вибирати герб та А 2 – вибирати решку; у противника такі самі дві стратегії: У 1 - герб і У 2 - решка. Таким чином, ця гра є гра 2×2. Вважатимемо виграш монети за +1. Матриця гри:

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

Справді, припустимо, що ми (гравець А) вибрали собі якусь стратегію (скажімо, А1) та дотримуємося її. Тоді вже за результатами перших кількох ходів противник здогадається про нашу стратегію і відповідатиме на неї найменш вигідним нам чином, тобто. вибирати решку. Нам явно невигідно завжди застосовувати якусь одну стратегію; щоб не опинитися у програші, ми маємо іноді вибирати герб, іноді – решку. Однак, якщо ми чергуватимемо герби і решки в якійсь певній послідовності (наприклад, через один), противник теж може здогадатися про це і відповісти на цю стратегію найгіршим для нас чином. Очевидно, надійним способом, який гарантує, що противник не знатиме нашої стратегії, буде така організація вибору при кожному ході, коли ми його самі наперед не знаємо (це можна забезпечити, наприклад, підкиданням монети). Таким чином, ми шляхом інтуїтивних міркувань підходимо до одного із суттєвих понять теорії ігор – до поняття «змішаної стратегії», тобто. такий, коли «чисті» стратегії - у разі A 1 і А 2 – чергуються випадково з певними частотами. У цьому прикладі з міркувань симетрії заздалегідь ясно, що стратегії A 1 і 2 повинні чергуватись з однаковою частотою; у складніших іграх рішення може бути не тривіальним.

приклад 2.Гравці А і В одночасно і незалежно один від одного записують кожен одне з трьох чисел: 1, 2 або 3. Якщо сума написаних чисел парна, то платить А цю суму в рублях; якщо вона непарна, то, навпаки, А платить у цю суму. Потрібно проаналізувати гру та скласти її матрицю.

Рішення. Гра складається із двох ходів; обидва – особисті. У нас (А) три стратегії: А 1 – писати 1; А 2 – писати 2; А 3 – писати 3. У противника (В) – ті ж три стратегії. Гра являє собою гру 3×3:

Очевидно, як і в попередньому випадку, на будь-яку обрану стратегію противник може відповісти найгіршим для нас чином. Справді, якщо ми виберемо, наприклад, стратегію А1, противник завжди відповідатиме на неї стратегією В2; на стратегію А2 - стратегією В3; на стратегію А3 - стратегією В2; таким чином, будь-який вибір певної стратегії неминуче призведе нас до програшу (не треба, втім, забувати, що в такому ж тяжкому становищі знаходиться й супротивник). Вирішення цієї гри (тобто сукупність найвигідніших стратегій обох гравців) буде дано в § 5.

приклад 3.У нашому розпорядженні є три види озброєння: А1, А2, А3; у противника - три види літаків: B 1 , 2 , 3 . Наше завдання – вразити літак; завдання противника- зберегти його неураженим. При застосуванні озброєння А 1 літаки B 1 2 3 уражаються відповідно з ймовірностями 0,9, 0,4 і 0,2; при озброєнні А 2 - з ймовірностями 0,3, 0,6 та 0,8; при озброєнні А 3 – з ймовірностями 0,5, 0,7 та 0,2. Потрібно сформулювати ситуацію термінах теорії ігор.

Рішення. Ситуація може розглядатися як гра 3×3 з двома особистими ходами та одним випадковим. Наш особистий хід – вибір типу озброєння; Особистий хід противника - вибір літака для участі в бою. Випадковий хід – застосування озброєння; цей хід може закінчитися поразкою чи непоразкою літака. Наш виграш дорівнює одиниці, якщо літак уражений, і дорівнює нулю в іншому випадку. Нашими стратегіями є три варіанти озброєння; стратегіями супротивника – три варіанти літаків. Середнє значення виграшу при кожній заданій парі стратегій є нічим іншим, як ймовірність поразки даного літака даною зброєю. Матриця гри:

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

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

§ 2. Нижня та верхня ціна гри. Принцип «мінімаксу»

Розглянемо гру mxn з матрицею, як у рис. 1. Позначатимемо літерою i номер нашої стратегії; літерою j- номер стратегії супротивника. Поставимо собі завдання визначити свою оптимальну стратегію. Проаналізуємо послідовно кожну з наших стратегій, починаючи з A1.

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

Тут знаком min (мінімум по j) позначено мінімальне значення цього параметра при всіх можливих j. Випишемо числа α i; поряд з матрицею праворуч у вигляді додаткового стовпця:

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

або, враховуючи формулу (2.1),

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

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

і знайдемо мінімальне з β j:

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

Як приклади визначимо нижню та верхню ціну гри та мінімаксні стратегії для прикладів 1, 2 та 3 § 1.

приклад 1.У прикладі 1 § 1 дана гра з наступною матрицею:

Так як величини α i і β j постійні та рівні відповідно –1 та +1, нижня та верхня ціна гри також рівні –1 та +1: α = –1, β = +1. Будь-яка стратегія гравця А є його максимінною, а будь-яка стратегія гравця В – його мінімаксною стратегією. Висновок тривіальний: дотримуючись будь-якої зі своїх стратегій, А може гарантувати, що він програє не більше 1; те саме може гарантувати і гравець Ст.

приклад 2.У прикладі 2 § 1 дана гра з матрицею:

Нижня ціна гри α = -3; верхня ціна гри β = 4. Наша максимінна стратегія є А1; застосовуючи її систематично, ми можемо твердо розраховувати виграти щонайменше –3 (програти трохи більше 3). Мінімаксна стратегія противника є будь-яка із стратегій В 1 і В 2; застосовуючи їх систематично, він, у всякому разі, може гарантувати, що програє не більше 4. Якщо ми відступимо від своєї максимінної стратегії (наприклад, виберемо стратегію А 2), противник може нас «покарати» за це, застосувавши стратегію 3 і звівши наш виграш до -5; і відступ противника від своєї мінімаксної стратегії може збільшити його програш до 6.

приклад 3.У прикладі 3 § 1 дана гра з матрицею:

Нижня ціна гри = 0,3; верхня ціна гри β = 0,7. Наша найбільш обережна (максиминна) стратегія є А2; користуючись озброєнням А 2 , ми гарантуємо, що вражатимемо літак у середньому щонайменше ніж 0,3 всіх випадків. Найбільш обережною (мінімаксною) стратегією противника є В 2; застосовуючи цей літак, противник може бути впевнений, що він буде уражатись не більше ніж у 0,7 всіх випадків.

на останньому прикладізручно продемонструвати одну важливу властивість мінімаксних стратегій – їх нестійкість. Нехай ми застосовуємо свою найбільш обережну (максимінну) стратегію А2, а противник - свою найбільш обережну (мінімаксну) стратегію В2. Доки обидва противники дотримуються цих стратегій, середній виграш дорівнює 0,6; він більший за нижню, але меншу верхньої ціниігри. Тепер припустимо, що противнику стало відомо, що ми застосовуємо стратегію А2; він негайно відповість на неї стратегією 1 і зведе виграш до 0,3. У свою чергу, на стратегію B 1 ми маємо гарну відповідь: стратегія A 1 , яка дає нам виграш 0,9, і т.д.

Таким чином, положення, при якому обидва гравці користуються своїми мінімаксними стратегіями, є нестійким і може бути порушено відомостями про стратегію протилежної сторони, що надійшли. Однак є деякі ігри, для яких мінімаксні стратегії є стійкими. Це ігри, котрим нижня ціна дорівнює верхньої: α = β. Якщо нижня ціна гри дорівнює верхній, то їх загальне значенняназивається чистою ціною гри (іноді просто ціною гри), ми його позначатимемо літерою ν.

Розглянемо приклад. Нехай гра 4×4 задана матрицею:

Знайдемо нижню ціну гри: α = 0,6. Знайдемо найвищу ціну гри: β = 0,6. Вони виявилися однаковими, отже, у гри є чиста ціна, що дорівнює α = β = ν = 0,6. Елемент 0,6, виділений у платіжній матриці, є одночасно мінімальним у своєму рядку та максимальним у своєму стовпці. У геометрії точку на поверхні, що має аналогічну властивість (одночасний мінімум по одній координаті і максимум по іншій), називають сідловою точкою, за аналогією цей термін застосовується і в теорії ігор. Елемент матриці, що має цю властивість, називається сідловою точкою матриці, а про гру говорять, що вона має сідлову точку.

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

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

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

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

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

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

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

§ 3. Чисті та змішані стратегії. Рішення гри у змішаних стратегіях

Серед кінцевих ігор, що мають практичне значення, порівняно рідко зустрічаються ігри з сідловою точкою; Найбільш типовим є випадок, коли нижня та верхня вартість гри різні. Аналізуючи матриці таких ігор, ми прийшли до висновку, що якщо кожному гравцю надано вибір однієї-єдиної стратегії, то в розрахунку на розумно чинного супротивника цей вибір повинен визначатися принципом мінімаксу. Дотримуючись своєї максимінної стратегії, ми за будь-якої поведінки противника свідомо гарантуємо собі виграш, що дорівнює нижній ціні гри α. Виникає природне питання: чи не можна гарантувати собі середній виграш, більший α, якщо застосовувати не одну «чисту» стратегію, а чергувати випадково кілька стратегій? Такі комбіновані стратегії, які перебувають у застосуванні кількох чистих стратегій, що чергуються за випадковим законом із певним співвідношенням частот, теорії ігор називаються змішаними стратегіями.

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

Висловлене твердження становить зміст так званої основної теореми теорії ігор. Ця теорема була вперше доведена фон Нейманом у 1928 р. Відомі докази теореми порівняно складні; тому наведемо лише її формулювання.

Кожна кінцева гра має принаймні одне рішення (можливо, в галузі змішаних стратегій).

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

(3.1) α ≤ ν ≤ β

Справді, α є максимальним гарантованим виграшем, який ми можемо собі забезпечити, застосовуючи лише свої чисті стратегії. Так як змішані стратегії включають як приватний випадок і всі чисті, то, допускаючи, крім чистих, ще й змішані стратегії, ми, принаймні, не погіршуємо своїх можливостей; отже, ν ≥ α. Аналогічно, розглядаючи можливості противника, покажемо, що ν ≤ β, звідки випливає нерівність, що доводиться (3.1).

Введемо спеціальне позначення для змішаних стратегій. Якщо, наприклад, наша змішана стратегія полягає у застосуванні стратегій А 1 , А 2 , А 3 із частотами p 1 , р 2 , р 3 , причому p 1 + р 2 + р 3 = 1, будемо позначати цю стратегію

Аналогічно змішану стратегію противника позначатимемо:

де q 1 , q 2 , q 3 - частоти, в яких змішуються стратегії B 1 , 2 , 3 ; q 1 + q 2 + q 3 = 1.

Припустимо, що ми знайдено рішення гри, що складається з двох оптимальних змішаних стратегій S A *, S B *. У загальному випадку не всі чисті стратегії, доступні цьому гравцю, входять до його оптимальної змішаної стратегії, а лише деякі. Будемо називати стратегії, що входять до оптимальної змішаної стратегії гравця, його «корисними» стратегіями. Виявляється, що рішення гри має ще одну чудову властивість: якщо один із гравців дотримується своєї оптимальної змішаної стратегії S A * (S B *), то виграш залишається незмінним і рівним ціні гри ν, незалежно від того, що робить інший гравець, якщо він тільки не виходить за межі своїх "корисних" стратегій. Він, наприклад, може користуватися будь-якою зі своїх «корисних» стратегій у чистому вигляді, а також може змішувати їх у будь-яких пропорціях.

§ 4. Елементарні методи вирішення ігор. Ігри 2x2 та 2xn

Якщо гра mxn не має сідлової точки, то знаходження рішення є взагалі досить важке завдання, особливо при великих m і n. Іноді це завдання вдається спростити, якщо попередньо зменшити кількість стратегій шляхом викреслення деяких зайвих. Зайві стратегії бувають: а) дублюючі та б) свідомо невигідні. Розглянемо, наприклад, гру з матрицею:

Неважко переконатися, що стратегія А 3 точно повторює («дублює») стратегію А 1, тому будь-яку з цих двох стратегій можна викреслити. Далі, порівнюючи рядки A 1 і А 2 бачимо, що кожен елемент рядка А 2 менший (або дорівнює) відповідного елемента рядка A 1 . Очевидно, що ми ніколи не повинні користуватися стратегією А2, вона є свідомо невигідною. Викреслюючи А 3 і А 2 наводимо матрицю до більш простому вигляду. Далі зауважуємо, що для противника стратегія В 3 свідомо невигідна; викреслюючи її, наводимо матрицю до остаточного вигляду:

Таким чином, гра 4×4 викреслюванням дублюючих та свідомо невигідних стратегій зведена до гри 2×3.

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

Розглянемо гру 2×2 з матрицею:

Тут можуть зустрітися два випадки: 1) гра має сідлову точку; 2) гра не має сідлової точки. У першому випадку рішення очевидне: це пара стратегій, що перетинаються в сідловій точці. Зауважимо до речі, що у грі 2×2 наявність сідлової точки завжди відповідає існуванню свідомо невигідних стратегій, які мають бути викреслені під час попереднього аналізу.

Нехай сідлова точка немає і, отже, нижня ціна гри не дорівнює верхній: α ≠ β. Потрібно знайти оптимальну змішану стратегію гравця А:

Вона відрізняється тим властивістю, що, якими б не були дії противника (якщо тільки він не виходить за межі своїх «корисних» стратегій), виграш дорівнюватиме ціні гри ν. У грі 2×2 обидві стратегії противника є «корисними», - інакше гра мала б рішення у сфері чистих стратегій (сідлову точку). Отже, якщо ми дотримуємося своєї оптимальної стратегії (4.1), противник може користуватися будь-якою зі своїх чистих стратегій B 1 , В 2 , не змінюючи середнього виграшу ν. Звідси маємо два рівняння:

з яких, зважаючи на те, що p 1 + p 2 = 1, отримаємо:

Ціну гри знайдемо, підставляючи значення р 1 , р 2 в будь-яке з рівнянь (4.2).

Якщо ціна гри відома, то для визначення оптимальної стратегії супротивника

достатньо одного рівняння, наприклад:

звідки, враховуючи, що q 1 + q 2 = 1, маємо:

приклад 1.Знайдемо рішення гри 2×2, розглянутої у прикладі 1 § 1, з матрицею:

Гра не має сідлової точки (α = -1; β = +1), і, отже, рішення має лежати в галузі змішаних стратегій:

Потрібно знайти p1, р2, q1 і q2. Для p 1 маємо рівняння

1*p 1 + (–1)(1 – p 1) = (–1)p 1 + 1(1 – p 1)

звідки p 1 = 1/2, p 2 = 1/2.

Аналогічно знайдемо: q1=1/2, q2=1/2, ν=0.

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

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

приклад 2.Гра полягає у наступному. Є дві карти: туз та двійка. Гравець А навмання виймає одну з них; Не бачить, яку карту він вийняв. Якщо А вийняв туза, він заявляє: «у мене туз» і вимагає у противника 1 рубль. Якщо А вийняв двійку, він може або А 1) сказати «у мене туз» і вимагати у противника 1 рубль, або А 2) зізнатися, що він двійка, і сплатити противнику 1 рубль.

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

Рішення.Гра має порівняно складну структуру; вона складається з одного обов'язкового випадкового ходу - вибору гравцем А однієї з двох карток - і двох особистих ходів, які, однак, необов'язково здійснюються. Справді, якщо А вийняв туза, він не робить ніякого особистого ходу: йому надана лише одна можливість - вимагати 1 рубль, що він і робить. У цьому випадку особистий хід – вірити чи не вірити (тобто платити чи не платити 1 рубль,) – передається гравцеві. Якщо А в результаті першого випадкового ходу отримав двійку, то йому надається особистий хід: сплатити 1 рубль або спробувати обдурити супротивника і вимагати 1 рубль (короче: «не обманювати» чи «обманювати»). Якщо А вибирає перше, то залишається тільки прийняти 1 рубль; якщо А вибрав друге, то гравцеві В надається особистий хід: вірити чи не вірити А (тобто сплатити А 1 рубль або вимагати перевірки).

Стратегії кожного з гравців є правилами, що вказують, як вчинити гравцю, коли йому надається особистий хід. Очевидно, А лише дві стратегії: А 1 - обманювати, А 2 - не обманювати. У - теж дві стратегії: B 1 - вірити, В 2 - не вірити. Побудуємо матрицю гри. Для цього обчислимо середній виграш за кожної комбінації стратегій.

1. А 1 В 1 (А дурить, В вірить). Якщо А отримав туза (імовірність цього ½, то йому не надається особистого ходу; він вимагає 1 рубль, і гравець В вірить йому; виграш А в рублях дорівнює 1. Якщо А отримав двійку (ймовірність цього теж ½), він відповідно до своєї стратегії обманює і вимагає 1 рубль, в нього вірить і сплачує, виграш А також дорівнює 1. Середній виграш: а 11 = ½ * 1 + ½ * 1 = 1.

2. А 1 В 2 (А дурить, В не вірить). Якщо А отримав туза, він не має особистого ходу; він вимагає 1 карбованець; Відповідно до своєї стратегії не вірить і в результаті перевірки сплачує 2 рублі (виграш А дорівнює +2). Якщо А отримав двійку, він відповідно до своєї стратегії вимагає 1 карбованець; У, відповідно до своєї, не вірить; в результаті А сплачує 2 рублі (виграш А дорівнює -2). Середній виграш дорівнює: 12 = ½*(+2) + ½*(–2) = 0.

3. A 2 В 1 (А не обманює, В вірить). Якщо А вийняв туза, він вимагає 1 карбованець; Відповідно до своєї стратегії сплачує; виграш А дорівнює +1. Якщо А вийняв двійку, він відповідно до своєї стратегії платить 1 карбованець; залишається тільки прийняти (виграш А дорівнює -1). Середній виграш дорівнює: 21 = ½*(+1) + ½*(–1) = 0.

4. А 2 В 2 (А не дурить, В не вірить). Якщо А вийняв туза, він вимагає 1 карбованець; У перевіряє і в результаті перевірки сплачує 2 рублі (виграш дорівнює +2). Якщо А вийняв двійку, він сплачує 1 карбованець; В залишається тільки прийняти (виграш дорівнює 1). Середній виграш дорівнює: 22 = ½*(+2) + ½*(–1) = ½.

Будуємо матрицю гри:

Матриця не має сідлової точки. Нижня ціна гри α = 0, верхня ціна гри β = ½. Знайдемо рішення гри у сфері змішаних стратегій. Застосовуючи формулу (4.3), отримаємо:

тобто. гравець А повинен в одній третині всіх випадків користуватися своєю першою стратегією (обманювати), а в двох третинах – другою (не обманювати). При цьому він виграватиме в середньому ціну гри = 1/3.

Значення ν = 1/3 свідчить про те, що в цих умовах гра вигідна для А і невигідна для В. Користуючись своєю оптимальною стратегією, завжди може собі забезпечити позитивний середній виграш. Зауважимо, що, якби А користувався своєю найбільш обережною (максимінною) стратегією (у разі обидві стратегії A 1 і А 2 є максимінними), він мав би середній виграш, рівний нулю. Таким чином, застосування змішаної стратегії дає можливість реалізувати свою перевагу над В, що виникає при даних правилах гри.

Визначимо оптимальну стратегію У. Маємо: q 1 *1 + q 2 *0 = 1/3, q 1 = 1/3, q 2 = 2/3. Звідки

тобто. гравець повинен в одній третині всіх випадків вірити А і сплачувати йому 1 рубль без перевірки, а в двох третинах випадків - перевіряти. Тоді він у середньому на кожну гру програватиме 1/3. Якби він мав свою мінімаксну чисту стратегію В 2 (не вірити), він на кожну гру програвав би в середньому 1/2.

Вирішенню гри 2×2 можна дати просту геометричну інтерпретацію. Нехай є гра 2×2 з матрицею

Візьмемо ділянку осі абсцис завдовжки 1 (рис. 4.1). Лівий кінець ділянки (крапка з абсцисою х = 0) зображуватиме стратегію А 1 ; правий кінець ділянки (х = 1) – стратегію А 2 . Проведемо через точки А 1 і А 2 два перпендикуляри до осі абсцис: вісь I-Iі вісь II-II. На осі I-Iбудемо відкладати виграші за стратегії A 1 ; на осі II-II-Виграші при стратегії А 2 . Розглянемо стратегію противника B1; вона дає дві точки на осях I-Iі II-IIз ординатами відповідно а 11 та а 21 . Проведемо через ці точки пряму B1B1. Очевидно, якщо при стратегії противника B 1 будемо застосовувати змішану стратегію

то наш середній виграш, рівний у цьому випадку а 11 р 1 + а 21 р 2 , Зображається точкою М на прямий В 1 B 1 ; абсцис цієї точки дорівнює р 2 . Пряму В 1 В 1 , що зображує виграш за стратегії В 1 , умовно називатимемо «стратегією В 1 ».

Очевидно, таким самим способом може бути побудована і стратегія В 2 (рис. 4.2).

Нам потрібно знайти оптимальну стратегію SA *, тобто таку, для якої мінімальний виграш (за будь-якої поведінки В) звертався б у максимум. І тому побудуємо нижню межу виграшу при стратегіях У 1 , У 2 , тобто. ламану B 1 NB 2 відзначену на рис. 4.2 жирною лінією. Ця нижня межа виражатиме мінімальний виграш гравця А за будь-яких його змішаних стратегій; точка N, у якій цей мінімальний виграш досягає максимуму, і визначає рішення та ціну гри. Неважко переконатися, що ордината точки N є ціна гри ν, а її абсцис дорівнює р 2 - частоті застосування стратегії А 2 в оптимальній змішаній стратегії S A *.

У разі рішення гри визначалося точкою перетину стратегій. Однак це не завжди буде так; на рис. 4.3 показано випадок, коли, незважаючи на наявність перетину стратегій, рішення дає для обох гравців чисті стратегії (A 2 і 2), а ціна гри ν = а 22 . У разі матриця має сідлову точку, і стратегія А 1 є свідомо невигідною, т.к. за будь-якої чистої стратегії противника вона дає менший виграш, ніж А 2 .

У разі, коли явно невигідна стратегія є у противника, геометрична інтерпретація має вигляд, представлений на рис. 4.4.

В даному випадку нижня межа виграшу збігається зі стратегією В1, стратегія В2 для противника є свідомо невигідною.

Геометрична інтерпретація дає можливість представити наочно нижню і верхню ціни гри (рис. 4.5).

Для ілюстрації побудуємо геометричні інтерпретації ігор 2×2, розглянутих у прикладах 1 та 2 (рис. 4.6 та 4.7).

Ми переконалися, що будь-яку гру 2×2 можна вирішити елементарними прийомами. Абсолютно аналогічно може бути вирішена будь-яка гра 2xn. де ми маємо лише дві стратегії, а й у противника - довільне число.

Нехай ми маємо дві стратегії: А 1 , А 2 , а противник - n стратегіями: В 1 , В 2 , …, В n . Матриця ‖a ij ‖ задана; вона складається з двох рядків та n стовпців. Аналогічно випадку двох стратегій дамо задачі геометричну інтерпретацію; n стратегій противника зобразяться n прямими (рис. 4.8). Будуємо нижню межу виграшу (ламану B 1 MNB 2) та знаходимо на ній точку N з максимальною ординатою. Ця точка дає рішення гри (стратегію ) ордината точки N дорівнює ціні гри ν, а абсцис дорівнює частоті р 2 стратегії A 2 .

В даному випадку оптимальна стратегія противника виходить застосуванням суміші двох «корисних» стратегій: В 2 і В 4, що перетинаються в точці N. Стратегія В 3 є наперед невигідною, а стратегія B 1 - невигідною при оптимальній стратегії SA *. Якщо А буде дотримуватися своєї оптимальної стратегії, то виграш не зміниться, який би зі своїх «корисних» стратегій не користувався, проте, він зміниться, якщо В перейде до стратегій B 1 або В 3 . Теоретично ігор доводиться, що з будь-якої кінцевої гри mxn є рішення, у якому число «корисних» стратегій тієї й іншої боку вбирається у найменшого з двох чисел m і n. Зокрема, з цього випливає, що гра 2xm завжди має рішення, в якому з того й іншого боку бере участь не більше двох «корисних» стратегій.

Користуючись геометричною інтерпретацією, можна дати простий спосіб вирішення будь-якої гри 2xm. Безпосередньо за кресленням знаходимо пару «корисних» стратегій противника B j і В k , що перетинаються в точці N (якщо в точці N перетинається більше двох стратегій, беремо дві з них). Ми знаємо, що якщо гравець А дотримується своєї оптимальної стратегії, то виграш не залежить від того, в якій пропорції застосовує свої «корисні» стратегії, отже,

З цих рівнянь та умови р 2 = 1 – p 1 знаходимо р1, р2 і ціну гри ν. Знаючи ціну гри, можна одразу визначити оптимальну стратегію гравця В. Для цього вирішується, наприклад, рівняння: q j a 1 j + q k a 1 k = ν, де q j + q k = 1. У випадку, коли ми маємо m стратегії, а противник - всього двома, очевидно, завдання вирішується абсолютно аналогічним способом ; Досить помітити, що, змінюючи знак виграшу на зворотний, можна перетворити гравця А з «виграє» на «програє». Можна вирішити гру без зміни знака виграшу; тоді завдання вирішується безпосередньо для, але будується не нижня, а верхня межа виграшу (рис. 4.9). На кордоні шукається точка N з мінімальною ординатою, яка є ціна гри ν.

Розглянемо і розв'яжемо кілька прикладів ігор 2×2 і 2xm, які є спрощеними зразками ігор, що мають практичне значення.

приклад 3.Сторона А посилає в район розташування противника У два бомбардувальники Iі II; Iлетить спереду, II- Ззаду. Один із бомбардувальників – заздалегідь невідомо який – має нести бомбу, інший виконує функцію супроводу. У районі противника бомбардувальники зазнають нападу винищувача сторони В. Бомбардувальники озброєні гарматами різної скорострільності. Якщо винищувач атакує задній бомбардувальник IIто по ньому ведуть вогонь гармати тільки цього бомбардувальника; якщо ж він атакує передній бомбардувальник, то ним ведуть вогонь гармати обох бомбардувальників. Імовірність ураження винищувача у першому випадку 0,3, у другому 0,7.

Якщо винищувач не збитий оборонним вогнем бомбардувальників, він вражає обрану ним ціль із ймовірністю 0,6. Завдання бомбардувальників – донести бомбу до мети; завдання винищувача – перешкодити цьому, тобто. збити бомбардувальник-носій. Потрібно вибрати оптимальні стратегії сторін:

а) для сторони А: який бомбардувальник зробити носієм?

б) для сторони: який бомбардувальник атакувати?

Рішення. Маємо простий випадок гри 2×2; виграш-імовірністьнепоразки носія. Наші стратегії: А 1 – носій – бомбардувальник I; А 2 - носій - бомбардувальник II. Стратегії противника: У 1 - атакується бомбардувальник I; У 2-атакується бомбардувальник II. Складемо матрицю гри, тобто. знайдемо середній виграш за кожної комбінації стратегій.

1. А 1 В 1 (носій I, атакується I). Носій не буде вражений, якщо бомбардувальники зіб'ють винищувач, або не зіб'ють, але він не вразить свою мету: 11 = 0,7 + 0,3 * 0,4 = 0,82.

2. А 2 В 1 (носій II, атакується I). a 21 = 1

3. А 1 В 2 (носій I, атакується II). A 12 = 1

4. А 2 В 2 (носій II, атакується II). A 22 = 0,3 + 0,7 * 0,4 = 0,58

Матриця гри має вигляд:

Нижня ціна гри – 0,82; верхня ціна 1. Матриця не має сідлової точки; рішення шукаємо у сфері змішаних стратегій. Маємо:

p 1 *0,82 + p 2 *1 = ν

p 1 *1 + p 2 *0,58 = ν

p 1 = 0,7; p 2 = 0,3

Наша оптимальна стратегія є т. е. як носій потрібно частіше вибирати Iчим II. Ціна гри дорівнює ν = 0,874. Знаючи ν, визначаємо q 1 і q 2 - частоти стратегій 1 і 2 в оптимальній стратегії противника S B *. Маємо: q 1 *0,82 + q 2 *1 = 0,874 і q 2 = 1 - q 1, звідки q 1 = 0,7; q 2 = 0,3, тобто оптимальна стратегія противника є .

приклад 4.Сторона А нападає на об'єкт, сторона - обороняє його. У сторони А – два літаки; у боку В - три зенітні знаряддя. Кожен літак є носієм потужного вражаючого засобу; для того, щоб об'єкт був вражений, достатньо, щоб до нього прорвався хоча б один літак. Літаки сторони А можуть вибирати для підходу до об'єкта будь-який із трьох напрямків: I, II, III(Рис. 4.10). Противник (сторона В) може розмістити будь-яку зі своїх знарядь на будь-якому напрямку; при цьому кожне знаряддя прострілює тільки область простору, що відноситься до даного напрямку, і не прострілює сусідні напрямки. Кожна зброя може обстріляти лише один літак; обстріляний літак уражається з ймовірністю 1. Сторона А не знає, де розміщені знаряддя; сторона не знає, звідки прилетять літаки. Завдання сторони А – вразити об'єкт; Завдання сторони В - не допустити його поразки. Знайти рішення гри.

Рішення. Гра є грою 2×3. Виграш – ймовірність ураження об'єкта. Наші можливі стратегії: А 1 - надіслати по одному літаку на два різні напрямки. А 2 - послати обидва літаки в одному напрямку. Стратегії противника: У 1 - поставити по одній зброї на кожен напрямок; У 2 - поставити два знаряддя однією напрям і одне - інше; У 3 - поставити всі три гармати на один напрямок. Складаємо матрицю гри.

1. А 1 В 1 (літаки летять по різним напрямкам; зброї розставлені по одному). Очевидно, при цьому жоден літак не прорветься до об'єкта: 11 = 0.

2. А 2 В 1 (літаки летять разом по одному напрямку; зброї розставлені по одному). Очевидно, що при цьому один літак пройде до об'єкта необстріляним: а 21 = 1.

3. А 1 В 2 (літаки летять по одному; противник захищає два напрямки і залишає незахищеним третій). Імовірність того, що хоча б один літак прорветься до об'єкта, дорівнює ймовірності того, що один з них вибере незахищений напрямок: 12 = 2/3.

4. А 2 В 2 (літаки летять разом по одному напрямку; противник захищає один напрямок двома знаряддями і один - одним, тобто фактично захищає один напрямок і залишає незахищеним два). Імовірність того, що хоча б один літак прорветься до об'єкта, дорівнює ймовірності вибору парою літаків фактично незахищеного напрямку: а 22 = 2/3.

5. А 1 В 3 (літаки летять по одному; противник захищає трьома знаряддями тільки один напрямок): а 13 = 1.

6. А 2 В 3 (літаки летять обидва разом; противник захищає трьома знаряддями тільки один напрямок). Щоб об'єкт був уражений, літаки мають вибрати незахищений напрямок: а 23 = 2/3.

Матриця гри:

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

Матриця має сідлову точку: нижня ціна гри 2/3 збігається із верхньою. Одночасно зауважуємо, що для нас (А) стратегія A 1 є свідомо невигідною. Висновок: обидві сторони і В повинні користуватися завжди своїми чистими стратегіями А 2 і 2 , тобто. ми повинні посилати літаки по 2, вибираючи випадковим чином напрямок, яким посилається пара; противник повинен ставити зброї так: два - на один напрямок, один - на інший, причому вибір цих напрямків також повинен проводитися випадково (тут, як ми бачимо, вже «чисті стратегії» включають елемент випадковості). Застосовуючи ці оптимальні стратегії, ми завжди отримуватимемо постійний середній виграш 2/3 (тобто об'єкт буде уражати ймовірність 2/3). Зауважимо, що знайдене рішення гри не є єдиним; окрім рішення в чистих стратегіях, існує ціла ділянка змішаних стратегій гравця А, які є оптимальними, від р 1 = 0 до р 1 = 1/3 (рис. 4.11).

Легко, наприклад, переконатися безпосередньо, що той самий середній виграш 2/3 вийде, якщо ми будемо застосовувати свої стратегії А1 і А2 у пропорції 1/3 та 2/3.

Приклад 5.Ті ж умови, що в попередньому прикладі, але для нас можливі чотири напрямки удару, а противник має чотири знаряддя.

Рішення.У нас, як і раніше, дві можливі стратегії: А 1 - посилати літаки по одному, А 2 - посилати два літаки разом. У противника п'ять можливих стратегій: У 1 - ставити по одній зброї на кожен напрямок; У 2 - ставити по дві зброї на два різні напрямки; У 3 - ставити дві зброї на один напрямок і по одному - на дві інші; У 4-ставити три гармати на один напрямок і одне - на інший; У 5 - ставити всі чотири гармати на один напрямок. Стратегії В4, В5 відкинемо заздалегідь як свідомо невигідні. Розмірковуючи аналогічно до попереднього прикладу, будуємо матрицю гри:

Нижня ціна гри 1/2, верхня 3/4. Матриця не має сідлової точки; рішення лежить у галузі змішаних стратегій. Користуючись геометричною інтерпретацією (рис. 4.12), виділимо «корисні» стратегії противника: 1 і 2 .

Частоти р 1 і р 2 визначимо з рівнянь: p 1 * 0 + (1 - p 1) * 1 = ν і p 1 * 5/6 + (1 - p 1) * 1/2 = ν; звідки p 1 = 3/8; p 2 = 5/8; ν = 5/8, тобто. наша оптимальна стратегія є . Користуючись нею, ми гарантуємо середній виграш 5/8. Знаючи ціну гри ν = 5/8, знаходимо частоти q 1 і q 2 «корисних» стратегій противника: q 1 *0 + (1 – q 1)*5/6 = 5/8, q 1 = ¼, q 2 = ¾. Оптимальна стратегія противника буде: .

Приклад 6.Сторона А має дві стратегії A 1 і А 2 , сторона В - чотирма B 1 , В 2 , В 3 і В 4 . Матриця гри має вигляд:

Знайти рішення гри.

Рішення. нижня ціна гри 3; верхня 4. Геометрична інтерпретація (рис. 4.13) показує, що корисними стратегіями гравця є В 1 і В 2 або В 2 і В 4:

Гравець А має безліч оптимальних змішаних стратегій: в оптимальній стратегії p 1 може змінюватися від 1/5 до 4/5. Ціна гри ν = 4. Гравець має чисту оптимальну стратегію В 2 .

§ 5. Загальні методи вирішення кінцевих ігор

Ми розглядали досі лише елементарні ігри типу 2xn, які можуть бути дуже просто вирішені і допускають зручну та наочну геометричну інтерпретацію. У загальному випадку рішення гри mxn представляє досить важке завдання, причому складність завдання та обсяг необхідних для вирішення обчислень різко зростає зі збільшенням m та n. Однак ці проблеми не носять принципового характеру і пов'язані тільки з дуже великим обсягом розрахунків, який у ряді випадків може виявитися практично нездійсненним. Принципова сторона способу відшукання рішення залишається за будь-якого m однієї й тієї ж.

Проілюструємо це з прикладу гри 3xn. Дамо їй геометричну інтерпретацію – вже просторову. Три наші стратегії А 1 , A 2 та A 3 зобразимо трьома точками на площині хОу; перша лежить на початку координат (рис. 5.1), друга і третя – на осях Охі Оуна відстані 1 від початку.

Через точки A 1 , А 2 та А 3 проводяться осі I – I, II – IIі III – III, перпендикулярні до площини хОу. На осі I – Iвідкладаються виграші за стратегії А 1 на осях II – IIі III – III- Виграші при стратегіях А2, А3. Кожна стратегія противника B j зобразиться площиною, що відсікає на осях I – I, II – IIі III – IIIвідрізки, рівні виграшам за відповідних стратегій A 1 , А 2 і А 3 і стратегії В j . Побудувавши таким чином усі стратегії супротивника, ми отримаємо сімейство площин над трикутником A 1 , А 2 та А 3 (рис. 5.2). Для цього сімейства також можна побудувати нижню межу виграшу, як ми це робили у випадку 2xn і знайти на цій межі точку N з максимальною висотою над площиною хОу. Ця висота і буде ціною гри.

Частоти p 1 , р 2 , р 3 стратегій A 1 , А 2 і А 3 оптимальної стратегії S A * будуть визначатися координатами (х, у) точки N, а саме: p 2 = x, p 3 = y, p 1 = 1 – p 2 – p 3 . Однак таке геометрична побудованавіть для випадку 3xn нелегко можна здійснити і вимагає великої витрати часу та зусиль уяви. У загальному випадку гри воно переноситься в m-мірне простір і втрачає будь-яку наочність, хоча вживання геометричної термінології в ряді випадків може виявитися корисним. При вирішенні ігор mxn практично зручніше користуватися не геометричними аналогіями, а розрахунковими аналітичними методами, тим паче, що з вирішення завдання обчислювальних машинах ці методи єдино придатні.

Всі ці методи по суті зводяться до розв'язання задачі шляхом послідовних проб, але впорядкування послідовності проб дозволяє побудувати алгоритм, що веде до вирішення найбільш економічним способом. Тут ми коротко зупинимося одному розрахунковому методі рішення ігор mxn - так званому методі «лінійного програмування». Для цього дамо спочатку загальну постановку задачі про знаходження рішення гри mxn. Нехай дана гра mxn з m стратегіями A 1 , А 2 , …, А m гравця А та n стратегіями B 1 , B 2 , …, B n гравця В та задана платіжна матриця ‖a i j ‖. Потрібно визначити рішення гри, тобто. дві оптимальні змішані стратегії гравців А та В

де p 1 + p 2 + … + p m = 1; q 1 + q 2 + … + q n = 1 (деякі з чисел p i і q j можуть дорівнювати нулю).

Наша оптимальна стратегія S A * повинна забезпечувати нам виграш, не менший ν, за будь-якої поведінки противника, і виграш, рівний ν, при його оптимальній поведінці (стратегія S B *). Аналогічно стратегія S B * повинна забезпечувати противнику програш, не більший ν, за будь-якої нашої поведінки і рівний ν при нашій оптимальній поведінці (стратегія S A *).

Величина ціни гри в цьому випадку нам невідома; вважатимемо, що вона дорівнює деякому позитивному числу. Вважаючи так, ми не порушуємо спільності міркувань; щоб було ν > 0, очевидно, достатньо, щоб усі елементи матриці ‖a i j ‖ були неотрицательными. Цього завжди можна досягти, додаючи до елементів ‖a i j ‖ досить велику позитивну величину L; при цьому ціна гри збільшиться на L, а рішення не зміниться.

Нехай ми вибрали свою оптимальну стратегію SA*. Тоді наш середній виграш при стратегії B j противника дорівнюватиме: a j = p 1 a 1j + p 2 a 2j + … + p m a mj . Наша оптимальна стратегія S A * має ту властивість, що за будь-якої поведінки противника забезпечує виграш не менший, ніж ν; отже, будь-яке з чисел a j не може бути меншим за ν. Отримуємо низку умов:

Розділимо нерівності (5.1) на позитивну величину і позначимо

Тоді умови (5.1) запишуться у вигляді

де ξ 1 , ξ 2 , …, ξ m - невід'ємні числа. Оскільки р 1 + p 2 + … + p m = 1, то величини ξ 1 , ξ 2 , …, ξ m задовольняють умову

(5.3) ξ 1 + ξ 2 + … + ξ m = 1/ν.

Ми хочемо зробити свій гарантований виграш максимально можливим; Вочевидь, у своїй права частина рівності (5.3) приймає мінімальне значення. Таким чином, завдання знаходження рішення гри зводиться до наступної математичної задачі: визначити невід'ємні величини ξ 1 , ξ 2 , …, ξ m , що задовольняють умовам (5.2), так, щоб їх сума Φ = ξ 1 + ξ 2 + … + ξ m була мінімальною.

Зазвичай під час вирішення завдань, що з знаходженням екстремальних значень (максимумів і мінімумів), функцію диференціюють і прирівнюють похідні нулю. Але такий прийом у разі некорисний, оскільки функція Φ, яку необхідно звернути у мінімум, лінійна, та її похідні за всіма аргументами рівні одиниці, тобто. ніде не перетворюються на нуль. Отже, максимум функції досягається десь на межі області зміни аргументів, що визначається вимогою невід'ємності аргументів та умовами (5.2). Прийом знаходження екстремальних значень за допомогою диференціювання непридатний і в тих випадках, коли для вирішення гри визначається максимум нижньої (або мінімум верхньої) межі виграшу, як ми, наприклад, робили під час вирішення ігор 2xn. Дійсно, нижня межа складена з ділянок прямих ліній, і максимум досягається не в точці, де похідна дорівнює нулю (такої точки взагалі немає), а на межі інтервалу або в точці перетину прямолінійних ділянок.

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

Потрібно знайти невід'ємні значення величин ξ 1 , ξ 2 , …, ξ m , що задовольняють умовам (5.4) і водночас звертають до мінімуму задану однорідну лінійну функцію величин ξ 1 , ξ 2 , …, ξ m (лінійну форму): Φ = c 1 ξ 1 + c 2 ξ 2 + … + c m ξ m

Легко переконатися, що поставлене вище завдання теорії ігор є окремим випадком задачі лінійного програмування при с 1 = с 2 = … = с m = 1. З першого погляду може здатися, що умови (5.2) не еквівалентні умовам (5.4), оскільки замість знаків рівності містять знаки нерівності. Однак знаки нерівності легко позбутися, вводячи нові фіктивні невід'ємні змінні z 1 , z 2 , …, z n і записуючи умови (5.2) у вигляді:

Форма Φ, яку потрібно звернути в мінімум, дорівнює Φ = ξ 1 + ξ 2 + … + ξ m . Апарат лінійного програмування дозволяє шляхом порівняно невеликої кількості послідовних проб підібрати величини ξ 1 , 2 , …, m , що задовольняють поставленим вимогам. Для більшої ясності ми продемонструємо застосування цього апарату прямо на матеріалі вирішення конкретних ігор.

приклад 1.Потрібно знайти рішення гри 3×3, даної в прикладі 2 § 1, з матрицею:

Щоб зробити все а ij невід'ємним, додамо до всіх елементів матриці L = 5. Отримаємо матрицю:

При цьому ціна гри збільшиться на 5, а рішення не зміниться.

Визначимо оптимальну стратегію SA*. Умови (5.2) мають вигляд:

де ξ 1 = p 1 /ν, ξ 2 = p 2 /ν, ξ 3 = p 3 /ν. Щоб позбавитися знаків нерівності, введемо фіктивні змінні z 1 , z 2 , z 3 ; умови (5.6) запишуться у вигляді:

Лінійна форма Φ має вигляд: Φ = ξ 1 + ξ 2 + ξ 3 і має бути зроблена якнайменше. Якщо всі три стратегії є «корисними», то всі три фіктивні змінні z 1 , z 2 , z 3 звернуться в нуль (тобто виграш, рівний ціні гри ν, буде досягатися при кожній стратегії B j). Але ми поки що не маємо підстав стверджувати, що всі три стратегії є «корисними». Щоб перевірити це, спробуємо висловити форму Φ через фіктивні змінні z 1 , z 2 , z 3 і подивимося, чи досягнемо ми, вважаючи їх рівними нулю, мінімуму форми. Для цього дозволимо рівняння (5.7) щодо змінних ξ 1 , ξ 2 , ξ 3 (тобто висловимо ξ 1 , ξ 2 , ξ 3 через фіктивні змінні z 1 , z 2 , z 3):

Складаючи ξ 1 , ξ 2 , ξ 3 отримаємо: Φ = 1/5 + z 1 /20 + z 2 /10 + z 3 /20. Тут коефіцієнти за всіх z позитивні; отже, будь-яке збільшення z 1 , z 2 , z 3 понад нуль може призвести тільки до збільшення форми Φ, а ми хочемо, щоб вона була мінімальною. Отже, значеннями z 1 , z 2 , z 3 , що обертають форму в мінімум, є z 1 = z 2 = z 3 = 0. Отже, мінімальне значення форми Φ: 1/ν = 1/5, звідки ціна гри ν = 5. Підставляючи нульові значення z 1 , z 2 , z 3 у формули (5.8), знаходимо: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20, або, помножуючи їх на ν, р 1 = 1/4, р2 = 1/2, р3 = 1/4. Таким чином, оптимальну стратегію А знайдено: , тобто. ми повинні в одній чверті всіх випадків писати цифру 1, у половині випадків 2 та в іншій чверті випадків 3.

Знаючи ціну гри ν = 5, можна вже відомими способами знайти оптимальну стратегію супротивника . Для цього скористаємося нашими будь-якими двома «корисними» стратегіями (наприклад, А2 та А3) і напишемо рівняння:

9q 1 + 11 (1-q 2 -q 1) = 5,

звідки q 1 = q3 = 1/4; q 2 = 1/2. Оптимальна стратегія противника буде такою самою, як наша: . Тепер повернемося до початкової (не перетвореної) гри. Для цього потрібно тільки від ціни гри ν = 5 відібрати величину L = 5, додану до елементів матриці. Отримаємо ціну вихідної гри v0 = 0. Отже, оптимальні стратегії обох сторін забезпечують середній виграш, що дорівнює нулю; гра однаковою мірою вигідна чи невигідна обох сторін.

приклад 2.Спортивний клуб А має у своєму розпорядженні три варіанти складу команди А 1 , А 2 і А 3 . Клуб В - також трьома варіантами B 1 , 2 і 3 . Подаючи заявку для участі у змаганні, жоден із клубів не знає, який склад обере супротивник. Імовірності виграшу клубу А за різних варіантів складів команд, приблизно відомі з досвіду минулих зустрічей, задані матрицею:

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

Рішення. Нижня ціна гри – 0,4; верхня 0,6; рішення шукаємо у сфері змішаних стратегій. Щоб не мати стосунків з дробами, помножимо всі елементи матриці на 10; при цьому ціна гри збільшиться у 10 разів, а рішення не зміниться. Отримаємо матрицю:

Умови (5.5) мають вигляд:

а умова мінімуму Φ = ξ 1 + ξ 2 + ξ 3 = min.

Перевіряємо, чи всі три стратегії противника є «корисними». Як гіпотезу спочатку припускаємо, що фіктивні змінні z 1 , z 2 , z 3 рівні нулю, і для перевірки розв'язуємо рівняння (5.10) щодо ξ 1 , ξ 2 , ξ 3:

(5.12) 136Φ = 30 +13z 1 +18z 2 – 51z 3

Формула (5.12) показує, що збільшення змінних z 1 і z 2 в порівнянні з їх передбачуваним значенням нуль може тільки збільшити Φ, тоді як збільшення 3 може зменшити Φ. Однак збільшення z 3 треба робити обережно, щоб величини ξ 1 , 2 , 3 , що залежать від z 3 , не стали при цьому негативними. Тому покладемо в правих частинах рівностей (5.11) величини z 1 і z 2 рівними нулю, а величину z 3 будемо збільшувати до допустимих меж (поки яка-небудь з величин ξ 1 , 2 , 3 не звернеться в нуль). З другої рівності (5.11) видно, що збільшення z 3 «безпечне» для величини 2 - вона від цього тільки збільшується. Що стосується величин ξ 1 і 3 , то тут збільшення z 3 можливе тільки до деякої межі. Розмір ξ 1 перетворюється на нуль при z 3 = 10/23; величина 3 звертається в нуль раніше, вже при z 3 = 1/4. Отже, даючи z 3 максимально допустиме значення z 3 = 1/4, ми при цьому звернемо в нуль величину ξ 3 .

Щоб перевірити, чи обертається мінімум форма Φ при z 1 = 0, z 2 = 0, ξ 3 = 0, виразимо інші (не рівні нулю) змінні через імовірно рівні нулю z 1 , z 2 , ξ 3 . Дозволяючи рівняння (5.10) щодо ξ 1 , ξ 2 і z 3 отримаємо:

(5.13) 32Φ = 7 + Зz 1 + 4z 2 + ξ 3

З формули (5.13) видно, що будь-яке збільшення z 1 , z 2 , 3 понад їх передбачуваних нульових значень може тільки збільшити форму Φ. Отже, рішення гри знайдено; воно визначається значеннями z 1 = z 2 = ξ 3 = 0, звідки ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4. Підставляючи формулу (5.13), знаходимо ціну гри ν: 32Φ = 7 = 32/ν; ν = 32/7. Наша оптимальна стратегія: . "Корисні" стратегії (склади A 1 і A 2) повинні застосовуватися з частотами 1/7 і 6/7; склад A3 - ніколи не застосовуватися.

Щоб знайти оптимальну стратегію противника, у випадку можна чинити так: змінити знак виграшу на зворотний, додати до елементів матриці постійну величину L, щоб зробити їх невід'ємними, і вирішувати завдання за противника так само, як ми вирішували її за себе. Однак те, що нам вже відома ціна гри ν, дещо спрощує завдання. До того ж у даному конкретному випадку завдання додатково спрощується тим, що у вирішенні беруть участь лише дві «корисні» стратегії противника В 1 і В 2, так як величина z 3 не дорівнює нулю, і, отже, при стратегії В 3 ціна гри не досягається . Вибираючи будь-яку «корисну» стратегію гравця А, наприклад, A 1 можна знайти частоти q 1 і q 2 . Для цього пишемо рівняння 8q1+2(1 – q1) = 32/7, звідки q1=3/7, q2=4/7; оптимальна стратегія противника буде: , тобто. противник не повинен користуватися складом 3 , а склади 1 і 2 повинні застосовуватися з частотами 3/7 і 4/7.

Повертаючись до початкової матриці, визначимо справжню ціну гри ν 0 = 32/7:10 = 0,457. Це означає, що за великої кількості зустрічей кількість перемог клубу А складе 0,457 всіх зустрічей.

§ 6. Наближені методи вирішення ігор

Часто у практичних завданнях немає необхідності знаходити точне рішення гри; достатньо знайти наближене рішення, що дає середній виграш, близький до ціни гри. Орієнтовне знання ціни гри ν може дати вже простий аналіз матриці та визначення нижньої (α) та верхньої (β) цін гри. Якщо α і β близькі, практично немає потреби займатися пошуками точного рішення, а досить вибрати чисті мінімаксні стратегії. У випадках, коли α та β не близькі, можна отримати прийнятне для практики рішення за допомогою чисельних методів вирішення ігор, з яких ми коротко висвітлимо метод ітерацій.

Ідея методу ітерацій зводиться до наступного. Розігрується «думковий експеримент», у якому противники А і В застосовують один проти одного свої стратегії. Експеримент складається із послідовності елементарних ігор, кожна з яких має матрицю заданої гри. Починається з того, що ми (гравець А) вибираємо довільно одну зі своїх стратегій, наприклад, А i . Противник цього відповідає тій своєї стратегією B j , яка найвигідніша нам, тобто. звертає виграш за стратегії А i в мінімум. На цей хід ми відповідаємо тією своєю стратегією А k, яка дає максимальний середній виграш при застосуванні противником стратегії Bj. Далі – знову черга супротивника. Він відповідає на нашу пару ходів A i і А k тією своєю стратегією B j , яка дає нам найменший середній виграш за цих двох стратегій (A i , Ак), і так далі. На кожному кроці ітераційного процесу кожен гравець відповідає на будь-який хід іншого гравця тією своєю стратегією, яка є оптимальною щодо всіх його попередніх ходів, які розглядаються як деяка змішана стратегія, в якій чисті стратегії представлені у пропорціях, що відповідають частоті їх застосування.

Такий спосіб є як би модель реального практичного «навчання» гравців, коли кожен з них на досвіді промацує спосіб поведінки противника і намагається відповідати на нього вигідним для себе чином. Якщо таку імітацію процесу навчання продовжуватиме досить довго, то середній виграш, що припадає на одну пару ходів (елементарну гру), прагнутиме ціни гри, а частоти р 1 … р m ; q 1 … q n , з якими зустрічаються стратегії гравців у цьому розіграші, наближатимуться до частот, що визначають оптимальні стратегії. Розрахунки показують, що збіжність методу дуже повільна, проте швидкодіючих рахункових машин це перешкодою.

Проілюструємо застосування ітераційного методу з прикладу гри 3×3, вирішеної прикладі 2 попереднього параграфа. Гра задана матрицею:

У таблиці 6.1 наведено перші 18 кроків ітераційного процесу. У першому стовпці надано номер елементарної гри (пари ходів) n; у другому – номер iобраної стратегії гравця А; у наступних трьох – «накопичений виграш» за перші nігор при стратегіях противника B 1 , 2 , 3 . Мінімальне із цих значень підкреслено. Далі йде номер jстратегії, обраної противником, і відповідно накопичений виграш за nігор при стратегіях A1, А2, А3 з цих значень підкреслено зверху максимальне. Підкреслені значення визначають вибір стратегії у відповідь іншого гравця. У наступних графах послідовно наведено: мінімальний середній виграш ν , що дорівнює мінімальному накопиченому виграшу, поділеному на число ігор n; максимальний середній виграш , що дорівнює максимальному накопиченому виграшу, поділеному на n, та їхнє середнє арифметичне ν* = (ν + )/2. При збільшенні nвсі три величини ν і ν* будуть наближатися до ціни гри ν, але величина ν*, природно, буде наближатися до неї порівняно швидше.

Таблиця 6.1.

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

§ 7. Методи вирішення деяких нескінченних ігор

Нескінченною грою називається гра, в якій принаймні одна зі сторін має безліч стратегій. Загальні методи вирішення таких ігор ще мало розроблені. Однак для практики можуть представляти інтерес деякі окремі випадки, які допускають порівняно просте рішення. Розглянемо гру двох противників А і В, кожен із яких має нескінченну (незліченну) безліч стратегій; ці стратегії для гравця А відповідають різним значенням параметра, що безперервно змінюється х, а для В - параметра у. В даному випадку замість матриці ‖a ij ‖ гру визначає деяка функція двох безперервно змінних аргументів а (х, у), яку ми називатимемо функцією виграшу (зауважимо, що сама функція а (х, у)необов'язково має бути безперервною). Функцію виграшу а(х, у)можна уявити геометрично деякою поверхнею а (х, у)над областю зміни аргументів (х, у)(рис. 7.1)

Аналіз функції виграшу а(х, у)провадиться аналогічно аналізу платіжної матриці. Спочатку знаходиться нижня ціна гри α; для цього визначається для кожного хмінімум функції а(х, у)по всім у: , потім шукається максимальне з цих значень по всьому х(Максимін):

Верхня ціна гри (мінімакс) визначається аналогічно:

Розглянемо випадок коли α = β. Так як ціна гри завжди укладена між α і β, то загальне їх значення і є ν. Рівність α = β означає, що поверхня а(х, у)має сідлову точку, тобто таку точку з координатами х 0 , у 0 , в якій а(х, у)є одночасно мінімальним по уі максимальним за х(Мал. 7.2).

Значення а(х, у)у цій точці і є ціна гри ν: ν = а(х 0, у 0).Наявність сідлової точки означає, що ця нескінченна гра має рішення у сфері чистих стратегій; х 0 , у 0являють собою оптимальні чисті стратегії А і В. У загальному випадку, коли α ≠ β гра може мати рішення тільки в області змішаних стратегій (можливо, не єдине). Змішана стратегія для нескінченних ігор є деяким розподілом ймовірностей для стратегій хі у, що розглядаються як випадкові величини. Цей розподіл може бути безперервним і визначатися густиною f 1 (х)і f 2 (у); може бути дискретним, і тоді оптимальні стратегії складаються з набору окремих чистих стратегій, що вибираються з якимись відмінними від нуля імовірностями.

У разі коли нескінченна гра не має сідлової точки, можна дати наочну геометричну інтерпретацію нижньої та верхньої ціни гри. Розглянемо нескінченну гру з функцією виграшу а(х, у)та стратегіями х, у, що заповнюють безперервно відрізки осей (х 1, х 2)і (у 1, у 2). Щоб визначити нижню ціну гри α, потрібно "подивитися" на поверхню а(х, у)з боку осі у, тобто. спроектувати її на площину хОа(Мал. 7.3). Отримаємо деяку фігуру, обмежену з боків прямими x = x 1 і х = х 2, а зверху і знизу - кривими К В і К Н. Нижня ціна гри α, очевидно, є не що інше, як максимальна ордината кривої К Н.

Аналогічно, щоб знайти верхню ціну гри β, потрібно «подивитися» на поверхню а(х, у)з боку осі х(спроектувати поверхню на площину уОа) та знайти мінімальну ординату верхньої межі К В проекції (рис, 7.4).

Розглянемо два елементарні приклади нескінченних ігор.

приклад 1.Гравці А та В мають кожну незліченну кількість можливих стратегій. хі у, причому 0 ≤ х ≤ 1; 0 ≤ у ≤ 1. Функція виграшу за а дана виразом а (х, у) – (х – у) 2 . Знайти рішення гри.

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

У разі максимум досягається завжди межі інтервалу (при х = 0 чи х = 1), тобто. він дорівнює тій із величин у 2; (1 – у) 2 яка більша. Зобразимо графіки цих функцій (рис. 7.6), тобто. проекцію поверхні а(х, у)на площину уОа. Жирною лінією на рис. 7.6 показано функцію . Очевидно, її мінімальне значення досягається за у = 1/2 і дорівнює 1/4. Отже, найвища ціна гри β = 1/4. У цьому випадку верхня ціна гри збігається із ціною гри ν. Дійсно, гравець А може застосувати змішану стратегію S А = , До якої крайні значення х = 0 і х = 1 входять з однаковими частотами; тоді за будь-якої стратегії у гравця У середній виграш гравця А дорівнюватиме: ½у 2 + ½(1 – у) 2 . Неважко переконатися, що ця величина за будь-яких значень уміж 0 і 1 має значення не менше ¼: ½у 2 + ½(1 – у) 2 ≥ ¼.

Таким чином, гравець А застосуванням цієї змішаної стратегії може гарантувати собі виграш, що дорівнює верхній ціні гри; так як ціна гри не може бути більшою за верхню ціну, то дана стратегія SA оптимальна: SA = S A *.

Залишається знайти оптимальну стратегію гравця В. Очевидно, що якщо ціна гри ν дорівнює верхній ціні гри β, то оптимальною стратегією гравця буде завжди його чиста мінімаксна стратегія, що гарантує йому верхню ціну гри. У разі такий стратегією є у 0 = ½. Справді, за цієї стратегії, хоч би що робив гравець А, виграш його більше ¼. Це випливає з очевидної нерівності (x – ½) 2 = x(x –1) + ¼ ≤ ¼

приклад 2.Сторона А («ми») веде стрілянину літаком В противника. Для того, щоб ухилитися від обстрілу, противник може маневрувати з деяким навантаженням у, якій він на свій розсуд може надавати значення від у= 0 (прямолінійний рух) до у = уmax(Політ по колу максимальної кривизни). Будемо рахувати уmaxодиницею виміру, тобто. покладемо уmax= 1. У боротьбі з противником ми можемо застосовувати прицільні пристрої, засновані на тій чи іншій гіпотезі про рух мети за час польоту снаряда. Перевантаження хпри цьому гіпотетичному маневрі може бути рівною будь-якому значенню від 0 до 1. Наше завдання - вразити противника; завдання противника – залишитися неураженим. Можливість поразки для даних хі уприблизно виражається формулою: а(х, у) = , де у- навантаження, що застосовується противником; х - навантаження, врахована в прицілі. Потрібно визначити оптимальні стратегії обох сторін.

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

Це - циліндрична поверхня, що утворюють яку паралельні бісектрисі координатного кута. хОу, А переріз площиною, перпендикулярною до твірної, є крива типу нормальної кривої розподілу. Користуючись запропонованою вище геометричною інтерпретацією нижньої та верхньої ціни гри, знаходимо β = 1 (рис. 7.8) та (рис. 7.9). Гра не має сідлової точки; рішення потрібно шукати у сфері змішаних стратегій. Завдання певною мірою аналогічне задачі попереднього прикладу. Дійсно, за малих значень kфункція поводиться приблизно як функція –(х – у) 2, та рішення гри вийде, якщо у вирішенні попереднього прикладу поміняти ролями гравців A та В; тобто. нашою оптимальною стратегією буде чиста стратегія х = 1/2, а оптимальна стратегія противника S B = полягатиме в тому, щоб з однаковими частотами застосовувати крайні стратегії у = 0 і y = 1. Це означає, що ми повинні у всіх випадках застосовувати приціл, розрахований на навантаження x = 1/2, а противник повинен у половині всіх випадків взагалі застосовувати маневру, а половині - максимально можливий маневр.

Мал. 7.8 Мал. 7.9.

Легко довести, що це рішення буде справедливим для значень k ≤ 2. Справді, середній виграш за стратегії супротивника S B = і за нашої стратегії хвиражається функцією , яка для значень k ≤ 2 має один максимум при х = 1/2, що дорівнює нижній ціні гри α. Отже, застосування стратегії S B гарантує противнику програш, не більший α, з чого зрозуміло, що α – нижня ціна гри – і є ціна гри ν.

При k > 2 функція а(х) має два максимуми (рис. 7.10), розташовані симетрично щодо х = 1/2 у точках x 0 і 1 – х 0, причому значення х 0 залежить від k.

Очевидно, при k= 2 х 0 = 1 - x 0 = ½; при збільшенні kточки х 0 і 1 – х 0 розсуваються, підходячи ближче до крайніх точок (0 та 1). Отже, рішення гри залежатиме від k. Задамо конкретне значення k, наприклад, k = 3, і знайдемо рішення гри; для цього визначимо абсцис х 0 максимуму кривої а(х). Прирівнюючи похідну нулю функції а(х), напишемо рівняння для визначення x 0:

Це рівняння має три корені: х = 1/2 (де досягається мінімум) і х 0 1 - х 0 де досягаються максимуми. Вирішуючи рівняння чисельно, знаходимо приблизно x 0 ≈ 0,07; 1 - x 0 ≈ 0,93.

Доведемо, що рішенням гри в цьому випадку буде наступна пара стратегій:

За нашої стратегії та стратегії супротивника усередній виграш дорівнює

Знайдемо мінімум a 1 (y) при 0< у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

Вважаючи у = 1/2, отримуємо

що більше, ніж a 1 (0); отже, ціна гри не менше, ніж 1 (0):

Тепер припустимо, що противник застосовує стратегію SB*, а ми – стратегію х. Тоді середній виграш буде

Але ми вибрали х 0 саме так, щоб за х = х 0 досягався максимум виразу (7.2); отже,

тобто. противник застосуванням стратегії S B * може не допустити програшу, більшого за 0,530; отже, ν = 0,530 і є ціна гри, а стратегії S A * та S B * дають рішення. Це означає, що ми повинні з однаковою частотою користуватися прицілами з х = 0,07 і x = 0,93, а противник з однаковою частотою не маневрувати та маневрувати з максимальним навантаженням.

Зауважимо, що виграш ν = 0,530 помітно більший, ніж нижня ціна гри , яку ми могли б забезпечити собі, застосовуючи свою максимальну стратегію x 0 = 1/2.

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

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

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