Словник / Рівновага Неша
Гра — це будь-яка ситуація, де ваш результат залежить не лише від вас: ціни конкурентів, переговори, пенальті, вибір смуги в заторі. Математик Джон Неш 1950 року запропонував простий спосіб передбачити, чим така гра закінчиться: шукати стан, з якого нікому не хочеться втекти самому. Цей стан стійкий. Але, як з'ясовується, він зовсім не мусить бути добрим.
Шар «На пальцях» приховано на всіх задачах.
Двох спільників тримають у різних кімнатах, домовитися вони не можуть. Слідчий пропонує кожному те саме: дай свідчення проти напарника. Вироки такі:
Що зроблять двоє розумних в'язнів?
Обидва зрадять і сядуть на 5 років, хоча могли б на 1.
Хоч би що зробив напарник, зрадити вигідніше. Напарник міркує так само. Кожен зробив найкраще для себе, а разом вони отримали гірше, ніж могли. Стан «обидва зраджують» і є рівновагою Неша: звідти жоден не хоче піти сам, бо мовчати поодинці означає 10 років замість 5. А з кращого стану «обидва мовчать» кожного тягне втекти.
Рівновагу легко знайти на око. Станьте в клітинку таблиці й спитайте кожного гравця: «Ти хочеш змінити свій вибір, якщо інший свого не змінить?» Якщо хоче, малюємо стрілку туди, куди його тягне. Клітинка, з якої не виходить жодна стрілка, і є рівновагою. Перемикайте ігри й натискайте на клітинки.
У пенальті клітинки без стрілок немає: хоч куди б'є гравець, воротареві вигідно стрибнути туди ж, а гравцеві тоді вигідно бити в інший бік. Здається, перемагає той, хто хитріший. Перевірте. Ви б'єте, бот стоїть у воротах. Він стрибає туди, куди, за його розрахунком, ви вдарите, і вчиться на кожному вашому ударі. Спробуйте його обіграти: чергуйте, блефуйте, плутайте сліди.
Спрощення: якщо воротар угадав бік, він бере м'яч, якщо ні, це гол. Бот шукає закономірності у ваших останніх ударах (до чотирьох поспіль) і в тому, куди ви б'єте частіше. Удари монетки він вивчає окремо.
Люди погано вигадують випадковість: ми надто часто чергуємо, уникаємо трьох однакових поспіль, маємо улюблений бік. Бот це ловить. Монетка ж не має звичок, тому навіть найхитріший воротар угадує її лише в половині випадків. Це і є рівновага пенальті: бити ліворуч і праворуч навмання, по 50%. Тут рівновага не конкретний удар, а непередбачуваність.
Шар «Строго» приховано на всіх задачах.
Рівновага Неша — це набір рішень усіх гравців, у якому нікому не вигідно змінити своє рішення, поки інші не змінюють своїх. Кожен грає найкраще, що може, у відповідь на те, що роблять інші. Перевірка завжди та сама: заморозьте всіх, крім одного, і спитайте, чи може він сам собі покращити результат. Якщо ні в кого не виходить, це рівновага.
Мисливці щодня виходять парами. Оленя можна вполювати лише вдвох, і тоді кожному дістається 4 кошики м'яса. Зайця кожен ловить сам, це завжди 3 кошики. Хто пішов на оленя, а напарник погнався за зайцем, лишається ні з чим. Олень вигідніший усім. Тож якщо на старті на оленя готова йти більшість, село рано чи пізно до цього прийде, правда? Задайте, яка частка мисливців спочатку довіряє напарникам. Щодня кілька людей дивляться, як полювало село вчора, і обирають те, що вигідніше.
200 мисливців. Темна точка йде на оленя, світла на зайця. Щодня кожен з імовірністю 15% переглядає свій вибір, порівнюючи 4 × (частка тих, хто йде на оленя) з певними 3 кошиками.
Обидва кінці стійкі: коли всі йдуть на оленя, зрадити означає взяти 3 замість 4; коли всі женуться за зайцями, піти на оленя самому означає взяти 0 замість 3. Тут дві рівноваги, і краща з них потребує, щоб понад три чверті села вже довіряли. Інакше кожен обережний крок тягне решту до гіршої.
Шар «Глибше» приховано на всіх задачах.
ui(si*, s−i*) ≥ ui(si, s−i*) для кожного гравця i і кожної його стратегії si
Тут ui — виграш гравця i, si* — його рівноважна стратегія, s−i* — стратегії всіх інших. Нерівність і є «самому змінювати невигідно». Стратегія може бути змішаною, тобто набором імовірностей: «ліворуч з імовірністю 1/2, праворуч з 1/2». Тоді ui — середній виграш.
Теорема Неша (1950). У кожній грі зі скінченною кількістю гравців і ходів є хоча б одна рівновага, якщо дозволити змішані стратегії. Доведення спирається на теорему про нерухому точку: відображення «кожен переходить до найкращої відповіді» має точку, яку воно не рухає. Тому пенальті й «камінь, ножиці, папір» мають рівновагу, хоча клітинки без стрілок у них немає.
Як знайти змішану рівновагу? Кожен гравець змішує так, щоб супернику стало байдуже, що обрати: якби одна з відповідей була кращою, суперник обирав би лише її, і змішування втратило б сенс. Візьмемо пенальтиста з сильним і слабким боком. Якщо воротар не вгадав, це завжди гол. Якщо вгадав, на сильному боці гол буває у 70% випадків, на слабкому в 50%.
q · 0,3 = (1 − q) · 0,5 ⇒ q = 0,5 / 0,8 = 5/8 = 62,5%
Бити на сильний бік варто в 62,5% випадків, і воротар у рівновазі стрибає туди з тією самою частотою 62,5%. Тоді гол буває у 81,25% ударів, і це однаково для обох боків: 0,625 · 0,7 + 0,375 · 1 = 0,625 · 1 + 0,375 · 0,5 = 0,8125. Здавалося б, найкраще бити завжди на сильний бік. Але тоді воротар завжди стрибатиме туди, і голів стане лише 70%.
Звідси перевірний прогноз: у рівновазі частка голів однакова, хоч куди бити, а удари не залежать від попередніх. Ігнасіо Паласіос-Уерта перевірив його на 1417 пенальті з європейських ліг 1995–2000 років (стаття «Professionals Play Minimax», 2003). Обидві ознаки підтвердилися: частки голів по боках статистично однакові, а послідовності ударів непередбачувані.
Пробийте кілька пенальті вище, і тут з'являться ваші частки голів по боках.
Варіант, який дає гравцеві більше за будь-який інший його варіант, хоч би що обрали інші.
Знижка вигідна кав'ярні, хоч би що зробила сусідня, але коли знижують обидві, кожна заробляє втричі менше, ніж якби обидві тримали ціну.
Розв'язування гри з кінця: спершу останній хід, потім передостанній, і так до першого.
У грі-стоніжці логіка велить забрати копійки на першому ж ході, хоча, граючи довше, обидва отримали б сотні, і живі люди так майже не роблять.
Усі знають факт, усі знають, що всі знають, і так без кінця.
Два генерали можуть обмінятися тисячею підтверджень і все одно не мати спільного знання, тож жоден не наважиться атакувати першим.