Введение

Парадокс, связанный с увеличением пропускной способности дорог

Парадокс Бресса – это наблюдение, что добавление одной или нескольких дорог к дорожной сети может замедлить общий трафик. Этот парадокс был впервые обнаружен Артуром Пигу в 1920 году и позднее назван в честь немецкого математика Дитриха Бресса в 1968 году. Аналоги парадокса могут встречаться в электрических сетях и биологических системах. Предполагается, что теоретически улучшение неэффективной сети можно достичь, удалив из неё некоторые элементы. Парадокс использовался для объяснения случаев улучшения транспортного потока при закрытии существующих магистральных дорог.

Открытие и определение

Дитрих Бресс, математик из Ру́рского университета в Германии, обнаружил, что при моделировании дорожного движения добавление новой дороги может приводить к снижению пропускной способности дорожной сети. Его идея заключалась в том, что если каждый водитель принимает оптимальное решение, исходя из собственных интересов, выбирая самый быстрый маршрут, то кратчайший путь может оказаться перегруженным, что увеличит общее время в пути. Более формально, суть открытия Бресса состоит в том, что равновесие Нэша не всегда соответствует оптимальному общему потоку в сети. Парадокс формулируется следующим образом: "Для каждой точки дорожной сети задано количество автомобилей, начинающих движение из этой точки, и их пункт назначения. В этих условиях необходимо оценить распределение транспортного потока. Предпочтительность одной улицы перед другой зависит не только от качества дороги, но и от плотности потока. Если каждый водитель выбирает путь, который кажется ему наиболее выгодным, то время в пути не обязательно будет минимальным. Более того, на примере показано, что расширение дорожной сети может вызвать перераспределение трафика, приводящее к увеличению индивидуального времени в пути". Добавление дополнительных мощностей в сеть, когда участники движения эгоистично выбирают свой маршрут, в некоторых случаях может снизить общую эффективность. Это происходит потому, что равновесие Нэша в такой системе не обязательно является оптимальным. Изменение сети создает новую игровую структуру, приводящую к многопользовательской дилемме заключенного. В равновесии Нэша у водителей нет стимула менять свой маршрут. Однако, пока система не находится в равновесии Нэша, отдельные водители могут сократить время своей поездки, изменив выбранный маршрут. В случае парадокса Бресса водители будут продолжать переключаться между маршрутами, пока не достигнут равновесия Нэша, несмотря на снижение общей эффективности. Если функции задержки линейны, добавление нового участка никогда не приведет к увеличению общего времени в пути в равновесии более чем в 4/3 раза.

Распространенность

В 1983 году Штейнберг и Зангвилл, при разумных допущениях, предоставили необходимые и достаточные условия возникновения парадокса Брэсса в общей транспортной сети при добавлении нового маршрута. (Следует отметить, что их результат применим к добавлению любого нового маршрута, а не только к добавлению одной связи.) Как следствие, они показали, что вероятность возникновения парадокса Брэсса примерно равна вероятности его отсутствия при добавлении случайного нового маршрута.

Движение транспорта

Парадокс Бресса имеет аналогию и в случае сокращения дорожной сети (что может привести к уменьшению индивидуального времени в пути). В Штутгарте (Германия) после инвестиций в дорожную сеть в 1969 году ситуация с движением не улучшилась, пока не был вновь закрыт участок недавно построенной дороги. В 1990 году временное закрытие 42-й улицы на Манхэттене (Нью-Йорк) в День Земли уменьшило заторы в этом районе. В 2008 году Юн, Гастнер и Чжон продемонстрировали конкретные маршруты в Бостоне, Нью-Йорке и Лондоне, где это может фактически произойти, и указали на дороги, которые можно было бы закрыть для сокращения прогнозируемого времени поездки. В 2009 году в Нью-Йорке экспериментировали с закрытием Бродвея на Таймс-сквер и Геральд-сквер, что привело к улучшению транспортного потока и созданию постоянных пешеходных зон. В 2012 году Поль Лекроар из Института планирования и развития региона Иль-де-Франс отметил, что "вопреки первоначальным опасениям, удаление основных дорог не приводит к ухудшению дорожной обстановки сверх первоначальных изменений. Перераспределение трафика ограничено и ниже ожидаемого".

Электричество

