Teoria gier to dział matematyki zajmujący się optymalnym podejmowaniem niezależnych decyzji z udziałem wielu graczy w przypadku konfliktu interesów. Znajduje ona szerokie zastosowanie w wielu dziedzinach nauki, między innymi w biologii, ekonomii, informatyce oraz naukach społecznych.

Przykładowym zastosowaniem z życia codziennego może być sytuacja, w której kierowca samochodu dojeżdża do przejścia dla pieszych i zauważa w pobliżu pieszego. Kierowca może zatrzymać się, zwolnić, przyspieszyć lub nie zareagować. Pieszy może przepuścić samochód albo wejść na pasy. Zarówno jeden jak i drugi gracz mogą podjąć odpowiednią decyzję mając na uwadze jakie zachowanie jest dla nich najlepsze w kontekście zbioru decyzji możliwych do podjęcia przez drugiego gracza. Innym przykładem może być sytuacja, w której producent pewnego wyrobu decyduje o jakości swego produktu mając na uwadze reakcję rynku i spodziewane zyski (koszty produkcji a sprzedaż).

Rozważamy dowolną liczbę graczy podejmujących niezależne decyzje.
Każdy z graczy ma dostępny własny zbiór strategii – możliwych do podjęcia decyzji.
Zbiór podjętych przez każdego z graczy decyzji odpowiada punktowi przestrzeni wielowymiarowej zawierającemu wypłaty dla wszystkich graczy. Im współczynnik wypłaty wyższy, tym sytuacja dla gracza jest korzystniejsza.

Optimum Hicks'a to punkt, w którym suma wypłat wszystkich graczy jest największa (w całej rozważanej przestrzeni).
Równowaga Nash'a to punkt, w którym żaden z graczy nie zmieniłby swojej decyzji, jeśli znałby prędzej decyzje pozostałych.
Atraktory to w tym zastosowaniu równowagi Nash'a, do których zmierzają (zgodnie z kierunkami preferencji graczy) pozostałe punkty przestrzeni. Obszary wskazujące na dany atraktor (przyciągane) stanowią jego basen przyciągania.

Przykładowe zastosowanie teorii gier

Jednym z najpopularniejszych przykładów zastosowań teorii gier jest dylemat więźnia. Intuicyjne rozumienie tej sytuacji jest następujące. Dwie osoby zostały schwytane przez policję przy okazji nieudanej próby kradzieży. Są oni także podejrzewani o popełnienie większej zbrodni. Nie ma jednak dowodów obciążających żadnego z podejrzanych. Więźniowie zostają rozdzieleni i każdemu z nich przedstawia się ofertę współpracy - zeznawania przeciwko drugiemu więźniowi w zamian za złagodzenie kary. Każdy więzień ma więc do dyspozycji 2 strategie (współpraca i milczenie). Dopiero po podjęciu decyzji przez każdego więźnia, znane są skutki ich działań (patrz macierz wypłat, Rys. 1). W przypadku milczenia obydwu więźniów żaden z więźniów nie odniesie żadnej korzyści. Jeśli obaj będą zeznawać przeciwko sobie, każdego więźnia obciążą zeznania drugiego, ale kara będzie odrobinę złagodzona. Z kolei gdy jeden więzień zeznaje a drugi milczy, pierwszy z nich otrzymuje złagodzenie kary a drugi zostaje obciążony zeznaniami.


Rys. 1. Przykładowa macierz wypłat

