## 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.
Slides
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.