Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki - Centralny System Uwierzytelniania
Strona główna

Algorytmiczne aspekty teorii gier

Informacje ogólne

Kod przedmiotu: 1000-2M02AA
Kod Erasmus / ISCED: 11.303 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Algorytmiczne aspekty teorii gier
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne: 6.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

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 uczenia się:

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.

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ą.

Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)

Okres: 2022-02-21 - 2022-06-15
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: Damian Niwiński, Pierre Ohlmann
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin

Zajęcia w cyklu "Semestr letni 2022/23" (jeszcze nie rozpoczęty)

Okres: 2023-02-20 - 2023-06-18

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: 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, Wydział Matematyki, Informatyki i Mechaniki.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 6.8.0.0-0cee12404 (2022-08-03)