Теория игр

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

1980 год. Роберт Аксельрод объявляет компьютерный турнир: присылайте стратегии для итерированной дилеммы заключённого. 14 программ от нобелевских лауреатов и экономистов. Победитель - 4 строки кода от психолога. Tit-for-Tat: скопируй то, что сделал противник в прошлый раз. Nash equilibrium предсказывает предательство. Повторение и репутация меняют всё.

  • **Климатические переговоры:** Парижское соглашение - попытка механизм-дизайна: изменить матрицу выплат через обязательства и репутационные издержки за выход
  • **GAN-обучение:** генератор и дискриминатор в непрерывной дилемме заключённого - Nash equilibrium = реалистичные данные; инженер конструирует этот механизм намеренно
  • **Антибиотическая резистентность:** каждый врач рационально прописывает антибиотик при малейшем сомнении - и коллективно создаются супербактерии
  • **Open source экосистема:** GitHub stars, contribution graph, npm download counts - репутационные механизмы, которые сдвигают равновесие от free-riding к вкладу
  • **Мультиагентное RL:** self-play в AlphaGo, AlphaStar, OpenAI Five - итерированная дилемма заключённого как движок обучения

Предварительные знания

  • Итеративное удаление доминируемых стратегий

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

1950 год. RAND Corporation, Санта-Моника. Математики Мерилл Флуд и Мелвин Дрешер конструируют стратегию ядерного сдерживания США и СССР. В процессе они наталкиваются на игру с двумя игроками - и не могут выбраться из неё 70 лет. Альберт Такер оборачивает её в историю про заключённых. Структура осталась прежней: два рациональных агента, идеальная информация о матрице выплат - и оба приходят к исходу, который хуже для каждого.

C = молчать (Cooperate), D = предать (Defect) Игрок 2: C Игрок 2: D Игрок 1: C (-1, -1) (-3, 0) Игрок 1: D ( 0, -3) (-2, -2) D доминирует C: 0 > -1 и -2 > -3 при любом действии другого. Равновесие Нэша - (D, D) = (-2, -2), хотя (C, C) = (-1, -1) лучше для обоих.

Структура воспроизводится в самых разных системах. Гонки вооружений: каждой стране выгоднее наращивать арсенал в одностороннем порядке - и обе тратят триллионы, оставаясь в том же балансе силы. Ценовые войны авиакомпаний: снизить цену первым выгодно, пока другой не снизил тоже - и обе несут убытки. Климатические переговоры: сокращать выбросы в одностороннем порядке экономически невыгодно - и глобальная температура растёт. Везде одна и та же матрица. Везде одно равновесие.

ПрофильВыигрыш 1Выигрыш 2Итог
(C, C)-1-1Парето-оптимум
(D, C)0-3Предатель выигрывает
(C, D)-30Жертва молчания
(D, D)-2-2Nash equilibrium - хуже оптимума

Если игроки могут поговорить - они договорятся о (C, C) и проблема исчезнет

Дешёвые разговоры (cheap talk) не меняют равновесие: договориться можно, но каждый рационально предаст после. Нужны обязывающие соглашения с реальными штрафами.

Обещание молчать не меняет матрицу выигрышей. После разговора D всё ещё доминирует C. Только внешние механизмы - контракт, репутация, повторные игры - могут сделать сотрудничество устойчивым.

Почему (D, D) является равновесием Нэша в дилемме заключённого?

Турнир Аксельрода и итерированная дилемма

1980 год. Политолог Роберт Аксельрод объявляет компьютерный турнир: присылайте стратегии для итерированной дилеммы заключённого. 14 программ от нобелевских лауреатов, экономистов, математиков. Самая длинная стратегия - 77 строк. Победитель - 4 строки кода от психолога Анатоля Рапопорта. Имя стратегии: Tit-for-Tat. Алгоритм: начать с кооперации, затем копировать последний ход соперника.

**Nice (добросердечная):** начинает с кооперации, никогда не предаёт первой. **Retaliatory (мстительная):** немедленно наказывает за предательство. **Forgiving (прощающая):** возвращается к кооперации, если соперник вернулся. **Clear (прозрачная):** простой алгоритм - соперник понимает логику и не боится экспериментировать. Аксельрод провёл второй турнир, уже с 62 участниками, знавшими результаты первого. Tit-for-Tat снова выиграл.

AlphaGo учится через self-play - итерированную игру с самой собой. Каждый новый агент - это соперник предыдущего в многотысячном турнире. GANs (генеративно-состязательные сети) - непрерывная дилемма заключённого: генератор и дискриминатор синхронно эволюционируют, ни один не должен выигрывать слишком сильно. Мозг решает дилемму заключённого биохимически: окситоцин снижает барьер к кооперации, дофамин кодирует ожидание взаимности.

**Условие Фолька:** в бесконечно повторяемой игре любой результат, дающий каждому игроку не меньше его минимаксного выигрыша, может поддерживаться как равновесие - при достаточно высоком коэффициенте дисконтирования. Проще: если игроки достаточно «терпеливы» (delta близко к 1), кооперация становится устойчивой. Обратная индукция разрушает это в конечной игре с известным горизонтом.

