Прийняття управлінських рішень - Петруня Ю.Є. - Розділ 9. Теорія ігор. Прийняття управлінських рішень в умовах ризику та невизначеності

9.1. Поняття і класифікація ігор в економіці

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

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

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

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

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

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

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

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

Фх(Ai,Bj) + ф2(Aj,Bj) = 0. Виграш одного гравця дорівнює програшу другого: cp/Aj,Bj) = <p(A,,Bj); q^(A,Bj) =-q>(A,Bj).

Позначимо ф(Aj, Bj) = , aj - виграш першого гравця (програш

другого), якщо перший гравець вибрав стратегію At , а другий гравець

- стратегію - Bj. Розглядатимемо стратегічні ігри, задані платіжною матрицею А: A = (atj)mxn. Розглядаються нижня ціна гри а, верхня

ціна гри Я та ціна гри V: a = maxmin ац або ос = max aj, де

, j ,

aj = min ац. Я = minmaxац або Я = minЯ ■, де Я, = maxац. а < V< Я.

j j і j j

Дії гравців вважаються обережними.

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

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

- значення Я j , а за рахунок вибору своєї стратегії він мінімізує свій програш. Якщо V = = а = Я, то гра розв'язана в чистих стратегіях, вона має сідлоеу точку - елемент матриці A : alk, який одночасно мінімальний у /-му рядку та максимальний у k-му стовпці. У цьому випадку V - чиста ціна гри, або ціна гри. Причому жодному з гравців не вигідно відхилятися

від своїх оптимальних стратегій A = Al та B = Bk, оскільки перший

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

Якщо а # Я, то гру розв'язують у змішаних стратегіях. Перший гравець має m стратегій: Aj,..., Лт з відповідними ймовірностями використання цих стратегій: д^,..., xm ^Y_xt = lj. Другий гравець має n стратегій: B1,_, Bn з відповідними ймовірностями їх використання:

Уі-,--,yn |zУі = ^

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

т * -

2 х*аіі > V (і = 1, п) гарантований виграш першого гравця;

2 а у у** < V (і = 1, т) - гарантований програш другого гравця.

і=1

Розглянемо гру 2 х 2: А = (ау )2х2. Для знаходження оптимальних

* . * * . *

змішаних стратегій х1 і х2 для першого гравця та у1 і у2 для другого

розв'язуємо відповідні системи:

* * -гг Г * * т7

ап х1 + а21х2 = V, а11 у1 + а12 у2 = V,

< X* + X* = 1^, І СІ21 у* + ¿^2у* = V,

X* + X* = 1. + у* = 1.

Отримуємо такі оптимальні стратегії х*, х*, у*, у* та ціну гри V:

*__а22 ~ а21_ *__а11 ~ а12_

х1 - , х2 - ,

а11 + а 22 - а12 - а21 а11 + а22 - а12 - а 21

*__а 22 ~ а12_ *__а11 ~ а 21_

у1 - , у 2 - ,

V _ а22 а11 ~ а12 а21

Графічна інтерпретація розв'язування гри 2 х 2 зображена на рис. 9.1:

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

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

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

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

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

а11 х1* + ... + ат1х*т ^ , < ................. ......................

а1пх* + ... + атпх*т ^ .

Ділимо ліву та праву частини нерівностей на V (V > 0) і позначає-

х* / - т *

мо - = іі і = 1,ті. Оскільки х* = 1, враховуючи, що перший гра-

V . '=1

вець намагається максимізувати свій виграш, отримуємо таку задачу

лінійного програмування:

1

2 = у = Ч + ... + Іт ~> тіП; апЧ + ... + ат1Іт ^ 1,

а1пЧ + ... + атпІт ^ 1;

Іі > 0, і = 1, т.

Маємо оптимальний план задачі лінійного програмування Т*, ціну гри Vта оптимальну змішану стратегію першого гравця X* = {х*,..., х*т}:

V 1 1 * і* (■ 7-)

V =-= -*-; X' =- і = 1, т).

Для другого гравця оптимальна змішана стратегія знаходиться аналогічно. Для довільної чистої стратегії першого гравця Лі (і = 1, т] згідно з вищезазначеною властивістю оптимальної змішаної стратегії другого гравця маємо:

а11 у* + ... + ащу* < V, <........................ ................

ат1у* + ... + атпУп ^ V.

Ділимо ліву та праву частини нерівностей на V (V > 0) і позначає*

мо - = Пд у' = 1, пу Оскільки ^ У і = 1, враховуючи, що другий гра... і=1.

вець намагається мінімізувати свій програш, отримуємо таку задачу лінійного програмування: f 1

f = - = M, + ... + un -> max V 1

anui + ... + a,nUn < 1, am1u, + ... + amnun < 1;

mi 1 mn n

u j > 0, j = 1, n.

Отримуємо оптимальний план задачі лінійного програмування U*, ціну гри V та оптимальну змішану стратегію другого гравця

U * = ll*n }; fmax = f (U*);

V 1 1 * u*j (■ ri

V = f- = --г; yj = f2- lj = 1 ^

f max u1 + ... + un f max

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