Algoritmická teorie her (NDMI098) - přednáška
Přednáška probíhá každou středu v 17:20 v místnosti S11.
Přednášku povede Martin Balko. E-mail přednášejícího: balko (AT) kam.mff.cuni.cz
Stránky cvičení.
Informace:
- 2/2, Z+Zk, 5 kreditů
- 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.
- Postupně zde budou přibývat poznámky shrnující již probraná témata.
- Seznam literatury:
- Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic game theory. Cambridge University Press, Cambridge, 2007.
- Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, Cambridge, 2016.
- Kevin Leyton-Brown and Yoav Shoham. Essentials of game theory, volume 3 of Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, Williston, VT, 2008.
- Jiří Matoušek and Bernd Gärtner. Understanding and Using Linear Programming. Springer-Verlag New York, Inc., 2006.
- Skripta: [PDF] (poslední aktualizace 9.10.2019)
- Skripta jsou stále ve vývoji. Pokud si všimnete nějaké nepřesnosti nebo místa k vylepšení, tak mi, prosím, dejte vědet e-mailem.
Jednotlivé přednášky:
- První přednáška (1.10.2019): Byl dohodnut čas přednášky a cvičení na úmluvě KAM a IÚUK.
- Druhá přednáška (8.10.2019):
- Úvod, informace a zápočtu a zkoušce,
- hry v normálním tvaru, Nashova ekvilibria (čistá a smíšená), konkrétní příklady her v normálním tvaru,
- rozpracovali jsme důkaz Nashovy věty pomocí Brouwerovy věty o pevném bodě.
- Třetí přednáška (16.10.2019): Bude doplněno.