Парадокс Брасса

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

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

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

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

Парадокс формулируется следующим образом:

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

Добавление дополнительной мощности в сеть , когда движущиеся объекты эгоистично выбирают свой маршрут, в некоторых случаях может снизить общую производительность. Это связано с тем, что равновесие по Нэшу такой системы не обязательно является оптимальным. Изменение сети приводит к появлению новой игровой структуры, которая приводит к (многопользовательской) дилемме заключенного . В равновесии Нэша у водителей нет стимула менять свои маршруты. Хотя система не находится в равновесии Нэша, отдельные водители могут сократить время в пути, изменив маршруты, которые они выбирают. В случае парадокса Брасса водители будут продолжать переключаться, пока не достигнут равновесия Нэша, несмотря на снижение общей производительности.

Если функции задержки линейны, добавление фронта никогда не может увеличить общее время путешествия в равновесии более чем в 4/3 раза.

Возможные примеры парадокса в действии

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

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

Трафик

См. Также: Вызванный спрос

Парадокс Брасса имеет аналог в случае сокращения дорожной сети (что может привести к сокращению индивидуального времени в пути).

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

В 2012 году Поль Лекроар из Института планирования и развития Иль-де-Франс написал: «Несмотря на первоначальные опасения, снос основных дорог не приводит к ухудшению условий дорожного движения за пределами начальных корректировок. Передача трафика ограничена. и ниже ожиданий». Он также отмечает, что некоторые поездки на личном транспорте (и связанная с ними экономическая деятельность) не переходят на общественный транспорт и просто исчезают («испаряются»).

То же явление наблюдалось и тогда, когда закрытие дорог было не частью городского проекта, а следствием аварии. В 2012 году в Руане сгорел мост. В течение следующих двух лет другие мосты использовались чаще, но общее количество автомобилей, проезжающих по мостам, сократилось.

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

В 2012 году ученые из Института динамики и самоорганизации Макса Планка продемонстрировали с помощью компьютерного моделирования возможность возникновения этого явления в сетях электропередачи , где производство электроэнергии децентрализовано.

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

Пружины

Справа — две пружины, соединенные последовательно короткой веревкой. Когда короткая веревка, соединяющая B и C, удалена (слева), груз висит выше.

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

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

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

Биология

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

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

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

Блокчейн-сети

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

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

Математический подход

Пример

Рассмотрим дорожную сеть, показанную на соседней диаграмме, по которой 4000 водителей желают проехать от точки начала до конца. Время в пути в минутах на дороге Старт-А представляет собой число пассажиров (Т), деленное на 100, а на дороге Старт-Б - постоянные 45 минут (аналогично и с дорогами напротив них). Если пунктирная дорога не существует (всего в дорожной сети 4 дороги), время, необходимое для проезда по маршруту Начало–А–Конец с $a$ водители были бы ${\tfrac {a}{100}}+45$. Время, необходимое для проезда по маршруту Начало–Б–Конец с $b$ водители были бы ${\tfrac {b}{100}}+45$. Поскольку имеется 4000 водителей, тот факт, что $a+b=4000$ можно использовать для вывода того факта, что $a=b=2000$ когда система находится в равновесии. Таким образом, каждый маршрут занимает ${\tfrac {2000}{100}}+45=65$ минут. Если бы любой маршрут занимал меньше времени, это не было бы равновесием Нэша: рациональный водитель переключился бы с более длинного маршрута на более короткий.

