An Introduction to the Complexity Class of Pure Nash Equilibrium

• Victor Hugo Wirz UNIRIO
• Pedro Nuno Moura UNIRIO

DOI: https://doi.org/10.5753/etc.2023.229527

Resumo

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.

Referências

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.