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

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

Названа іменем відомого американського математика та економіста, спеціаліста в галузі теорії ігор, лауреата Нобелівської премії з економіки (1994 р.) Джона Форбса Неша (1928—2015), який запропонував цей термін і зробив вагомий внесок у розробку формалізованого опису конфліктних ситуацій, зокрема у визначення формули рівноваги (постійність рішень суперників у грі).

Застосування

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

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

Умови повної інформованості гравців

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

Визначення

Неформальне визначення

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

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

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

Формальне визначення

Припустимо, $(S,f)$ — гра $n$ осіб в нормальній формі, де $S_{i}$ — набір стратегій $i$-го гравця, $S=S_{1}\times S_{2}\times \dotsb \times S_{n}$ множина всіх можливих чистих стратегій, а $f=(f_{1}(x),\dotsc ,f_{n}(x))$ — набір виграшів для $x\in S$. Коли кожен гравець $i\in \{1,\dotsc ,n\}$ вибирає стратегію $x_{i}$ в профілі стратегій $x=(x_{1},\dotsc ,x_{n})$ , гравець $i$ отримує виграш $f_{i}(x)$ . Зауважте, що виграш залежить від усього профілю стратегій: не тільки від стратегії, обраної самим гравцем $i$ , але і від чужих стратегій. Профіль стратегій $x^{*}\in S$ є рівновагою по Нешу, якщо зміна своєї стратегії з $x^{*}$ на $x_{i}$ не вигідно ні одному гравцеві $i$ , тобто

$\forall i,x_{i}\in S_{i}:f_{i}(x_{i}^{*},x_{-i}^{*})\geqslant f_{i}(x_{i},x_{-i}^{*}).$

Коли наведена нерівність виконується строго (> замість ≥) для всіх гравців і всіх можливих альтернативних стратегій, то рівновага класифікується як строга рівновага Неша. Якщо замість цього, хоч один гравець, має точну рівність між $x_{i}^{*}$ та якоюсь іншою стратегією в множині $S$, то рівновага класифікується як слабка рівновага Неша.

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

Теорема Неша про існування рівноваги

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

Приклади

Координаційна гра

Приклад координаційної гри

	Гравець 2 приймає стратегію A	Гравець 2 приймає стратегію B
Гравець 1 приймає стратегію A	4 / 4	1 / 3
Гравець 1 приймає стратегію B	3 / 1	2 / 2

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

Дилема в'язня

Двоє підозрюваних, А і Б, арештовані. У поліції немає достатніх доказів для звинувачення, і ізолювавши їх один від одного, вони пропонують їм одну і ту ж операцію: якщо один свідчить проти іншого, а той зберігає мовчання, то перший звільняється, а другий одержує 10 років в'язниці. Якщо обидва мовчать, у поліції мало доказів, і вони засуджуються до 6 місяців. Якщо обидва свідчать проти один одного, вони одержують по 2 роки. Кожен ув'язнений вибирає, мовчати або свідчити проти іншого. Проте жоден з них не знає точно, що зробить інший. Що відбудеться?

	В'язень Б зберігає мовчання	В'язень Б надає свідчення
В'язень А зберігає мовчання	Обидва одержують півроку.	А одержує 10 років Б звільняється
В'язень А надає свідчення	А звільняється Б одержує 10 років тюрми	Обидва одержують 2 роки в'язниці

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

Представимо міркування одного з ув'язнених. Якщо партнер мовчить, то найкраще його зрадити і вийти на свободу (інакше — півроку в'язниці). Якщо партнер свідчить, то найкраще теж свідчити проти нього, щоб одержати 2 роки (інакше — 10 років). Стратегія «свідчити» строго домінує над стратегією «мовчати». Аналогічно інший ув'язнений приходить до того ж висновку.

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

Потік в мережі

Проста потокова мережа. Значення ребер — час руху «автомобіля» по ребру. $x$ — це число автомобілів, що рухаються ребром.

Рівноваги Неша застосовують для визначення потоку в мережі. Нехай маємо граф справа. Якщо ми припустимо що є x «автомобілів» які подорожують від А до D, тоді яким буде розподіл трафіку в мережі?

