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

Czech

Výklad základních matematických modelů a pojmů souvisejících s racionalním řešením konfliktních situací.

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

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

Week 1

Course

• Matrix games formalism

• Best response

• Minimax policy, Nash equilibrium

• Zero sum games

Practice

• OpenSpiel

• Exploitability computation (i.e policy evaluation)

Week 2

Course

• Minimax theorem

• Minimax policy = Nash equilibrium

• Linear/convex optimization problem

Practice

• Linear programming for solving matrix games

Week 3 - Regret

Course

• Regret

• Folk’s theorem - connecting regret to exploitability

Practice

• Regret minimization in matrix games

• Average/current policy convergence

Week 4 - Sequential Decision Making

Course

• Extensive form games

• Factored observation games

Practice

• Small poker game

• Exploitability computation in extensive form games

Week 5 - Sequence Form

Course

• Sequence -> matrix = exponential explosion

• Sequence form

• Sequence LP

Practice

• Sequence LP

Week 6 - Counterfactual Regret Minimization

Course

• Counterfactual regret minimization

• CFR-BR

Practice

• CFR

Week 7 - Monte Carlo Methods

Course

• MCCFR

• Control variates

Practice

• MCCFR

• VR-MCCFR

Last update: Hubička Jan, doc. Mgr., Ph.D. (14.02.2022)