Algorithmic game theory (NDMI098) - lecture

---

Homepage

Time of the lecture: Tuesday 12:20pm, in the room S3.

Instructor: Martin Balko. E-mail: balko (AT) kam.mff.cuni.cz

Tutorials:

• Monday 3:40pm, S6 (Tomáš Čížek),
• Monday 3:40pm, S11 (David Sychrovský),
• Tuesday 2:00pm, S6 (Tomáš Čížek),
• Wednesday 9:00am, S6 (Martin Balko).

Information:	up

• 2/2, C+Ex, 5 E-Credits
• Annotation: An introduction to algorithmic game theory, a relatively new field whose objective is to study formal models of strategic environments and to design effective algorithms for them. This introductory course covers basic concepts and methods that are illustrated with several practical applications. To successfully pass the course, it is recommended to know basics from complexity theory.
• Exam:
  • The dates are in SIS. The exam is oral with written preparation, and the total time is 3 hours.
  • I will ask about two topics, one survey question and one with proofs. There can also be a simple problem to solve, if you have at least 85 points from the tutorials, then you do not need to solve this problem. The questions will be selected from the topics that we covered (see the list of lectures below). Everything is included in the lecture notes.
  • Example of the exam assignment: [PDF].
  • Do not forget to check the time of your exam the evening before the exam. Your term might be moved to an earlier time as people sign off.
• Literature:
  • Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors. Algorithmic game theory. Cambridge University Press, Cambridge, 2007.
  • Tim Roughgarden. Twenty lectures on algorithmic game theory. Cambridge University Press, Cambridge, 2016.
  • Kevin Leyton-Brown and Yoav Shoham. Essentials of game theory, volume 3 of Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, Williston, VT, 2008.
  • Jiří Matoušek and Bernd Gärtner. Understanding and Using Linear Programming. Springer-Verlag New York, Inc., 2006.
• Lecture notes: [PDF] (last update: 10.11.2025)
  • The lecture notes are still under construction. If you notice any mistake or place for improvement, please, let me know by e-mail.

Lectures:	up

• First lecture (30.9.2025):
  • Introduction, information about the course,
  • normal-form games, Nash equilibria (pure and mixed), examples of normal-form games,
  • Nash's theorem and preparation for its proof using Brouwer's fixed point theorem,
  • full presentation [PDF] and short presentation [PDF].
• Second lecture (7.10.2025):
  • Proof of Nash's theorem,
  • Pareto optimality,
  • the Minimax theorem and remarks,
  • full presentation [PDF] and short presentation [PDF].
• Third lecture (14.10.2025):
  • Recalling the Minimax theorem,
  • preliminaries from geometry and linear programming,
  • proof of the Minimax theorem based on the duality of linear programming,
  • best response condition,
  • brute-force algorithm to find all Nash equilibria,
  • full presentation [PDF] and short presentation [PDF].
• Fourth lecture (24.10.2025):
  • Best response polyhedra,
  • best response polytopes,
  • Lemke–Howson algorithm and a proof of its correctness,
  • full presentation [PDF] and short presentation [PDF].
• (28.10.2025):
  • The lecture is cancelled (Day of the Czechoslovak Republic).
• Fifth lecture (4.11.2025):
  • Complexity classes FNP and PPAD,
  • NASH being FNP-complete implies NP = coNP (without proof),
  • the END-OF-THE-LINE problem,
  • NASH is PPAD-complete (without proof),
  • epsilon-Nash equilibria,
  • quasi-polynomial time algorithm for finding epsilon-Nash equilibria (without proof),
  • correlated equilibria and their properties,
  • linear program for finding correlated equilibria,
  • full presentation [PDF] and short presentation [PDF].
• Sixth lecture (11.11.2025):
  • No-regret dynamics,
  • proof of the Minimax theorem using regret minimization,
  • coarse correlated equilibria,
  • convergence to coarse correlated equilibria with no-regret dynamics,
  • internal regret and swap regret,
  • full presentation [PDF] and short presentation [PDF].
• Seventh lecture (18.11.2025):
  • No-regret dynamics,
  • proof of the Minimax theorem using regret minimization,
  • coarse correlated equilibria,
  • convergence to coarse correlated equilibria with no-regret dynamics,
  • internal regret and swap regret,
  • full presentation [PDF] and short presentation [PDF].
• Eighth lecture (25.11.2025):
  • To be added.
  • full presentation [PDF] and short presentation [PDF].
• Ninth lecture (2.12.2025):
  • To be added.