Algorithmic Game Theory - Summer 26 - RWTH Aachen University

Logbook Algorithmic Game Theory - Summer 2026

Lecture 4 -- 22.04.2026:
Congestion games, Rosenthal's potential function, exact potential games, singleton congestion games, convergence time of improvement sequences in singleton congestion games.
Material and Literature:
- Slides Pure Nash Equilibria, pages 1-29.
- Monderer, Shapley. Potential Games. Games and Economic Behavior 14:1124-1143, 1996.
- Ieong, McGrew, Nudelman, Shoham, Sun. Fast and Compact: A Simple Class of Congestion Games. AAAI 2005.

Lecture 3 -- 20.04.2026:
Recap complexity of Nash equilibrium. 2-player zero-sum games, optimal strategies, value of the game (Minimax Theorem), linear programs and strong duality, efficient computation of mixed Nash equilibria
Material and Literature:
- Slides Strategic Games and Nash Equilibrium, pages 40-65.
- Owen. Game Theory, 2001. (Chapter 1+2).
- Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 1.4)
- von Neumann, Morgenstern. Theory of Games and Economic Behavior, 1944
- More on linear optimization, duality, and algorithms:
  Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 3rd edition. MIT Press, 2009. (Chapter 29)

Lecture 2 -- 15.04.2026:
Existence of mixed Nash equilibria (Nash theorem), proof with Brouwer's fixed point theorem, complexity class PPAD, END-OF-LINE problem, Nash is in PPAD, triangle coloring, Sperner's Lemma.
Material and Literature:
- Slides Strategic Games and Nash Equilibrium, pages 18-43.
- Slides for Sperner's Lemma
- Sperner's Lemma in German: Video from the 80s, general result on Wikipedia.
- Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 2)
- Nash. Non-cooperative Games. Annals of Math. 54:195-259, 1951.
In the lecture we only sketched the proof how to find mixed Nash equilibria by solving an END-OF-LINE problem, thereby showing that the problem is in in PPAD. Finding mixed Nash equilibria has also been shown to be PPAD-complete. Hence, by finding an approximate Nash equilibrium we can also solve END-OF-LINE or arbitrary Brouwer fixed point problems in polynomial time. This holds even for Nash equilibria in games with 2 players.
- Goldberg, Daskalakis, Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM J. Comput. 39(1):195-259, 2009.
- Chen, Deng, Teng. Settling the Complexity of Computing Two-Player Nash Equilibria. J. ACM 56(3), 2009.

Lecture 1 -- 13.04.2026:
Basic concepts of game theory, strategic games, dominant strategies, dominant strategy equilibrium, best response strategy, pure Nash equilibrium, mixed strategy, mixed best response, mixed Nash equilibrium.

The material is standard and can be found in every book on game theory.
Material and Literature:
- Slides Strategic Games and Nash Equilibrium, pages 1-17.
- Owen. Game Theory, 2001. (Chapter 1)
- Nisan, Roughgarden, Tardos, Vazirani. Algorithmic Game Theory, 2007. (Chapter 1)