The Complexity of Pure Nash Equilibria

  • Alex Fabrikant ,
  • Christos Papadimitriou ,
  • Kunal Talwar

STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing |

Published by Association for Computing Machinery, Inc.

We investigate from the computational viewpoint multi-player games that are guaranteed to have pure Nash equilibria. We focus on congestion games, and show that a pure Nash equilibrium can be computed in polynomial time in the symmetric network case, while the problem is PLS-complete in general. We discuss implications to non-atomic congestion games, and we explore the scope of the potential function method for proving existence of pure Nash equilibria.