Algorithmic Game Theory

Каждое утро миллионы водителей независимо выбирают маршруты в Google Maps. Каждую секунду тысячи серверов балансируют нагрузку. Каждый раз при TCP соединении алгоритм «договаривается» о скорости. Это не централизованное управление - это стратегические системы. Algorithmic Game Theory изучает вычислительные аспекты равновесий: насколько далеко от оптимума и как быстро найти.

• **Интернет-маршрутизация:** BGP (Border Gateway Protocol) - игра между провайдерами. Price of Anarchy для интернет-трафика и почему централизация (SDN) может помочь
• **Облачные вычисления:** распределение задач по серверам - congestion game. Алгоритмы балансировки нагрузки (Amazon, Google) учитывают PoA и потенциальные функции
• **Google AdWords (смарт-биддинг):** алгоритм автоматического назначения ставок - no-regret learning, сходящийся к correlated equilibrium рекламного аукциона

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

• Evolutionary Game Theory

Price of Anarchy

Утром тысячи водителей едут на работу. Каждый выбирает маршрут, который минимизирует его личное время. Никто не думает об общей пробке. В результате - знаменитый парадокс Брайеса: добавление новой дороги может увеличить суммарное время в пути. Разрыв между «эгоистичным» равновесием Нэша и социальным оптимумом называется Price of Anarchy (PoA) - цена анархии.

PoA = (худшее NE) / (социальный оптимум) PoS = (лучшее NE) / (социальный оптимум) PoA ≥ PoS ≥ 1 (при минимизации стоимости; при максимизации - ≤ 1). PoA = 1: равновесие = оптимум (нет социальных потерь от эгоизма) PoA = ∞: равновесие катастрофически хуже оптимума

Congestion Games и потенциальные игры

Congestion game - каждый игрок выбирает набор ресурсов (дорог, серверов), стоимость ресурса растёт с числом пользователей. Почему нас интересует этот класс? Потому что он имеет замечательное свойство: всегда существует равновесие в чистых стратегиях. Доказательство через **потенциальную функцию** - скалярную функцию, убывающую при каждом улучшении игрока.

Игра - потенциальная, если существует Φ(s) такая, что: uᵢ(sᵢ', s₋ᵢ) - uᵢ(sᵢ, s₋ᵢ) = Φ(sᵢ', s₋ᵢ) - Φ(sᵢ, s₋ᵢ) Каждый шаг, улучшающий выигрыш игрока, увеличивает Φ. Поскольку Φ ограничена сверху → Best Response Dynamics сходится → существует NE в чистых стратегиях. Congestion games - потенциальные с Φ(s) = Σ_r Σ_{k=1}^{nᵣ(s)} cᵣ(k)

Потенциальные игры - самый изученный класс игр в algorithmic GT. Их свойства: гарантированное NE в чистых стратегиях, сходимость best-response dynamics, тесная связь с оптимизацией (минимизация Φ = социальный оптимум в некоторых случаях). TCP congestion control - это congestion game на уровне транспортного протокола!

Маршрутизация и парадокс Брайеса

Парадокс Брайеса: добавление дороги нулевого времени в сеть может увеличить время для ВСЕХ. Почему? Все хотят воспользоваться «быстрой» дорогой, создавая перегрузку. Что хуже - перегрузка перевешивает выигрыш от быстрой дороги. Решение: убрать дорогу. Это контринтуитивный результат с серьёзными практическими следствиями.

Сеть: S → A, S → B, A → T, B → T (4 пути по 1), плюс A → B с нулевым временем. Без A→B: NE = поровну по S→A→T и S→B→T, время = 1.5 С A→B: NE = все по S→A→B→T, время = 2 (хуже!) PoA routing networks с линейными latency функциями = 4/3 (теорема Roughgarden-Tardos, 2002)

Практические следствия парадокса Брайеса: в интернет-маршрутизации добавление прямого канала может ухудшить общую пропускную способность. В финансах: добавление нового финансового инструмента (дериватива) может дестабилизировать рынок. Регуляторный вывод: проектирование сетей должно учитывать стратегическое поведение агентов.

Вычислительная сложность поиска NE

Нэш доказал существование равновесия. Но как его найти? Это оказалось удивительно сложной задачей. Поиск NE в общей игре - PPAD-полная задача (Daskalakis, Goldberg, Papadimitriou, 2006). PPAD - класс задач, где существование решения гарантировано, но нахождение - экспоненциально сложно. Иными словами: NE существует, но вычислить его - астрономически долго в худшем случае.

PPAD (Polynomial Parity Arguments on Directed graphs) - класс задач, сводящихся к задаче о конце пути в графе. GNash = поиск NE в 2-игровой биматричной игре - PPAD-полна. Следствие: если P ≠ NP (что почти наверняка), нет полиномиального алгоритма для поиска NE в общих играх. Практически: работают аппроксимации и специальные случаи.

Если NE так сложно найти - как работают реальные системы? Ответы: 1. Специальные структуры (zero-sum, potential games) решаемы эффективно. 2. Аппроксимации (ε-NE) достаточны на практике. 3. Онлайн-обучение (no-regret algorithms) сходится к coarse correlated equilibrium, а не NE - это более слабая, но вычислимая концепция. 4. Real markets work via price signals, not by computing NE.

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

• **Price of Anarchy:** PoA = (worst NE) / (social optimum) - стоимость эгоизма. Для linear routing PoA = 4/3
• **Congestion games:** всегда NE в чистых стратегиях через потенциальную функцию - TCP, routing, cloud
• **Парадокс Брайеса:** добавление дороги может всем навредить - контринтуитивное следствие стратегического поведения
• **PPAD-полнота:** нахождение NE экспоненциально сложно в общем случае; практика - аппроксимации и no-regret learning

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

Algorithmic GT - мост между теорией игр и computer science:

• Игры с нулевой суммой — Zero-sum NE находится за полиномиальное время через LP - эффективный частный случай
• Mechanism Design — Механизмы проектируются так, чтобы PoA = 1 или минимальный
• Теория игр в ML — No-regret learning в ML = подход к correlated equilibrium в AGT

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

• Kubernetes автоматически распределяет pods по нодам - это congestion game? Какой будет PoA при наивной жадной стратегии планировщика?
• Парадокс Брайеса в программировании: добавление кеша иногда замедляет систему (cache invalidation storms). Как это аналогично парадоксу маршрутизации?
• No-regret learning гарантирует сходимость к coarse correlated equilibrium, а не к NE. Достаточно ли этого для практических систем? Когда разница важна?

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

• alg-20-greedy