Парадокс брасса

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

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

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

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

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

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

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

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

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

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

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

Движение

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

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

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

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

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

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

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

Биология

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

Доказательство: Пусть будет некоторая конфигурация трафика с соответствующей энергией и общим временем в пути . Для каждого ребра энергия представляет собой сумму арифметической прогрессии , и, используя формулу для суммы арифметической прогрессии, можно это показать . Если - это социально-оптимальный транспортный поток и транспортный поток с минимальным потреблением энергии, неравенство подразумевает это .${\displaystyle Z}$${\displaystyle E(Z)}$${\displaystyle T(Z)}$${\displaystyle E(Z)\leq T(Z)\leq 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] интерпретируют парадокс Браесса как динамическую проблему тройного выбора. Анализ показывает, как новый путь меняет проблему. До того, как новый путь станет доступным, динамика будет такой же, как и при бинарном выборе с внешними эффектами, но новый путь трансформирует его в проблему троичного выбора. Добавление дополнительного ресурса увеличивает сложность динамики. Фактически, может даже существовать сосуществование циклов, и значение парадокса для динамики можно увидеть как с геометрической, так и с аналитической точки зрения.

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

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

использованная литература

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

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

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

Викискладе есть медиафайлы, связанные с парадоксом Брэсса .

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