Добавление кратчайшего пути может замедлить всех: индивидуальная рациональность ведёт к коллективной неэффективности в сетевой маршрутизации
В 1968 году Дитрих Браес показал, что добавление дороги в транспортную сеть может парадоксально увеличить время поездки всех. Когда водители эгоистично выбирают самый быстрый маршрут (равновесие Нэша), они могут коллективно получить худший результат, чем при сотрудничестве. Парадокс возникает, поскольку выбор каждого водителя меняет перегрузку для других.
Классическая сеть имеет 4 узла: Старт (A), Финиш (D) и промежуточные узлы (B, C). Всегда существуют два маршрута: A→B→D и A→C→D. Стоимости рёбер фиксированные (постоянное время) или переменные (время = базис/T_ref × трафик). Ребро краткого пути B→C создаёт новый маршрут A→B→C→D, использующий оба ребра с переменной стоимостью. Этот маршрут кажется привлекательным, но увеличивает перегрузку обоих переменных рёбер, ухудшая общую производительность системы.
Парадокс Браеса наблюдался в реальных городах: закрытие 42-й улицы в Нью-Йорке улучшило трафик; Сеул снёс эстакаду и восстановил рекеку, улучшив поток. Помимо транспорта, парадокс встречается в сетевой маршрутизации, электросетях, спортивных стратегиях и механических пружинных системах. Метрика "Цена анархии" показывает, насколько хуже эгоистичное поведение по сравнению с социальным оптимумом.
Начните с классической предустановки. Наблюдайте время поездки в равновесии Нэша без краткого пути. Затем включите краткий путь — заметьте, как время увеличивается несмотря на новую дорогу. Настройте количество водителей и стоимости рёбер, чтобы увидеть, когда возникает парадокс. Отношение цены анархии показывает потерю эффективности.