Новая дорога может замедлить весь город – даже если каждый водитель по-прежнему выбирает для себя наилучший маршрут. Парадокс Браеса – строгое следствие теории графов и эгоистичной маршрутизации. Игроки Cities: Skylines наблюдают эффект ежедневно, не зная имени, а для геймдизайнера – редкий трофей: контринтуитивная теорема, которую игра доказывает убедительнее учебника.
Эгоистичная маршрутизация на графе
Дорожная сеть – ориентированный граф G(V, E), где каждому ребру приписана функция задержки l(x): время проезда растёт вместе с потоком x машин. Маршрут каждый водитель выбирает сам, поэтому устойчивое состояние сети – равновесие Вардропа. Транспортный вариант равновесия Нэша: ни один водитель не сократит время, сменив путь в одиночку.
Равновесие не совпадает с системным оптимумом – распределением, минимизирующим суммарное время всех. Оптимум требует, чтобы кто-то ехал дольше «за команду», а эгоисты так не делают. Существование равновесия гарантировано: эгоистичная маршрутизация – потенциальная игра, и водители, поочерёдно улучшая собственные маршруты, сходятся к нему без всякого диспетчера.
Отношение суммарного времени в равновесии к оптимуму называют ценой анархии. Для линейных задержек она не превышает 4/3. Парадокс Браеса существует именно в этом зазоре значений.
Арифметика парадокса
Каноническая сеть Дитриха Браеса (1968) – ромб. Из Старта в Финиш ведут два маршрута: через А и через Б. Узкие участки Старт – А и Б – Финиш зависят от потока: x/100 минут при x машинах; широкие А – Финиш и Старт – Б всегда занимают 45 минут. Пусть едут 4000 водителей. В равновесии поток делится поровну, и каждый тратит 2000/100 + 45 = 65 минут.
Построим сверхбыструю перемычку А – Б с нулевой задержкой. Маршрут Старт – А – Б – Финиш выглядит неотразимо, и в новом равновесии его выбирают все: 4000/100 + 0 + 4000/100 = 80 минут. Сворачивать некуда: любой старый маршрут теперь стоит 40 + 45 = 85 минут.
Дорогу добавили – каждый едет на пятнадцать минут дольше, и ни у кого нет личной причины что-то менять. Цена анархии выросла до 80/65 ≈ 1,23, почти упёршись в потолок 4/3. Симметричный вывод важнее: удаление перемычки ускорит всех. Происходит «улучшение вычитанием».
Схема 1. Эгоистичная маршрутизация на графе.
От Штутгарта до электросетей
Новая магистраль в Штутгарте (1969) ухудшила движение – помогло закрытие участка. Перекрытие 42-й улицы в Нью-Йорке снизило заторы вместо ожидаемого коллапса. Снос эстакады Чхонгечхон в Сеуле ускорил город и вернул реку.
Парадокс структурен: группа Шефера экспериментально воспроизвела эффект в электросети и на детальной модели энергосистемы Германии (Nature Communications, 2022) – вплоть до практической рекомендации отключать работающие линии ради устойчивости.
В работе предложена топологическая теория, предсказывающая «браесовские» рёбра по одной лишь структуре сети – прообраз автоматического поиска вредных дорог. Там, где поток подчиняется физике, водителей винить не в чем.
Cities: Skylines – песочница Браеса
В первой Cities: Skylines (2015) агенты прокладывали кратчайший по стоимости путь и держались его до конца: стояли в заторе, не меняли ряд и вытягивались в одну полосу – эгоизм в предельно чистом виде. Мод Traffic Manager: President Edition добавил «продвинутый ИИ транспорта», учитывающий загрузку дорог, – сдвинув поведение от слепого эгоизма к динамическому равновесию.
Рис. 1. Cities: Skylines. Игровой процесс.
В Cities: Skylines II (2023) Colossal Order переделала систему: стоимость маршрута складывается из времени, денег, комфорта и поведения, агенты реагируют на аварии и перестраиваются – но выбор остаётся индивидуальным, то есть эгоистичным по устройству. Завязка парадокса: стоит игроку добавить более короткий транзит между внешними соединениями, и весь сквозной поток переключается на него.
Поэтому парадокс воспроизводится честно: сообщество давно лечит пробки бульдозером – сносом «удобных» диагоналей, лишних съездов и переулков, стягивающих весь транзит. Песочница получила и академическое признание: урбанисты используют Cities: Skylines как серьёзную игру для обучения планированию и анализа трафика.
Парадокс как дизайн-приём
Что отсюда извлекает геймдизайнер:
- глубина из эгоизма: пока агенты маршрутизируются индивидуально, а задержки растут с потоком, Браес возникает сам – скриптовать не нужно, достаточно не мешать
- снос ребра обязан быть интерфейсно равноправен строительству – в Mini Motorways (2021) с лимитом плиток стереть и перерисовать дорогу – основной ход
- уровни-ловушки: заранее заложенная браесовская перемычка – готовая головоломка, где игрок побеждает, убирая; родственный жанр развязочных пазлов вроде Freeways (2017) целиком держится на подобных задачах
- ручка реализма: спектр между системным оптимумом («телепатический» трафик – послушный и скучный) и равновесием Нэша (живой и драматичный) – осознанный выбор характера симуляции
- телеметрия: отношение суммарного времени поездок к оптимуму – численный индикатор здоровья сети; поиск вредных рёбер в общем случае вычислительно труден, поэтому честный перебор сносов в симуляции – состояние искусства.
Рис. 2. Mini Motorways. Игровой процесс.
Заключение
Парадокс Браеса – редкий случай, когда математика, реальный город и игра показывают одно и то же: локально выгодное ребро может вредить глобально. Практический порядок:
- моделировать дороги функциями задержки, иначе парадоксу неоткуда взяться
- уравнять снос со строительством; закладывать браесовские перемычки как головоломки
- измерять цену анархии в телеметрии живого города.
Если нужен наглядный урок для игрока, достаточно показать два числа: сколько город едет сейчас – и сколько ехал бы при идеальном диспетчере. Иногда лучший граф – тот, из которого вычеркнули ребро.