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

Материал из MachineLearning.

Версия от 14:12, 25 июля 2026; Kirill Bazhutov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM и проверена участником Kirill Bazhutov 18:12, 25 июля 2026 (MSD)

Дилемма заключённого (англ. Prisoner's dilemma) — симметричная некооперативная игра двух лиц, в которой у каждого игрока имеется строго доминирующая стратегия отказа от сотрудничества, однако возникающее при её выборе обоими игроками равновесие Нэша Парето-доминируется исходом взаимного сотрудничества.

Матричная игра была исследована Мериллом Фладом (Merrill Flood) и Мелвином Дрешером (Melvin Dresher) в RAND Corporation в 1950 году.^[1] Альберт Такер предложил интерпретацию игры в виде истории о двух арестованных преступниках и ввёл закрепившееся за ней название.

В машинном обучении дилемма заключённого используется прежде всего как простейшая матричная среда для исследования обучения в играх. Её последовательные и пространственные варианты применяются для изучения возникновения сотрудничества, нестационарности многоагентного обучения и зависимости выученных политик от структуры вознаграждений.

Содержание

1 Формальная математическая модель
- 1.1 Платежная матрица
- 1.2 Математические условия и равновесие Нэша
2 Повторная игра и турниры стратегий
- 2.1 Конечный и бесконечный горизонт
- 2.2 Турниры Аксельрода и алгоритмические стратегии
3 Дилемма заключённого в машинном обучении
4 Обобщения
5 Вычислительный эксперимент на Python
6 См. также
7 Примечания
8 Литература

Формальная математическая модель

Платежная матрица

В классической постановке каждый из двух агентов имеет два возможных действия: Сотрудничать (Cooperate, $C$ ) или Предать (Defect, $D$ ). Возможные исходы игры описываются платежной матрицей, где выигрыши обозначаются следующим образом:

$T$ (Temptation) — искушение, выигрыш при предательстве сотрудничающего оппонента;
$R$ (Reward) — вознаграждение при взаимном сотрудничестве;
$P$ (Punishment) — наказание за взаимное предательство;
$S$ (Sucker's payoff) — участь простака, выигрыш сотрудничающего при предательстве оппонента.

Платежная матрица дилеммы заключённого
	Агент 2: Сотрудничает (C)	Агент 2: Предаёт (D)
Агент 1: Сотрудничает (C)	$(R, R)$	$(S, T)$
Агент 1: Предаёт (D)	$(T, S)$	$(P, P)$

Математические условия и равновесие Нэша

Игра классифицируется как дилемма заключённого, если её параметры строго удовлетворяют неравенству:

$T > R > P > S$

Анализ показывает, что предательство ( $D$ ) является строго доминирующей стратегией для обоих агентов: вне зависимости от выбора оппонента, действие $D$ приносит строго больший выигрыш ( $T > R$ и $P > S$ ). В результате рационального выбора агентов игра приходит к исходу $(D, D)$ с выигрышами $(P, P)$ , который является единственным равновесием Нэша.

Исход $(C, C)$ Парето-доминирует равновесие $(D, D)$ , поскольку оба игрока получают $R > P$ . При этом $(C, C)$ не обязательно является единственным Парето-эффективным исходом: в исходах $(C, D)$ и $(D, C)$ один из игроков получает максимальный выигрыш $T$ . Если дополнительно выполнено условие $2R > T + S$ , взаимное сотрудничество максимизирует суммарный выигрыш в одной партии. Этот конфликт между индивидуальной рациональностью и коллективной эффективностью составляет содержание дилеммы.^[1]

Повторная игра и турниры стратегий

Динамика игры кардинально меняется при многократном повторении партий. Теоретический анализ требует строгого разделения игр с конечным и бесконечным горизонтом.

Конечный и бесконечный горизонт

Если число партий конечно и заранее известно, обратная индукция приводит к предательству в последней партии, а затем последовательно во всех предшествующих партиях. Поэтому единственным совершенным по подыграм равновесием при стандартных предположениях остаётся постоянное предательство.^[1]

При бесконечном или случайно завершающемся взаимодействии будущие последствия текущего действия могут поддерживать сотрудничество. Ожидаемый выигрыш вычисляется с учётом фактора дисконтирования $\gamma \in [0, 1)$ . Профиль, при котором оба игрока используют триггерную стратегию (Grim Trigger, сотрудничество до первого предательства оппонента с последующим вечным $D$ ), является совершенным по подыграм равновесием при условии:

$\frac{R}{1-\gamma} \ge T + \frac{\gamma P}{1-\gamma},$

что математически сводится к:

$\gamma \ge \frac{T - R}{T - P}.$

Турниры Аксельрода и алгоритмические стратегии

В начале 1980-х годов Роберт Аксельрод провел серию компьютерных турниров среди алгоритмических стратегий для итеративной дилеммы.^[1] Стратегия Tit-for-Tat («Око за око»), предложенная Анатолем Рапопортом, получила наибольший суммарный результат в обоих турнирах.

Этот результат не означает существования универсально оптимальной стратегии: итог зависит от набора соперников, продолжительности взаимодействия, функции оценки и вероятности ошибок. В среде с шумом (когда исполняемое действие может случайно измениться) Tit-for-Tat уязвима, так как единичная ошибка запускает бесконечную цепочку взаимных наказаний. Для уменьшения последствий случайных ошибок исследовались прощающие варианты Generous Tit-for-Tat и стратегия Win-Stay, Lose-Shift (или Pavlov), которая способна восстанавливать сотрудничество после обоюдного предательства.^[1]

Отдельное направление образуют стратегии с нулевым детерминантом (Zero-Determinant strategies), позволяющие одному игроку алгоритмически задавать строгие линейные соотношения между долговременными выигрышами участников, фактически форсируя долю выигрыша оппонента.^[1]

Дилемма заключённого в машинном обучении

Последовательные социальные дилеммы

Для применения в машинном обучении классическая матричная игра обобщается до частично наблюдаемой марковской игры (Partially Observable Markov Game). Такая среда описывается кортежем:

$\mathcal{G} = \langle \mathcal{S}, \{\mathcal{A}_i\}_{i=1}^n, \{\mathcal{O}_i\}_{i=1}^n, \mathcal{P}, \{r_i\}_{i=1}^n, \{O_i\}_{i=1}^n, \gamma \rangle,$

где $\mathcal{S}$ — множество состояний, $\mathcal{A}_i$ — действия агента $i$ , $\mathcal{O}_i$ — пространства наблюдений, $\mathcal{P}$ — ядро вероятностей переходов, $r_i$ — индивидуальные функции вознаграждения, $O_i$ — функции наблюдения. В таких последовательных социальных дилеммах (Sequential Social Dilemmas) сотрудничество и предательство — не одиночные действия, а комплексные свойства выученных политик на протяжении эпизода.^[1]

Проблема нестационарности в MARL

При использовании независимого Q-обучения (Independent Q-learning) в MARL каждый агент максимизирует собственную функцию полезности. Однако изменение политик других агентов в процессе обучения делает наблюдаемую среду нестационарной. В социальных дилеммах независимое обучение может приводить к субоптимальным равновесиям или нестационарной динамике. Результат критически зависит от механизма исследования (exploration), инициализации, представления состояния, продолжительности взаимодействия и структуры вознаграждений.^[1]

Централизованное обучение (CTDE)

Для смягчения проблемы нестационарности и облегчения координации агентов широко применяется принцип CTDE (Centralized Training with Decentralized Execution). В рамках этого подхода модель на этапе обучения имеет доступ к глобальному состоянию $\mathcal{S}$ и совместным действиям всех агентов, а во время исполнения агенты действуют децентрализованно, опираясь только на локальные наблюдения $o_i \in \mathcal{O}_i$ .

MADDPG используется для смешанных кооперативно-конкурентных сред, где критик обучается централизованно;^[1]
QMIX предназначен для полностью кооперативных задач с общей командной наградой, используя монотонную сеть смешивания.^[1]

Важно отметить, что CTDE является принципом организации обучения, а не гарантией сходимости к Парето-оптимальной политике. Для QMIX гарантируется лишь согласованность централизованной и децентрализованной максимизации при условии монотонного разложения общей функции ценности.

Обобщения

Матричная формулировка допускает ряд концептуальных расширений:

Эволюционная теория игр: изучает популяционную динамику дилеммы с помощью уравнений репликатора, где успешные стратегии (аллели) пропорционально увеличивают свою долю в популяции.
Пространственные игры на графах: агенты взаимодействуют только с соседями по топологической решетке, что порождает сетевую реципрокность — механизм выживания кооператоров через образование локальных кластеров.
Игры общественных благ (Public Goods Games): многопользовательское обобщение проблемы, формализующее «трагедию общин», где индивидуальный вклад в общий ресурс масштабируется фактором синергии, но распределяется поровну среди всех, включая безбилетников (free-riders).
Смежные классы игр: при изменении порядка выигрышей возникают другие известные паттерны взаимодействия, такие как «Охота на оленя» (Stag Hunt, координационная игра) или «Цыплёнок» (Chicken / Snowdrift, антикоординационная игра).

Вычислительный эксперимент на Python

Для демонстрации зависимости успешности политики от состава участников и наличия шума ниже реализован круговой турнир пяти базовых детерминированных алгоритмов. Код строит матрицу попарных выигрышей $M_{ij} = \frac{1}{L} \sum_{t=1}^L r_t(s_i, s_j)$ с использованием фиксированного генератора псевдослучайных чисел для обеспечения воспроизводимости.

import numpy as np
 
# Базовые алгоритмические стратегии
# 0 - Cooperate (C), 1 - Defect (D)
def all_c(my_hist, opp_hist): return 0
def all_d(my_hist, opp_hist): return 1
def tft(my_hist, opp_hist):   return opp_hist[-1] if opp_hist else 0
def grim(my_hist, opp_hist):  return 1 if 1 in opp_hist else 0
 
def pavlov(my_hist, opp_hist):
    if not my_hist:
        return 0
    # Pavlov: сотрудничает после (C,C) и (D,D), предает после (C,D) и (D,C)
    return 0 if my_hist[-1] == opp_hist[-1] else 1
 
strategies = [all_c, all_d, tft, grim, pavlov]
names = ["AllC", "AllD", "TFT", "Grim", "Pavl"]
 
def run_pairwise_tournament(noise=0.0, steps=200, runs=10, seed=42):
    rng = np.random.default_rng(seed)
    # Выигрыши: (0,0)->(3,3), (0,1)->(0,5), (1,0)->(5,0), (1,1)->(1,1)
    payoffs = {(0,0): (3,3), (0,1): (0,5), (1,0): (5,0), (1,1): (1,1)}
    n = len(strategies)
    matrix = np.zeros((n, n))
 
    for i, s1 in enumerate(strategies):
        for j, s2 in enumerate(strategies):
            total_score = 0
            for _ in range(runs):
                h1, h2 = [], []
                for _ in range(steps):
                    a1, a2 = s1(h1, h2), s2(h2, h1)
 
                    # Внесение стохастического шума в наблюдения/исполнение
                    if rng.random() < noise: a1 = 1 - a1
                    if rng.random() < noise: a2 = 1 - a2
 
                    h1.append(a1)
                    h2.append(a2)
                    total_score += payoffs[(a1, a2)][0]
 
            # Средний выигрыш стратегии i против стратегии j
            matrix[i, j] = total_score / (steps * runs)
 
    return matrix
 
def print_matrix(title, M):
    print(title)
    print(" " * 6 + "".join([f"{n:>7}" for n in names]) + " |   Mean")
    print("-" * 49)
    for i, row in enumerate(M):
        row_str = "".join([f"{val:7.2f}" for val in row])
        print(f"{names[i]:<5} {row_str} | {row.mean():7.2f}")
    print()
 
M_clean = run_pairwise_tournament(noise=0.0)
M_noisy = run_pairwise_tournament(noise=0.05)
 
print_matrix("Матрица попарных выигрышей M_{ij} (без шума):", M_clean)
print_matrix("Матрица попарных выигрышей M_{ij} (шум 5%):", M_noisy)

Запуск кода демонстрирует хрупкость реактивных стратегий и то, как итоговое место зависит от состава турнира:

Матрица попарных выигрышей M_{ij} (без шума):
          AllC   AllD    TFT   Grim   Pavl |   Mean
-------------------------------------------------
AllC     3.00   0.00   3.00   3.00   3.00 |   2.40
AllD     5.00   1.00   1.02   1.02   3.00 |   2.21
TFT      3.00   0.99   3.00   3.00   3.00 |   2.60
Grim     3.00   0.99   3.00   3.00   3.00 |   2.60
Pavl     3.00   0.50   3.00   3.00   3.00 |   2.50
 
Матрица попарных выигрышей M_{ij} (шум 5%):
          AllC   AllD    TFT   Grim   Pavl |   Mean
-------------------------------------------------
AllC     3.00   0.24   2.82   0.62   2.77 |   1.89
AllD     4.75   1.00   1.21   1.21   3.81 |   2.39
TFT      2.88   0.97   2.24   1.23   2.22 |   1.91
Grim     0.68   0.96   1.25   1.14   1.28 |   1.06
Pavl     2.78   0.88   2.26   1.29   2.79 |   2.00

В детерминированной среде AllD успешно эксплуатирует безусловных кооператоров, но показывает низкий средний результат из-за неспособности договориться с остальными. В зашумлённой среде (где случайное искажение запускает у TFT цепь взаимных предательств, а Grim Trigger навсегда уходит в глухую оборону) средние выигрыши резко падают. Pavlov, напротив, демонстрирует лучшую выживаемость среди кооперативных алгоритмов благодаря способности восстанавливать сотрудничество после взаимных ошибок.

См. также

Примечания

Литература

Flood M. M. Management Science. — 1958. — Т. 5. — № 1. — С. 5–26.
Luce R. D., Raiffa H. Games and Decisions: Introduction and Critical Survey. — Wiley, 1957. — ISBN 978-0486659435
Axelrod R. Journal of Conflict Resolution. — 1980. — Т. 24. — № 1. — С. 3–25.
Axelrod R. Journal of Conflict Resolution. — 1980. — Т. 24. — № 3. — С. 379–403.
Axelrod R. The Evolution of Cooperation. — Basic Books, 1984. — ISBN 978-0465021215
Fudenberg D., Tirole J. Game Theory. — MIT Press, 1991. — ISBN 978-0262061414
Nowak M., Sigmund K. Nature. — 1993. — Т. 364. — С. 56–58.
Press W. H., Dyson F. J. Proceedings of the National Academy of Sciences (PNAS). — 2012. — Т. 109. — № 26. — С. 10409–10413.
Busoniu L., Babuska R., De Schutter B. IEEE Transactions on Systems, Man, and Cybernetics, Part C. — 2008. — Т. 38. — № 2. — С. 156–172.
Leibo J. Z., Zambaldi V., Lanctot M., Marecki J., Graepel T. Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). — 2017. — С. 464–473.
Lowe R., Wu Y., Tamar A., Harb J., Abbeel O., Mordatch I. Advances in Neural Information Processing Systems (NeurIPS). — 2017. — Т. 30.
Rashid T., Samvelyan M., Schroeder de Witt C., Farquhar G., Foerster J., Whiteson S. Proceedings of the 35th International Conference on Machine Learning (ICML). — 2018. — С. 4295–4304.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%B7%D0%B0%D0%BA%D0%BB%D1%8E%D1%87%D1%91%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE»

Категории: Теория игр | Обучение с подкреплением | Популярные и обзорные статьи