Game Theory for AI
Instructor: Dietmar Berwanger
Lectures: Mondays, 16h15, 2 hours
Exercise sessions: Wednesdays, 8h30, 2 hours
Language: English
Synopsis
This course provides an introduction to game theory for computer science students. The emphasis is on fundamental models and solution concepts, together with their algorithmic aspects. Connections with artificial intelligence will be illustrated through adversarial search, learning in games, game solving, and reinforcement learning.
The course also provides game-theoretic prerequisites for the subsequent course on Mechanism Design.
Prerequisites
Familiarity with basic logic, discrete mathematics, and algebra will be useful.
Principal references
- Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory, MIT Press, 1994.
- Yoav Shoham and Kevin Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009.
- Krzysztof R. Apt and Erich Grädel (eds.), Lectures in Game Theory for Computer Scientists, Cambridge University Press, 2011.
- Nathanaël Fijalkow (ed.), Games on Graphs: From Logic and Automata to Algorithms, Cambridge University Press, 2026.
Tentative schedule
Week 1: Strategic and zero-sum games
Strategic games, best responses, dominance, mixed strategies, maxmin and minimax, matrix games, linear programming.
Reading: Shoham-Leyton-Brown, Sections 3.2.2 -- 3.2.4, 3.4.1.
Exercises 16/09/2029
Week 2: Nash equilibrium and incomplete information
Nash equilibrium, mixed equilibria, existence, Bayesian games, types and beliefs, Bayes-Nash equilibrium, dominant strategies, simple auction examples.
Reading: Osborne-Rubinstein, Chapters 2-3; Shoham-Leyton-Brown, Chapters 3 and 6.3.
Week 3: Repeated games and learning
Repeated play, fictitious play, regret, multiplicative weights, correlated equilibrium, no-regret learning and self-play.
Reading: Shoham-Leyton-Brown, Chapters 6.1 and 7; selected material from Cesa-Bianchi-Lugosi.
Week 4: Extensive-form games
Game trees, backward induction, subgame-perfect equilibrium, credible threats, forward induction; minimax search, alpha-beta pruning and MCTS.
Reading: Osborne-Rubinstein, Chapter 6; Shoham-Leyton-Brown, Chapter 5.
Week 5: Games with imperfect information
Information sets, mixed and behavioural strategies, perfect recall, Kuhn's theorem, equilibrium and regret-based game solving; CFR and poker as examples.
Reading: Osborne-Rubinstein, Chapters 11-12; Shoham-Leyton-Brown, Chapter 5.2.
Week 6: Games on graphs
Reachability and safety games, attractors and winning regions, Büchi and parity games, positional strategies; mean-payoff games if time permits.
Reading: Apt-Grädel, Chapters 2-3; Fijalkow, Chapters 1-4.
Week 7: Stochastic games and reinforcement learning
Markov decision processes, stochastic games, Bellman and Shapley equations, value iteration, stationary strategies; reinforcement learning and multi-agent RL.
Reading: Apt-Grädel, Chapter 5; Shoham-Leyton-Brown, Chapters 6.2 and 7.