Парадокс Брасса - Braesss paradox - Wikipedia

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

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

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

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

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

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

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

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

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

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

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

Трафик

Смотрите также: Индуцированный спрос

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

В Сеул, Южная Корея, ускорение движения по городу было замечено, когда автомагистраль была убрана как часть Чхонгечхон проект реставрации.^[5] В Штутгарт, Германия После инвестиций в дорожную сеть в 1969 году ситуация с дорожным движением не улучшилась до тех пор, пока участок недавно построенной дороги не был снова закрыт для движения.^[6] В 1990 году временное закрытие 42-й улицы в г. Нью-Йорк за земной день уменьшилось количество скоплений в этом районе.^[7] В 2008 году Юн, Гастнер и Чон продемонстрировали конкретные маршруты в Бостоне, Нью-Йорке и Лондоне, где это могло действительно произойти, и указали дороги, которые могут быть закрыты, чтобы сократить прогнозируемое время в пути.^[8] В 2009 году Нью-Йорк экспериментировал с закрытием Бродвей в Таймс Сквер и Herald Square, в результате чего улучшился транспортный поток и постоянные пешеходные площади.^[9]

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

То же явление наблюдалось, когда закрытие дороги было не частью городского проекта, а следствием аварии. В 2012 г. Руан, в результате аварии сгорел мост; в течение следующих двух лет другие мосты использовались чаще, но общее количество автомобилей, пересекающих мосты, уменьшилось.^[4] Аналогичным образом в 2015 г. Варшава, мост был закрыт; власти наблюдали более активное использование других дорог и общественного транспорта, но половина транспортных средств, обычно пересекающих мост, «исчезла» (52 000 из 105 000 ежедневно).^[4]

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

В 2012 году ученые из Институт динамики и самоорганизации Макса Планка продемонстрировано через вычислительное моделирование, возможность возникновения явления в сети передачи электроэнергии куда выработка энергии децентрализовано.^[10]

В 2012 году международная группа исследователей из Institut Néel (CNRS, Франция), INP (Франция), IEMN (CNRS, Франция) и UCL (Бельгия) опубликовала в Письма с физическими проверками^[11] документ, показывающий, что парадокс Браесса может возникнуть в мезоскопический электронные системы. В частности, они показали, что добавление пути для электронов в наноскопической сети парадоксальным образом снижает ее проводимость. Это было показано как моделированием, так и экспериментами при низкой температуре с использованием сканирующая микроскопия на затворе.

Биология

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

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

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

В футболе Эленио Эррера хорошо известен своей знаменитой цитатой «с 10 [игроками] наша команда играет лучше, чем с 11».

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

Пример

Сравнение парадокса Браесса для дорожных и весенних сетей.
(1) имеет два маршрута, соединяющих начало и конец, каждый из которых включает дорогу с фиксированным временем в пути 45 минут, а другой, который зависит от общего количества путешественников. Т=4000.
В (2), когда объездная дорога соединяет A и B, каждый путешественник использует маршрут начало – A – B – конец, чтобы минимизировать время в пути, что приводит к увеличению общего времени.
(3) - аналог с пружинами и веревкой; при раздельных A и B каждая пружина несет половину веса W и длиной 20 см.
В (4), когда A и B прикреплены, тросы ослабляются, и каждая пружина принимает на себя полный вес, удлиняясь до 40 см.

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

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

Наличие равновесия

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

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

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

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

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

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

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

Поиск равновесия

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

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

Позволять п быть некоторой схемой движения.пока п не находится в равновесии: вычислить потенциальную энергию е из п    для каждого Водитель d в п:        для каждого альтернативный путь п доступен d: вычислить потенциальную энергию п образца, когда d идет по пути п            если п < е: изменить п так что d идет по пути пПродолжить самый верхний пока

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

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

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

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

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

Анализ динамики парадокса Браесса

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

Смотрите также

• Аномалия Белади
• Выбор маршрута
• Парадокс Даунса – Томсона
• Парадокс джевонса
• Постоянная Маркетти
• Индуцированный спрос
• Позиция Льюиса – Могриджа
• Закон Хотеллинга
• Парадокс обогащения
• Волна трафика
• Парадокс распределения
• Джон Глен Уордроп
• Эффект гидры
• Крыса бегает
• Дорожная диета
• Bufferbloat

• Убывающая отдача

Рекомендации

