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

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

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

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

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

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

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

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

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

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

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

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

Припустимо, (S, f) - гра n осіб в нормальній формі, де S_i - набір чистих стратегій i гравця, а 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}) \geq f_i(x_{i},x^*_{-i}).

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

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

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

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

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

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

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

Дилема в'язня[ред.ред. код]

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

Двоє підозрюваних, А і Б, арештовані. У поліції немає достатніх доказів для звинувачення, і ізолювавши їх один від одного, вони пропонують їм одну і ту ж операцію: якщо один свідчить проти іншого, а той зберігає мовчання, то перший звільняється, а другий одержує 10 років в'язниці. Якщо обидва мовчать, у поліції мало доказів, і вони засуджуються до 6 місяців. Якщо обидва свідчать проти один одного, вони одержують по 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. Критерій загального знання може бути не дотриманий, якщо всі граці, фактично, дотримуються всіх інших умов. Гравці, які неправильно розподіляють раціональність інших, можуть приймати контр-стратегії до очікуваної нераціальної поведінки їхніх опонентів.

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

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

Джерела[ред.ред. код]

  1. а б «РІВНОВАГА НЕША». Фінансово-економічний словник. Процитовано 1.8.2011. 



Теорія ігор

Типи ігор

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

Ситуації

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

Стратегія

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

Теореми

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

Ігри

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