Modern Algorithmic Game Theory

About the Course

Games have long served as benchmarks and marked milestones in the progress of artificial intelligence. This course provides a foundational introduction to algorithmic game theory, bridging theoretical concepts with practical implementation of algorithms. Students will learn fundamental solution concepts such as Nash equilibrium and minimax strategies, as well as learning dynamics like fictitious play, regret minimization, and replicator dynamics. The course systematically explores both normal-form and extensive-form games with perfect and imperfect information.

The course focuses on tabular methods with hands-on implementation of algorithms that converge to Nash equilibria in small games, such as simplified Poker variants. Homework assignments emphasize practical understanding by guiding students through the implementation of these algorithms. A follow-up course in the summer semester extends the material to approximation methods and large-scale games. For a more theory-oriented perspective, students are also encouraged to take Algorithmic Game Theory (NDMI098), offered in the winter term. This course is offered as part of the inter-university programme prg.ai Minor (https://prg.ai/minor).

Organizational Details

• This course is currently taught by Martin Schmid at the Faculty of Mathematics and Physics, at Charles University.

• The lectures are held on Wednesdays from 09:00 to 10:30, in the room S9 at Malostranske namesti 25, 1st floor. 

• You can find more information about the course in the Study Information System (SIS).

• All materials for this course are available in the associated GitHub repository.

Prerequisites

• Basic knowledge of Python and its popular libraries -- NumPy and Matplotlib

• Basic understanding of concepts from optimization (convex functions, local/global optima, etc.)

Not required, but helpful:

• Familiarity with reinforcement learning and linear programming

Course Syllabus

Week 1 (slides)

• Normal-form games

• Iterated removal of dominated strategies

• Solution concepts: Maximin strategy and Nash equilibrium

Week 2 (slides)

• Solution concepts: Maximin strategy and Nash equilibrium

• Properties of Maximin strategies and Nash equilibria

• Support enumeration

Week 3 (slides)

• The Price of Anarchy, Tragedy of the Commons and Braess' Paradox

• Evaluation metrics and ε-Nash equilibria

• Fictitious Play

Week 4 (slides)

• Finding Nash equilibria in two-player zero-sum games using LP

• Finding correlated equilibria using LP

Literature

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

• Martin Balko. ‘Algorithmic Game Theory (NDMI098)’. Lecture Notes (2025). 

• Martin Schmid. ‘Search in Imperfect Information Games’. ArXiv abs/2111.05884 (2021).

Teaser

After going through both courses, you will have a solid understanding of modern algorithms for solving large scale games, such as AlphaZero and DeepStack.