Почему новая короткая связь может увеличить время всем участникам

Новая связь сокращает один маршрут, но после её появления поездка может стать дольше для всех. Это возможно, если время зависит от чужого выбора, а каждый минимизирует только своё. Проверим возможность на полной вымышленной сети. Она не описывает реальный трафик и не утверждает, что строительство дороги обычно ухудшает движение.

Задайте сеть и все четыре решения

Четыре условных участника едут из S в T. Есть верхний путь S–A–T и нижний S–B–T. Время S–A равно числу участников, выбравших это ребро, в минутах; B–T устроено так же. На A–T и S–B время постоянно 5 минут. Обратных и других связей нет.

Зависимость от числа людей задана непосредственно, не выведена из скорости или физического расписания. Все выбирают маршрут; при проверке изменения один участник переключается, а остальные остаются. После переключения время пересчитывается с новой загрузкой, включая самого изменившего выбор. Устойчивым назовём распределение, где никто не сокращает своё время таким одиночным переходом.

До новой связи устойчиво разделение два на два

Если по верхнему пути едут двое, его время 2+5=7 минут. На нижнем тоже двое:5+2=7. Любой переход на другой путь создал бы там троих, и переключившийся получил бы 3+5=8 вместо 7. Значит, деление 2/2 устойчиво.

Другие распределения неустойчивы. При 3/1 человек из тройки едет 8 минут, а после перехода к одиночке получил бы 7. При 4/0 переход даёт 6 вместо 9. Симметричные варианты аналогичны. Суммарное время устойчивой четвёрки равно 4×7=28 участнико-минут.

Добавьте идеализированный переход A–B

Теперь открывается только новая направленная связь A–B с нулевым временем. Появляется третий путь S–A–B–T. Исходное деление 2/2 больше не устойчиво: один из верхних, перейдя на новый путь, оставляет S–A загруженным двумя, а B–T увеличивает до трёх. Его время становится 2+0+3=5 вместо 7.

Если в итоге все четверо выбрали новый путь, S–A и B–T загружены четырьмя. Каждый едет 4+0+4=8 минут. Перейти единолично на верхний путь означало бы 4+5=9; на нижний —5+4=9. Поэтому итог всех на новой связи устойчив, хотя каждому требуется на минуту больше прежнего.

Проверьте, что не пропущено иное устойчивое деление

Обозначим количества на верхнем, нижнем и новом путях x,y,z; их сумма 4. Для человека на верхнем переход на новый сохраняет его загрузку S–A и увеличивает B–T на 1. Сокращение времени равно x минутам, поэтому при x положительном такой переход выгоден. Для нижнего аналогичное сокращение равно y.

Следовательно, в устойчивом состоянии x=0 и y=0, остаётся z=4. Все 8 минут не взяты из случайно выбранного неудобного распределения. Суммарное время стало 32 вместо 28, рост 4, или 1/7≈14,2857%. Старые маршруты при этом не удалялись и их правила не ухудшались.

Граница полезного вывода

При фиксированных временах добавление разрешённого пути не может ухудшить минимум отдельного поиска: прежний путь остаётся. Здесь меняются загрузки из-за решений других людей, поэтому сравнивается другое условие. Для реальной поездки нужны измеренные зависимости, спрос и ограничения. Наша четвёрка не выбирает маршрут или дорожный проект; она показывает, почему наличие короткой связи и итог совместного выбора не одно и то же.

Ограничения разбора

• Все дороги, участники и зависимости времени вымышлены; нулевой переход — математическая идеализация.
• Ровно четыре отдельных участника, три допустимых направленных маршрута после добавления; каждый сравнивает собственное время при одном одиночном изменении.
• Никакого физического движения волн трафика, случайных задержек, платы, координации, ограничений пропуска или реального равновесия дорог не установлено.
• Сравнивается устойчивость по объявленному правилу, не общественный оптимум, вероятность поведения людей или эффект любого строительства.

Источники