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

Парадокс Бреса
Названо на честь	Dietrich Braess^d
Першовідкривач або винахідник	Dietrich Braess^d
Парадокс Бреса у Вікісховищі

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

Найпростішим прикладом парадоксу Бреса може бути дорожня мережа. Припустімо, що задана певна мережа доріг, при чому для кожного її вузла відома кількість автомобілів, що виїжджають звідти та пункти призначення цих автомобілів. Одна дорога може бути більш бажаною для водіїв не лише завдяки якості покриття, але і завдяки меншій щільності потоку інших автомобілів. Якщо кожен водій обиратиме маршрут, який виглядає найсприятливішим для нього, то отриманий час перебування в дорозі не обов'язково буде мінімальним. Більш того можна навести приклад, коли перерозподіл трафіку — через будівництво нових доріг — призведе до того, що час в дорозі тільки збільшиться.

Приклад

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

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

Якби водії домовилися між собою не використовувати дорогу між А та В, то вони з'економили б цей час, але оскільки кожен окремий водій виграє час, користуючись дорогою А-В, то такий розподіл не є соціально оптимальним, в чому власне кажучи і складається парадокс Бреса.

Приклади реалізації парадоксу Бреса

Як приклад проявів парадоксу Бреса в реальному житті приводять поліпшення ситуації на дорогах в Штутгарті після закриття для руху однієї з секцій нової дороги[2]. В 1990 році закриття 42-ї вулиці на Мангеттені (Нью-Йорк), скоротило кількість заторів в цьому районі[3]. Парадокс Бреса може реалізовуватися не лише в мережах автомобільного транспорту, але і в системах децентралізованої енергогенерації (на прикладі вітропарків об'єднаних в одну мережу)[4]. Також є свідчення того, що франко-бельгійській групі фізиків-теоретиків вдалося зафіксувати реалізацію парадоксу Бреса в окремо взятій мережі напівпровідників розміром 1 на 1,6 мікрометрів[5]. Роль транспортних артерій в цій мережі відігравали вузькі (150–500 нанометрів) струмопровідні канали. Розрахунки та експерименти дослідників показали, що додання додаткового третього каналу до вже існуючих двох не робить мережу більш ефективною в цілому (принаймні до збільшення його до певної величини).

Див. також

• Рівновага Неша
• Трагедія спільнот
• Дорожній затор
• Індукований попит
• Модальний розподіл
• Парадокс Доунса-Томсона
• Позиція Льюїса-Могриджа
• Ефект Морінга

Література

• D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1969) [1] [2]
• 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) [3]
• T. Roughgarden. «The Price of Anarchy.» MIT Press, Cambridge, MA, 2005.

Посилання

• Software Testing Paradoxes
• Домашня сторінка Бреса

Примітки

1. D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1969)
2. Knödel W (1969). Graphentheoretische Methoden und ihre Anwendungen. Springer-Verlag. с. 57—9. ISBN 978-3-540-04668-4.
3. Kolata, Gina (25 декабря 1990 года). What if They Closed 42d Street and Nobody Noticed? (англ.). New York Times. Процитовано 9 травня 2013 року.
4. ecoleaks (17 вересня 2012 року). Альтернативная энергетика наткнулась на парадокс Браеса (рос.). ecoleaks. Процитовано 06 березня 2015 року.
5. Галиброда, Роман (03 листопада 2012 року). Физикам удалось обнаружить и зафиксировать парадокс Браеса в полупроводниковой сети (рос.). Проект Вся Физика. Процитовано 06 березня 2015 року.