Теорія ігор: Насижний рівновага та в’язницьке дилема

Три інгредієнти, одна матриця

Теорія ігор – це математика ситуацій, де результат агента залежить не тільки від власного вибору, але й від вибору інших учасників. Кожна гра складається з трьох основних компонентів: набір гравців, набір стратегій, доступних кожному, та функція оплати (payoff function), яка відображає кожну комбінацію виборів у значення для кожного гравця. Для двох гравців ця функція оплати зручно зображується у вигляді матриці: рядки – варіанти вибору гравця 1, стовпчики – варіанти вибору гравця 2, а кожна клітинка містить пару отриманих результатів.

Найвідомішою матрицею оплати в цій галузі є ‘В’язниця Штайн’. Два підозрювані, допитувані окремо, можуть обирати або Співпрацювати (тримати мовчання), або Зрадити (свідчити проти іншого). Якщо обидва співпрацюють, кожен відбуває рік у в'язниці. Якщо обидва зраджують, кожен відбуває два роки. Якщо один здається, а інший – ні, той, хто здався, звільняється, а той, хто не здався, відбуває три роки. Розглянемо ситуацію з позиції будь-якого гравця: незалежно від того, що робить інший гравець, зрада завжди скорочує його термін у в'язниці на рік. Зрада є домішованою стратегією – вибором, який найкращий незалежно від дій опонента, тому прогнозування дій опонента не потрібне.

Гравець 2: С Гравець 2: Д Гравець 1: С (-1, -1) (-3, 0) Гравець 1: Д ( 0, -3) (-2, -2) обидва домішовані стратегії -> (Д, Д), оплата (-2,-2) але (С, С) з оплатою (-1,-1) краще для обох Обидва гравці, логічно міркуючи, опиняються в гіршій ситуації, ніж якби вони домовилися співпрацювати. Ця проміжна відстань між індивідуально раціональними рішеннями та колективно кращим результатом є центральною напругою, яку існують теорія ігор намагаються формалізувати – і вона повторюється скрізь, від гонитви озброєнь до витрат на рекламу та перелову спільних вод.

              Player 2: C        Player 2: D
Player 1: C    (-1, -1)          (-3,  0)
Player 1: D    ( 0, -3)          (-2, -2)

both dominant strategies -> (D, D), payoff (-2,-2)
yet (C, C) with payoff (-1,-1) is better for both

Равновесище Неша: ніхто не може покращити свою ситуацію самостійно

Внесок Джона Нерса 1950 року був загальним визначенням стабільного результату, яке застосовується до будь-якої гри, а не лише до 'В'язня-Дилеми'. Равновесище Неша — це набір стратегій, по одній на гравця, за яким жоден гравець не може покращити свій виграш, змінивши свою стратегію, при цьому всі інші залишаються на своїх позиціях. Кожен крок гравця є найкращою відповіддю на те, що роблять усі інші. Нерс довів — використовуючи теорему про фіксовану точку Какатані — що будь-яка кінцева гра має принаймні один такий рівноваг, можливо, де гравці випадково обирають між своїми варіантами замість того, щоб зобов'язуватися до єдиної чистої стратегії (змішана стратегія).

У 'В'язня-Дилеми' (Відмовитися, Відмовитися) — це єдине рівноважне Неша: якщо опонент відмовляється, то найкращою відповіддю для вас також є відмова, тому жоден з гравців не має стимулу односторонньо змінювати свою стратегію. У грі 'Камінь-Ножиці-Папір' жодна чиста стратегія не виживає при передбаченні, тому єдине рівноважне Неша полягає в тому, що кожен гравець випадково обирає між трьома варіантами з однаковим розподілом — кожен варіант відіграється третиною часу, точна частота, яка залишає опонента байдужим до всіх його власних виборів. Деякі ігри мають більше одного рівноваги: у грі 'Олені' два мисливці можуть спільно вбити оленя (високий виграш, вимагає довіри) або кожен зловити зайця окремо (нижчий, але гарантований). Обидва (Олень, Олень) і (Заєць, Заєць) є рівновагами Неша, а те, на якій з них опиниться населення, залежить від історії та очікувань, а не лише від максимізації виграшу.

Повторення змінює все

