Предмет і завдання теорії ігор
Тема 2. ПРИЙНЯТТЯ РІШЕНЬ В УМОВАХ НЕВИЗНАЧЕНОСТІ.
ТЕОРІЯ ІГОР
Предмет і завдання теорії ігор
Предмет теорії ігор. Переважну більшість соціально-економічних рішень доводиться приймати з урахуванням суперечливих інтересів, що відносяться або до різних осіб або організацій, або до різних аспектів даного явища, або до того і іншого разом узятих. У таких випадках неможливо застосувати традиційні методи оптимізації. У звичайних екстремальних задачах йдеться про вибір рішення однією особою, і результат рішення залежить від цього вибору, тобто визначається діями тільки однієї особи. У таку схему не укладаються ситуації, коли рішення, оптимальні для однієї сторони, зовсім не є оптимальними для іншої і результат (рішення) залежить від усіх конфліктуючих сторін.
Конфліктний характер таких завдань не припускає ворожнечі між учасниками, а свідчить про різні інтереси. Необхідність аналізувати подібні ситуації викликала до життя спеціальний математичний апарат – теорію ігор.
Теорія ігор (ТІ) є частиною великої теорії, що вивчає процеси прийняття оптимальних рішень. Вона дає формальну мову для опису процесів ухвалення свідомих, цілеспрямованих рішень за участю однієї або декількох осіб в умовах невизначеності і конфлікту, що викликане зіткненням інтересів конфліктуючих сторін. Невизначеність може бути викликана не лише прагненням супротивників приховати свої дії в грі, але і дефіцитом інформації і даних про досліджуване явище. У цьому випадку можна говорити про конфлікт людини з природою.
Метою теорії ігор є вироблення рекомендацій щодо раціонального способу дій учасників в конфліктних ситуаціях, тобто визначення оптимальної стратегії кожного учасника.
Перші роботи з ТІ ( Цермело, Борель, Дж. фон Нейман) припадають на початок ХХ ст. Але тільки поява і широке поширення ЕОМ привернула до ТІ увагу широких кіл фахівців.
Теорія стратегічних ігор у своїй математичній формі виникла в 1930-х роках. Її творцем вважається Джон фон Нейман. Першою фундаментальною книгою з теорії ігор була видана в 1944 році робота "Теорія ігор і економічна поведінка" (Нейман Дж., Моргенштерн О. – М.: Наука, 1970).
Практичне значення ТІ полягає в тому, що вона служить основою моделювання ігрових експериментів, зокрема, ділових ігор, які дозволяють визначати оптимальну поведінку в складних ситуаціях. У принципі, можливий опис військових, правових конфліктів, спортивних змагань, "салонних" ігор, а також біологічних явищ, пов'язаних з боротьбою за існування.
Від реальної конфліктної ситуації гра відрізняється тим, що ведеться за цілком певними правилами. Реальні конфлікти зазвичай важко піддаються формальному опису, тому будь-яка гра є спрощенням початкового завдання: у ній відбиваються лише основні, первинні чинники, що відбивають сутність процесу або явища.
Основні завдання ігрових моделей. Залежно від того, які дані має в своєму розпорядженні дослідник і яке завдання перед собою ставить, можна сформулювати різні теоретико-ігрові моделі. Розрізняють три основні типи завдань:
1) Знаходження оптимального результату. Як результат в загальному випадку може розглядатися соціально-економічна ситуація. Залежно від змісту завдання ситуацію можна описати наборами благ, які отримує кожен гравець (виграші), або результатом може бути обрання того або іншого кандидата, прийняття того або іншого проекту, угоди і т.д. У загальному випадку тут потрібно знайти коаліційну структуру і коаліційні стратегії, за яких реалізується оптимальний результат.
2) Знаходження оптимального результату за фіксованої коаліційної структури, тобто коли нам свідомо відомо, що, наприклад, утворення коаліцій заборонене, неможливе або існуюча коаліційна структура не повинна змінюватися з певних політичних або економічних міркувань. У цьому випадку загальним завданням є знаходження правил прийняття рішень в коаліціях (порядок винагороди її членів), за яких коаліційна структура не розпадеться, а, значить, система функціонуватиме згідно з інтересами і можливостями її учасників.
3) Знаходження стійкої коаліційної структури при заданих правилах прийняття рішень (конституції, нормативних актах, статуті підприємства тощо) в коаліціях. Такі завдання часто зустрічаються під час вирішення економічних і соціальних проблем.
Формалізовані моделі конфліктів відомі з давніх пір: це ігри в буквальному розумінні слова – шахи, карти, кістки і тому подібне. Ці ігри мають змагальний характер, який відбувається за відомими правилами. Термінологія, запозичена з практики таких ігор, застосовується і для інших конфліктних ситуацій, які розглядає теорія ігор.
Основні поняття та визначення.Грою називається будь-яка конфліктна ситуація, яка вивчається в теорії ігор і є спрощеною схематизованою моделлю реальної ситуації.
Від реальної конфліктної ситуації гра відрізняється тим, що не включає другорядні, неістотні для ситуації чинники і ведеться за певними правилами, які в реальній ситуації можуть порушуватися.
Будь-яка гра включає три елементи: учасники гри – гравці, правила гри, оцінку результатів дій гравців:
Г = < I, { x }, { H } > = < гравці, стратегії, виграші >.
Гравцем (особою, стороною, або коаліцією) називається окрема сукупність інтересів, що відстоюється в грі. Якщо цю сукупність інтересів відстоює декілька учасників гри, то вони розглядаються як один гравець. Гравці, що мають протилежні один відносно іншого інтереси, називаються супротивниками. У грі можуть стикатися інтереси двох або більше за супротивників.
Стратегії – доступні для гравців дії, у загальному випадку – це набір правил і обмежень.
Ситуації – можливі результати конфлікту. Кожна ситуація – результат вибору кожним гравцем своєї стратегії.
Стратегічні ігри – ігри, в яких конфлікт відбиває інтереси активних учасників, тобто таких, які чинять вплив на вибір стратегій і ситуацію.
Антагоністичні ігри
Гра Г = < X, Y, H>, де X, Y – це непорожня множина стратегій відповідно першого і другого гравців, H – функція виграшу Н1 = -Н2, називається антагоністичною.
У процесі гри кожен гравець вибирає свою стратегію, внаслідок чого утворюється ситуація (x, y), якій відповідає виграш Н(x, y) для першого гравця і [– Н(x, y)] – для другого.
У сукупності всіх можливих антагоністичних ігор виділяється клас афінно-еквівалентних ігор.
Дві антагоністичні гри Г = < X, Y, H> і Г' = < X ', Y ', H'>, називаються афінно-еквівалентними, якщо X = X', Y = Y' і H' = k H + a, де а – дійсне, а k > 0. У цьому випадку використовується позначення Г ~ Г'.
Антагоністичні ігри, у яких кожен гравець має скінченну множину стратегій, називаються матричними іграми. Для задання такої гри досить виписати так звану платіжну матрицю, у якійо рядки відповідають стратегіям першого гравця, а стовпці – стратегіям другого гравця. Елементами матриці служать виграші першого гравця.
Ситуації рівноваги (сідлові точки).Метою під час пошуку рішення антагоністичної гри вважається ситуацію рівноваги, тобто стійке і вигідне рішення.
У матричних іграх ситуація (i*, j*) називається прийнятною для першого гравця, якщо aij* £ ai*j* і прийнятною для другого гравця, якщо ai*j* £ ai*j.
Таким чином, будь-яке відхилення від прийнятної ситуації зменшує виграш першого гравця і збільшує програш другого.
Ситуація ( i*, j* ) називається рівноважною, якщо вона прийнятна для обох гравців. aij* £ ai*j* £ ai*j . Стосовно антагоністичних ігор говорять про сідлові точки на поверхні виграшу (в них досягається max за першою координатою і min – за другою).
Властивості сідлових точок:
1) рівноцінність. Якщо в грі декілька сідлових точок, то значення функції виграшу в них однакові.
2) взаємозамінність оптимальних стратегій. Гравці можуть замінити свої оптимальні стратегії іншими оптимальними стратегіями, при цьому рівновага не порушиться, а виграш (програш) залишиться незмінним.
Теорема.
Аффинно-еквівалентні ігри мають одні і ті ж сідлові точки, тобто їхні рішення збігаються.
Сідлові точки і мінімакси.Стійке рішення гри може бути отримане шляхом наступних міркувань:
У найбільш несприятливому випадку виграш першого гравця не може бути зменшений з вини супротивника, якщо він задовольняє умові:
aij* = min аij.
З іншого боку, керуючись принципом вигідності перший гравець буде прагнути збільшити свій виграш, зберігаючи властивість стійкості, тому
vн = max min аij.
Це нижня ціна гри.
Міркуючи так само за другого гравця отримаємо верхню ціну гри:
vв = min max аij
Інтуїтивно зрозуміло, що значення (ціна) гри лежить між vні vв.
Теорема.
Для того, щоб в матричній грі існували мінімакси, необхідно і достатньо, щоб мінімакси були рівні:
max min аij = min max аij.
Оптимальні змішані стратегії і їх властивості.Якщо матрична гра не має сідлової точки (ситуації рівноваги), то її рішення в чистих стратегіях стає непередбачуваним: кожному гравцеві можна лише гарантувати, що його виграш за розумної поведінки буде не меншим нижньої межі і не більшим верхньої межі ціни гри.
Матрична гра без сідлової точки приводить до нестійкості використання стратегій за багатократного повторення гри.
Змішаною стратегією гравця в матричній грі називається повний набір вірогідності x = ( x1, x2 .. xm) і y = ( y1, y2 .. yn) застосування його чистих стратегій (чисті стратегії – вихідні).
Властивості змішаних стратегій:
1) Якщо x" = ( x1, x2, .. xm ) і y" = ( y1, y2,..yn ) – оптимальні змішані стратегії гравців в матричній грі, то для довільних стратегій x і y є справедливим:
Н (А, x", y) = å aij xi" ³ v для усіх j=1:n, оскільки це рівносильно використанню другим гравцем чистої j-ї стратегії: y = ( 0, 0,..yj =1,.. 0, 0 )
Н (А, x, y") = å aij yj" £ v для усіх i=1:m, оскільки це рівносильно використанню першим гравцем чистої i-ї стратегії: x = (0, 0,..xi =1,.. 0, 0 )
2) Якщо в матричній грі з матрицею А і ціною гри v стратегії x" і y" оптимальні, то
якщо å aij xi" > v, то yj" = 0;
якщо å aij yj" < v, то xi" = 0;
якщо нерівності перетворюються в рівності, то відповідно: xi" ¹ 0, yj" ¹ 0.
На цих властивостях засноване рішення матричних ігор у змішаних стратегіях.
Метод наближеного визначення ціни гри.Спосіб відшукування наближеного рішення прямокутних ігор був сформульований в роботі Г.В.Брауна, а збіжність процесу була доведена Джулією Робінсон у 1951 році.
Цей метод, званий ще ітеративним, спирається на традиційний статистичний принцип: засновувати майбутні рішення на відповідній передісторії. Полягає він в послідовній процедурі "зближення" верхньої і нижньої ціни гри із заданою точністю.
Біматричні ігри
Функція виграшу біматричної гри являє собою дві платіжні матриці:
А – визначає виграш першого гравця,
В – виграш другого гравця.
Перший гравець має m чистих стратегій (m рядків у матрицях А і В). Другий гравець має n чистих стратегій (n стовпців в матрицях А і В).
У результаті вибору першим гравцем i-ї стратегії, а другим гравцем j-ї стратегії, перший гравець отримує виграш aij, а другий – bij.
Рішення біматричних ігор зводиться до відшукання ситуацій рівноваги і рівноважних (оптимальних) стратегій гравців.
У біматричній грі ситуація i*j називається прийнятною для першого гравця, якщо його виграш в цій ситуації не менший, ніж в будь-якій іншій :
аi*j ³ аij j=1:n
Для другого гравця ситуація ij* прийнятна, якщо його виграш в цій ситуації не менший, ніж в будь-якій іншій :
bij* ³ bij i=1:m
Tаким образом, прийнятні ситуації для першого гравця – це максимальні елементи в стовпцях матриці А, а для другого гравця – максимальні (теж!) елементи в рядках матриці В.
Ситуація i*j* в грі біматриці називається рівноважною, якщо вона прийнятна для обох гравців, тобто якщо будь-яке відхилення від неї як для першого гравця, так і для другого тільки зменшує їх виграш:
аi*j* ³ аij*
bi*j* ³ bi*j
Безліч ситуацій рівноваги G утворюється як перетин множин прийнятних ситуацій першого і другого гравців.
Приклад.
| А: | У: | |||||||
G1={(1,1)(1,3)(3,2)(3,3)}
G2={(1,1)(2,1)(2,3)(3,2)} G = {(1,1)(3,2)}
I v(1,1)= 3 II v(1,1)= 3
v(3,2)= 3 v(3,2)= 2
Таким чином, якщо в біматричній грі є декілька рівноважних ситуацій, то за вигідністю вони не є рівнозначними, на відміну від матричних ігор.
З прикладу добре видно, що хоча (1,1) і (3,2) – це ситуації рівноваги, то ситуації (1,2) і (3,1) такими не є, на відміну від матричних ігор.
Принциповою відмінністю біматричних ігор від матричних є відсутність в них антагонізму. У матричних іграх переговори між гравцями були безглуздими, оскільки їх інтереси були прямо протилежні, в біматричних іграх угоди між учасниками мають реальну основу.
Так, у даному прикладі другий гравець зацікавлений в тому, щоб перший вибрав i=1, оскільки при цьому v(II)=3. Першому ж гравцеві з точки зору вигоди байдуже, яку стратегію вибрати – першу або третю. У будь-якому випадку його виграш складає 3. Якщо перший гравець доброзичливо налагоджений по відношенню до супротивника, то він вибере першу стратегію, щоб і другий гравець отримав максимальний виграш. У протилежному випадку перший зажадає за вибір вигіднішої для другого стратегії додаткової плату, і якщо ця плата буде меншою 1, то очевидно, що другий гравець погодиться на цю угоду. Така гра називається грою з побічними платежами.
Якщо в біматричній грі ситуації рівноваги немає, але гравці мають можливість домовитися між собою, то зазвичай застосовують такий штучний прийом: знаходиться i*j* така, що:
max (aij + bij) = ( ai*j* + bi*j* )
і ділиться між гравцями за заздалегідь обумовленим правилом.
Приклад.
| А: | У: | |||||||
Ситуацій рівноваги немає. Знаходимо максимальний елемент в матриці А+В
| А+В: | |||
max = 5(3,2). Ця сума має бути розділена між першим і другим гравцями.
У разі, якщо договір між гравцями є неможливим, гра стане нестійкою і гравцям буде вигідно приховувати свої стратегії. Рішення такої гри буде в змішаних, ймовірнісних стратегіях.
Поняття змішаних стратегій в біматричних іграх таке ж, як і в матричних іграх, тобто це повний набір вірогідності застосування їх чистих стратегій. Виграш гравців теж знаходиться як математичне очікування.
Нестратегічні ігри
Основні поняття і визначення.На практиці досить часто зустрічаються випадки, коли в типово ігрових ситуаціях учасники вступають між собою в угоди, утворюють союзи, коаліції, корпорації, трести, об'єднання і т.п. Під час розгляду стратегічних ігор передбачалося, що кожен гравець діє ізольовано від інших, але в загальному випадку така поведінка не завжди є вигідною. У рішенні біматричної гри з побічними платежами можна легко в цьому переконатися.
Розглянемо гру біматриці з побічними платежами. Якщо учасники по умові гри в змозі домовитися один з одним, то рішення – тобто виграші гравців, не залежатиме від вибираних ними стратегій, а тільки від способу поділу загального доходу. При цьому для них важливо ще і те, наскільки вигідно їм вступати в таку угоду або коаліцію.
Коаліцією в кооперативній грі називається будь-яка підмножина множин гравців.
Приклад.
Нехай I = { 1, 2, ...i, ...n }– деяка множина гравців. Коаліціями будуть:
k1 = { 1, 2, 5, i };
k2 = { i } = i;
k3 = { } = Æ ;
k4 = { 1, 2, ...n } = I.
Коли гравці об’єднані в коаліцію, природно розглядати їхній загальний виграш, який можна отримати в грі. Зрозуміло, гравців цікавить максимально гарантований виграш, який і є мірою корисності об'єднання гравців.
Характеристичною функцією v(k) називається найбільший виграш, який гарантовано отримує коаліція k.
Приклад.
Припустимо, що існує невелика бригада, яка складається з двох робітників (p1, p2) і майстра (М). Денне завдання може виконуватися всією бригадою або майстром разом із одним робітником. Виконання денного завдання гарантує бригаді заробіток в С одиниць (виграш).
Задати характеристичну функцію цієї гри.
Рішення:
I = { M, p1, p2 } – множина гравців гри.
Тоді
v(Æ) = v(p1, p2) = v (p1) = v (p2)= v (M) = 0,
v (M, p1, p2) = v( M, p1) = v( M, p2) = C.
Із заданої характеристичної функції видно, у які коаліції вигідно вступати гравцям, оскільки виграш істотно залежить від складу коаліцій. Таким чином, характеристична функція задається на множині всіх підмножин множини гравців I гри Г і набуває дійсних значень.
Властивості характеристичної функції :
1) персональность:
vr (Æ) = 0;
2) супераддитивність:
vr (КÈL) ³ vr (К) + vr (L),деK, LÎI, KÇL =Æ;
3) доповняльність:
vr (К) + vr (I\K) = vr (I) = C, де С – постійна сума виграшу.
Поділи в кооперативних іграх.Як тільки гравці в коаліції отримали свій максимально гарантований виграш, виникає завдання про те, як його розділити між учасниками.
Зазвичай розподіл виграшу задається вектором Х з числом компонент, що дорівнює числу гравців в коаліції.
Нехай задана характеристична функція v над множиною гравців I. Які вектори поділу в цьому випадку припустимі?
Передусім, кожен гравець вступає в коаліцію тільки у тому випадку, якщо це, принаймні, не зменшує його виграш, тобто якщо:
xi ³ v(i) егалітарний підхід
å xi = v (I) утилітарний підхід
Наведені умови мають назву індивідуальної і колективної раціональності, оскільки дозволяють отримати максимальну вигоду і використовувати можливості системи повністю.
Поділом в умовах характеристичної функції v називається вектор Х = ( х1, х2, .. хn), який задовольняє умовам індивідуальної і колективної раціональності.
Класичною кооперативною грою називається система < I, v >, яка включає множину гравців I і характеристичну функцію v над цією множиною, а так само множина Х поділів в умовах цієї характеристичної функції.
Теорема.
Для того, щоб вектор Х = ( х1, х2, .. хn)був поділом в кооперативній грі < I, v >, необхідно і достатньо, щоб
хi = v (i) + ai, ai ³ 0, i Î I;
å ai = v(I) – å v(i).
Неважко бачити, що компоненти вектора Х задовольняють умові індивідуальної раціональності. Умова кооперативної раціональності
åxi = å v (i) + v(I) – å v(i) = v(I)
виконується також. Тут ai – це додатковий виграш гравця, що отримується за рахунок кооперації з іншими учасниками.
Важливою відмінною рисою кооперативних ігор є те, що для кожного гравця має значення не виграш коаліції в тій або іншій ситуації, а результат поділу, який не залежить від вибору стратегій. Тому цей клас ігор називається нестратегічним.
Відповідно до наведеного означення можна побудувати нескінченну множину класичних кооперативних ігор. Для вивчення їхніх властивостей ігри поділяться на класи, що не перетинаються, усередині яких ігри мають однакові або близькі властивості.
Існуюча класифікація ділить усі кооперативні ігри, передусім, на істотні і неістотні.
Неістотною грою називається кооперативна гра, в якій характеристична функція будь-якої коаліції дорівнює сумі характеристичних функцій будь-яких підкоаліцій.
v (КÈL) = v (К) + v (L), где K, LÎI, KÇL = Æ.
Істотними називається решта ігор.
Гравці так само діляться на істотних і несуттєвих (нездар, російською мовою – болван), а множина гравців – на носіїв гри і множини нездар.
Істотним називається гравець i, якщо існує така коаліція К, для якої
v(K) + v(i) < v(KÈi).
Нездарою називається гравець i, якщо для будь-якої коаліції K Ì I справджується
v(K) + v(i) = v( KÈi).
Припустимо, L – множина нездар (неістотних гравців) і L Ì K, тоді
v(K) = v(K\ L) + å v(i), а якщо K = L, то v(K) = å v(i).
Істотні гравці утворюють множину носіїв гри, NÌI. Ознакою цього для коаліції К є:
v(K) = v(KÇN) + åi ÎK\N v(i).