Теория игр: равновесие Нэша, стратегические взаимодействия и механизм-дизайн

Теория игр — математический язык стратегических взаимодействий. Когда результат каждого агента зависит от действий других, классическая оптимизация недостаточна. Теория игр, разработанная Нэшем, Ауманом, Шапли (все — нобелевские лауреаты), стала универсальным инструментом экономики, политологии, биологии и компьютерных наук.

Нормальная форма игры

Игра в нормальной форме: (I, {Sᵢ}ᵢ∈I, {uᵢ}ᵢ∈I):

• I = {1,...,n} — множество игроков
• Sᵢ — множество стратегий игрока i
• uᵢ: S₁×...×Sₙ → ℝ — функция выигрыша

Равновесие Нэша (1950): профиль стратегий (s₁*,...,sₙ*) такой, что ни один игрок не может улучшить свой выигрыш, изменив стратегию в одностороннем порядке:

uᵢ(sᵢ*, s_{-i}) ≥ uᵢ(sᵢ, s_{-i}) для всех sᵢ ∈ Sᵢ, i ∈ I

Расшифровка: s_{-i}* = стратегии всех игроков кроме i. Равновесие Нэша — «точка покоя»: никто не хочет отклоняться.

Теорема Нэша (1950): В каждой конечной игре в нормальной форме существует равновесие в смешанных стратегиях.

Классические примеры

Дилемма заключённого:

Доминирующая стратегия для обоих — «доносить» (payoff 5>3 или 1>0). НЭ: (Доносить, Доносить) = (1,1). Парето-неэффективно — (Молчать, Молчать) = (3,3) лучше для обоих. Фундаментальная иллюстрация: индивидуальная рациональность ≠ коллективная эффективность.

Реальные примеры: гонка вооружений, ценовые войны, рыбный промысел (каждый ловит сколько может → коллапс ресурса).

Координационные игры:

Два НЭ: (Лево,Лево) и (Право,Право). Без координации — возможна катастрофа. Решение: социальные нормы (в России — правостороннее движение), законы.

Равновесие Корно (олигополия): n фирм с издержками c, рыночный спрос P = a − bQ. НЭ: каждая фирма производит q* = (a−c)/((n+1)b). Цена: P* = (a+nc)/(n+1). При n→∞: P* → c (конкуренция). При n=1 (монополия): P* = (a+c)/2.

Экстенсивная форма и подыгровое совершенство

Игра в экстенсивной форме: дерево решений с информационными множествами. Стратегия = полный план действий в каждом информационном множестве.

Обратная индукция: в играх с полной информацией решаем «от конца»: сначала оптимум в последнем узле, затем в предпоследнем и т.д.

Подыгровое совершенное равновесие (SPE): НЭ в каждом подыгровой (не только вся игра). Устраняет невероятные угрозы.

Пример: монопольный вход. Entrant: войти или нет. Incumbent: бороться или уступить. НЭ: много, включая «Войти, Уступить». Угроза «буду бороться» устраняется SPE — incumbent предпочтёт уступить в этом подыгре (если борьба дороже уступки).

Механизм-дизайн: обратная теория игр

Задача: дизайнер хочет реализовать определённый социальный выбор (аллокацию, правило), но агенты имеют частную информацию (типы). Как создать «правила игры», чтобы агенты добровольно раскрывали истинные типы?

Принцип выявления (Revelation Principle): любой реализуемый результат достижим механизмом прямого выявления (каждый агент сообщает свой тип), при котором правдивость — доминирующая стратегия (strategy-proof mechanism).

VCG (Vickrey-Clarke-Groves) механизм: в задачах эффективного размещения общественных благ: каждый агент получает transfer tᵢ = h(θ_{-i}) + Σⱼ≠ᵢ vⱼ(k*, θⱼ). При правдивом сообщении: максимизирует суммарное благосостояние. Правдивость — доминирующая стратегия. Пример: второй ценовой аукцион (Vickrey) — выиграет давший высшую ставку, заплатит вторую.

Аукцион Викри: покупатели с валюацией θᵢ. Доминирующая стратегия — ставить ровно θᵢ. Победитель — максимальная ставка, платит вторую. Доказательство правдивости: если θᵢ > max θⱼ (j≠i), завысить ставку не поможет, занизить — риск потери.

Численный пример: Равновесие Нэша в смешанных стратегиях

Матрица Matching Pennies: игрок 1 выбирает H/T, игрок 2 — H/T. Если совпало — 2 платит 1 (выигрыш (1,−1)), не совпало — 1 платит 2 (выигрыш (−1,1)). Чистых НЭ нет. Смешанное НЭ: каждый выбирает H с вероятностью p*. Условие безразличия: 1·p* + (−1)(1−p*) = (−1)·p* + 1·(1−p*) → p* = 0.5. Ожидаемый выигрыш каждого = 0.

Задание: Игра: две фирмы выбирают цены p₁,p₂ ∈ [0,10]. Спрос на продукцию фирмы i: Dᵢ = 12−2pᵢ + pⱼ. Издержки: cᵢ = 2. (1) Найдите функции реакции (best responses). (2) Вычислите НЭ Бертрана. (3) Сравните с кооперативным равновесием (совместная максимизация прибыли). (4) Если игра повторяется бесконечно с дисконтом δ=0.9 — при каких условиях сотрудничество поддерживается стратегией grim trigger?