Доминирование и итеративное удаление

8,59 миллиарда долларов в день. Каждый поисковый запрос в Google запускает аукцион за миллисекунды - тысячи рекламодателей, тысячи ставок. Оптимальная стратегия рекламодателя в second-price auction - говорить правду о своей реальной ценности. Не торговаться. Не блефовать. Просто честно. Это не этика и не наивность. Это математика: truthful bidding строго доминирует все остальные стратегии. IESDS объясняет почему механизм Викри работает - ложь является доминируемой стратегией и вылетает на первом же шаге удаления. Аукцион на восемь миллиардов в день держится на одной теореме.

• **Аукцион Викри (VCG)**: second-price auction делает честную ставку доминирующей стратегией - используется Google AdWords, Facebook Ads, eBay. Ложь строго доминируема и вылетает на первом шаге IESDS.
• **Multi-agent RL**: алгоритмы LOLA и MADDPG явно используют dominance reasoning при обучении. DeepMind Hanabi challenge - кооперативный MARL с explicit dominance reasoning превышает базовый RL.
• **AI safety**: доминируемые стратегии - 'провальные планы' рационального агента. Если агент выбирает доминируемое действие - нарушена рациональность или модель ценностей.

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

• Nash Equilibrium

Доминирующая стратегия

8,59 миллиарда долларов в день. Каждый раз, когда пользователь вводит запрос в Google, за миллисекунды проходит аукцион - тысячи рекламодателей делают ставки. Вопрос к рекламодателю: сколько поставить? Ответ теории игр: говори правду о своей реальной ценности. Не чуть меньше. Не чуть больше. Точно столько, сколько клик действительно стоит. Это не совет - это теорема. Truthful bidding строго доминирует все остальные стратегии.

Стратегия sᵢ строго доминирует sᵢ', если uᵢ(sᵢ, s₋ᵢ) > uᵢ(sᵢ', s₋ᵢ) для ВСЕХ s₋ᵢ. Стратегия sᵢ слабо доминирует sᵢ', если uᵢ(sᵢ, s₋ᵢ) >= uᵢ(sᵢ', s₋ᵢ) для всех s₋ᵢ, и > хотя бы для одного s₋ᵢ. Строгое доминирование - безусловно лучше. Слабое - не хуже нигде и лучше хоть где-то.

Равновесие в доминирующих стратегиях (DSE) - сильнейшая концепция решения в теории игр. Не требует знания о рациональности соперника. Не требует знания его конкретной стратегии. Достаточно собственной рациональности - и выбор однозначен. Именно поэтому механизм Викри (second-price auction) так элегантен: он проектирует аукцион так, что DSE = честная ставка. Google не просит рекламодателей быть честными. Он делает честность доминирующей стратегией.

Большинство интересных игр DSE не имеют - битва полов, Matching Pennies, Камень-Ножницы-Бумага. Но концепция доминирования не теряет силу: доминируемые стратегии можно удалять. И удаление открывает новые доминируемые стратегии - так работает IESDS.

IESDS: итеративное удаление

Удалили строго доминируемую стратегию - игра уменьшилась. В меньшей игре появились новые доминируемые стратегии, которых раньше не было. Удалили их - игра уменьшилась снова. Этот процесс называется IESDS (Iterated Elimination of Strictly Dominated Strategies). Каждый шаг опирается на рациональность: "раз соперник никогда не играет X, мне не нужна стратегия Y". Каждый следующий шаг требует знания того, что соперник знает о твоей рациональности.

Критическое свойство: **порядок удаления не влияет на результат** - для строго доминируемых стратегий. Неважно, какую удалить первой. Финальное множество всегда одно. Математически это называется слиянием (confluence) - как в lambda-исчислении. Для слабо доминируемых стратегий это свойство не выполняется: порядок может изменить результат, и некоторые NE могут быть удалены.

IESDS опирается на common knowledge of rationality (CKR): все рациональны, все знают что все рациональны, все знают что все знают - и так до бесконечности. Шаг 1 удаления требует рациональности игрока. Шаг 2 - знания о рациональности соперника. Шаг k - (k-1)-го уровня вложенного знания. В поведенческой экономике люди останавливаются на уровне 1-3. В 'guessing game' (угадай 2/3 среднего) IESDS предсказывает 0, реальные люди угадывают около 22.

В multi-agent reinforcement learning (MARL) алгоритмы вроде LOLA (Learning with Opponent-Learning Awareness) явно используют рассуждения о рациональности соперника - это вычислительный аналог IESDS. DeepMind Hanabi challenge показал: кооперативные агенты, способные к explicit dominance reasoning, превосходят агентов, оптимизирующих только собственный reward. Удаление доминируемых стратегий - не академический трюк, а инженерный примитив.

Рационализируемость

После IESDS остаётся множество стратегий. Не любых - только тех, которые рациональный игрок может обоснованно выбрать. Стратегия рационализируема, если она является best response на какие-то рациональные убеждения о действиях соперника. Убеждения должны быть рациональными - то есть соперник тоже отвечает best response на свои рациональные убеждения. Рекурсивно, без конца.

Стратегия sᵢ рационализируема, если существует цепочка убеждений: - sᵢ - best response на убеждения о σ₋ᵢ - σ₋ᵢ содержит только рационализируемые стратегии других - ...рекурсивно Для игр двух игроков: множество рационализируемых стратегий = множество, пережившее IESDS. Для трёх и более игроков: рационализируемость может быть шире IESDS.

В AI safety исследованиях рационализируемость используется для анализа поведения агентов. MIRI и Anthropic Alignment используют dominance reasoning для классификации действий агента: доминируемые стратегии - это "провальные планы", которые рациональный агент никогда не выберет при любой модели мира. Если агент всё же выбирает доминируемую стратегию - это сигнал о нарушении рациональности или неверной модели ценностей.

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

• **Строгое доминирование** - стратегия лучше при ВСЕХ действиях соперника; DSE - сильнейшая концепция решения, не требует знания о сопернике
• **Слабое доминирование** - не хуже нигде, лучше хоть где-то; удаление слабо доминируемых рискованно - может убрать NE
• **IESDS** - итеративное удаление строго доминируемых; порядок не важен; никогда не удаляет NE; требует CKR
• **Рационализируемость** - стратегии, обоснованные рациональными убеждениями; для 2 игроков совпадает с IESDS

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

Доминирование и IESDS - первый шаг анализа любой игры, сужающий пространство возможных исходов:

• Равновесие Нэша — NE - подмножество IESDS: все равновесия Нэша переживают итеративное удаление
• Дилемма заключённого — Классический кейс где DSE существует, но приводит к Парето-субоптимальному исходу
• Введение в RL — Multi-agent RL использует dominance reasoning для поиска Nash-совместимых стратегий

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

• Аукцион Викри делает честную ставку доминирующей стратегией. Но Google использует не чистый Викри - правила сложнее. Как это влияет на то, является ли truthful bidding всё ещё доминирующей стратегией?
• В 'guessing game' (угадай 2/3 среднего) люди останавливаются на 1-3 шагах IESDS вместо теоретических бесконечных. Это значит, что люди нерациональны - или что common knowledge of rationality нереалистична как допущение?
• Механизм-дизайн проектирует правила так, чтобы нужное действие стало доминирующей стратегией. Какие ещё механизмы в реальном мире достигают этого - налоги, законы, социальные нормы?

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

• gt-02 — Nash equilibrium - отправная точка для понимания доминирования
• gt-04 — Дилемма заключённого - доминирование в действии
• gt-05 — Игры с неполной информацией: доминирование под неопределённостью
• rl-01 — Multi-agent RL: IESDS как итеративный best-response поиск
• prob-07-expectation — Ожидаемый выигрыш при доминировании смешанными стратегиями
• alg-21-dp