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í
• Garant: doc. RNDr. Martin Balko, Ph.D.; prof. RNDr. Martin Loebl, CSc.
• Vyučující: doc. RNDr. Martin Balko, Ph.D.; Mgr. Tomáš Čížek; Mgr. David Sychrovský
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace

Anotace

čeština

Ú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 a základy lineárního programování.

Poslední úprava: Maxová Jana, RNDr., Ph.D. (06.05.2025)

angličtina

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 and basics from linear programming.

Poslední úprava: Maxová Jana, RNDr., Ph.D. (06.05.2025)

Podmínky zakončení předmětu

čeština

Podmínkou na zápočet je získání alespoň 65 bodů z celkového počtu bodů, které lze získat za řešení domácích úkolů a písemek. 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. (21.09.2025)

angličtina

The credit for the tutorial is given after obtaining at least 65 points. The points are given for solving problems that are assigned during semester and for tests. The nature of the conditions does not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (21.09.2025)

Literatura

čeština

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

čeština

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.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (01.10.2025)

angličtina

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.

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (01.10.2025)

Sylabus

čeština

Formální modely teorie her

Teorie aukcí, Myersonovo lemma

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. (01.10.2025)

angličtina

Formal models in game theory

Auctions, Myerson's Lemma

Nash equilibrium, Nash's Existence Theorem

Finding equilibria, complexity class PPAD

Correlated equilibiria and other variants

Minimax Theorem

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (01.10.2025)