Теория игр
Сетевые игры и равновесие Вардропа
Города тратят миллиарды на строительство дорог, которые... создают больше пробок. Интернет-провайдеры добавляют пропускную способность, которую мгновенно перегружают. Парадокс Брасса - и есть причина, почему. Теория сетевых игр объясняет эту иррональность и предлагает решения.
- **GPS-навигаторы**: Waze направляет всех по «лучшему маршруту» - который немедленно перегружается; это равновесие Вардропа в реальном времени
- **Сеул, 2003**: снос шестиполосной магистрали улучшил трафик в центре - классический парадокс Брасса в городском планировании
- **Congestion pricing**: Лондон, Стокгольм, Сингапур вводят платные въезды в центр - это tax для сдвига от UE к System Optimum
Предварительные знания
Игры на сетях: маршрутизация и перегрузка
Wardrop-равновесие в дорожной сети Лондона с 3.5 млн поездок в час показывает парадокс Брэсса: добавление новой дороги увеличивает среднее время в пробке на 15%. Сетевые игры (network games) изучают стратегическое поведение агентов в сетях - дорожных, коммуникационных, социальных. Каждый агент выбирает маршрут, соединение или стратегию, не учитывая влияние на других. Результат - **congestion** (перегрузка) и социально субоптимальные равновесия.
Ключевая идея: когда выбираете маршрут по загруженной дороге, создаёте **отрицательную экстерналию** для всех остальных на этой дороге - но не учитываете это в своём решении. Совокупный результат эгоистичных решений хуже централизованного оптимума.
• **Интернет-маршрутизация**: TCP-пакеты выбирают пути; протоколы должны учитывать congestion • **Электрические сети**: потребители и генераторы; потоки распределяются по физическим законам • **Социальные сети**: вирусные распространения; каждый узел «решает» делиться ли контентом • **Финансовые рынки**: трейдеры перегружают одни активы, игнорируют другие
Почему индивидуально рациональный выбор маршрута пользователем создаёт отрицательную экстерналию?
Равновесие Вардропа
Джон Вардроп (1952)
Британский транспортный инженер Джон Вардроп в 1952 году сформулировал два принципа распределения потоков в дорожных сетях, которые теперь носят его имя. Первый принцип - User Equilibrium (UE) - описывает равновесное эгоистичное поведение. Второй принцип - System Optimum (SO) - описывает централизованный оптимум. Вардроп заложил основы Transportation Science - раздела теории игр и исследования операций.
Равновесие Вардропа существует и единственно при выпуклых функциях стоимости (монотонно растущая задержка с нагрузкой). Это важное теоретическое свойство: в отличие от Nash equilibrium в общем виде, у нас есть гарантия уникальности.
В равновесии Вардропа (User Equilibrium) все используемые маршруты имеют одинаковую задержку. Почему?
Парадокс Брасса: больше дорог - больше пробки
Один из самых контринтуитивных результатов теории игр: **добавление новой дороги может замедлить движение для всех**. Это парадокс Брасса (Braess paradox, 1968) - прямое следствие несовпадения индивидуального и социального оптимума.
Реальные случаи парадокса Брасса
В 1990 году Сеул закрыл магистраль Cheonggyecheon (восстановление реки). Транспортные эксперты ожидали коллапса. Вместо этого пробки уменьшились - парадокс Брасса в реальности. Аналогичные случаи: Stuttgart (1969), снос San Francisco freeway после землетрясения 1989. В интернет-маршрутизации: BGP routing, когда добавление нового пути увеличивало congestion.
Парадокс возникает потому что добавление новой дороги создаёт новый стратегически доминирующий маршрут. Каждый рационально переключается на него, не учитывая, что остальные делают то же самое. Индивидуально рациональные решения создают коллективно иррациональный результат - квинтэссенция проблемы common good.
В парадоксе Брасса добавление новой дороги ухудшило ситуацию для всех. Что исправило бы ситуацию?
Price of Anarchy: цена эгоизма
**Price of Anarchy (PoA)** - формальный способ измерить, насколько хуже результат эгоистичного поведения по сравнению с централизованным оптимумом. Введён Papadimitriou и Roughgarden.
Результат PoA ≤ 4/3 для линейных сетей - один из красивейших в алгоритмической теории игр. Он говорит: даже без координации, в худшем случае эгоистичная маршрутизация лишь на треть хуже оптимума. Для многих практических сетей - приемлемый результат.
| Механизм | Описание | Эффект |
|---|---|---|
| Congestion pricing | Плата за использование перегруженных дорог/сетей | Сдвигает UE к SO |
| Stackelberg routing | Центр контролирует часть трафика, остальные эгоистичны | Снижает PoA |
| Информационный дизайн | Показывать только часть информации о маршрутах | Может улучшить равновесие |
| Удаление дорог | Парадокс Брасса в обратном - убрать стратегически вредные рёбра | Снижает совокупную задержку |
Price of Anarchy = 4/3 для линейных routing games означает:
Ключевые идеи
- **Сетевые игры** - пользователи выбирают маршруты, минимизируя свою задержку, создавая congestion экстерналии
- **Равновесие Вардропа (UE)** - все используемые пути имеют одинаковую задержку; Nash equilibrium в непрерывном потоке
- **System Optimum** - минимизация суммарной задержки; требует учёта маргинальной, а не средней стоимости
- **Парадокс Брасса** - добавление новой дороги может увеличить задержку для всех из-за изменения равновесия
- **Price of Anarchy** - отношение наихудшего Nash к оптимуму; для линейных сетей PoA ≤ 4/3
Связанные темы
Сетевые игры - пересечение теории игр, алгоритмики и экономики внешних эффектов:
- Algorithmic Game Theory — PoA и routing games - центральные темы AGT; вычислительная сложность поиска равновесий
- Игры с нулевой суммой — Routing games - игры с ненулевой суммой; потери от перегрузки создают social cost
- Механизм-дизайн — Congestion pricing - механизм для коррекции экстерналий и сдвига к социальному оптимуму
Вопросы для размышления
- Используете ли навигатор? Что происходит, когда ВСЕ следуют рекомендациям Waze одновременно?
- Congestion pricing (платные въезды) эффективны, но политически непопулярны. Как объяснить их пользу обычному водителю?
- Применим ли парадокс Брасса к социальным сетям? Что будет «дорогой» в Facebook/Twitter?