PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Algoritmická teorie her - NDMI098
Anglický název: Algorithmic Game Theory
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: RNDr. Martin Balko, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
Úvod do algoritmické teorie her, relativně nové oblasti věnující se formálním modelům chování v kompetitivních prostředích a návrhům efektivních algoritmů pro jejich řešení. Tato úvodní přednáška pokrývá základní pojmy a metody, které jsou ilustrovány praktickými aplikacemi. K absolvování přednášky je vhodné znát základy teorie složitosti.
Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)

Podmínkou na zápočet je získání dostatečného počtu bodů za domácí příklady. Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce.

Literatura -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)

Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: Algorithmic Game Theory, Cambridge University Press, 2007.

Tim Roughgarden, Lecture Notes on Algorithmic Game Theory : http://theory.stanford.edu/~tim/f13/f13.html

Požadavky ke zkoušce -
Poslední úprava: RNDr. Martin Balko, Ph.D. (04.10.2018)

Zkouška je ústní s písemnou přípravou. Zkouší se odpřednesená témata a schopnost aplikace na lehčí až středně těžké příklady.

Sylabus -
Poslední úprava: RNDr. Martin Balko, Ph.D. (04.10.2018)

Formální modely teorie her

Teorie aukcí, Myersonovo lemma

Cena anarchie

Nashovo ekvilibrium, Nashova věta

Hledání ekvilibrií, složitostní třída PPAD

Korelovaná ekvilibria a další varianty

Minimaxová věta

 
Univerzita Karlova | Informační systém UK