Algorytmiczne aspekty teorii gier

Teoria gier została zapoczątkowana przez von Neumanna i Morgensterna jako matematyczna teoria racjonalnego zachowania. Gra składa się z opisu możliwych posunięć i definicji funkcji zysku dla każdego z graczy. Oczywiście, każdy z graczy stara się wybrać taką strategię, jaka maksymalizuje jego zysk. Najczęściej w teorii gier uważa się, że racjonalne zachowanie graczy jest dobrze opisywane pojęciem równowagi Nasha.

Bardzo wiele rzeczywistych sytuacji pasuje do ogólnego schematu teorii gier. W informatyce gra może modelować współzawodnictwo procesów o zasoby komputera, albo interakcję komputera z otoczeniem. W ekonomii używa się gier do modelowania zachowań rynku. W socjologii do modelowania zachowań społecznych.

W trakcie wykładu omówimy ważniejsze pojęcia teorii gier, jak równowaga Nasha, gry z informacją pełną (jak szachy) i niepełną (jak brydż), gry o zerowej sumie, "social choice theory'' i aukcje. Następnie skoncentrujemy się na pewnych grach z pełną informacją, jakie okazują się być szczególnie przydatne do modelowania zachowań systemów informatycznych. W grach tych dwóch graczy wykonuje na przemian nieskończony ciąg ruchów. Wynikiem gry jest więc nieskończony ciąg pozycji, na podstawie którego wyznacza się zwycięzcę. Gry te mają ścisły związek z teoria automatów oraz komputerowo wspomaganą weryfikacją.

Zagadnienie rozwiązywania takich gier, tzn. znajdowania strategii wygrywającej - a także znajdowania strategii optymalnej, np. ze względu na wykorzystywaną pamięć - jest ciekawym i intensywnie badanym problemem algorytmicznym.

Wiedza.

1. Rozróżnia postać ektensywną i postać strategiczną gier i rozumie właściwe im pojęcia determinacji i punktu równowagi.

2. Poznaje dowody twierdzeń o determinacji wybranych gier (np. gier parzystości) i o istnieniu punktu równowagi Nasha i rozumie, że dowody te implikują metody algorytmiczne.

3. Poznaje algorytmy znajdujące strategie w grach w postaci ekstensywnej, w tym także w grach nieskończonych i w grach z uśrednioną wypłatą. Poznaje problemy otwarte związane ze złożonością takich gier.

4. Poznaje algorytmiczne problemy wokół znajdowania punktów równowagi Nasha i algorytm Lemkego-Howsona.

Umiejętności.

1. Potrafi określić strukturę matematyczną logicznych gier towarzyskich i budować teoretyczne algorytmy rozwiązujące takie gry.

2. Potrafi adaptować poznane techniki rozwiązywania gier nieskończonych do gier z nowymi kryteriami wygrywania.

3. Potrafi modelować proste sytuacje informatyczne przy pomocy gier.

4. Potrafi zaimplementować przynajmniej jedną metodę znajdowania równowagi Nasha.

Kompetencje.

1. Rozumie rosnące znaczenie teorii gier w modelowaniu sytuacji informatycznych, zwłaszcza związanych z rozproszeniem i interakcją, np. Internetu i sieci społecznościowych.

2. Rozumie bogactwo problematyki algorytmicznej wokół rozwiązywania gier i znaczenie problemów growych dla rozwoju algorytmiki i teorii złożoności obliczeniowej.