2.4. Елементи теорії ігор

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

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

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

Нехай гравець А має в своєму розпорядженні m альтернативних рішень, а гравець В – n (гра m  n), тобто і – множини можливих рішень гравців А і В відповідно. Пару (х, у) прийнятих рішень називають бістратегією або наслідком гри.

Кожній бістратегії (х, у) ставлять у відповідність два дійсних числа F_A(x, y) та F_В(x, y). Число F_A(x, y) інтерпретують як виграш гравця А, а F_В(x, y) – виграш гравця В (від’ємний виграш прийнято називати програшем).

Припустимо, що значення F_ij  F(x, y) виграшу гравця А (програшу гравця В) для кожної бістратегії (x_і, y_j) відоме. Всі значення {F_ij} можна записати у вигляді матриці, рядки якої відповідають стратегіям {x_i} гравця А, а стовпчики – стратегіям {y_j} гравця В.

Таку матрицю називають платіжною матрицею або матрицею гри.

yj хі	y1	y2	…	yn
x1	F11	F12	…	F1n
x2	F21	F22	…	F2n
…	…	…	…	…
xm	Fm1	Fm2	…	Fmn

Нехай гравець А вибирає стратегію х_і; тоді в найгіршому випадку він отримає виграш min (F_ij). Передбачаючи таку можливість, гравець А повинен вибрати таку стратегію, щоб максимізувати свій мінімальний виграш :

. (2.4.1)

Величина  – гарантований виграш гравця А – називається нижньою ціною гри. Стратегія х_і0, яка забезпечує отримання , називається максимінною стратегією.

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

. (2.4.2)

Величина  називається верхньою ціною гри, а відповідна стратегія y_j0 – мінімаксною.

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

, (2.4.3)

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

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

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

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

Розв’яжемо цю задачу. Перевіримо, чи має вихідна матриця сідлову точку. Для цього знаходимо мінімальні елементи в її рядках: (22, 21, 20), і максимальні в стовпчиках (22, 23, 24). Максимальним серед мінімальних елементів рядків є число  = 22, а мінімальним серед максимальних елементів стовпчиків – число  = 22. Отже,  =  = 22. Це число є ціною гри. Гра має сідлову точку, яка відповідає варіанту А випуску нової моделі взуття. Об’єм випуску даної моделі забезпечить прибуток 22 у.г.о при будь-якому стані попиту.

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

 =  = . (2.4.4)

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

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

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

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

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

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

Легко довести, що в будь-якому випадку ціна гри  знаходитиметься у межах

    . (2.4.5)

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

Розглянемо гру, матриця якої має розмірність m  n:

. (2.4.6)

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

При оптимальній стратегії гравця А має виконуватися умова

, (2.4.7)

а при оптимальній стратегії гравця В – умова

. (2.4.8)

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

(2.4.9)

Ціна гри невідома, однак можна вважати, що   0. Розділимо всі доданки нерівностей системи (2.4.9) на . Отримаємо нову систему:

(2.4.10)

де .

Оскільки (з точки зору гравця А) розв’язок гри має максимізувати значення , то функція має набути мінімального значення. Тобто, ми отримали задачу лінійного програмування: мінімізувати цільову функцію при виконанні обмежень (2.4.10) і умов не-від’ємності змінних t_i.

Розв’язуючи сформульовану задачу, знаходимо t_i і величину 1/, звідки можна отримати х_і = t_i.

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

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

Приклад. Знайти розв’язок гри, заданої матрицею

.

Перш за все перевіримо наявність сідлової точки в даній матриці. Для цього знайдемо мінімальні елементи в рядках (2, 4) і максимальні в стовпчиках (6, 5). Отже, нижня ціна гри  = max (2, 4) = 4, а верхня ціна гри  = min (6, 5) = 5. Оскільки   , то розв’язком гри є змішані стратегії, а ціна гри  буде знаходитись в межах 4    5.

Припустимо, що для гравця А стратегія задається вектором U = (u₁, u₂). Тоді, згідно теореми про оптимальну змішану стратегію, при застосуванні гравцем В стратегій В₁ чи В₂ гравець А отримає середній виграш, рівний ціні гри, тобто

(при В₁),

(при В₂).

Окрім двох записаних рівнянь відносно додамо ще одне, яке пов’язує ці частоти:

.

Розв’язуючи отриману систему трьох рівнянь з трьома невідомими, знаходимо: ; ; .

Тепер знайдемо оптимальну стратегію для гравця В. Нехай стратегія цього гравця задається вектором Z = (z₁, z₂). Тоді

Розв’язок наведеної системи рівнянь: .

Отже, розв’язком гри є змішані стратегії та , а ціна гри .

Подамо геометричну інтерпретацію розв’язку даної гри. Для цього в системі координат uOz на осі Ou відкладемо відрізок одиничної довжини А₁А₂, кожній точці якого поставимо у відповідність деяку змішану стратегію U^*. Точці А₁ відповідатиме стратегія А₁(0, 1), точці А₂ – стратегія А₂(1, 0).

В точках А₁ і А₂ до проведеної прямої поставимо перпендикуляри і на отриманих прямих будемо відкладати виграші гравців. На першому перпендикулярі відкладемо виграш гравця А при стратегії А₁, а на другому – при стратегії А₂. Якщо гравець А застосує стратегію А₁, то його виграш при стратегії В₁ гравця В дорівнюватиме 2 а при В₂ – 5.

Якщо гравець А застосує стратегію А₂, то його виграш відповідно рівний 6 і 4. З’єднуючи точки В₁ та В₂ між собою, отримаємо дві прямі, віддаль від яких до осі Ou визначає середній виграш при довільному сполученні будь-яких стратегій (рис.2.4).

Отже, ординати точок, що належать до ламаної лінії визначають мінімальний виграш гравця А при застосуванні ним довільних змішаних стратегій. Ця мінімальна величина є максимальною в точці М. Тобто, цій точці відповідає оптимальна стратегія U*, а її ордината рівна ціні гри. Проекція точки М на відрізок А₁А₂ поділить його у співвідношенні, яке покаже долю кожної чистої стратегії в оптимальній змішаній.

Аналогічно розв’язують задачі і для гравця В.

Рис.2.4.