PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   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 [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: doc. RNDr. Martin Balko, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace
Anotace -
Ú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.
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)
Podmínky zakončení předmětu -

Podmínkou na zápočet je získání alespoň čtvrtiny bodů z celkového počtu bodů, které lze získat za řešení domácích úkolů. Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (07.10.2019)
Literatura -

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (29.01.2018)
Požadavky ke zkoušce -

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. Zkouška může probíhat distanční formou.

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

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

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (04.10.2018)
 
Univerzita Karlova | Informační systém UK