Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
An introduction to algorithmic game theory, a relatively new field whose objective is to study formal models of
strategic environments and to design effective algorithms for them. This introductory course covers basic concepts
and methods that are illustrated with several practical applications. To successfully pass the course, it is
recommended to know basics from complexity theory.
Last update: 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.
Course completion requirements -
Last update: doc. RNDr. Martin Balko, Ph.D. (07.10.2019)
The credit for the tutorial is given after obtaining at least one quater of all available points. The points are given for solving problems that are assigned during semester. The nature of the conditions does not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.
Last update: doc. RNDr. Martin Balko, Ph.D. (07.10.2019)
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.
Literature -
Last update: 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
Last update: 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
Requirements to the exam -
Last update: doc. RNDr. Martin Balko, Ph.D. (22.09.2020)
There will be oral exam with time for preparation of the answers. The material required for the exam will be the same as taught in the lecture. The exam may include easier or moderately difficult problems from these topics. The exam can be done online.
Last update: doc. RNDr. Martin Balko, Ph.D. (22.09.2020)
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.
Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (29.01.2018)
Formal models in game theory
Auctions, Myerson's Lemma
Price of anarchy
Nash equilibrium, Nash's Existence Theorem
Finding equilibria, complexity class PPAD
Correlated equilibiria and other variants
Minimax Theorem
Last update: doc. RNDr. Martin Balko, Ph.D. (04.10.2018)