Ситуація може бути змодельована як «гра», де кожен подорожуючий має вибір з 3 стратегій, де кожна стратегія це маршрут від A до D(ABD, ABCD, ACD). Виграшем кожної стратегії є час руху по маршруту. В графі справа, автомобіль рухається по ABD з часом подорожі (1+x/100)+2, де x це число автомобілів, що рухаються по AB. Тому, виграші для будь-якої заданої стратегії залежать від вибору інших гравців, як завжди. Однак, метою в цьому випадку є мінімізація часу подорожі, а не максимізація. Рівновага буде присутня, коли час на всіх шляхах однаковий. Коли це відбудеться, жоден водій не матиме стимулу міняти шлях, так як це лише збільшить його час руху. Для графу справа, якщо, наприклад, 100 автомобілів подорожують від A до D, тоді рівновага буде, коли 25 водіїв оберуть маршрут ABD, 50 — ABCD, 25 — ACD. Кожен водій має загальний час руху 3.75.

Зауважимо, що цей розподіл не є соціально оптимальним. Якщо 100 автомобілів погодяться, що 50 рухаються по ABD, а інші 50 по ACD, тоді час руху для кожного автомобіля буде 3.5 що менше ніж 3.75. Це також є рівновагою Неша, якщо шлях між B і C буде усунутий, що означає, що додавання можливого маршруту може зменшити ефективність системи, феномен відомий як парадокс Бреса.

Поширеність

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

1. Всі гравці будуть робити все можливе для максимізації їхніх очікуваних виграшів згідно правил гри.
2. Гравці бездоганні у виконанні стратегій.
3. Гравці достатньо розумні для знаходження рішення.
4. Гравці знають сплановану стратегію рівноваги всіх інших гравців.
5. Гравці вірять, що відхилення в їхніх власних стратегіях не призведе до відхилення в стратегіях інших гравців.
6. Існує загальне знання, що всі гравці дотримуються цих умов.

Коли умови не дотримуються

Приклади проблем теорії ігор де ці умови не дотримуються:

1. Перша умова не дотримується, якщо гра не коректно описує кількість гравців, які бажають максимізувати виграш. В цьому випадку не має сенсу приймати стратегію рівноваги. Наприклад, дилема в'язня не буде дилемою, якщо один з гравців хоче опинитися у в'язниці.
2. Навмисна або випадкова недосконалість у виконанні. Наприклад, комп'ютер здатний до бездоганної логічної грі проти другого бездоганного комп'ютера призведе до рівноваги. Введення недосконалості призведе до руйнування рівноваги або через втрати гравця, який робить помилку, або через відкидання критерію загальновідомого знання, що може призвести до перемоги гравця.
3. В багатьох випадках третя умова не дотримується тому, що навіть хоча рівновага повинна існувати, вона є невідомою через складність гри. Наприклад, в грі «Сянці». Або, як буває, вона не може бути відомою для всіх гравців, наприклад, при грі в хрестики-нулики з маленькою дитиною, яка відчайдушно хоче виграти (задоволення інших критеріїв).
4. Критерій загального знання може бути не дотриманий, якщо всі гравці, фактично, дотримуються всіх інших умов. Гравці, які неправильно розглядають раціональність поведінки інших, можуть приймати контр-стратегії, очікуючи нераціональної поведінки їхніх опонентів. Це суттєво в перегонах озброєнь та в грі «Яструби і голуби».

Коли умови дотримуються

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

Зв'язок з обережними недомінованими стратегіями

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

Зв'язок з оптимальними за Парето ситуаціями

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

Проте це не означає, ані що такий розв'язок ситуації є єдиним, ані що не існує іншої ймовірності перерозподілу гравців. Іншими словами, щоб розрахувати утворення коаліції ми повинні дослідити найгірший варіант розвитку ситуації в обидвох моделях для прийняття єдиного оптимального рішення. Ймовірність розв'язків гри змушує Неша знаходитися в визначних рамках MinMax теорії фон Ноймана — Морґенштерна.

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

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

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

Див. також

• Теорема Какутані про нерухому точку
• Теорія ігор

Література

• Мак-Кинси Дж. Введение в теорию игр. — М.: ГИФМЛ, 1960. — 420 с.
• Мулен Э. Теория игр с примерами из математической экономики. — М.: Мир, 1985. — 200 с.
• фон Нейман Дж., Моргенштерн Э. Теория игр и экономическое поведение. — М.: Наука, 1970. — 708 с.
• Оуэн Г. Теория игр. — М.: Мир, 1971. — 232 с.
• A Beautiful Mind: A Biography of John Forbes Nash, Jr., Winner of the Nobel Prize in Economics Simon & Schuster, 1994. ISBN 0-684-81906-6