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

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

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

Пример

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

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

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