Algorytmiczne aspekty teorii gier 1000-2M02AA
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.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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.
Kryteria oceniania
Egzamin polega na samodzielnym rozwiązaniu określonej liczby problemów w wyznaczonym kilkudniowym terminie. Egzamin sprawdza zrozumienie poznanych pojęć i zdolność do twórczego stosowania poznanych metod algorytmicznych.
W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie napisanie krótkiego raportu, w którym autor samodzielnie sformułuje problemy badawcze w powiązaniu z wykładem i literaturą przedmiotu, a następnie omówienie tego raportu z wykładowcą.
Literatura
Guillermo Owen, Teoria gier, PWN, Warszawa 1975.
Philip D. Straffin, Teoria gier, Warszawa 2001.
E. Graedel, W. Thomas, and T. Wilke, Automata, Logics, and Infinite Games, Lecture Notes in Computer Science 2500, Springer 2002.
N.Nisan, T.Roughgarden, E.Tardos, V.Vazirani eds., Algorithmic Game Theory, Cambridge U.Press, 2007.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: