Теория игр
Алгоритмическая теория игр: цена анархии
Алгоритмическая теория игр исследует вычислительную сложность нахождения равновесий и цену децентрализации. Ключевые вопросы: насколько равновесие хуже оптимума (PoA) и как проектировать механизмы с правильными стимулами?
- **Google AdWords:** аукцион с обобщённым вторым местом (GSP) приносит 237 млрд долларов в год; проектирование вдохновлено VCG
- **Транспортные сети:** парадокс Браесса объясняет, почему закрытие дорог иногда улучшает трафик; PoA = 4/3 для линейных задержек
- **Распределённые вычисления:** протоколы Tor (анонимность) и BitTorrent (tit-for-tat) - реализации механизмов с правильными стимулами
Предварительные знания
Цена анархии
Парадокс Браесса: добавление новой дороги в транспортную сеть Штутгарта в 1969 году увеличило среднее время поездок всех водителей. Это противоречит интуиции. Цена анархии для маршрутизации с линейными задержками не превышает 4/3 - результат Раффгардена и Тардоса (2002).
Цена анархии PoA = 4/3 для сетевой маршрутизации с линейными задержками означает...
Проектирование механизмов
Google в 2002 году запустил систему аукциона AdWords с ценообразованием второй цены (аукцион Викри). К 2023 году выручка Google от рекламы составила 237 млрд долларов. Аукцион Викри - единственный доминантно-стратегический механизм, максимизирующий суммарную ценность при правдивом сообщении.
Почему в аукционе Викри (второй цены) правдивая заявка является доминантной стратегией?
Метод гладкости для оценки PoA
Раффгарден (2009) предложил унифицированный метод гладкости для доказательства верхних границ цены анархии в широком классе игр. Ключевое преимущество: метод применим к correlated equilibria, not just Nash - что делает результаты более общими.
Метод гладкости унифицирует доказательства PoA для разных классов игр: конгестионные игры, аукционы с оплатой за клик (GSP), задачи о рюкзаке. В отличие от потенциальных функций, гладкость применима даже там, где потенциал не существует.
Почему метод гладкости Раффгардена сильнее, чем прямое доказательство границы PoA для Nash-равновесий?
Метод гладкости доказывает одно неравенство, которое выполняется для всех типов равновесий (Nash, correlated, coarse correlated). Это делает результат более общим: PoA ≤ λ/(1−μ) гарантирован для всего класса равновесий.
Ключевые идеи
- **Цена анархии PoA:** max(Nash_cost)/opt_cost; для маршрутизации с линейными задержками PoA = 4/3 (Раффгарден-Тардос)
- **Цена стабильности PoS:** min(Nash_cost)/opt_cost; PoS = 1 означает: оптимум является равновесием
- **VCG-механизмы:** IC + IR + эффективность; платёж = экстернальность агента для остальных
- **Теорема Майерсона:** IC <=> монотонность x_i + формула платежа; формула аукциона с максимальным доходом
- **Метод гладкости:** (λ,μ)-гладкая игра имеет PoA ≤ λ/(1−μ); результат распространяется на correlated equilibria
Вопросы для размышления
- Почему парадокс Браесса возникает именно из-за эгоизма игроков, а не из-за ошибки проектирования сети?
- Как связаны IC-совместимость механизма и монотонность функции распределения (теорема Майерсона)?
- Почему теорема Мирлиса-Сэттертуэйта делает идеальный механизм невозможным?