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^[1].

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 ${\displaystyle U}$

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

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

Przykład

Poniższy przykład pochodzi z oryginalnego artykułu Dietricha Braessa^[1]. 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 ${\displaystyle p}$ oznacza gęstość ruchu w tysiącach aut.

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

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

Analiza równowagi Nasha

Każde auto 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 ${\displaystyle p}$ i ${\displaystyle q}$ to liczby aut w tysiącach pokonujących odpowiednio trasy AXB i AYB, otrzymujmy równania:

${\displaystyle p+q=6}$

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

czyli

${\displaystyle p+q=6}$

${\displaystyle 50+p+10p=10q+50+q}$

których rozwiązaniem jest ${\displaystyle p=q=3.}$

Przy tej gęstości ruchu pokonanie obu dostępnych tras zabiera ${\displaystyle 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 ${\displaystyle 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żde auto 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 ${\displaystyle p,}$ ${\displaystyle q}$ i ${\displaystyle r}$ to liczby aut w tysiącach pokonujących odpowiednio trasy AXB, AYB i AYXB, otrzymujmy równania:

${\displaystyle p+q+r=6}$

${\displaystyle 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

${\displaystyle p+q+r=6}$

${\displaystyle 50+p+10(p+r)=10(q+r)+50+q=10(q+r)+10+r+10(p+r)}$

których rozwiązaniem jest ${\displaystyle p=q=r=2.}$ Czas przejazdu każdej z tych dróg wynosi wówczas ${\displaystyle 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.

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^[2].

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

Wskazywano także na symptomy wystąpienia paradoksu Braessa na drogach Winnipeg^[4].

Praca Rapoporta i in.^[5] 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.^[6] 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.

Istnieją także fizyczne analogi paradoksu Braessa. Prace Cohena i in.^[7] oraz Penchiny i in.^[8] 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

Przypisy