Теорія ігор · Формалізм
📅 Липень 2026 ⏱ ≈ 10 хв читання 🎯 Середній рівень

Формалізм теорії ігор: Nash equilibrium і домінантна стратегія

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

Коротко: Це практичний інструментарій для розв'язування ігор вручну: як записати матрицю виграшів, знайти домінантні/доміновані стратегії та поетапно їх усунути, обчислити функції найкращої відповіді й визначити чисті рівноваги Неша. Насамкінець стаття показує, як за принципом байдужості знайти змішану рівновагу — на прикладі гри "Битва статей".

Автор: MySimulator Team · Рецензія: MySimulator Editorial Review

Гри в нормальній формі

Гра в нормальній (стратегічній) формі визначається трійкою G = (N, S, u): скінченна множина гравців N, множина стратегій Sᵢ для кожного гравця i, та функція виграшу uᵢ: S₁ × S₂ × ... × Sₙ → ℝ, що дає виграш кожного гравця для кожної комбінації стратегій. Для двох гравців зі скінченними множинами стратегій це саме та матриця виграшів, яку ви, ймовірно, бачили для Дилеми в'язня.

G = (N, S, u) N = {1, 2, ..., n} множина гравців Sᵢ = {s₁, s₂, ...} множина стратегій гравця i uᵢ: S₁ × S₂ × ... × Sₙ → ℝ функція виграшу гравця i

Розв'язати гру — означає відповісти: який профіль стратегій (s₁*, ..., sₙ*) насправді оберуть раціональні, зацікавлені у власній вигоді гравці? Решта статті розбирає стандартний набір інструментів у порядку зростання загальності.

Домінантні та доміновані стратегії

Стратегія sᵢ' строго домінує стратегію sᵢ для гравця i, якщо sᵢ' дає строго вищий виграш, ніж sᵢ, проти будь-якої стратегії, яку можуть обрати інші гравці:

sᵢ' строго домінує sᵢ ⟺ uᵢ(sᵢ', s₋ᵢ) > uᵢ(sᵢ, s₋ᵢ) для всіх s₋ᵢ ∈ S₋ᵢ

(s₋ᵢ позначає "стратегії всіх гравців, крім i".) Якщо гравець має стратегію, що строго домінує кожну доступну альтернативу, ця стратегія — його домінантна стратегія — раціональний гравець обирає її незалежно від дій інших. У Дилемі в'язня Зрада строго домінує Співпрацю для обох гравців, саме тому (Зрада, Зрада) — настільки стійкий прогноз, попри те що він гірший для обох, ніж (Співпраця, Співпраця).

Слабке домінування — відповідна нестрога версія: sᵢ' слабко домінує sᵢ, якщо вона ніколи не гірша й іноді строго краща. Слабко доміновані стратегії "безпечно усувати" у більшості практичних аналізів, але в рідкісних випадках це може прибрати законну рівновагу — строге домінування завжди безпечне.

Ітеративне усунення домінованих стратегій (IEDS)

Навіть якщо жодна окрема стратегія не домінує решту відверто, часто можна звузити розв'язок, повторно видаляючи доміновані стратегії:

1. Для кожного гравця видалити будь-яку стратегію, строго домінована за умови стратегій, що ще лишились у всіх інших. 2. Повторити для зменшеної гри. 3. Зупинитись, коли жодну стратегію більше не можна усунути.

Розгляньмо гру 3×3, де Гравець 1 має стратегії {Верх, Середина, Низ}, а Гравець 2 — {Ліво, Центр, Право}. Припустимо, Низ строго домінується Верхом для Гравця 1 — видаляємо Низ. У зменшеній грі 2×3 Право може тепер строго домінуватись Центром для Гравця 2 (адже Низ, який робив Право привабливим, зник) — видаляємо Право. Продовжуємо, доки гра не звузиться до однієї клітини або жодну стратегію більше не можна усунути.

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

Функції найкращої відповіді

Функція найкращої відповіді гравця i, BRᵢ(s₋ᵢ), повертає стратегію (або множину стратегій, якщо є нічия), що максимізує виграш i за даних стратегій інших гравців s₋ᵢ:

BRᵢ(s₋ᵢ) = { sᵢ ∈ Sᵢ : uᵢ(sᵢ, s₋ᵢ) ≥ uᵢ(sᵢ', s₋ᵢ) для всіх sᵢ' ∈ Sᵢ }

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

Пошук чистих рівноваг Неша

Застосуємо аналіз найкращої відповіді до класичної гри "Битва статей" (пара віддає перевагу різним подіям, але обидва хочуть бути разом):

Гравець 2 Опера Футбол Гравець 1 Опера (2, 1)* (0, 0) Футбол (0, 0) (1, 2)* * = взаємна найкраща відповідь → рівновага Неша

Підкреслюючи найкращі відповіді: якщо Гравець 2 обирає Оперу, найкраща відповідь Гравця 1 — Опера (2 > 0) — позначаємо. Якщо Гравець 2 обирає Футбол, найкраща відповідь Гравця 1 — Футбол (1 > 0) — позначаємо. Роблячи те саме для Гравця 2, знаходимо дві клітини, де підкреслені обидва виграші: (Опера, Опера) і (Футбол, Футбол). Обидві є чистими рівновагами Неша — ця гра не має єдиного прогнозу, що якраз і є проблемою координації, яку модель ілюструє.

Розв'язання змішаних рівноваг

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

Для "Битви статей" нехай Гравець 1 обирає Оперу з ймовірністю p, а Гравець 2 обирає Оперу з ймовірністю q. Гравець 2 байдужий між Оперою і Футболом, коли:

u₂(Опера | p) = u₂(Футбол | p) 1·p + 0·(1-p) = 0·p + 2·(1-p) p = 2(1-p) → p = 2/3 За симетрією, розв'язавши умову байдужості Гравця 1 щодо q, отримуємо q = 1/3. Змішана рівновага Неша: Гравець 1 обирає Оперу з ймов. 2/3, Гравець 2 — з ймов. 1/3.

Зауважте контрінтуїтивний результат: Гравець 1 (якому подобається Опера) змішує в бік Опери відносно рідше за поріг Гравця 2, і навпаки — ймовірність змішування кожного гравця визначається умовою байдужості іншого гравця, а не власними уподобаннями. Це загальна й часто не помічена властивість змішаних рівноваг, яка збиває з пантелику новачків.

Часта помилка: формулювати умову байдужості через власні виграші замість виграшів опонента. Щоб знайти, як ви маєте змішувати, потрібно розв'язати ймовірність, що робить байдужим вашого опонента, — а не навпаки.

🤝 Запустити симуляцію Дилеми в'язня

Еволюційна теорія ігор, tit-for-tat та популяційна динаміка кооперації

Відкрити симуляцію →