Paradoks Braessa

Paradoks Braessa – twierdzenie matematyczne orzekające, że w pewnym modelu ruchu drogowego czasy podróży pojazdów mogą ulec wydłużeniu po dodaniu do sieci drogowej nowego połączenia. Autorem twierdzenia jest niemiecki matematyk Dietrich Braess.

Model ruchu drogowego

Model ruchu drogowego w paradoksie Braessa ma następujące cechy:

1. Sieć drogowa składa się ze skończenie wielu węzłów i łączących je odcinków dróg
2. Po sieci porusza się skończenie wiele pojazdów, każdy z nich ma wyznaczony węzeł startowy i węzeł docelowy
3. Odcinki dróg mają przypisane sobie czasy przejazdu, przy czym czasy te mogą zależeć od liczby pokonujących dany odcinek pojazdów.
4. Układ sieci drogowej i czasy przejazdu poszczególnych odcinków są znane pojazdom
5. Celem pojazdów jest przejazd przez sieć z węzłów początkowych do docelowych po trasie złożonej z odcinków drogowych tak, by zminimalizować łączny czas ich pokonania
6. Decyzje o wyborze tras pojazdy podejmują indywidualnie i niezależnie od siebie

Sformułowanie w teorii gier

Przy powyższych założeniach problem wyborów tras przez pojazdy może być badany w ramach teorii gier. Każdemu konkretnemu układowi dróg, pojazdów i ich punktów startowych i docelowych odpowiada gra wieloosobowa:

• Gracze to poszczególne pojazdy
• Strategie dostępne graczowi to wszystkie możliwe trasy złożone z odcinków drogowych łączące jego węzeł początkowy z docelowym
• Wypłata gracza to łączny czas przejazdu całej wybranej przez niego trasy; zależy on także od tras wybranych przez inne pojazdy (założenie 3)
• Gracze dążą do minimalizacji swojej wypłaty (założenie 5)
• Wypłaty we wszystkich możliwych układach decyzji wszystkich graczy są znane im wszystkim (założenie 4)

W tym ujęciu czasy podróży poszczególnych pojazdów to wypłaty graczy w równowadze Nasha gry odpowiadającej danemu układowi dróg, ich czasów przejazdu, pojazdów i ich węzłów startowych i docelowych. Zgodnie z definicją, w tej równowadze zmiana strategii przez dowolnego gracza, przy niezmienionych decyzjach pozostałych graczy, powoduje zwiększenie się jego wypłaty.

Paradoks Braessa można teraz sformułować następująco:

Istnieje układ drogowy $U$

oraz istnieje układ drogowy $V$ uzyskany z $U$ przez dodanie jednego odcinka drogowego,

takie, że w grze odpowiadającej $V$ czasy przejazdu wszystkich pojazdów w równowadze Nasha są większe niż w równowadze Nasha gry uzyskanej z $U.$

Przykład

Poniższy przykład pochodzi z oryginalnego artykułu Dietricha Braessa. Został opisany w mniej formalnej terminologii.

Wyjściowy układ drogowy

Wyjściowy układ drogowy z autostradami AX i YB oraz drogami lokalnymi AY i XB

Sieć drogowa i auta

Przykład sytuacji, w której ujawnia się paradoks Braessa jest skonstruowany z czterech miast A, B, X i Y. Są one połączone odcinkami drogowymi jak na rysunku i z następującymi czasami przejazdu, przy czym $p$ oznacza gęstość ruchu w tysiącach aut.

• z A do X prowadzi autostrada AX z czasem przejazdu $t_{AX}(p)=50+p$ minut
• z Y do B prowadzi autostrada YB z czasem przejazdu $t_{YB}(p)=50+p$ minut
• z X do B prowadzi droga lokalna XB z czasem przejazdu $t_{XB}(p)=10p$ minut
• z A do Y prowadzi droga lokalna AY z czasem przejazdu $t_{AY}(p)=10p$ minut

Aut jest 6000 i wszystkie mają za zadanie przejechać trasę z A do B.

Analiza równowagi Nasha

Każdy kierowca musi zdecydować się na wybór trasy albo AXB albo AYB.

Równowaga Nasha to taka sytuacja, w której każdy z samochodów spowoduje wydłużenie swojego czasu jazdy, zmieniając decyzję co do wyboru trasy przy niezmienionych decyzjach pozostałych aut. Taka sytuacja występuje wówczas, gdy każdą z dwóch dostępnych tras pokonuje się w tym samym czasie, bo wtedy zmieniający decyzję kierowca powoduje zwiększenie czasu jazdy na trasie, na którą się przeniósł, czyli traci na zmianie. Jeśli $p$ i $q$ to liczby aut w tysiącach pokonujących odpowiednio trasy AXB i AYB, otrzymujmy równania:

$p+q=6$

$t_{AX}(p)+t_{XB}(p)=t_{AY}(q)+t_{YB}(q)$

czyli

$p+q=6$

$50+p+10p=10q+50+q$

których rozwiązaniem jest $p=q=3.$

Przy tej gęstości ruchu pokonanie obu dostępnych tras zabiera $50+3+30=83$ minuty.

Uzupełniony układ drogowy

Układ drogowy po dodaniu jednokierunkowej autostrady YX

Sieć drogowa i auta

Do wyjściowego układu drogowego dodana zostaje droga:

• jednokierunkowa autostrada z Y do X z czasem przejazdu $t_{YX}(p)=10+p$ minut

Aut jest nadal 6000 i wszystkie mają za zadanie przejechać trasę z A do B.

Analiza równowagi Nasha

