Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmiczne aspekty teorii gier

Informacje ogólne

Kod przedmiotu: 1000-2M02AA Kod Erasmus / ISCED: 11.303 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmiczne aspekty teorii gier
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: 6.00
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Skrócony opis:

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.

Pełny opis:

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.

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.

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.

Metody i 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.

Zajęcia w cyklu "Semestr letni 2017/18" (w trakcie)

Okres: 2018-02-17 - 2018-06-10
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Damian Niwiński
Prowadzący grup: Lorenzo Clemente, Damian Niwiński
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.