Teoria gier, czyli sposób na korki w mieście

03.02.2011 - Krzysztof Dryś
TrudnośćTrudność

Kolejna gra

Teraz zobaczymy inną, bardziej skomplikowaną grę i sprawdzimy, jakie ma ona stany równowagi. Potem zastanowimy się, czy przewidywania tej teorii mają odbicie w rzeczywistości.

W pewnym mieście wszyscy jadą z punktu A do B. Średnio w ciągu minuty tę trasę stara się przebyć 4000 samochodów. Przyjmijmy następujące założenia:

  • z każdą ulicą związane są dwa współczynniki $ a $ i $ b $, wynikające między innymi z jej długości i jakości nawierzchni,
  • jeżeli w ciągu minuty na ulicę wjeżdża $ n $ samochodów, to przebycie tej ulicy zajmuje im $ a \cdot n + b $ minut.

Popatrzmy teraz na układ ulic w tym mieście. Widzimy, że mamy dwa rodzaje ulic:

  • ulice, których pokonanie zajmuje zawsze tyle samo czasu, niezależnie od liczby samochodów (dla nich $ a = 0 $),
  • ulice, których pokonanie zajmuje czas wprost proporcjonalny do liczby jadących przez nie samochodów (dla nich $ b = 0 $).

alternative text Układ ulic w naszym mieście. Strzałki reprezentują połączenia, a liczby obok nich pokazują czas przejazdu ($ N $ to liczba samochodów jadących ulicą).

Tak jak poprzednio, zajmiemy się stanami równowagi. Teraz graczami są kierowcy samochodów. Stan równowagi, to takie rozłożenie ruchu, w którym nikomu nie opłaca się zmienić trasy.

Można pokazać, że w tym modelu jest tylko jeden stan równowagi. Mianowicie taki, że:

  • Trasą $ A \rightarrow C \rightarrow B $ jedzie 2000 samochodów
  • Trasą $ A \rightarrow D \rightarrow B $ jedzie 2000 samochodów

Czas przejazdu każdą z tych tras wynosi 65 minut. Oznacza to, że nasz model przewiduje, że w przy tym układzie ulic przejazd od A do B zajmie właśnie 65 minut.

Czas na zmiany!

Teraz dodamy do naszego miasta jeszcze jedną ulicę i zobaczymy jak zmienią się przewidywania modelu. Nowa ulica będzie prowadzić od $ C $ do $ D $. Dla uproszczenia założymy, że nowa ulica jest bardzo krótka. Tak krótka, że przejazd nią w ogóle nie zajmuje czasu.

alternative text Nowy układ ulic w naszym mieście. Dodaliśmy połączenie od $ C $ do $ D $ Strzałki reprezentują możlwie połączenia, a liczby obok nich pokazują czas przejazdu ($ N $ to liczba samochodów jadących ulicą).

Intuicja podpowiada nam, że jeżeli otworzymy nową ulicę, to czas przejazdu nie powinien spaść. A co mówi nasz model? Przede wszystkim zauważmy, że stan:

  • Trasą $ A \rightarrow C \rightarrow B $ jedzie 2000 samochodów
  • Trasą $ A \rightarrow D \rightarrow B $ jedzie 2000 samochodów
wciąż jest stanem równowagi. Ale już nie jedynym! W nowym układzie ulic jest jeszcze jeden stan równowagi. Mianowicie taki, w którym wszystkie samochody jadą trasą $ A \rightarrow C \rightarrow D \rightarrow B $. Tyle, że ten stan jest mniej korzystny! W tym stanie przejazd samochodem przez miasto zajmuje 80 minut.

Wprowadziliśmy pewien model ruchu samochodów w mieście. W naszym modelu dodanie ulicy może spowodować, że powstanie nowy, mniej korzystny stan równowagi. Oznacza to, że nasz model przewiduje, że dodanie ulicy może spowodować wydłużenie czasu jazdy przez miasto. To zdecydowanie jest sprzeczne z naszą intuicją. Dlatego twierdzenie, że stworzenie dodatkowej drogi może pogorszyć przepustowość, dorobiło się własnej nazwy. Nazywamy je paradoksem Braessa.

Paradoks Braessa

Paradoks Braessa jest przewidywaniem naszego modelu. Przewidywaniem, które jest dla nas niespodziewane. Dlatego od razu nasuwa się pytanie: czy to zjawisko ma miejsce w rzeczywistości? Okazuje się, że tak. Naprawdę zdarza się, że ulice są zamykane po to, by polepszyć warunki jazdy w mieście. Oto parę przykładów.

  • W 1990 roku w Nowym Yorku zamknięto 42 ulicę, co poprawiło warunki jazdy w mieście. Pisał o tym The New York Times (artykuł po angielsku).
  • W Seulu warunki jazdy poprawiły się, gdy zamknięto kawałek obwodnicy.

Ważne jest, żeby mieć świadomość, że powyższy model ma więcej zastosowań niż tylko opis ruchu samochodowego. Może on równie dobrze służyć do opisywania każdej sytuacji, w której różni gracze muszą niezależnie od siebie wybierać drogę. Taką sytuacją jest na przykład internet, gdzie każdy użytkownik chce, by jego pakiety szły najszybszymi (czyli najmniej obciążonymi) łączami.

4.714285
Twoja ocena: Brak Ocena: 4.7 (7 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com