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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проста потокова мережа. Значення ребер — час руху «автомобіля» по ребру. ${\displaystyle 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. В багатьох випадках третя умова не дотримується тому, що навіть хоча рівновага повинна існувати, вона є невідомою через складність гри. Наприклад, в грі «Сянці»[2]. Або, як буває, вона не може бути відомою для всіх гравців, наприклад, при грі в хрестики-нулики з маленькою дитиною, яка відчайдушно хоче виграти (задоволення інших критеріїв).
4. Критерій загального знання може бути не дотриманий, якщо всі гравці, фактично, дотримуються всіх інших умов. Гравці, які неправильно розглядають раціональність поведінки інших, можуть приймати контр-стратегії, очікуючи нераціональної поведінки їхніх опонентів. Це суттєво в перегонах озброєнь та в грі «Яструби і голуби».

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