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

Ботанік не повинен полоти будяки. Він обчислить швидкість їх росту і цього достатньо.

С.Паркинсон

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

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

Розв'язок. Гра двох учасників.

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

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

Тобто, якщо інший питає, то найкраще мовчати. Якщо інший мовчить — найкраще питати. Ці дві ситуації є рівновагами Неша в цій грі, а загальний тип ігор називається Курча. Ці дві ситуації є рівновагами в чистих стратегіях. За визначенням рівновага Неша — це ситуація, в якій всі гравці не мають бажання змінювати стратегію в тому сенсі, що вони не можуть отримати більший виграш при (одноосібному) відхиленні. Дійсно, якщо перший гравець відхилиться від точки (питати, мовчати), то він отримає 0 замість 6.

Цікаво, що ще однією концепцією розв'язання ігор (крім ідеї рівноваги) є раціоналізування. В цьому випадку, гравці вибирають рішення з тих, що є найкращими відповідями. І в цьому сенсі багато припущень з коментарів мали сенс.

Але крім чистих стратегій в теорії ігор є також важливе розширення, яке називається змішаними стратегіями. Змішана стратегія — це ймовірнісний розподіл на просторі чистих стратегій. Тобто, коли ви граєте в камінь-ножиці-папір (скажімо багато раундів) ви вибираєте різні варіанти з різною ймовірністю (рандомізуєте свій вибір). При цьому найкращий результат буде, коли ви будете вибирати з рівною ймовірністю. Розуміти змішані стратегії можна по різному. Один підхід — це ймовірність зробити якусь дію (для тих, хто грає в преферанс — коли ви скидуєте «пробої» на мізері іноді найкраща стратегія зробити це випадково), тоді ви розраховуєте очікуваний виграш в результаті зустрічі певної комбінації змішаних стратегій. По суті — це математичне сподівання вашого результату. Інший підхід пов'язаний з еволюційними іграми.

Отже, припустимо, що інший студент вибрав стратегію (р, 1 — р). Тобто, з ймовірністю р він питає, і з ймовірністю 1 — р — мовчить. Які виграші дає кожна стратегія першому гравцю?

Стратегія Питати завжди дає виграш 6.

Стратегія Мовчати дає виграш 10р + 0(1 — р) = 10р, тобто з ймовірністю р ми отримуємо 10, і з ймовірністю 1 — р — нуль.

Для визначення рівноважного значення р прирівняємо виграші:

10р = 6

р = ⅗

Отже, якщо р < ⅗ , то вигідніше питати, якщо р > ⅗, то вигідніше мовчати. Якщо ж р = ⅗, то будь-яка стратегія дає однаковий виграш. Аналогічно можна записати і для іншого гравця.

Давайте нанесемо ці рішення на графік виграшів в залежності від р.

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

Зауваження. Я пишу відображення, тому, що строго кажучи це не функції. Справа в тому, що для деяких значень р найкращим рішенням є весь відрізок [0,1], тобто вся нескінченна множина змішаних стратегій першого гравця.Такі відображення в математиці називають багатозначними і це одна з точок перетину «страшної» математики і досить реальних ситуацій ухвалення рішень.

Отже відображення найкращої відповіді першого гравця. Позначимо його змішану стратегію через (q, 1- q). Нагадаю, що якщо р < ⅗ , то вигідніше питати, тобто q = 1.

Якщо р > ⅗, то вигідніше мовчати, тобто q = 0. Якщо ж р = ⅗, то всі стратегії дають однаковий виграш, тобто q є [0,1].

Нанесемо аналогічне відображення для другого гравця.

Перетини цих відображень утворюють рівноваги Неша — набори стратегій, які є найкращою відповіддю на найкращу відповідь. Бачимо, що тут є три перетини — дві рівноваги в чистих стратегіях і одна в змішаних. Чому перетин утворює рівновагу, якщо для р = ⅗ всі стратегії дають однакові виграші? Тому що як тільки перший гравець змінить свою стратегію на, наприклад, ( ½,½ ), інший може відхилитись і отримати більший виграш граючи чисту стратегію питати. Вибираючи стратегію (⅗,⅖) кожен учасник гарантує, що іншому не вигідно відхилятись від даного набору стратегій.

Тому рівновага в змішаних стратегіях буде така: кожен має питати з ймовірністю ⅗ і мовчати з ймовірністю ⅖. Тоді виграш кожного буде наступний:

⅗ * 6 + ⅖*⅗*10 = 6

Тобто, граючи змішану стратегію кожен має очікуваний виграш 6. Ймовірність того, що ніхто не задасть питання дорівнює ⅖ * ⅖, що дорівнює 0.16.

Розв'язок. Гра N учасників.

Тепер розглянемо гру N учасників. Матриця буде занадто великою, тому спробуємо використати ідею того, що учасники однакові (раціональні гравці, які максимізують свій виграш). Припустимо, що вони використовують змішану стратегію (р, 1 — р). Ймовірність має бути однакова для всіх, бо їх виграші однакові — гра симетрична. Розглянемо «уявну» гру, коли інші N — 1 гравець уявляються одним учасником. Тоді рішення окремого гравця можна представити такою матрицею.

Ймовірність того, що ніхто не питає дорівнює (1-p)^(N-1), ймовірність того, що хтось спитає дорівнює відповідно 1- (1-p)^(N-1). Тоді виграші першого (окремого) гравця дорівнюють

питати — 6

мовчати — 10(1- (1-p)^(N-1))

Прирівнюючи, отримуємо

10(1- (1-p)^(N-1))) = 6

(1-p)^(N-1) = ⅖

p=1 — (⅖)^(1/(N-1))

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

Цікаві висновки

По-перше, ймовірність з якою кожен зі студентів задає питання дорівнює кореню степені N — 1 з ⅖. Її графік зображений на наступному рисунку (залежно від кількості студентів).

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

Але при цьому ймовірність того, що питання не буде задане дорівнює ⅖ у степені N/(N -1) і при зростанні N наближається до постійного значення ⅖ = 0.4. Тобто ймовірність того, що ніхто не спитає зростає з кількістю студентів і це стається у 40% випадків! Відповідно і ймовірність того, що питання буде задано прагне до 0.6.

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