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

Szukamy zastosowań

Czy nasz model może się na coś przydać? Zgodnie z tym co zobaczyliśmy wyżej można sądzić, że teoria gier znajduje bezpośrednie zastosowanie przy planowaniu komunikacji w mieście. Można na przykład zastosować poniższy algorytm:

1
2
3
4
5
6

 Przedstaw sieć połączeń w mieście jako graf
 Dla każdej krawędzi w grafie:
  Usuń tę krawędź. 
  Sprawdź, czy usunięcie tej krawędzi poprawiło przepustowość
    Jeżeli tak, to krawędź jest niepotrzebna. Zwróć ją i zakończ działanie algorytmu,
 Wszystkie krawędzie są potrzebne.

Dlaczego jednak ciągle jeździmy po zatłoczonych drogach, skoro powyższy algorytm mógłby uczynić nasze życie dużo prostszym (i to tylko poprzez zamykanie ulic!)? Pierwszy powód jest dosyć prosty: nasz model jest dosyć naiwnym opisem rzeczywistości. Mimo że sprawdza się w prostych przypadkach i poprawnie przewiduje naturę zjawisk, to już konkretne przewidywania często są zwyczajnie mylne. Ciężko jest na przykład wyznaczyć stałe i dla prawdziwych ulic.

Czym są problemy -zupełne? Bardziej niż ich definicja interesuje nas ich pewna ważna właściwość. Mianowicie nie umiemy efektywnie (czyli szybko) rozwiązywać tych problemów. I co więcej: podejrzewamy, że jest to niemożliwe. Więcej o problemach można przeczytać na polskiej Wikipedii .

Drugi powód ma zupełnie inną naturę. Żeby nasz algorytm dział, musimy umieć szybko szukać najgorszego stanu równowagi dla zadanego grafu. Jednakże w grafach, które opisują prawdziwe miasta, z kierowcami jadącymi różnymi samochodami w różnych kierunkach to zadanie jest bardzo trudne. Dokładniej mówiąc jest -zupełne. Ale to akurat jest kwestia wykraczająca poza temat tego artykułu.

Po co komu teoria gier?

W artykule mówiliśmy o bardzo małym wycinku teorii gier. Jednak już ten wycinek jest bardzo interesujący. Dlaczego?

Teoria gier jest ciekawa

Po pierwsze teorie, które opisywaliśmy są bardzo ciekawe matematycznie. Już w przypadku prostych gier pojawia się wiele ciekawych pytań takich jak:

• Kiedy w tej grze istnieje stan równowagi?
• Czy wszystkie stany równowagi są jednakowo korzystne dla graczy? Nie było tak w przypadku dwóch firm i w przypadku ruchu w mieście.
• Czy przypadek najlepszy dla ogółu jest stanem równowagi? Na przykład może okazać się, że w stanie, w którym średni czas przejazdu jest najmniejszy, któremuś kierowcy opłaca się zmienić strategię tak, żeby jego czas przejazdu się zmniejszył. Oznaczać to będzie jednak pogorszenie warunków dla pozostałych kierowców i w konsekwencji spadek średniego czasu przejazdu przez miasto.

	Gracz A wybiera strategię 1	Gracz A wybiera strategię 2
Gracz B wybiera strategię 1	Wypłata gracza A to złotych Wypłata gracza B to złotych	Wypłata gracza A to złotych Wypłata gracza B to złotych
Gracz B wybiera strategię 2	Wypłata gracza A to złotych Wypłata gracza B to złotych	Wypłata gracza A to złotych Wypłata gracza B to złotych

Ogólna gra macierzowa dla dwóch graczy, z dwiema opcjami wyboru. Ta gra jest parametryzowana ośmioma liczbami: . W zależności od tego, jak je wybierzemy, nasza gra będzie miała różne właściwości (np. może mieć, bądź nie mieć stanów równowagi).

Drugim argumentem za tym, że teoria gier jest interesująca jest to, że pozwala ona tworzyć modele opisujące rzeczywistość. Oczywiście, te modele mogą być mniej lub bardziej dokładne. Ale pozostaje faktem, że biolodzy wykorzystują je do opisu zwierząt w stadzie, a ekonomiści do opisu zachowań firm i konsumentów.

Wreszcie, teoria gier jest miejscem ciekawej interakcji pomiędzy informatyką, a pozostałymi dziedzinami nauki. Oczywiście: biolodzy mogą tworzyć modele. Ale przecież ktoś musi pisać programy, które będą liczyły, co te modele przewidują. W przypadku ruchu w mieście musimy wiedzieć, kiedy, dla miasta zadanego grafem, umiemy policzyć najgorszy stan równowagi, kiedy umiemy policzyć jego rozsądne przybliżenie, a kiedy nie umiemy policzyć nic. Wiedzę o tym, jak policzyć przewidywania modelu (i czy jest to w ogóle możliwe) muszą dostarczyć właśnie informatycy.