Парадокс Браеса
Парадокс Браеса — парадокс, приписываемый немецкому математику Дитриху Браесу (статья 1968 года[1]), гласящий, что добавление дополнительных мощностей в сеть при условии, что двигающиеся по сети сущности сами выбирают свой маршрут, может снизить общую производительность. Происходит это по той причине, что равновесие Нэша для таких систем не обязательно оптимально.
Парадокс можно изложить на примере дорожной сети. Пусть у нас задана сеть дорог, для каждого её узла известно количество автомобилей, выезжающих оттуда, и пункты назначения этих автомобилей. Одна дорога может оказаться предпочтительнее другой не только благодаря качеству покрытия, но и благодаря меньшей плотности потока. Если каждый водитель будет выбирать маршрут, который выглядит наиболее благоприятным для него, полученное время нахождения в пути не обязательно будет минимальным. Более того, можно привести пример, когда перераспределение трафика в ответ на создание дополнительных дорог приведёт к тому, что время нахождения в пути только возрастёт.
Пример
Предположим, автомобилисты хотят попасть из пункта Start в пункт End. Имеется два пути — через город A и через город B. Время пути от пункта Start до города A зависит от плотности потока и равно количеству автомобилей (T), делённому на 100. Путь от пункта Start до города B не зависит от количества автомобилей и равен 45 минутам. Аналогично, путь из А в пункт назначения занимает 45 минут, а время в пути от B до пункта назначения равно T/100. Если A и B не соединены, то время по маршруту Start-A-End будет равно <math>\tfrac{A}{100} + 45</math>, а на маршрут Start-B-End будет затрачено <math>\tfrac{B}{100} + 45</math>. Если бы один из путей был короче, то отсутствовало бы равновесие Нэша, каждый рациональный водитель переключился бы на более короткий маршрут. Допустим, у нас выехало из точки Start 4000 автомобилей, тогда из того, что <math>A + B = 4000</math>, можно вывести, что система придёт в равновесие когда <math>A = B = 2000</math>. Следовательно, независимо от выбранной дороги автомобиль будет в пути <math>\tfrac{2000}{100} + 45 = 65</math> минут.
Теперь предположим, что пунктирная линия между A и B представляет собой новый, очень короткий путь, езда по которому занимает приблизительно 0 минут. В этой ситуации все водители предпочтут маршрут Start-A маршруту Start-B, потому что маршрут Start-A займёт в самом худшем случае <math>\tfrac{T}{100} = \tfrac{4000}{100} = 40</math> минут, в то время как маршрут Start-B гарантированно занимает 45. В узле A каждый рациональный водитель предпочтёт добраться по короткому пути до B и затем доехать до пункта назначения, потому что маршрут A-End гарантировано занимает 45 минут, а маршрут A-B-End в самом худшем случае займёт только <math>0 + \tfrac{4000}{100} = 40</math> минут. Таким образом, время в пути для каждого водителя станет <math>\tfrac{4000}{100} + \tfrac{4000}{100} = 80</math> минут, то есть после строительства новой дороги время в пути возросло на 15 минут.
Если бы водители договорились не пользоваться дорогой между A и B, то они бы сэкономили это время, но поскольку каждый отдельный водитель выгадывает время, пользуясь дорогой A-B, то такое распределение не является социально оптимальным, в чём проявляется парадокс Браеса.
Парадокс Браеса в реальной жизни
В качестве примеров проявления парадокса Браеса в реальной жизни приводят улучшение ситуации на дорогах в Штутгарте после закрытия для движения секции одной из новых дорог[2]. В 1990 году закрытие 42-й улицы в Нью-Йорке сократило количество заторов в этом районе[3].
Напишите отзыв о статье "Парадокс Браеса"
Примечания
- ↑ D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258—268 (1969)
- ↑ Knödel W. Graphentheoretische Methoden und ihre Anwendungen. — Springer-Verlag, 1969. — P. 57–9. — ISBN 978-3-540-04668-4.
- ↑ Kolata, Gina. [query.nytimes.com/gst/fullpage.html?res=9C0CE7D81530F936A15751C1A966958260&scp=8&sq=&st=nyt What if They Closed 42d Street and Nobody Noticed?] (англ.), New York Times (25 декабря 1990 года). Проверено 9 мая 2013 года.
Литература
- D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258—268 (1969) [homepage.ruhr-uni-bochum.de/Dietrich.Braess/paradox.pdf] [homepage.rub.de/Dietrich.Braess/Paradox-BNW.pdf]
- A. Rapoport, T. Kugler, S. Dugar, and E. J. Gisches, Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox. Games and Economic Behavior 65 (2009) [www.parisschoolofeconomics.eu/IMG/pdf/Choices_of_routes.pdf]
- T. Roughgarden. «The Price of Anarchy.» MIT Press, Cambridge, MA, 2005.
Ссылки
- [msdn.microsoft.com/msdnmag/issues/05/12/TestRun/default.aspx Software Testing Paradoxes]
- [homepage.ruhr-uni-bochum.de/Dietrich.Braess/#paradox Домашняя страница Браеса]
|
||||||
Отрывок, характеризующий Парадокс Браеса
– Свет увидали, ваше сиятельство, как светлейший поступил, – робко и беспрестанно оглядываясь на своего полкового командира, сказал Тимохин.– Отчего же так? – спросил Пьер.
– Да вот хоть бы насчет дров или кормов, доложу вам. Ведь мы от Свенцян отступали, не смей хворостины тронуть, или сенца там, или что. Ведь мы уходим, ему достается, не так ли, ваше сиятельство? – обратился он к своему князю, – а ты не смей. В нашем полку под суд двух офицеров отдали за этакие дела. Ну, как светлейший поступил, так насчет этого просто стало. Свет увидали…
– Так отчего же он запрещал?
Тимохин сконфуженно оглядывался, не понимая, как и что отвечать на такой вопрос. Пьер с тем же вопросом обратился к князю Андрею.
– А чтобы не разорять край, который мы оставляли неприятелю, – злобно насмешливо сказал князь Андрей. – Это очень основательно; нельзя позволять грабить край и приучаться войскам к мародерству. Ну и в Смоленске он тоже правильно рассудил, что французы могут обойти нас и что у них больше сил. Но он не мог понять того, – вдруг как бы вырвавшимся тонким голосом закричал князь Андрей, – но он не мог понять, что мы в первый раз дрались там за русскую землю, что в войсках был такой дух, какого никогда я не видал, что мы два дня сряду отбивали французов и что этот успех удесятерял наши силы. Он велел отступать, и все усилия и потери пропали даром. Он не думал об измене, он старался все сделать как можно лучше, он все обдумал; но от этого то он и не годится. Он не годится теперь именно потому, что он все обдумывает очень основательно и аккуратно, как и следует всякому немцу. Как бы тебе сказать… Ну, у отца твоего немец лакей, и он прекрасный лакей и удовлетворит всем его нуждам лучше тебя, и пускай он служит; но ежели отец при смерти болен, ты прогонишь лакея и своими непривычными, неловкими руками станешь ходить за отцом и лучше успокоишь его, чем искусный, но чужой человек. Так и сделали с Барклаем. Пока Россия была здорова, ей мог служить чужой, и был прекрасный министр, но как только она в опасности; нужен свой, родной человек. А у вас в клубе выдумали, что он изменник! Тем, что его оклеветали изменником, сделают только то, что потом, устыдившись своего ложного нарекания, из изменников сделают вдруг героем или гением, что еще будет несправедливее. Он честный и очень аккуратный немец…
– Однако, говорят, он искусный полководец, – сказал Пьер.
– Я не понимаю, что такое значит искусный полководец, – с насмешкой сказал князь Андрей.
– Искусный полководец, – сказал Пьер, – ну, тот, который предвидел все случайности… ну, угадал мысли противника.
– Да это невозможно, – сказал князь Андрей, как будто про давно решенное дело.
Пьер с удивлением посмотрел на него.
– Однако, – сказал он, – ведь говорят же, что война подобна шахматной игре.
– Да, – сказал князь Андрей, – только с тою маленькою разницей, что в шахматах над каждым шагом ты можешь думать сколько угодно, что ты там вне условий времени, и еще с той разницей, что конь всегда сильнее пешки и две пешки всегда сильнее одной, a на войне один батальон иногда сильнее дивизии, а иногда слабее роты. Относительная сила войск никому не может быть известна. Поверь мне, – сказал он, – что ежели бы что зависело от распоряжений штабов, то я бы был там и делал бы распоряжения, а вместо того я имею честь служить здесь, в полку вот с этими господами, и считаю, что от нас действительно будет зависеть завтрашний день, а не от них… Успех никогда не зависел и не будет зависеть ни от позиции, ни от вооружения, ни даже от числа; а уж меньше всего от позиции.
– А от чего же?
– От того чувства, которое есть во мне, в нем, – он указал на Тимохина, – в каждом солдате.
Князь Андрей взглянул на Тимохина, который испуганно и недоумевая смотрел на своего командира. В противность своей прежней сдержанной молчаливости князь Андрей казался теперь взволнованным. Он, видимо, не мог удержаться от высказывания тех мыслей, которые неожиданно приходили ему.
– Сражение выиграет тот, кто твердо решил его выиграть. Отчего мы под Аустерлицем проиграли сражение? У нас потеря была почти равная с французами, но мы сказали себе очень рано, что мы проиграли сражение, – и проиграли. А сказали мы это потому, что нам там незачем было драться: поскорее хотелось уйти с поля сражения. «Проиграли – ну так бежать!» – мы и побежали. Ежели бы до вечера мы не говорили этого, бог знает что бы было. А завтра мы этого не скажем. Ты говоришь: наша позиция, левый фланг слаб, правый фланг растянут, – продолжал он, – все это вздор, ничего этого нет. А что нам предстоит завтра? Сто миллионов самых разнообразных случайностей, которые будут решаться мгновенно тем, что побежали или побегут они или наши, что убьют того, убьют другого; а то, что делается теперь, – все это забава. Дело в том, что те, с кем ты ездил по позиции, не только не содействуют общему ходу дел, но мешают ему. Они заняты только своими маленькими интересами.