Tym razem każdy kierowca musi zdecydować się na wybór jednej z tras: AXB, AYB albo AYXB. Analogicznie jak poprzednio, równowaga Nasha to sytuacja, gdy przejazd każdą z dostępnych tras zabiera tyle samo czasu. Jeśli $p,$ $q$ i $r$ to liczby aut w tysiącach pokonujących odpowiednio trasy AXB, AYB i AYXB, otrzymujmy równania:

$p+q+r=6$

$t_{AX}(p)+t_{XB}(p+r)=t_{AY}(q+r)+t_{YB}(q)=t_{AY}(q+r)+t_{YX}(r)+t_{XB}(p+r)$

czyli

$p+q+r=6$

$50+p+10(p+r)=10(q+r)+50+q=10(q+r)+10+r+10(p+r)$

których rozwiązaniem jest $p=q=r=2.$ Czas przejazdu każdej z tych dróg wynosi wówczas $50+2+10(2+2)=92$ minuty.

Założenie jednokierunkowości YX

Po obliczeniu czasu jazdy w stanie równowagi można stwierdzić, że założenie o jednokierunkowości autostrady YX jest nieistotne. Najkrótszy możliwy czas przejazdu trasą autostradową AXYB wynosi ponad 110 minut – ponad 50 minut na każdym z odcinków AX i YB oraz ponad 10 minut na XY. Zatem w stanie równowagi Nasha żaden samochód nie wybrałby tego wariantu.

Wyjaśnienie intuicyjne

Wąskim gardłem systemu są drogi lokalne, na których czas przejazdu bardzo szybko wzrasta wraz z intensywnością ruchu. Po pojawieniu się dodatkowej drogi dostępna staje się nowa trasa, prowadząca oprócz nowego skrótu YX tylko drogami lokalnymi.

Z perspektywy pojedynczego pojazdu, dopóki nową trasą AYXB jeździ mniej aut niż trasami AXB i AYB, kierowca zmieniający trasę na AYXB oszczędza trochę czasu sobie i tym, którzy jadą autostradą, z której użycia zrezygnował, oraz powoduje stratę czasu u tych, którzy jadą drogą lokalną, na którą przeniósł się z autostrady. Ta strata jest 10 razy większa niż zysk w przeliczeniu na jeden samochód. Zatem z każdym kolejnym kierowcą decydującym się na AYXB sumaryczny czas przejazdu wszystkich kierowców rośnie. Ponieważ w stanie równowagi wszyscy kierowcy jadą równie długo a suma czasów podróży wzrosła, nowy stan równowagi jest mniej efektywny od starego.

Z perspektywy całości systemu nowy odcinek drogowy odciąża ruch na autostradach, gdzie jest to mało odczuwalne, a w zamian jeszcze bardziej zagęszcza ruch na drogach lokalnych, powodując wydłużenie czasu podróży.

Paradoks Braessa w sytuacjach rzeczywistych

Znane są przykłady sytuacji, gdy w prawdziwym ruchu drogowym wystąpiły efekty przewidywane przez paradoks Braessa. Wielokrotnie też były dyskutowane sytuacje, rzekomo negujące jego zasadność.

Warunki niewystępowania paradoksu Braessa

Przez kilkadziesiąt lat, utrwaliły się w literaturze reguły dotyczące sytuacji, gdy paradoksu Braessa nie zaobserwujemy:

1. Mała liczba pojazdów w ruchu (niski popyt na przestrzeń transportową)
2. Bardzo duża liczba pojazdów w ruchu (bardzo wysoki popyt)
3. Czas przejazdu poszczególnych odcinków jest stosunkowo mały (pomijalny) – paradoks występuje, lecz czas przejazdu nie ulegnie zmianie przy rozbudowie sieci transportowej.

Sytuacje i przykłady występowania paradoksu Braessa

W 1969 w Stuttgarcie inwestycje drogowe w centrum doprowadziły do znacznego pogorszenia się warunków ruchu drogowego w okolicy Schlossplatz, czemu zaradzono dopiero zamykając dla ruchu kołowego fragment Königsstraße.

W Nowym Jorku w 1990 czasowe zamknięcie 42. Ulicy zwiększyło płynność ruchu w jej okolicy.

Wskazywano także na symptomy wystąpienia paradoksu Braessa na drogach Winnipeg.

Praca Rapoporta i in. relacjonuje eksperymenty z uczestnikami biorącymi w warunkach laboratoryjnych udział w symulowanym ruchu drogowym. Eksperymentatorzy wywołali w nich paradoks Braessa.

Praca Youna i in. przedstawia na ilustracji przewidywany w symulacjach efekt zamknięcia poszczególnych głównych ulic w trzech wielkich aglomeracjach: Nowego Jorku, Boston-Cambridge i Londynu. W każdej z nich są ulice, których zamknięcie miałoby negatywny wpływ na czasy przejazdu oraz ulice, których zamknięcie skróciłoby te czasy, czyli wywołało efekt przewidywany w paradoksie Braessa.

Analogi fizyczne paradoksu Braessa

Two springs joined in series by a short rope. When the short rope is added connecting B and C, the weight hangs lower.

Istnieją także fizyczne analogi paradoksu Braessa. Prace Cohena i in. oraz Penchiny i in. opisują przykłady układów sprężyn i cięgieł podtrzymujących wiszący na nich ciężar, w których dodanie dodatkowego cięgła pomiędzy elementami układu powoduje opadnięcie ciężaru niżej. W tych samych pracach wskazano, że efekty analogiczne do paradoksu Braessa występują też w układach elektrycznych, hydraulicznych i przewodnictwa cieplnego, w których obowiązują pierwsze prawo Kirchhoffa i drugie prawo Kirchhoffa albo ich analogie.

Zobacz też

• paradoks Downsa-Thomsona