1. Новый Ученый, 42nd St Paradox: отбирайте лучших, чтобы улучшить ситуацию, 16 января 2014 г., Джастин Маллинз
2. Roughgarden, Тим; Тардос, Ева. "Насколько плохо эгоистичная маршрутизация?" (PDF). Журнал ACM. В архиве (PDF) из оригинала 9 апреля 2016 г.. Получено 18 июля 2016.
3. Steinberg, R .; Зангвилл, В. И. (1983). «Распространенность парадокса Браесса». Транспортная наука. 17 (3): 301. Дои:10.1287 / trsc.17.3.301.
4. (На французском) Оливье Раземон, «Парадокс« испарения »автомобильного транспорта», Le monde, Четверг, 25 августа 2016 г., стр. 5. Опубликовано в Интернете как "Et si le trafic s’évaporait?" 24 августа 2016 г. и обновлено 25 августа 2016 г. (страница была посещена 19 сентября 2016 г.).
5. Исли, Д .; Клейнберг, Дж. (2008). Сети. Cornell Store Press. п. 71.
6. Knödel, W. (31 января 1969). Graphentheoretische Methoden Und Ihre Anwendungen. Springer-Verlag. С. 57–59. ISBN  978-3-540-04668-4.
7. Колата, Джина (25 декабря 1990 г.). «Что, если они закроют 42-ю улицу и никто этого не заметит?». Нью-Йорк Таймс. Получено 16 ноября 2008.
8. Юн, Хеджин; Гастнер, Майкл; Чон, Хауунг (2008). «Цена анархии в транспортных сетях: контроль эффективности и оптимальности». Письма с физическими проверками. 101 (12): 128701. arXiv:0712.1598. Bibcode:2008PhRvL.101l8701Y. Дои:10.1103 / PhysRevLett.101.128701. ISSN  0031-9007. PMID  18851419. S2CID  20779255.
9. Бойд, Эндрю. "Парадокс Браесса". Двигатели нашей изобретательности. Эпизод 2814.
10. Сотрудники (Институт Макса Планка) (14 сентября 2012 г.), «Исследование: энергия солнца и ветра может стабилизировать энергосистему», Журнал R&D, rdmag.com, получено 14 сентября 2012
11. Pala, M. G .; Baltazar, S .; Liu, P .; Sellier, H .; Hackens, B .; Мартинс, Ф .; Байот, В .; Wallart, X .; Desplanque, L .; Хуант, С. (2012) [6 декабря 2011 г. (v1)]. "Транспортная неэффективность в разветвленных мезоскопических сетях: аналог парадокса Брэсса". Письма с физическими проверками. 108 (7): 076802. arXiv:1112.1170. Bibcode:2012ПхРвЛ.108г6802П. Дои:10.1103 / PhysRevLett.108.076802. ISSN  0031-9007. PMID  22401236. S2CID  23243934.
12. Моттер, Адилсон Э. (2010). «Повышение производительности сети за счет антагонизма: от синтетических средств спасения до комбинаций нескольких препаратов». BioEssays. 32 (3): 236–245. Дои:10.1002 / bies.200900128. ЧВК  2841822. PMID  20127700.
13. Сахасрабуде С., Моттер А. Э., Спасение экосистем от каскадов вымирания с помощью компенсаторных возмущений, Nature Communications 2, 170 (2011).
14. Скиннер, Брайан; Гастнер, Майкл Т; Чон, Хауунг (2009). «Цена анархии в баскетболе». Журнал количественного анализа в спорте. 6 (1). arXiv:0908.1801. Bibcode:2009arXiv0908.1801S. CiteSeerX  10.1.1.215.1658. Дои:10.2202/1559-0410.1217. S2CID  119275142.
15. Исли, Дэвид; Клейнберг, Джон. «Сети, толпы и рынки: рассуждения о мире с высокой степенью взаимосвязей (дополнительный материал 8.3: Социальная стоимость трафика при равновесии)» (PDF). Домашняя страница Джона Кляйнберга. Джон Кляйнберг. В архиве (PDF) из оригинала 16 марта 2015 г.. Получено 30 мая 2015. - Это препринт ISBN  9780521195331
16. Даль Форно, Арианна; Мерлон, Уго (2013). «Гранично-коллизионные бифуркации в модели парадокса Браесса». Математика и компьютеры в моделировании. 87: 1–18. Дои:10.1016 / j.matcom.2012.12.001. ISSN  0378-4754.

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

• Д. Браесс, Uber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1969) [1] [2]
• Катарина Белага-Вербицки: «Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M / M / 1-Bedienern» ISBN  3-89959-123-2
• Перевод статьи Браесса 1968 года с немецкого на английский появился как статья Д. Браесса, А. Нагерни и Т. Ваколбингера «О парадоксе планирования движения» в журнале «Транспортная наука», том 39, 2005, стр. 446 –450. Дополнительная информация
• Ирвин, А. Д. (1993). «Как парадокс Брэсса решает проблему Ньюкома». Международные исследования в философии науки. 7 (2): 141–160. Дои:10.1080/02698599308573460.
• Steinberg, R .; Зангвилл, В. И. (1983). «Распространенность парадокса Браесса». Транспортная наука. 17 (3): 301. Дои:10.1287 / trsc.17.3.301.
• А. Рапопорт, Т. Куглер, С. Дугар и Э. Дж. Гишес, Выбор маршрутов в перегруженных сетях трафика: экспериментальные испытания парадокса Браесса. Игры и экономическое поведение 65 (2009) [3]
• T. Roughgarden. «Цена анархии». MIT Press, Кембридж, Массачусетс, 2005.

внешняя ссылка

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