В 2012 году ученые из Института динамики и самоорганизации Макса Планка продемонстрировали с помощью вычислительного моделирования возможность возникновения этого явления в сетях передачи электроэнергии с децентрализованной генерацией. В 2012 году международная группа исследователей из Института Неэля (CNRS, Франция), INP (Франция), IEMN (CNRS, Франция) и UCL (Бельгия) опубликовала в журнале Physical Review Letters статью, показывающую, что парадокс Бресса может проявляться в мезоскопических электронных системах. В частности, они показали, что добавление пути для электронов в наноскопической сети парадоксальным образом уменьшает ее проводимость. Это было подтверждено как результатами моделирования, так и экспериментами при низких температурах с использованием сканирующей зондовой микроскопии.

Спрингс

Модель с пружинами и веревками может показать, что подвешенный вес может подняться выше, несмотря на то, что в системе подвески перерезана натянутая веревка, и это вытекает из той же математической структуры, что и парадокс Бресса. Для двух идентичных пружин, соединенных последовательно короткой веревкой, их общая жесткость равна половине жесткости каждой отдельной пружины, что приводит к значительному растяжению при подвешивании определенного веса. Это остается верным, если добавить две более длинные, свободно висящие веревки, соединяющие нижний конец верхней пружины с подвешенным весом (нижний конец нижней пружины) и верхний конец нижней пружины с точкой подвеса (верхний конец верхней пружины). Однако, когда короткая веревка перерезается, длинные веревки натягиваются, и пружины оказываются соединенными параллельно (в механическом смысле). Общая жесткость в этом случае удваивается, и если длина длинных веревок не слишком велика, подвешенный вес фактически окажется выше, чем до перерезания короткой веревки. Тот факт, что вес поднимается вверх при перерезании натянутой веревки (короткой веревки) в системе подвески, противоречит интуиции, но это следует из закона Гука и принципов работы пружин при последовательном и параллельном соединении.

Биология

Адилсон Э. Моттер и его коллеги показали, что результаты, соответствующие парадоксу Браэсса, часто наблюдаются в биологических и экологических системах. Моттер предполагает, что удаление части нарушенной сети может помочь восстановить её функционирование. В контексте управления ресурсами пищевых сетей находящихся под угрозой исчезновения видов, где вымирание многих видов может происходить последовательно, избирательное удаление видов, не имеющих перспектив выживания, из сети теоретически может привести к положительному результату – предотвращению цепной реакции дальнейших вымираний.

Стратегия командного спорта

Было предложено рассматривать баскетбольную команду как сеть возможных способов забросить мяч в корзину, каждый из которых обладает своей эффективностью. Звездный игрок может снизить общую эффективность команды, подобно тому, как часто используемая «короткая дорога» увеличивает общее время поездки по дорожной сети. Предлагаемое решение для достижения максимальной эффективности при наборе очков заключается в том, чтобы звездный игрок совершал примерно столько же бросков, сколько и его партнеры по команде. Однако, как отмечается в оригинальной статье, этот подход не имеет под собой серьезной статистической базы.

Сети блокчейна

Парадокс Бресса проявляется в сетях платежных каналов блокчейна, также известных как сети второго уровня. Сети платежных каналов предлагают решение проблемы масштабируемости блокчейн-сетей, позволяя совершать большое количество транзакций без записи каждой из них в блокчейн. В такой сети пользователи могут установить канал, заблокировав средства с обеих сторон. Транзакции выполняются либо непосредственно между плательщиком и получателем через канал, либо по пути, состоящему из нескольких каналов с участием промежуточных пользователей, взимающих комиссию. Интуитивно, открытие новых каналов должно повышать гибкость маршрутизации, однако добавление нового канала может привести к увеличению комиссий, а закрытие существующих – к их снижению. В данной работе представлен теоретический анализ условий возникновения парадокса, методы его смягчения, а также эмпирическое исследование, демонстрирующее проявление парадокса на практике и его влияние на сеть Lightning Bitcoin.

Пример