Taka macierz wypłat może zostać zamodelowana przy pomocy appletu (musisz mieć zainstalowaną javę dostępną w przeglądarce). Należy wybrać w menu konfiguracji opcję "Wprowadź", następnie wybrać liczbę 2 graczy oraz przejść dalej. Opcjonalnym krokiem jest nazwanie instancji problemu i graczy a także ich poszczególnych strategii. Po dodaniu 2 graczy następuje przejście do trybu przeglądania. Macierz wypłat jest tu reprezentowana w przestrzeni 2 lub 3-wymiarowej (w zależności od liczby graczy). Każdy punkt przestrzeni odpowiada kombinacji podjętych decyzji. Po wybraniu odpowiedniego punktu (przez kliknięcie na nim lub wybór z menu bocznego odpowiednich współrzędnych) możliwe jest zmodyfikowanie wypłat graczy w wybranej sytuacji. Po nadaniu odpowiednich wypłat (patrz macierz wypłat, Rys. 1) możliwe jest wyznaczanie opisanych powyżej cech teorii gier (wybór w menu opcji "Wyznaczanie cech". Wybierając do wyznaczenia poszczególne parametry zauważamy, że największe sumaryczne korzyści daje sytuacja, gdy obaj więźniowie współpracują (Optimum Hicks'a). Więźniowie, nie mogąc komunikować się między sobą, wybiorą jednak zeznawanie, bo jest to dla nich lepsza decyzja, gdy nie znają decyzji drugiego więźnia (Równowaga Nash'a).

Applet

Wybierz język interfejsu programu: (applet wymaga javy w przeglądarce i nie jest podpisany)

Opis appletu

Wybór konfiguracji

Menu główne aplikacji (Rys. 2) umożliwia wprowadzanie konfiguracji (czyli wypłat dla graczy w zależności od ich strategii) na trzy sposoby. Każdy z nich został opisany poniżej.

• Pierwszy przycisk prowadzi do trybu definiowania nowej konfiguracji.
  • W następstwie naciśnięcia go, pojawia się panel konfiguracji (Rys. 3), gdzie można ustalić nazwę instancji gry oraz liczbę graczy.
    • Przejście dalej aktywuje panel edycji graczy (Rys. 4). Można tu edytować nazwy graczy, liczbę ich strategii oraz ich nazwy. Po dodaniu graczy trafimy do okna przeglądania w trybie edycji, gdzie możliwa będzie edycja wypłat graczy (Rys. 6).
• Przycisk środkowy umożliwia wybór jednej z predefiniowanych konfiguracji. Po jego wciśnięciu pojawia się panel z konfiguracjami do wyboru (Rys. 5).
• Ostatni przycisk pozwala na załadowanie konfiguracji z pliku.

Po wyborze konfiguracji następuje przejście do widoku przeglądania:

• w trybie edycji (Rys. 6) – dla nowej konfiguracji
• w trybie wyznaczania cech (Rys. 7) – dla wczytanej konfiguracji

Rys. 2. Menu główne

Rys. 3. Panel konfiguracji

Rys. 4. Panel edycji graczy

Rys. 5. Panel wyboru konfiguracji

Przeglądanie przestrzeni

W widoku przeglądania dostępne są 2 tryby: edycji oraz wyznaczania cech. Panele wspólne to:

• Konfiguracja – umożliwia zapis aktualnej instancji do pliku,
• Panel sterujący umożliwiający wybór trybu oraz powrót do menu,
• Przeglądarka przestrzeni (w różnych trybach wyświetlania).

Tryb edycji

W trybie edycji (Rys. 6) charakterystyczną cechą jest panel wyboru elementu przestrzeni i edycji jego wypłat (co ma wpływ na wyznaczane cechy). Osie x, y, z reprezentują poszczególnych graczy, a ich kolory oznaczone na panelu odpowiadają osiom w przeglądarce przestrzeni. Dla każdego gracza możliwa jest zmiana jego strategii, co jest równoznaczne z przesunięciem pozycji w przestrzeni. Aktualne położenie (lub zbiór określony wyborami jedynie części graczy) wyróżnione są w przeglądarce przestrzeni.

Tryb wyznaczania cech

Z kolei w trybie wyznaczania cech (Rys. 7), możliwy jest wybór optimów Hicksa lub równowag Nasha wraz z ich basenami przyciągania. Optima Hicksa są wyróżnione jednym kolorem. Każda równowaga Nasha jest oznaczona odmiennym kolorem, a baseny przyciągania tych atraktorów wypełnione są kolorami przyciągających je atraktorów, w stopniu odpowiadającym sile przyciągania poszczególnych równowag.

Rys. 6. Tryb edycji

Rys. 7. Tryb wyznaczania cech

Szczegóły techniczne: zastosowane algorytmy

Opis algorytmu wyznaczania optimów Hicksa: dla całej przestrzeni sprawdzana jest suma wypłat wszystkich graczy w danym punkcie. Optimami Hicksa są punkty przestrzeni z największą znalezioną sumą wypłat.

Algorytm wyznaczania równowag Nasha oraz ich basenów przyciągania opisano poniżej.

• Znalezienie równowag Nasha
  • Wyszukaj punkty przestrzeni, w których dla każdego gracza zachodzi następująca sytuacja:
    • Znając decyzje pozostałych graczy, gracz nie może podjąć lepszej decyzji
• Wyznaczanie basenów przyciągania do równowag Nasha
  • Dla każdego punktu przestrzeni:
    • Jeśli to równowaga Nasha, przejdź do następnego punktu przestrzeni
    • Powtórz wielokrotnie (np. 10 000 przebiegów):
      • Zaczynając z tego punktu, tak długo jak nie znajdziesz się w którejś z równowag Nasha, wykonuj:
        • Wylosuj (z równym prawdopodobieństwem) jednego z graczy
        • Niech gracz ten zmieni strategię na jedną z dających mu największy zysk (wybór losowy z równym prawdopodobieństwem, a decyzje pozostałych graczy nie zmieniają się)
    • Wyznacz wszystkie osiągalne z danego punktu atraktory wraz z ich współczynnikami przyciągania (określającymi to, jak często z tego punktu docieramy do każdego z osiągalnych atraktorów)
    • Wizualizuj punkt jako zbiór osiągalnych atraktorów z różnym prawdopodobieństwem przyciągania.

Przydatne źródła

• Game Theory – Theodore L. Turocy, Bernhard von Stengel
• http://en.wikipedia.org/wiki/Game_theory
• http://en.wikipedia.org/wiki/Attractor

Program i tekst: Marcin Samsonowski

Opiekun: Maciej Komosinski