ALFRED GALICHON'S
MASTERCLASSES
Bernhard von Stengel's invited masterclass
on Equilibrium Computation for Non-Cooperative Games
Paris, December 18-19, 2024
These lectures are about the computation of equilibria in non-cooperative games, with an emphasis on Nash equilibria for two-player games, and some considerations beyond that (correlated equilibrium, small games with more than two players).
Pre-requisites: Familiarity with the concepts of games in strategic and extensive form,
mixed strategies, and Nash equilibrium.
About the lecturer: Professor Bernhard von Stengel is the Head of Department and a Professor of Mathematics at the London School of Economics, which he joined in 1998 after postdoctoral positions at Berkeley and ETH Zurich. He holds a PhD in Mathematics from Passau, and a Habilitation in Computer Science from Munich. His main research is on mathematical and computational questions of game theory, in particular the structure and computation of equilibria in games. Among his contributions, his "sequence form" for solving imperfect-information games such as poker allows to find optimal play in game trees with millions (previously hundreds) of decision points. Professor von Stengel is a Council member and Fellow of the Game Theory Society, a former Area Editor for Game Theory for the journal Mathematics of Operations Research, and co-editor of the International Journal of Game Theory. He has been an organiser and scientific chairman of ten international conferences and workshops on game theory, including the World Congress of the Game Theory Society in 2016.
Practical information
• The course will be taught in person in Paris over two consecutive days, December 18 and 19, 2024, 10am- 1230pm and 230pm-5pm Paris time. Address will be communicated to registered participants.
• Participation is free and open to all, but registration is required by emailing math.econ.code@gmail.com.
Course outline
Part 1
Bimatrix games (two-player games in strategic form)
• Mixed strategies
• Best-response condition (only pure best responses can be played with positive
probability)
• Convex combinations
Zero-sum games
• Short proof of the minimax theorem by Loomis
• Zero-sum games and linear programming duality
• Brief recall of the simplex algorithm
Part 2
Geometry of Nash equilibria in bimatrix games (several lectures)
• Upper envelope of expected payoffs
• Best-response polyhedra and polytopes
• The Lemke-Howson algorithm
• Nondegeneracy
• Oddness of Nash equilibria in nondegenerate games
• Complementary pivoting
• Lexicographic degeneracy resolution
• Integer Pivoting
• The Harsanyi-Selten tracing procedure via Lemke’s algorithm
• Finding all Nash equilibria via vertex enumeration
Part 3
The equilibrium index
• Definition of the index via determinants
• Endpoints of Lemke-Howson paths have opposite index
Advanced use of best-response polytopes
• Maximal numbers of Nash equilibria in bimatrix games
• Exponentially long Lemke-Howson Paths via cyclic polytopes
Part 4
Extensive games
Games in extensive form, information sets
The sequence form
• Reduced strategies in extensive games
• Exponential size of the reduced strategic form
• Sequences instead of strategies: same (instead of exponential) size as the game tree
• Kuhn’s theorem for games with perfect recall: behavior strategies suffice
• Finding optimal strategies in a zero-sum extensive game with perfect recall via a linear
program of the same size
• Non-zero-sum extensive game: Linear Complementarity Problem
• Applying the Harsanyi-Selten tracing procedure and Lemke's algorithm to the sequence form
Part 5
Correlated equilibria
Definition of correlated equilibrium (CE), coarse correlated equilibrium
• Existence proof of CE via zero-sum games (Hart and Schmeidler 1990)
Challenge: CE for extensive games
• New definition: Extensive-Form Correlated Equilibrium
• Computational hardness results
Part 6 (time permitting)
Games with more than two players
Challenge: Polynomial equations and inequalities
Bounds for equilibrium numbers in binary-action games