Доминантные стратегии и итеративное устранение

Логика «отсечения невыгодных действий»

Прежде чем искать равновесие Нэша, полезно задать более простой вопрос: есть ли стратегии, которые никогда не выгодно применять? Такие стратегии называются доминируемыми: что бы ни делали соперники, другая стратегия всегда лучше. Рациональный игрок никогда не выберет доминируемую стратегию — можно «отсечь» её и упростить игру.

Повторяя эту процедуру итерационно, мы иногда приходим к единственному исходу — равновесию. Этот метод требует не только рациональности каждого игрока, но и общего знания рациональности: я знаю, что ты рационален; ты знаешь, что я знаю; и так далее.

Строгое и слабое доминирование

Строгое доминирование: Стратегия sᵢ строго доминирует sᵢ', если для всех s₋ᵢ ∈ S₋ᵢ: uᵢ(sᵢ, s₋ᵢ) > uᵢ(sᵢ', s₋ᵢ). Строго доминируемая стратегия никогда не выбирается рациональным игроком, вне зависимости от убеждений о соперниках.

Слабое доминирование: uᵢ(sᵢ, s₋ᵢ) ≥ uᵢ(sᵢ', s₋ᵢ) для всех s₋ᵢ, и хотя бы для одного s₋ᵢ неравенство строгое. Слабо доминируемые стратегии требуют более аккуратного обращения — устранение может зависеть от порядка.

Доминирование смешанными стратегиями: Чистая стратегия может быть доминируемой смешанной, даже если ни одна другая чистая её не доминирует. Это важно: только проверки попарного доминирования недостаточно.

Алгоритм IESDS

IESDS (Iterated Elimination of Strictly Dominated Strategies):

Найти строго доминируемые стратегии каждого игрока
Устранить их из игры
Повторить с оставшейся (меньшей) игрой
Продолжать до стабилизации

Теорема: Порядок устранения при строгом доминировании не влияет на конечный результат (инвариантность порядка). Для слабого доминирования — может влиять!

Если IESDS приводит к единственному профилю — это единственное равновесие Нэша. Если к нескольким — IESDS не решил задачу выбора равновесия.

Числовой пример: матрица 3×3

	L	C	R
T	(4,3)	(5,1)	(6,2)
M	(2,1)	(8,4)	(3,6)
B	(3,0)	(9,6)	(2,8)

Шаг 1. Анализируем стратегии Игрока 2 (столбцы). Сравниваем C и R: при T: u₂(C)=1, u₂(R)=2 → R>C; при M: u₂(C)=4, u₂(R)=6 → R>C; при B: u₂(C)=6, u₂(R)=8 → R>C. Стратегия C строго доминируется R. Устраняем C.

Шаг 2. Оставшаяся игра (без C):

	L	R
T	(4,3)	(6,2)
M	(2,1)	(3,6)
B	(3,0)	(2,8)

Анализируем стратегии Игрока 1. Сравниваем T и B: при L: u₁(T)=4, u₁(B)=3 → T>B; при R: u₁(T)=6, u₁(B)=2 → T>B. Стратегия B строго доминируется T. Устраняем B.

Шаг 3. Оставшаяся игра:

	L	R
T	(4,3)	(6,2)
M	(2,1)	(3,6)

Анализируем стратегии Игрока 1. T vs M: при L: 4>2 → T лучше; при R: 6>3 → T лучше. M строго доминируется T. Устраняем M.

Шаг 4. Оставшийся Игрок 1 — только T. Игрок 2 выбирает: u₂(L|T)=3, u₂(R|T)=2 → L лучше.

Результат: (T, L) — единственное равновесие Нэша. Выигрыши: (4, 3).

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

В дилемме заключённого «Предать» строго доминирует «Молчать» для каждого игрока — один шаг IESDS приводит к равновесию (Предать, Предать). Это объясняет парадокс: равновесие единственно и находится устранением доминируемых стратегий, но оно Парето-субоптимально.

Ограниченная глубина стратегического мышления

IESDS предполагает бесконечную «вложенность» знания о рациональности. В реальности люди мыслят стратегически лишь до нескольких уровней (уровень 0: выбирает случайно; уровень k: оптимально отвечает на уровень k−1).

Эксперимент Нагеля — задача p-красоты: Игроки называют число от 0 до 100. Побеждает тот, чьё число ближе к p × (среднее по всем). При p = 2/3:

Уровень 0: наивный выбор 50. Уровень 1: думает, что все на уровне 0, выбирает 50 × 2/3 ≈ 33. Уровень 2: выбирает 33 × 2/3 ≈ 22. Уровень 3: ≈ 15. Равновесие Нэша: 0.

В реальных экспериментах большинство отвечают 22–33. Это «уровень 2–3» стратегического мышления. Менеджеры инвестиционных фондов показывают уровень 4–5 — больше, чем студенты, но всё равно далеко от равновесия.

Реальное приложение: ценообразование в авиации

Авиакомпании устанавливают цены почти одновременно несколько раз в день. Стратегии: держать высокую цену (H) или снизить (L). Если H строго доминирует L при любых стратегиях конкурента — ценовой войны не будет. Если нет — IESDS не даёт ответа, нужен анализ повторяющейся игры.

Доминантные стратегии в проектировании рынков и аукционов

Концепция доминантных стратегий имеет фундаментальное практическое значение: механизм, в котором правдивое поведение является доминантной стратегией для каждого участника, называется стратегически устойчивым. Аукцион Викри (второй цены) — классический пример: независимо от того, что делают другие участники, правдивое декларирование собственной оценки доминирует. Именно это свойство лежит в основе механизма VCG (Викри–Кларк–Гровс), применяемого в аукционах частотного спектра и интернет-рекламе. Процедура итеративного устранения строго доминируемых стратегий (IESDS) используется в поведенческой экономике для предсказания результатов экспериментов. Модели «k-уровневого мышления» показывают: реальные люди делают обычно 1–2 итерации устранения, а не бесконечное число, что объясняет их отклонения от равновесия Нэша в экспериментах. В корпоративных переговорах знание о том, какие стратегии являются строго доминируемыми для оппонента, позволяет «срезать» пространство возможных исходов и точнее предсказать его поведение. Это используется инвестиционными банками при структурировании сложных сделок с несколькими контрагентами.

Задание: Дана матрица. Примените IESDS. Совпадает ли результат с равновесием Нэша? Есть ли доминирование смешанными стратегиями?

	L	C	R
T	3,1	2,3	4,2
M	1,2	5,4	2,5
B	2,3	3,2	1,4