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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Застосування[ред.ред. код]

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

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

Визначення[ред.ред. код]

Неформальне визначення[ред.ред. код]

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

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

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

Формальне визначення[ред.ред. код]

Припустимо, (S, f) — гра n осіб в нормальній формі, де S_i — набір стратегій[en] 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}).

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

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

Теорема Неша про існування рівноваги[ред.ред. код]

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

Приклади[ред.ред. код]

Координаційна гра[ред.ред. код]

Приклад координаційної гри
Гравець 2 приймає стратегію A Гравець 2 приймає стратегію B
Гравець 1 приймає стратегію A 4 / 4 1 / 3
Гравець 1 приймає стратегію B 3 / 1 2 / 2

Координаційна гра — це класична (симетрична[en]) гра двох гравців, з двома стратегіями (матриця виграшів на таблиці справа). Гравці повинні координувати свої дії, обидва адаптуючи стратегію А, для отримання найбільшого виграшу; тобто 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 буде усунутий, що означає, що додавання можливого маршруту може зменшити ефективність системи, феномен відомий як парадокс Браєса.

Поширеність[ред.ред. код]

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

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

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

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

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

Коли умови дотримуються[ред.ред. код]

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

Примітки[ред.ред. код]

  1. РІВНОВАГА НЕША. Фінансово-економічний словник. Процитовано 1.8.2011. 
  2. T. L. Turocy, B. Von Stengel, Game Theory, copyright 2001, Texas A&M University, London School of Economics, pages 141–144. Такі ігри не мають єдиної рівноваги Неша, але хоча б одна зі стратегій рівноваги, яка гіпотетично може бути зіграна, має загально відомі знання, які представляються 10150 деревами ігор[en].
  3. J. C. Cox, M. Walker, Learning to Play Cournot Duoploy Strategies, copyright 1997, Texas A&M University, University of Arizona, pages 141–144


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.


Теорія ігор

Типи ігор

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

Ситуації

Безвиграшна ситуація · Парадокс Бертрана (економіка) · Ситуація рівноваги 

Стратегія

змішана · оптимальна · поведінки · чиста 

Теореми

Максіміна принцип · Мінімаксу теорема

Ігри

Дилема в'язня · РВ-ПП