Modern Algoritmic Game Theory - NOPT021

• Title: Algoritmy moderní teorie her
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: winter
• E-Credits: 5
• Hours per week, examination: winter s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Additional information: http://Ústní zkouška. Požadavky k ústní zkoušce odvovídají sylabu.
• Guarantor: prof. RNDr. Martin Loebl, CSc.
• Teacher(s): Mgr. Radovan Haluška; Mgr. Martin Schmid, Ph.D.
• Class: Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Optimalization

Annotation

English

The objective of this course is to provide a foundational introduction to algorithmic game theory, bridging theoretical concepts with practical algorithm implementations. Students explore fundamental solution concepts such as Nash equilibrium and minimax strategies, alongside learning dynamics including fictitious play, regret minimization, and replicator dynamics. The course systematically covers both normal-form and extensive-form games. The course is part of the inter-university programme prg.ai Minor (https://prg.ai/minor).

Last update: Maxová Jana, RNDr., Ph.D. (22.05.2025)

Czech

Cílem tohoto kurzu je poskytnout základní úvod do algoritmické teorie her, který propojuje teoretické koncepty s praktickými implementacemi algoritmů. Studenti se seznámí se základními pojmy řešení, jako je Nashovo equilibrium a minimax strategie, a s dynamikami učení, včetně fictitious play, regret minimization a replicator dynamics. Kurz systematicky pokrývá hry v normální formě i v rozšířené formě. Kurz je součástí meziuniverzitního programu prg.ai Minor (https://prg.ai/minor).

Last update: Maxová Jana, RNDr., Ph.D. (22.05.2025)

Course completion requirements

English

Oral exam.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Czech

Ústní zkouška.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Literature

English

[1] Nisan, Noam, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani. ‘Algorithmic Game Theory’. Cambridge University Press, 2007.

[2] Schmid, Martin. ‘Search in Imperfect Information Games’. ArXiv abs/2111.05884 (2021).

Last update: Maxová Jana, RNDr., Ph.D. (22.05.2025)

Requirements to the exam

English

Oral exam, requirements according to the sylabus of the lecture.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Czech

Ústní zkouška, požadavky rozsahem odpovídají sylabu přednášky.

Last update: Maxová Jana, RNDr., Ph.D. (26.04.2025)

Syllabus

1. Introduction, matrix games. Solution concepts - Nash equilibrium, Minimax strategies

2. Minimax theorem, Fictitious play learning dynamics

3. Linear programming approaches, correlated equilibria

4. Regret minimization framework, regret matching

5. Invited talk - Double Oracle.

6. Sequential decision making, extensive-form games, best response implementation

7. Fictitious play, averaging

8. Sequence-form linear programming, subgame perfect equilibria

9. Counterfactual regret minimization

10. CFR+, CFR-BR, Discounted CFR

11. History of AI in games

Last update: Schmid Martin, Mgr., Ph.D. (14.09.2025)