Одноразовий сценарій ‘В’язниці’ не передбачає жодних можливостей для формування репутації. Якщо грати повторно проти одного й того ж суперника, то дезертирство сьогодні може бути покаране завтра – загроза майбутніх покарань стає стратегічною перевагою в собі. У 1980 році політичний вчений Роберт Аксельрод провів комп’ютерний турнір, запросивши дослідників подавати стратегії для ітеративного сценарію ‘В’язниці’. Найпростіший варіант – ‘Ти за тиму’ – тобто спочатку співпрацювати, а потім копіювати те, що зробив опонент у минулому раунді – переміг вражаюче та знову виграв у наступному турнірі з більшою кількістю учасників. Його чотири характеристики (добрий, помстивий, прощаючий, простий) виявилися важливішими за будь-який обсяг розумності проти різноманітного населення суперників.

Стратегії, які виживають: еволюційна теорія ігор

Джон Мейнард Сміт та Джордж Прайс переформулювали питання з біологічної точки зору: замість того, щоб запитувати, яку стратегію має обрати раціональна особистість, запитуйте, яка стратегія може існувати в популяції під впливом природного відбору. Стратегія – це Еволюційно Стабільна Стратегія (ESS), якщо після її домінування в популяції жодна невелика група мутантів, які грають щось інше, не зможе вторгнутися та розповзтися. Класичний приклад – Вовки та Голуби: вовки завжди перемагають у змаганні за ресурс і биються доти, поки хтось не отримає поранення; голубі демонструють, але відступають, як тільки вовк ескалює. Популяція, що складається лише з голубів, невразлива для мутанта-вовка, який виграє кожне змагання без шкоди. Популяція, що складається лише з волків, невразлива для мутанта-голуба, який уникає витратних сутичок. Жодна з чистих стратегій не є стабільною — замість цього популяція встановлює змішаний рівноважний частотний склад.

Умова ESS: payoff(I, I) > payoff(J, I) для кожної мутантської стратегії J Вовк-Голуб частота голубів: p* = V / C (коли V < C) V = вартість ресурсу, C = вартість втрати бою Це популяційно-рівневий погляд узагальнюється далі: агенти, розміщені на просторовій решітці та взаємодіючи лише з сусідами, можуть підтримувати співпрацю навіть без повторного парного гри або взаємності, оскільки кооператори скупчуються разом і захищають себе від експлуатації по сусідству дефекторами. Місцева структура сама по собі може врятувати співпрацю від долі, яку не може уникнути добре змішана популяція.

ESS condition: payoff(I, I) > payoff(J, I)  for every mutant strategy J

Hawk-Dove equilibrium frequency of hawks:
  p* = V / C     (when V < C)
  V = value of the resource, C = cost of losing a fight

Як ця симуляція моделює це

Симуляція теорії ігор на цьому сайті розміщує популяцію агентів на сітці, кожен з яких несе стратегію — співпрацювати або дезертирувати, або ймовірність кожної — та грає в стилі ‘В’ із винагороди проти сусідів кожного раунду. Після кожного раунду агенти можуть наслідувати більш успішних сусідів або мутувати, що є точним правилом оновлення, яке вивчає теорія ігор: винагорода визначає розмноження, а не раціональне обмірковування. Спостерігаючи за групами співробітників, які виживають, зменшуються або поширюються у міру зміни параметрів винагороди, це є прямим візуальним демонстрацією формування, руйнування або відсутності ESS — ви можете підштовхнути нагороду за експлуатацію співробітника та спостерігати, як змінюється поведінка всієї популяції.

Теорія ігор досягає свого охоплення далеко за межами двох-гравних ігрових матриць. В економіці рівновага Наша прогнозує ціни в олігополіях та лежить в основі дизайну аукціонів — аукціон Вікрі (друге місце) робить ставку на справжню вартість домінантою стратегією. У політичній науці взаємна гарантована знищення аналізується як рівновага Наша, підтримувана лише катастрофічними витратами відхилення. В інформатиці парадокс Брейсса показує, що додавання дороги в мережу може погіршити подорож кожного водія, коли кожен з них самозацікавлено маршрутується до нової рівноваги: визначте гравців, стратегії, винагороди та запитайте, чого ніхто не може покращити наодинці.

Frequently asked questions

Спробуйте наживо

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