Теперь предположим, что пунктирная линия A–B представляет собой дорогу с чрезвычайно коротким временем в пути, примерно 0 минут. Предположим, что дорога открыта и один водитель пытается начать-А-Б-Конец. К своему удивлению, он обнаруживает, что его время истекло. ${\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01$ минут, экономия почти 25 минут. Вскоре еще больше из 4000 водителей опробуют этот новый маршрут. Затраченное время увеличивается с 40.01 и продолжает расти. Когда количество водителей, пробующих новый маршрут, достигнет 2500, а 1500 все еще будут на маршруте Начало-Б-Конец, их время будет равно ${\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65$ минут, что не является улучшением по сравнению с исходным маршрутом. Между тем, эти 1500 водителей замедлились до $45+{\tfrac {4000}{100}}=85$ минут, увеличение на 20 минут. Они также вынуждены перейти на новый маршрут через А, поэтому теперь требуется ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ минут. Ни у кого нет стимула ехать А-Конец или Старт-Б, потому что любому водителю потребуется 85 минут. Таким образом, открытие перекрестного маршрута вызывает необратимое изменение его всеми, что обходится каждому в 80 минут вместо первоначальных 65. Если бы каждый водитель согласился не использовать путь A–B или если бы этот маршрут был закрыт, каждый водитель выиграет от сокращения времени в пути на 15 минут.

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

Если предположить, что время пути для каждого человека, движущегося по краю, одинаково, равновесие будет существовать всегда.

Позволять $L_{e}(x)$ быть формулой времени пути каждого человека, путешествующего по ребру $e$ когда $x$ люди берут это преимущество. Предположим, имеется график трафика с $x_{e}$ люди едут по краю $e$. Пусть энергия $e$, $E(e)$, быть

$\sum _{i=1}^{x_{e}}L_{e}(i)=L_{e}(1)+L_{e}(2)+\cdots +L_{e}(x_{e})$

(Если $x_{e}=0$ позволять $E(e)=0$). Пусть полная энергия графа трафика равна сумме энергий каждого ребра графа.

Выберите маршрут, который минимизирует общую энергию. Такой выбор должен существовать, поскольку существует конечное число вариантов маршрутов. Это будет равновесие.

Предположим, от противного, что это не так. Тогда найдется хотя бы один водитель, который сможет изменить маршрут и сократить время в пути. Предположим, что исходный маршрут $e_{0},e_{1},\ldots ,e_{n}$ пока новый маршрут $e'_{0},e'_{1},\ldots ,e'_{m}$. Позволять $E$ быть полной энергией графа трафика и рассмотрим, что произойдет, когда маршрут $e_{0},e_{1},...e_{n}$ удаляется. Энергия каждого края $e_{i}$ будет сокращено на $L_{e_{i}}(x_{e_{i}})$ и поэтому $E$ будет сокращено на ${\textstyle \sum _{i=0}^{n}L_{e_{i}}(x_{e_{i}})}$. Это просто общее время в пути, необходимое для прохождения исходного маршрута. Если затем будет добавлен новый маршрут, $e'_{0},e'_{1},\ldots ,e'_{m}$, полная энергия $E$ будет увеличено на общее время в пути, необходимое для проезда по новому маршруту. Поскольку новый маршрут короче исходного, $E$ должно уменьшаться относительно исходной конфигурации, что противоречит предположению, что исходный набор маршрутов минимизировал общую энергию.

Следовательно, выбор маршрутов, минимизирующих общую энергию, является равновесием.

Нахождение равновесия

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

Псевдокод для лучшей динамики отклика:

Let P be some traffic pattern.
while P is not at equilibrium:
    compute the potential energy e of P
    for each driver d in P:
        for each alternate path p available to d:
            compute the potential energy n of the pattern when d takes path p
            if n < e:
                modify P so that d takes path p
continue the topmost while

На каждом этапе, если какой-то конкретный драйвер мог бы добиться большего, выбрав альтернативный путь («лучший ответ»), это строго уменьшает энергию графа. Если ни один водитель не имеет наилучшего ответа, график находится в равновесии. Поскольку энергия графа строго уменьшается с каждым шагом, лучший алгоритм динамики ответа должен в конечном итоге остановиться.

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

Если функции времени прохождения линейны, то есть $L_{e}(x)=a_{e}x+b_{e}$ для некоторых $a_{e},b_{e}\geq 0$, то в худшем случае движение в условиях равновесия, минимизирующего потребление энергии, в два раза хуже, чем социально оптимальное.

Доказательство: Пусть $Z$ быть некоторой конфигурацией трафика с соответствующей энергией $E(Z)$ и общее время в пути $T(Z)$. Для каждого ребра энергия представляет собой сумму арифметической прогрессии , и используя формулу суммы арифметической прогрессии, можно показать, что $E(Z)\leq T(Z)\leq 2E(Z)$. Если $Z_{o}$ – это социально-оптимальный транспортный поток и $Z_{e}$ представляет собой энерго-минимизирующий транспортный поток, из неравенства следует, что $T(Z_{e})\leq 2E(Z_{e})\leq 2E(Z_{o})\leq 2T(Z_{o})$.

Таким образом, общее время прохождения для энерго-минимизирующего равновесия не более чем в два раза меньше, чем для оптимального потока.

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

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

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

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

См. также

• Парадокс Даунса-Томсона - Парадокс в дорожной инженерии, связанный с улучшением дорожной сети.
• Парадокс Джевонса : эффективность приводит к увеличению спроса
• Константа Маркетти – Среднее время в пути
• Позиция Льюиса – Могриджа – Теория дорожного движения
• Цена анархии в играх с перегрузками - количественный анализ потери эффективности, вызванной внешними факторами перегрузки.

Дальнейшее чтение

• Браесс, Д. (1969). «О парадоксе планирования дорожного движения » (PDF) . Корпоративные исследования (на немецком языке). 12 :258-268. (перевод Нагурни и Ваколбингера)
• Катарина Белага-Вербицки: «Парадокс Брасса в расширенных сетях Уитстона с операторами M/M/1» ISBN   3-89959-123-2
• Перевод статьи Брасса 1968 года с немецкого на английский представлен как статья Д. Брасса, А. Нагерни и Т. Ваколбингера «О парадоксе планирования дорожного движения» в журнале Transportation Science, том 39, 2005 г., стр. 446. –450. Дополнительная информация. Архивировано 27 сентября 2011 г. на Wayback Machine.
• Ирвин, AD (1993). «Как парадокс Брасса решает проблему Ньюкомба». Международные исследования в философии науки . 7 (2): 141–160. дои : 10.1080/02698599308573460 .
• Стейнберг, Р.; Зангвилл, Висконсин (1983). «Распространенность парадокса Брасса». Транспортная наука . 17 (3): 301. doi : 10.1287/trsc.17.3.301 .
• Рапопорт, А.; Куглер, Т.; Дугар, С.; Гишес, Э.Дж. (2009). «Выбор маршрутов в перегруженных транспортных сетях: экспериментальные проверки парадокса Брасса» (PDF) . Игры и экономическое поведение . 65 (2): 538–571. дои : 10.1016/j.geb.2008.02.007 .
• Т. Рафгарден. «Цена анархии». MIT Press, Кембридж, Массачусетс, 2005.

Внешние ссылки

• Парадоксы тестирования программного обеспечения (декабрь 2005 г.) Прямая ссылка
• Домашняя страница Дитриха Брасса
• Парадокс дорожной сети
• Короткое видео, иллюстрирующее парадокс Брасса с помощью минифигурок Lego.
• Весенний парадокс , на YouTube видео Стива Молда , объясняющее парадокс Брасса, а также тесно связанный с ним весенний парадокс.