Сотрудничество возможно только у альтруистов или при сильных эмоциональных связях

Сотрудничество эволюционирует у полностью эгоистичных агентов в повторяемых взаимодействиях - через взаимную выгоду, а не альтруизм.

Аксельрод показал, что Tit-for-Tat побеждает без каких-либо добрых намерений - просто через математику повторяемых игр. Эволюция человеческой кооперации работает по тем же принципам.

Что делает стратегию Tit-for-Tat эффективной в повторяемой дилемме заключённого?

Социальные дилеммы и механизм-дизайн

Трагедия общих ресурсов (Гаррет Хардин, 1968): деревня с общим пастбищем. Каждый пастух рационально добавляет ещё одну корову - личная выгода полная, ущерб пастбищу делится на всех. Пастбище деградирует. Это дилемма заключённого с n участниками. Рыболовство в открытом море, перегрузка серверов, загрязнение воздуха - один паттерн.

Реальная дилеммаПредательNash equilibriumМеханизм выхода
Климатические соглашенияНе сокращать выбросыГлобальное потеплениеУглеродные рынки (price signal)
ОПЕК (нефть)Превысить квоту добычиНизкие ценыМониторинг + исключение
Открытый исходный кодБрать без вкладаДеградация проектовРепутация + лицензии
Антибиотики (резистентность)ЗлоупотреблятьСупербактерииРегуляция + ценообразование

Mechanism design - "обратная теория игр": дизайнер выбирает правила так, чтобы Nash equilibrium совпало с желаемым исходом. Три инструмента: 1. **Изменение матрицы выплат** - штрафы, субсидии, налоги. Углеродный налог делает D дороже. 2. **Репутационные механизмы** - история видна всем. eBay ratings, GitHub contribution graph. 3. **Commitment devices** - обязывающие контракты с внешним enforcer. Международные договоры с санкциями.

GAN-training - mechanism design в действии. Генератор и дискриминатор - два агента в дилемме заключённого. Инженер-дизайнер конструирует функции потерь так, чтобы Nash equilibrium совпало с генерацией реалистичных данных. Когда дискриминатор не может отличить реальное от сгенерированного - Nash достигнут. Это не случайность архитектуры - это заложено в математике механизма.

Доминирующая стратегия всегда ведёт к лучшему исходу

Доминирующая стратегия лучшая для конкретного игрока, но равновесие доминирующих стратегий может быть хуже других исходов для всех участников.

Дилемма заключённого - наглядный пример: D доминирует у обоих, но (D,D) = (-2,-2) хуже для обоих, чем (C,C) = (-1,-1). Индивидуальная оптимальность не равна коллективной.

Стратегия строго доминирует другую, если она:

Ключевые идеи

  • **Дилемма заключённого:** D строго доминирует C, равновесие Нэша (D,D) хуже Парето-оптимального (C,C) - локальная рациональность глобально иррациональна
  • **Tit-for-Tat** (Аксельрод, 1980): 4 строки кода побеждают нобелевских лауреатов. Добросердечная, мстительная, прощающая, прозрачная
  • **Повторяемые игры** и «тень будущего» делают кооперацию рационально выгодной при дисконтировании delta >= 0.5
  • **Mechanism design:** изменить правила игры так, чтобы Nash = Pareto. GAN loss functions, углеродные рынки, репутационные системы - один паттерн

Связанные темы

Дилемма заключённого - фундамент для понимания более сложных игр и механизмов:

  • Равновесие Нэша — (D,D) - классический пример равновесия Нэша, не являющегося Парето-оптимальным
  • Кооперативные игры — Как выйти из дилеммы через коалиции и переговоры о дележе выигрыша
  • Эволюционная теория игр — Как Tit-for-Tat и кооперация эволюционируют в популяции стратегий

Вопросы для размышления

  • Углеродный налог меняет матрицу выплат климатической дилеммы. Какие ещё механизмы способны сдвинуть Nash equilibrium к кооперативному исходу - без изменения предпочтений агентов?
  • GAN-обучение нестабильно на практике: генератор и дискриминатор часто расходятся вместо схождения к Nash. На языке дилеммы заключённого - что происходит и почему?
  • Grim Trigger создаёт мощный сдерживающий стимул, но одна ошибка разрушает кооперацию навсегда. Какие реальные Grim Trigger-стратегии существуют в международных отношениях - и чем они отличаются от Tit-for-Tat?

Связанные уроки

  • gt-05 — Социальные дилеммы - многоагентная версия той же структуры
  • gt-10 — Эволюционная теория игр: Tit-for-Tat в популяции стратегий
  • gt-07 — Кооперативные игры: как выйти из дилеммы через коалиции
  • prob-03-conditional — Условная вероятность: Байесовское обновление репутации агентов
  • gt-02 — Nash equilibrium: база для понимания (D,D) как NE
Дилемма заключённого

0

1

Войти