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:

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.