Рассмотрим дорожную сеть, как показано на прилегающей диаграмме, по которой 4000 водителей хотят проехать от точки «Старт» до точки «Финиш». Время в минутах на дороге «Старт–А» равно количеству путешественников (T), деленному на 100, а на дороге «Старт–Б» – постоянные 45 минут (аналогично и на дорогах, ведущих в противоположном направлении). Если пунктирной дороги не существует (то есть в транспортной сети всего 4 дороги), время, необходимое для проезда маршрута «Старт–А–Финиш» с T водителями, составит , а время, необходимое для проезда маршрута «Старт–Б–Финиш» с T водителями, составит . Поскольку имеется 4000 водителей, из этого факта можно вывести, что когда система находится в равновесии. Следовательно, каждый маршрут занимает минут. Если бы какой-либо из маршрутов занимал меньше времени, это не было бы равновесием Нэша: рациональный водитель перешел бы с более длинного маршрута на более короткий. Теперь предположим, что пунктирная линия «А–Б» – это дорога с чрезвычайно коротким временем проезда, примерно 0 минут. Предположим, что дорога открыта, и один водитель пробует маршрут «Старт–А–Б–Финиш». К его удивлению, он обнаруживает, что его время составляет минут, что позволяет сэкономить почти 25 минут. Вскоре больше водителей из этих 4000 пробуют этот новый маршрут. Время в пути возрастает с 40,01 и продолжает увеличиваться. Когда число водителей, использующих новый маршрут, достигнет 2500, а на маршруте «Старт–Б–Финиш» останется 1500, их время составит минут, что не является улучшением по сравнению с первоначальным маршрутом. Тем временем, время в пути этих 1500 водителей увеличилось до минут, что на 20 минут больше. Они вынуждены переключиться на новый маршрут через «А», так что теперь это занимает минут. Ни у кого нет стимула ехать по маршруту «А–Финиш» или «Старт–Б», потому что любой водитель, который попробует это, потратит 85 минут. Таким образом, открытие поперечной дороги вызывает необратимые изменения для всех, обходясь всем в 80 минут вместо первоначальных 65. Если бы все водители согласились не использовать путь «А–Б», или если бы этот путь был закрыт, каждый водитель выиграл бы 15 минут времени в пути.

Существование равновесия

Если предположить, что время в пути для каждого человека, движущегося по ребру, одинаково, то равновесие всегда будет существовать. Пусть – формула для времени в пути каждого человека, проезжающего по ребру , когда человек выбирают это ребро. Предположим, есть граф трафика с людьми, движущимися по ребру . Пусть энергия , , будет (если ). Пусть общая энергия графа трафика будет суммой энергий всех ребер графа. Выберем набор маршрутов, который минимизирует общую энергию. Такой выбор должен существовать, поскольку число возможных наборов маршрутов конечно. Этот набор маршрутов и будет равновесием. Предположим для противоречия, что это не так. Тогда существует хотя бы один водитель, который может изменить маршрут и улучшить время в пути. Пусть исходный маршрут – , а новый маршрут – . Пусть – общая энергия графа трафика, и рассмотрим, что произойдет, если маршрут исключить. Энергия каждого ребра уменьшится на , и, следовательно, уменьшится на . Это просто общее время в пути, необходимое для прохождения по исходному маршруту. Если затем добавить новый маршрут , то общая энергия увеличится на общее время в пути, необходимое для прохождения по новому маршруту. Поскольку новый маршрут короче исходного, должно уменьшиться по сравнению с исходной конфигурацией, что противоречит предположению о том, что исходный набор маршрутов минимизировал общую энергию. Следовательно, набор маршрутов, минимизирующий общую энергию, является равновесием.

Насколько далеко от оптимального находится движение в равновесии?

Если функции времени в пути линейны, то есть для некоторого α, то в худшем случае загруженность в энергоминимизирующем равновесии в два раза выше, чем в социально оптимальной. Доказательство: пусть задана некоторая конфигурация трафика с соответствующей энергией и общим временем в пути. Для каждого ребра энергия является суммой арифметической прогрессии, и, используя формулу для суммы арифметической прогрессии, можно показать, что если – социально оптимальный поток трафика, а – энергоминимизирующий поток трафика, то неравенство влечет за собой, что. Таким образом, общее время в пути для энергоминимизирующего равновесия не более чем в два раза выше, чем для оптимального потока.

Динамический анализ парадокса Бресса

В 2013 году Даль Форно и Мерлоне интерпретируют парадокс Бресса как динамическую задачу тройного выбора. Анализ показывает, как появление нового пути изменяет суть задачи. До того, как новый путь становится доступным, динамика соответствует бинарному выбору с внешними эффектами, однако новый путь трансформирует её в задачу тройного выбора. Добавление дополнительного ресурса усложняет динамику. Фактически, возможно даже сосуществование циклов, а влияние парадокса на динамику можно рассмотреть как с геометрической, так и с аналитической точки зрения.

Влияние топологии сети

Мильхтайх доказал, что парадокс Бресса возникает тогда и только тогда, когда сеть не является серией параллельных графов.