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

Парадокс Браеса — парадокс, приписываемый немецкому математику Дитриху Браесу^[en] (статья 1968 года^[1]), гласящий, что добавление дополнительных мощностей в сеть при условии, что двигающиеся по сети сущности сами выбирают свой маршрут, может снизить общую производительность. Происходит это по той причине, что равновесие Нэша для таких систем не обязательно оптимально.

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

ПримерПравить

Предположим, автомобилисты хотят попасть из пункта Start в пункт End. Имеется два пути — через город A и через город B. Время пути от пункта Start до города A зависит от плотности потока и равно количеству автомобилей (T), делённому на 100. Путь от пункта Start до города B не зависит от количества автомобилей и равен 45 минутам. Аналогично, путь из А в пункт назначения занимает 45 минут, а время в пути от B до пункта назначения равно T/100. Если A и B не соединены, то время по маршруту Start-A-End будет равно $\text{[math]}$ $\text{[math]}$ ${\tfrac {A}{100}}+45$ , а на маршрут Start-B-End будет затрачено $\text{[math]}$ $\text{[math]}$ ${\tfrac {B}{100}}+45$ . Если бы один из путей был короче, то отсутствовало бы равновесие Нэша, каждый рациональный водитель переключился бы на более короткий маршрут. Допустим, у нас выехало из точки Start 4000 автомобилей, тогда из того, что $\text{[math]}$ $\text{[math]}$ $A+B=4000$ , можно вывести, что система придёт в равновесие, когда $\text{[math]}$ $\text{[math]}$ $A=B=2000$ . Следовательно, независимо от выбранной дороги автомобиль будет в пути $\text{[math]}$ $\text{[math]}$ ${\tfrac {2000}{100}}+45=65$ минут.

Теперь предположим, что пунктирная линия между A и B представляет собой новый, очень короткий путь, езда по которому занимает приблизительно 0 минут. В этой ситуации все водители предпочтут маршрут Start-A маршруту Start-B, потому что маршрут Start-A займёт в самом худшем случае $\text{[math]}$ $\text{[math]}$ ${\tfrac {T}{100}}={\tfrac {4000}{100}}=40$ минут, в то время как маршрут Start-B гарантированно занимает 45. В узле A каждый рациональный водитель предпочтёт добраться по короткому пути до B и затем доехать до пункта назначения, потому что маршрут A-End гарантировано занимает 45 минут, а маршрут A-B-End в самом худшем случае займёт только $\text{[math]}$ $\text{[math]}$ $0+{\tfrac {4000}{100}}=40$ минут. Таким образом, время в пути для каждого водителя станет $\text{[math]}$ $\text{[math]}$ ${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ минут, то есть после строительства новой дороги время в пути возросло на 15 минут.

Если бы водители договорились не пользоваться дорогой между A и B, то они бы сэкономили это время, но поскольку каждый отдельный водитель выгадывает время, пользуясь дорогой A-B, то такое распределение не является социально оптимальным, в чём проявляется парадокс Браеса.

Парадокс Браеса в реальной жизниПравить

В качестве примеров проявления парадокса Браеса в реальной жизни приводят улучшение ситуации на дорогах в Штутгарте после закрытия для движения секции одной из новых дорог^[2]. В 1990 году закрытие 42-й улицы в Нью-Йорке сократило количество дорожных заторов в этом районе^[3].

Математик Алексей Савватеев утверждает, что парадокс Браеса обычно долго не длится: дорожные службы уже через несколько месяцев исправляют ситуацию. Около своего дома, в Метрогородке, он поймал такой пример: проезд по улицам Щёлковское шоссе — проспект Ветеранов длится 1 час. Лесная дорога, ведущая из Метрогородка к проспекту Ветеранов, отнимает 20 минут. К Щёлковскому шоссе накатали 10-минутную колею (ныне асфальтовая дорога). Пропускная способность той и другой на порядок меньше, чем у шоссе, и небольшой процент машин, желающих срезать по грунтовкам, совершенно не разгрузил шоссе, однако из-за них жители Метрогородка встали в 30-минутной пробке (1 ч − 10 − 20 = 30)^[4].

ПримечанияПравить

↑ D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258—268 (1968)
↑ Knödel, W. Graphentheoretische Methoden und ihre Anwendungen (нем.). — Springer-Verlag, 1969. — S. 57—59. — ISBN 978-3-540-04668-4.
↑ Kolata, Gina. What if They Closed 42d Street and Nobody Noticed? (англ.), New York Times (25 December 1990). Архивировано 16 февраля 2009 года. Дата обращения: 9 мая 2013.
↑ Алексей Савватеев | Теория игр вокруг нас - YouTube (неопр.). Дата обращения: 13 июля 2019. Архивировано 17 августа 2019 года.

ЛитератураПравить

D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258—268 (1968) [1] [2]
A. Rapoport, T. Kugler, S. Dugar, and E. J. Gisches, Choice of routes in congested trafﬁc networks: Experimental tests of the Braess Paradox. Games and Economic Behavior 65 (2009) [3]
T. Roughgarden. «The Price of Anarchy.» MIT Press, Cambridge, MA, 2005.

СсылкиПравить

[1] D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258—268 (1968)

[2] Knödel, W. Graphentheoretische Methoden und ihre Anwendungen (нем.). — Springer-Verlag, 1969. — S. 57—59. — ISBN 978-3-540-04668-4.

[3] Kolata, Gina. What if They Closed 42d Street and Nobody Noticed? (англ.), New York Times (25 December 1990). Архивировано 16 февраля 2009 года. Дата обращения: 9 мая 2013.

[4] Алексей Савватеев | Теория игр вокруг нас - YouTube (неопр.). Дата обращения: 13 июля 2019. Архивировано 17 августа 2019 года.

[1]

[2]

[3]

[4]