An Introduction to the Complexity Class of Pure Nash Equilibrium

  • Victor Hugo Wirz UNIRIO
  • Pedro Nuno Moura UNIRIO


Taxonomy of problems in Computer Science has been typically done with formulations as decision problems. This approach is inadequate for many search problems of interest when the structure of the instance in itself guarantees the existence of a positive certificate. In this paper, we provide an introduction to the class of problems PLS and its connections with finding Pure Nash Equilibrium in Congestion Games.


Fabrikant, A., Papadimitriou, C., and Talwar, K. (2004). The complexity of pure nash equilibria. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pages 604–612, New York, NY, USA. Association for Computing Machinery.

Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.

Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V. V., editors (2007). Algorithmic Game Theory. Cambridge University Press, USA.

Papadimitriou, C. H. and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.

Rosenthal, R. W. (1973). A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2(1):65–67.

Schäffer, A. A. and Yannakakis, M. (1991). Simple local search problems that are hard to solve. SIAM J. Comput., 20(1):56–87.

Turocy, T. L. and von Stengel, B. (2003). Game theory. In Bidgoli, H., editor, Encyclopedia of Information Systems, pages 403–420. Elsevier, New York.
Como Citar

Selecione um Formato
WIRZ, Victor Hugo; MOURA, Pedro Nuno. An Introduction to the Complexity Class of Pure Nash Equilibrium. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 104-108. ISSN 2595-6116. DOI: