Теория игр
Повторяющиеся игры и теорема Фолька
Airbnb и Uber работают без центрального арбитра - потому что игра повторяется. Airbnb: 4+ млн хозяев доверяют незнакомцам. Uber: 5+ млн водителей. Ни у одного нет постоянного договора. Теорема Фолька объясняет: при высоком δ (пользователи планируют снова путешествовать) кооперация - самовыполняющееся равновесие.
- **ОПЕК:** 13 стран ограничивают добычу без принудительного механизма с 1960. Повторяющееся взаимодействие + прозрачность данных о поставках = кооперативное равновесие.
- **Airbnb/Uber рейтинги:** система оценок создаёт 'тень будущего' - угрозу плохого рейтинга = инструментализированный Grim Trigger.
- **Open Source:** разработчики пишут качественный код в публичных репозиториях. Репутация на GitHub = ценность δ·будущих возможностей. Folk theorem в действии.
Предварительные знания
Почему Airbnb работает без полиции
Airbnb достиг $75B капитализации без полиции нравов: незнакомцы ночуют в домах незнакомцев. Uber - 5M+ поездок в день с неизвестными водителями. Оба работают потому, что игра повторяется. Теорема Фолька объясняет: при δ > 0.5 кооперация устойчива как Nash-равновесие бесконечно повторяемой игры.
В одноразовой дилемме заключённого единственное равновесие Нэша - оба предают, получают (1,1). Но если игра повторяется снова и снова теми же игроками с **наблюдаемой историей** - угроза будущего наказания делает кооперацию рациональной.
Парадокс конечной повторяющейся игры: если T известно, обратная индукция разрушает кооперацию. В раунде T будущего нет - оба предают. В T-1 оба знают это - снова предают. Индукция до раунда 1 - кооперации нет никогда. Бесконечный горизонт (или неизвестный T) - единственный выход.
**Международные договоры без суда:** страны соблюдают ВТО, NATO, ядерные соглашения без глобального принудительного механизма. Повторяющееся взаимодействие + угроза каскадного выхода = самовыполняющееся равновесие. Теорема Фолька - математическое обоснование международного порядка.
Почему в конечно повторяющейся игре с известным числом раундов T кооперация всегда разрушается через обратную индукцию? Как неизвестный горизонт решает эту проблему?
Обратная индукция в конечно повторяющейся игре с уникальным Nash equilibrium (дилемма заключённого) разрушает кооперацию полностью: знание конца устраняет угрозу наказания на каждом шаге вплоть до первого. Неизвестный горизонт или δ-вероятность продолжения делает «последний раунд» недостижимым.
Фактор дисконтирования: математика терпения
Параметр δ ∈ (0,1) - фактор дисконтирования. Выплата x через k раундов стоит сегодня δᵏ·x. При δ = 0: только сегодня важно. При δ → 1: будущее почти так же важно, как настоящее. Это и нетерпение, и вероятность продолжения игры (1-δ = вероятность конца).
**Интерпретации δ:** 1) чистое предпочтение настоящего (нетерпение), 2) вероятность p = 1-δ конца игры после каждого раунда, 3) процентная ставка r через δ = 1/(1+r). Airbnb: δ высокий - пользователь планирует ещё путешествовать. Разовая сделка: δ ≈ 0 - как одноразовая игра.
В ОПЕК страны ограничивают добычу без принудительного механизма. Найдите критический δ* и объясните, почему δ реального ОПЕК обычно выше этого порога.
Условие устойчивости кооперации по Grim Trigger: δ ≥ δ* = (t-π)/(t-p), где t - выгода от одностороннего отклонения, π - выгода при кооперации, p - выгода при наказании (Nash война). При данных числах δ* = 2/4 = 0.5.
Grim Trigger и Tit-for-Tat: стратегии наказания
Угроза наказания работает только если она **credible**: соперник должен верить, что наказание последует. Нужна конкретная стратегия - план действий для каждой возможной истории игры.
Grim Trigger: кооперировать до первого предательства, потом предавать вечно. Максимальная угроза. Tit-for-Tat: первый раунд C, потом копировать последний ход соперника. Прощает после одного ответного D.
**Турниры Аксельрода (1980-1984):** политолог Robert Axelrod провёл компьютерные турниры - разные стратегии в повторяющейся дилемме заключённого. Победил Tit-for-Tat Анатолия Рапопорта. Четыре свойства победителя: добросовестность (начинает с C), провоцируемость (отвечает на D), снисходительность (прощает), простота (стратегия понятна). Книга «The Evolution of Cooperation» (1984) стала основой для эволюционной теории игр.
Почему Grim Trigger имеет меньший δ* (работает при большем разнообразии игроков), чем Tit-for-Tat, но Tit-for-Tat выигрывает турниры Аксельрода?
Grim Trigger использует максимальное наказание (вечная война), что минимизирует δ* и делает кооперацию достижимой для нетерпеливых игроков. Однако любая случайная ошибка (D вместо C) запускает вечную войну - в реальных зашумлённых условиях TfT устойчивее за счёт прощения.
Теорема Фолька: любая кооперация возможна
Теорема Фолька - один из самых глубоких результатов теории игр. При δ → 1 любая индивидуально рациональная и достижимая комбинация выплат является равновесием SPE (subgame perfect equilibrium) бесконечно повторяющейся игры.
**Парадокс теоремы Фолька:** она одновременно оптимистична (кооперация возможна!) и пессимистична (равновесий бесконечно много - которое реализуется?). «Too many equilibria» problem. Теория не предсказывает конкретное равновесие - нужны дополнительные концепции: focal points, историческая координация, fairness norms.
Что означает 'индивидуальная рациональность' в теореме Фолька, и почему без неё кооперативное соглашение не будет устойчивым?
Минимаксная выплата v*ᵢ - это гарантированный минимум, который игрок может обеспечить себе в одностороннем порядке при любых действиях остальных. Теорема Фолька говорит: достижимы только выплаты, удовлетворяющие vᵢ ≥ v*ᵢ для всех i, иначе игрок рационально выйдет из соглашения.
Ключевые идеи
- **Повторяющаяся игра**: та же стадийная игра бесконечно теми же игроками. История наблюдаема - стратегии зависят от истории.
- **δ = фактор дисконтирования**: V_coop = π/(1-δ) > V_defect = t + δp/(1-δ) при δ ≥ δ* = (t-π)/(t-p)
- **Grim Trigger**: максимальная угроза (δ* минимален), но не устойчив к ошибкам
- **Tit-for-Tat**: прощает после одного D, устойчив к ошибкам, выиграл турниры Аксельрода
- **Теорема Фолька**: при δ → 1 любые вᵢ ≥ v*ᵢ из conv(V) поддерживаются SPE. Слишком много равновесий.
Связанные темы
Повторяющиеся игры - мост между статической теорией и динамической реальностью:
- Равновесие Нэша — Повторяющиеся игры расширяют множество SPE далеко за пределы одноразовой игры через угрозы наказания
- Дилемма заключённого — Классическая стадийная игра для Folk Theorem: δ* = 0.5 разделяет кооперацию и предательство
- Сигнальные игры — Репутация в повторяющихся играх с асимметричной информацией - сигнальные механизмы в Airbnb/Uber
Вопросы для размышления
- GitHub, Stack Overflow, Wikipedia - репутационные системы без принуждения. Какой параметр в модели повторяющейся игры создаёт 'тень будущего' в этих системах? Как бы изменилось поведение, если бы аккаунты были анонимными и одноразовыми?
- Теорема Фолька - 'слишком много равновесий'. Как реальные организации (ОПЕК, ВТО) решают проблему координации на конкретном равновесии? Что играет роль 'focal point'?
- Климатические переговоры (Парижское соглашение) - повторяющаяся игра между ~200 странами с очень разными δ. Как низкий δ развивающихся стран (высокое 'нетерпение' роста) влияет на устойчивость кооперативного равновесия?