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
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
The objective of this course is to bridge 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. (06.03.2025)
Course completion requirements -

Oral exam.

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

G. Owen: Game Theory, London 1971 nebo kterékoliv pozdější vydání (or any later edition).

E. Mendelson: Introducing Game Theory and Its Applications,CRC Press LLC,ISBN 1-58488-300-6, 2004

M. Chobot, F. Turnovec, V. Ulašin: Teória hier a rozhodovania, Alfa Bratislava, 1991.

M. Maňas: Teorie her a její ekonomické aplikace, SPN Praha 1983 nebo pozdější vydání.

Last update: Maxová Jana, RNDr., Ph.D. (22.05.2025)
Requirements to the exam

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

Last update: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)
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)