Algorytmiczne aspekty teorii gier
Informacje ogólne
Kod przedmiotu: | 1000-2M02AA |
Kod Erasmus / ISCED: |
11.303
|
Nazwa przedmiotu: | Algorytmiczne aspekty teorii gier |
Jednostka: | Wydział Matematyki, Informatyki i Mechaniki |
Grupy: |
Przedmioty obieralne dla informatyki Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka |
Punkty ECTS i inne: |
6.00
|
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 2023/24" (w trakcie)
Okres: | 2024-02-19 - 2024-06-16 |
Przejdź do planu
PN WT WYK
CW
ŚR CZ CW
CW
PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Damian Niwiński | |
Prowadzący grup: | Antonio Casares Santos, Kacper Kluk, Damian Niwiński | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Zajęcia w cyklu "Semestr letni 2024/25" (jeszcze nie rozpoczęty)
Okres: | 2025-02-17 - 2025-06-08 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Damian Niwiński | |
Prowadzący grup: | Kacper Kluk, Damian Niwiński | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Egzamin |
Właścicielem praw autorskich jest Uniwersytet Warszawski.