Algoritmy moderní teorie her - NOPT021

• Anglický název: Modern Algoritmic Game Theory
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• 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í
• Další informace: http://Ústní zkouška. Požadavky k ústní zkoušce odvovídají sylabu.
• Garant: prof. RNDr. Martin Loebl, CSc.
• Vyučující: Mgr. Radovan Haluška; Mgr. Martin Schmid, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Optimalizace

Anotace

čeština

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

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

angličtina

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

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

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

čeština

Ústní zkouška.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

angličtina

Oral exam.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Literatura

čeština

[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).

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

Požadavky ke zkoušce

čeština

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

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

angličtina

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

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Sylabus

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

Poslední úprava: Schmid Martin, Mgr., Ph.D. (14.09.2025)