The computational complexity of Nash equilibria and Fixed Points of Algebraic Functions
Lecturer:
Prof. Kousha Etessami (University of Edinburgh, Scotland, UK).
About the lecturer | Course Summary | Slides | Exercises
About the lecturer:
Kousha Etessami is a Reader in the Laboratory for Foundations of Computer
Science in the School of Informatics at the University of Edinburgh, which
he joined in 2002. From 1997 to 2002, he was a member of the research staff
at Bell Laboratories in the Computing Principles Research Department, in
Murray Hill, NJ. He received a Ph.D. in computer science at the University
of Massachusetts at Amherst in 1995, and held postdoctoral fellowships at
the DIMACS (1995-6) and BRICS (1996-7) institutes.
His recent research interests include: algorithmic game theory, analysis of probabilistic systems, stochastic games, automated verification of reactive systems, logic and automata theory, algorithms and computational complexity theory.
Course summary:
A variety of fundamental computational problems in many fields
(economics, game theory, probability, etc.) can be formulated as a
problem of finding a fixed point x = F(x) for an algebraically
specified function, F: R^n --> R^n.
Such problems include finding a Nash Equilibrium in finite games, finding economic/market equilibria, finding the game value in Shapley's stochastic games, finding extinction probabilities in (multi-type) branching processes, and many others.
These lectures address the computational complexity of such problems. We will begin by closely examining what it means to compute a fixed point in settings where F(x) may be an algebraically defined function with no rational fixed points.
An outline of the lectures follows:
- We recall basic definitions related to games and fixed points: Nash equilibria, epsilon-Nash equilibria, Brouwer fixed points, etc.
- We discuss two distinct notions of approximation for fixed points: weak vs. strong approximation.
- We recall Scarf's classic algorithm for approxmating a fixed point, and we discuss its complexity implications.
- This leads us to the complexity class PPAD, defined by Papadimitriou. We discuss its connections to weak approximation, and the PPAD-completeness results for 2-player Nash equiliria, and for \epsilon-Nash Equilibria in games with at least 3 players.
- We then discuss hardness results for strong approximation with respect two important open problems in numerical computation: (1) the square-root-sum problem & (2) a fundamental arithmetic circuit decision problem.
- We show that any non-trivial approximation of an actual (exact) Nash equilibrium in a finite normal form game with 3 or more players is at least as hard as these two problems.
- This leads us to the definition of a new complexity class, FIXP, which captures the complexity of fixed points for functions specified by algebraic circuits over basic {+,*,max} with rational coefficients.
- We show that computing an actual Nash equilibrium for games with at least 3 players is FIXP-complete in several senses.
- We show that the class PPAD corresponds precisely to a piecewise-linear fragment of FIXP, or equivalently to finding a fixed point for functions specified for algebraic circuits over basis {+,max} with multiplication by rational constants.
- We discuss the complexity of other FIXP
problems:
- market price equilibria,
- simple stochastic games and Shapley's stochastic games
- multi-type branching processes
- We conclude with a discussion of the many open problems and future challenges.
Exercises, updated on July 7 (c.f. previous version).
Please send the solutions to professor Etessami (kousha AT staffmail DOT ed DOT ac DOT uk) till July, 15.
If you have a solution for problem 6, please send it simultaneously to niwinski AT mimuw AT edu AT pl.