An Introduction to the Complexity Class of Pure Nash Equilibrium
ResumoTaxonomy 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.
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.