Теория игр
Повторяющиеся игры и народная теорема
В однопериодной дилемме заключённого рациональные игроки всегда предают. При бесконечном повторении картина меняется: сотрудничество становится равновесием. Народная теорема объясняет стабильность картелей, союзов и международных соглашений.
- **OPEC:** картель 13 стран координирует добычу нефти; механизм - повторяющаяся игра с угрозой ценовых войн при отклонении от квот
- **Антимонопольное право:** многолетние соглашения о ценах (дело Archer Daniels Midland, 1990-е) - реализованные равновесия повторяющихся игр
- **Международные договоры:** климатические соглашения устойчивы при высоком долгосрочном весе (delta -> 1) участников
- **Репутация в e-commerce:** платформы Amazon и eBay реализуют повторяющиеся игры через систему рейтингов, где обман стоит будущих продаж
Предварительные знания
- Равновесие Нэша
- Подыгровое совершенное равновесие
- Дилемма заключённого
Повторяющиеся игры: мотивация и минимакс
OPEC координирует добычу нефти 13 стран с 1960 года. В 2022 году картель контролировал около 32 млн баррелей в сутки. Математически это бесконечно повторяющаяся дилемма заключённого: каждая страна-участница предпочла бы добывать больше квоты, но угроза коллективного наказания удерживает от отклонения. Сотрудничество устойчиво при достаточно высоком факторе дисконтирования.
Чем повторяющаяся игра отличается от одношаговой?
В повторяющейся игре G^∞ игроки выбирают стратегии (планы действий, зависящие от истории) и максимизируют sum_t delta^t u_i(a_t). Дисконт delta < 1 отражает предпочтение текущей выгоды и вероятность продолжения игры. Это позволяет рассуждать о репутации и угрозах наказания.
Народная теорема: множество равновесных выплат
Минмаксная выплата игрока i: bar_v_i = min_{sigma_{-i}} max_{sigma_i} u_i(sigma_i, sigma_{-i}). Это наименьшее, что игрок может гарантировать себе независимо от действий противников. В дилемме заключённого минмакс для обоих игроков равен выплате (D, D).
Важный нюанс: в конечно повторяющейся игре (T периодов) единственное равновесие при строгом NE в однопериодной игре - взаимное отклонение во всех периодах. Рассуждение по обратной индукции: в последнем периоде T нет будущего наказания, поэтому оба отклоняются; зная это, в периоде T-1 тоже нет смысла сотрудничать - и так до t=0. Бесконечность горизонта принципиально меняет картину.
Что утверждает народная теорема для повторяющейся игры?
Народная теорема (Friedman, 1971; Aumann-Shapley, 1976): множество SPNE-выплат повторяющейся игры при delta → 1 совпадает со множеством {v : v - допустимый и v_i > min-max выплата игрока i}. Это объясняет, почему многократное взаимодействие порождает кооперативные исходы, недостижимые в одношаговой игре.
Триггер-стратегии и применение к OPEC
Народная теорема не говорит, что при delta -> 1 равновесие единственно. Наоборот: множество равновесий огромно. Это объясняет, почему реальные картели и союзы требуют дополнительных механизмов координации (третья сторона, история переговоров, focal points).
Различие между народной теоремой и её усиленной версией (Ауман-Шапли, 1994): базовая теорема требует, чтобы равновесный вектор строго доминировал минмакс; усиленная версия допускает нестрогое неравенство и требует дополнительных конструкций для SPE.
Что такое grim trigger strategy?
Grim trigger: играй кооперативно пока никто не отступал; после первого отступления переходи к минимаксной стратегии навечно. При delta достаточно близком к 1 это SPNE, потому что краткосрочная выгода от отступления (u_def - u_coop) меньше дисконтированных потерь от вечного наказания.
Связи с другими областями
Повторяющиеся игры и народная теорема - основа для анализа долгосрочного взаимодействия в экономике, политике и информатике.
- Повторяющиеся игры и народная теорема — Понятие народной теоремы расширяет анализ повторяющихся игр на бесконечный горизонт
- Дилемма заключённого — Каноничный пример, где повторение порождает кооперативные равновесия
- Эволюционная теория игр — Стратегии вроде Tit-for-Tat выживают в эволюционных моделях повторяющихся игр
Итоги
- Повторяющаяся игра G^inf(delta): дисконтированная сумма выплат, нормированная на (1-delta) для сравнимости с однопериодными выплатами
- Grim trigger: сотрудничать до первого отклонения, потом D навсегда; SPE при delta >= (g-c)/(g-p)
- Народная теорема (Ауман-Шапли): при delta -> 1 любой допустимый вектор выше минмаксных значений реализуем как SPE
- Обратная индукция разрушает сотрудничество в конечно повторяющейся игре с уникальным NE в однопериодной
- Tit-for-Tat - менее жёсткая стратегия, чем grim trigger: допускает восстановление после ошибок
Вопросы для размышления
- Почему в конечно повторяющейся игре единственное равновесие - взаимное отклонение, но в бесконечной возможно сотрудничество?
- Как народная теорема объясняет устойчивость международных картелей даже при асимметрии информации?
- В чём принципиальная разница между grim trigger и Tit-for-Tat с точки зрения робастности к ошибкам?