ІГРИ З НЕПРОТИЛЕЖНИМИ ІНТЕРЕСАМИ. РІВНОВАГА НЕША. ПАРЕТО-ОПТИМАЛЬНІСТЬ

Визначення 2.10. Нехай задана гра G в нормальній формі ( N, Sj , Вихід s = (s ,, s 2 > •••>%) е5 називається рівновагою

Неша (NE - Nash Equilibrium) гри G, якщо Vi е 1 ..... N, Уу, е 5,

Інакше кажучи, кожен з гравців максимізує свою функцію корисності

на безлічі своїх стратегій.

У точці рівноваги Неша стратегія х, - - одна з кращих для гравця i стратегій у відповідь на х_ ; = (х 1 , х 2 , -., ^ _ 1 , х 1 + 1 , ..., х лг ) - стратегії інших гравців. Гравець i розглядає стратегії з х_ ; як задану цілком певну сукупність стратегій «зовнішнього світу», на яку він не може активно впливати. Він може активно вибирати лише свою стратегію в ,, яка буде найкращим вибором, якщо інші гравці виберуть s_j. При цьому гравець i вважає, що аналогічно вибирають свої стратегії і всі інші гравці.

У точці рівноваги Неша гравцеві i невигідно самотужки відхилятися від стратегії s it якщо інші гравці дотримуються стратегій 5 1 , s 2 , ... s, -_ 1 , s i + 1 ... s N . Дії «поодинці» можуть тільки зменшити виграш гравця i. Пошук точки рівноваги Неша, таким чином, зводиться до вирішення системи з N задач максимізації функцій корисності за відповідними змінним

Нехай G - (N, 5, -, Uj , i - 1, .. N) - кінцева гра в нормальній формі.

Назвемо X, - безліччю змішаних стратегій гравця i, а безліч X = X, Х 2 -...- X jV - безліччю профілів всіх змішаних стратегій. Позначимо АЕХ - елементи цієї множини.

Назвемо гру G = (N; X; і) змішаним розширенням гри G. Тоді рівновага в змішаних стратегіях в грі G - це рівновага Неша в її змішаному розширенні.

Приклад 2.17. Задана біматричних гра

Які виграші будуть у гравців при виборі ними стратегій т = 0 , а + 0, і п = 0,25 с + 0, 75d ?

Рішення

Запишемо поруч з чистими стратегіями ймовірності їх вибору:

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

Відповідь: щ - 2; і 2 = 0,25.

Поряд з рівновагою Неша введемо ще одне важливе поняття - домінування по Парето.

Нехай задана гра в нормальній формі G = (N, Si, u it i = l, ..., N). Розглянемо два профілі стратегій x = (x ,, x 2 , ..., x jY ) e5 і i / = (i / v i / 2 , ..., yy) & S.

Визначення 2.11. Профіль стратегій х домінує по Парето профіль стратегій у, якщо

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

Визначення 2.12. Профіль стратегій х називається оптимальним за Парето (Парето-оптимальним), якщо він недомініруем але Парето.

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

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

Рішення

Очевидно, жодна зі стратегій не є строго домінованих. Тому рівноваги в строго домінуючих стратегіях немає.

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

Результати з подвійними підкресленнями будуть равновесиями Неша: (a; d) (b; с); ( B; d ).

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

Мал. 2.21

Парето-оптимальними є точки, в напрямку штрихування від яких (до «північний схід») немає інших точок. Такими є результати ( а ; d) (а; с); (Ь; с). Введемо для стислості позначення для Парето- оптимальних точок - Р і для рівноважних Неша - N. Отримаємо

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

Нехай стратегії а й b граються з вірогідністю р і 1 - р відповідно, а стратегії з і d - з вірогідністю q і 1 - q. Запишемо матрицю очікуваних виграшів першого і другого гравців:

Максимізували функцію щ (р, q) = 3q - 2pq по змінної р е [0; 1] при постійному значенні q

До аналогічного результату приводить розгляд раціональної поведінки другого гравця, оптимизирующего u 2 (p, q ) по змінній q при постійному значенні р

Зобразимо отриманий результат (рис. 2.22) в координатах (q, р ):

Мал. 2.22

Як бачимо, обидва графіка збіглися.

Рівновага Неша:

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

Рішення

Очевидно, що домінують стратегій в грі немає. Точок рівноваги Неша в чистих стратегіях також немає. Парето-оптимальні профілі: ( а ; d) і {bd).

Розглянемо змішані стратегії гравців.

Нехай стратегії а й b граються з вірогідністю р і 1 - р відповідно, а стратегії cud - з вірогідністю q і 1 - q. Запишемо матрицю очікуваних виграшів першого і другого гравців:

Очевидно, перший гравець вирішує завдання

Рішенням задачі є

Ці три випадки представлені на рис. 2.23.

Мал. 2.23

Аналогічно другий гравець вирішує завдання Рішенням завдання є

Ці три випадки представлені на рис. 2.24.

Мал. 2.24

Поєднуючи малюнки, отримаємо рис. 2.25.

Мал. 2.25

Точка N (р = 0,75; q = 0,6), очевидно, є точкою рівноваги Неша в змішаних стратегіях, оскільки вона отримана в результаті рішення задач максимізації функції u x (p, q ) пори u 2 (p, q) по q.

Відповідь: рівновага Неша:

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

Теорема 2.3. Якщо існує процедура ітераційного виключення суворо домінованих стратегій в грі G - (S ;, щ; i - 1, ..., N), яка призводить до єдиного результату s = (s i , s 2 , ..., s N ) , то цей результат є єдиним рівновагою Неша.

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

Зауваження. Якщо в теоремі 2.3 виключити слово «строго», то вона перестає бути справедливою. Наприклад, в грі

результати (а; с) і ( Ь; с) є точками рівноваги Неша, хоча стратегія b домінованих.

Теорема 2.4. Якщо результат явля

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

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

Приклад 2.20. Розглянемо матричну гру:

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

Приклад 2.21. Розглянемо гру двох гравців, звану «битва підлог» (або «сімейна суперечка»). Саша і Маша намагаються вирішити, як їм проводити вихідний день, - піти на футбол або на балет. Звичайно, Саші більше хочеться піти на футбол, Маша ж отримує більше задоволення від балету. Але зовсім ніякого задоволення вони не отримають, якщо будуть розважатися порізно (буває ж таке!). Саша і Маша вибирають місце розваги одночасно і незалежно один від одного, не змовляючись. Матриця виграшів має такий вигляд [1] :

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

Виграш Саші дорівнює

Стратегія Саші визначається вибором ймовірності р. Функція виграшу Саші і з (р, q) є монотонно зростаючою по змінної р ,

якщо , і, отже, пріСаша вибере максимальне значення ймовірності, тобто р.н. = 1.

Аналогічно якщо, то функція u c (p, q) - спадна по змінної / ;, і, отже, при Саша, максимізуючи свій виграш, вибере мінімальне значення ймовірності, тобто р = 0.

При функція і з (р> q) не залежить від р і Сашу задовольняє будь-яке значення р е [0; 1]. Таким чином, маємо

Все сказане наочно представляється діаграмою (рис. 2.26).

Мал. 2.26

Виграш Маші дорівнює

Стратегія Маші визначається вибором ймовірності q. Функція виграшу Маші u M (p, q) є монотонно зростаючою по змінної q,

якщо , і, отже, пріМаша вибере максимальне значення ймовірності, тобто .q = 1.

Аналогічно якщо , то функція u M (p, q) - спадна по змінної q, і, отже, пріМаша вибере мінімальне значення

ймовірності, тобто <7 = 0.

При функція і та (р, q) не залежить від q і Машу задовольняє

будь-яке значення <7 е [0; 1].

Все сказане наочно представляється діаграмою (рис. 2.27). Поєднання діаграм на рис. 2.26 і 2.27 дає три точки перетину найкращих виборів гравців на всілякі дії іншого гравця (рис. 2.28).

Маємо три точки рівноваги Неша. перші

дві з них відповідають вибору чистих стратегій (Балет; балет) і (Футбол; футбол). Третя точка є точкою рівноваги Неша в змішаних стратегіях.

Зауважимо, що значення платіжних функцій обох гравців в точці В сусідній точці, наприклад , значення платіжних функцій гравців рівні Однак

ця крапка не буде точкою рівноваги, оскільки якщо Маша дотримуватиметься стратегії , то Саші буде більш вигідна стратегія р = 1,

оскільки Рис. 2.28

Мал. 2.27 Рис. 2.28

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

Виграш першого гравця дорівнює

З умови максимізації функції виграшу по змінної р отримаємо

Графічно цей вибір зображується наступним чином (рис. 2.29).

Мал. 2.29

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

Виграш другого гравця дорівнює

З умови максимізації функції виграшу по змінної q отримаємо

Графічно цей вибір зображується наступним чином (рис. 2.30).

Мал. 230

Сумісний графіки на рис. 2.29 і 2.30 (рис. 2.31).

Мал. 2.31

Графіки збігаються на відрізку АВ і на початку координат. Всі ці точки і будуть равновесиями Неша в змішаних стратегіях. Точка p = q = 0 означає вибір профілю чистих стратегій ( b; d ). Тому отримаємо: NE: {(b; d), ( pa + (lp) b ; с), ре [0,4; 1]}.

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

Теорема 2.5 (Неш, 1950). Для будь-якої кінцевої гри ( тобто безліч гравців і безлічі їх чистих стратегій кінцеві) в нормальній формі G = (N, S jt Uj, i = 1, ..., N) завжди існує принаймні одна точка рівноваги Неша, можливо, в змішаних стратегіях.

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

Приклад 2.23. Дана біматричних гра:

Знайти всі рівноваги Неша в змішаних стратегіях.

Рішення

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

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

Очевидно, ніяка змішана стратегія ра + (1 р) Ь не зможе домінувати чисту стратегію с, оскільки нерівність /? - 0 + (1 - /?) - 2> 14 нездійсненно ні при яких значеннях р е [0; 1]. Значить, стратегія з не може бути строго домінованих навіть із застосуванням змішаних стратегій.

Як було доведено вище, величина f (p) = pA + (lp) B при /? Е [0; 1], {А і В - дійсні числа) може приймати всі значення між числами А і В. Дійсно, оскільки / ( /?) - лінійна функція, то безліччю її значень є відрізок E (f) = [min (A; В); шах (Л: В). Наприклад, якщо / (р) = /? • 2 + (1 - /?) • 5, то Д (/) = [2; 5].

Аналогічно стратегія а не може бути домінованих змішаною стратегією pb + (l-р) с, оскільки (при виборі другим гравцем стратегії е) буде потрібно виконання нерівності 4 /? + 4 (1 /?)> 6.

Припускаючи, що змішана стратегія pa + (1 - р) з може строго домінувати чисту стратегію Ь, також отримаємо нездійсненне нерівність 2 /? + 4 (1 /?)> 8.

Отже, в даній грі не існує строго домінованих стратегій першого гравця.

Розглянемо стратегії другого гравця. Випишемо матрицю його виграшів:

Очевидно, стратегії їй / недомініруемих. Оскільки 2 <8, 2 <10, 3 е [2; 6], 1 е [0; 6], то можемо припустити, що існує змішана стратегія qe + (lq) f, строго домінуюча чисту стратегію d. Перевіримо наше припущення. Для цього слід дотримуватися системи нерівностей:

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

видно, що змішана стратегія строго домінує стратегію d.

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

Викресливши перший стовпець, отримаємо матрицю

Неважко побачити, що в цій матриці змішана стратегія першого

гравця строго домінує стратегію з (це стало очевидним тільки

після виключення стратегії d). Гра скоротилася до біматричних гри розмірності 2x2:

Тепер е> /. отримаємо

І нарешті, а > - Ь.

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

Приклад 2.24. Послідовним винятком строго домінованих чистих стратегій привести біматричних гру до гри розмірності 2x2 (змішана стратегія може домінувати чисту). Знайти всі рівноваги Неша в змішаних стратегіях.

5) Нехай перший гравець грає змішану стратегію РА + ( 1 - р) С, а другий - qE + (-q) F.

Виграш першого гравця дорівнює

З умови максимізації функції виграшу по змінної р отримаємо

Графічно цей вибір зображується наступним чином (рис. 2.32).

Мал. 2.32

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

Виграш другого гравця дорівнює

З умови максимізації функції виграшу по змінної q отримаємо Графічно цей вибір зображується наступним чином (рис. 2.33).

Мал. 2.33

Сумісний графіки на рис. 2.32 і 2.33 (рис. 2.34).

Мал. 2.34

Графіки збігаються в трьох точках. Ці точки і будуть визначати рівноваги Неша:

Приклад 2.25. Знайти всі рівноваги Неша в змішаних стратегіях в біматричних грі

Рішення

Спосіб 1. Неважко бачити, що в даній грі не існує строго домінованих стратегій. Введемо змішані стратегії гравців:

Виграш першого гравця максимізували по змінної р:

Виграш другого гравця максимізували по змінним q і р

Розглянемо різні значення р (рис. 2.35).

Мал. 235

Випадок 1. Нехай р < 0,5. Тоді з (2) і (3) отримаємо <7 = 0; r = 1. Але тоді з (1) маємо р - 0. Отже, (р = (); q = 0; г = 1) - рівновага Неша. Це результат (b, d).

Випадок 2. Нехай р = 0,5. Тоді з (2) отримаємо q = 0, а з (1) 5г = 3, або г = 0,6. Отже, (р = 0,5; q = 0; г = 0,6) - рівновага Неша. Це результат (0,5 А + 0,56, 0,6 d + 0,4е).

Випадок 3. Нехай р е (0,5; 1). Тоді з (2) і (3) отримаємо q = 0; г = 0. Але тоді з (1) маємо р = 1, що суперечить вихідному умові.

Випадок 4. Нехай р = 1. Тоді з (3) отримаємо г = 0, а з (1) q < 3, що виконується при всіх допустимих q. Отже, (р = 1; — рівновага Неша. Ці ісходи (a, qc + (-q) e), qe [0; 1].

Відповідь: (6, d) (0,5 А + 0,56, 0,6с / + 0,4 с); (a, qc + (-q) e), ^ е [0; 1].

Покажемо ще один спосіб знаходження рівноваг Неша в таких іграх.

Спосіб 2 (рішення прикладу 2.25). Розглянемо виграші другого гравця за умови вибору першим гравцем змішаної стратегії ра + (-р) Ь. Виграш другого гравця при виборі їм чистої стратегії з дорівнює U - 3 р при виборі чистої стратегії d - = р + 3 (- р)] при виборі чистої стратегії е - U? 2 = Зр + (-р).

Побудуємо графіки функцій виграшу другого гравця (рис. 2.36).

Мал. 2.36

Випадок 1. Нехай р <0,5. Тоді другий гравець вибирає чисту стратегію d. Але найкращою відповіддю першого гравця на стратегію другого d є чиста стратегія b (2> 0), тобто р- 0, що задовольняє вихідному умові р < 0,5. Отже, ( b , d) - рівновага Неша.

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

Випадок 3. Нехай р = 0.5. Тоді другим гравцем НЕ буде гратися стратегія с, Г.Є. q - 0. Розглянемо гру

Математичне сподівання виграшу першого гравця одно

Значення р = 0,5 може бути найкращою відповіддю на змішану стратегію другого гравця тільки при г = 0,6. Тоді результат (0,5 А + 0,56, 0,6 d + + 0,4 с) - рівновага Неша.

До того ж результату ми прийдемо і з інших міркувань. А саме, для першого гравця значення р = 0,5 можливо тільки в разі його байдужості до вибору стратегії а чи Ь. Е го значить:

Випадок 4. Нехай р = 1. Тоді другим гравцем НЕ буде гратися стратегія d, тобто г = 0. Матриця набирає вигляду

Тоді (a, qc + (1 - q) e) - рівновага Неша при будь-яких <у е 10; 1].

Приклад 2.26. Знайти всі рівноваги Неша в змішаних стратегіях в біматричних грі

Рішення

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

Побудуємо графіки цих функцій (рис. 2.37).

Мал. 2.37

У точці А перетинаються прямі d ні. Знайдемо точку перетину:

У точці В перетинаються прямі це. Знайдемо точку перетину:

Ламана лінія MABN - найкраща відповідь другого гравця при різних значеннях р. Розглянемо кілька випадків.

Випадок 1: . Тоді найкращою відповіддю другого гравця є

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

Випадок 2: . Тоді найкращою відповіддю другого гравця є

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

Випадок 3: . Тоді найкращою відповіддю другого гравця є

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

Випадок 4: (точка Л). У цій точці свідомо не грається стратегія с. Матриця гри набирає вигляду

Розглянемо математичне очікування виграшу першого гравця:

При рівноважному Неша результаті перший гравець максимізує по р свою функцію корисності:

Очевидно, якщо є оптимальним для першого гравця, то

. Це значення можна отримати з умови рівності значень функції виграшу першого гравця при виборі їм а й / ;. Іншими словами, першого гравця байдуже, вибере він а чи b :

Отже, профіль стратегій є одно

весіем Неша.

Випадок 5: (точка В). У цій точці свідомо не грається стратегія d. Матриця гри набирає вигляду

Оскільки а > - b , то р = 1 , що суперечить вихідному умові Отже, не існує рівноваги Неша, при якому другий гравець вибирає

Цей метод вирішення можна застосовувати для знаходження рівноваг Неша в будь-яких біматричних іграх розмірності 2 хп або п х 2, і, отже, він більш універсальний, ніж метод, застосований в способі 1 рішення попереднього прикладу.

  • [1] Тут і далі в аналогічних прикладах стратегії Саші (Футбол, Балет) обозначенисловом, що починається з великої літери, стратегії Маші - з малої.
 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >