{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:01Z","timestamp":1759638001939},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,12,12]],"date-time":"2013-12-12T00:00:00Z","timestamp":1386806400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00224-013-9523-7","type":"journal-article","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T06:10:46Z","timestamp":1386742246000},"page":"491-527","source":"Crossref","is-referenced-by-count":10,"title":["Complexity of Rational and Irrational Nash Equilibria"],"prefix":"10.1007","volume":"54","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,12,12]]},"reference":[{"key":"9523_CR1","first-page":"113","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Sciences","author":"T. Abbott","year":"2005","unstructured":"Abbott, T., Kane, D., Valiant, P.: On the complexity of two-player win-lose games. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Sciences, pp.\u00a0113\u2013122 (2005)"},{"issue":"1","key":"9523_CR2","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.geb.2009.04.016","volume":"70","author":"C. Borgs","year":"2010","unstructured":"Borgs, C., Chayes, J., Immorlica, N., Tauman Kalai, A., Mirrokni, V., Papadimitriou, C.H.: The myth of the Folk theorem. Games Econ. Behav. 70(1), 34\u201343 (2010)","journal-title":"Games Econ. Behav."},{"key":"9523_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J.\u00a0ACM 56(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"issue":"3","key":"9523_CR4","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.ipl.2005.01.010","volume":"94","author":"B. Codenotti","year":"2005","unstructured":"Codenotti, B., Stefanovic, D.: On the computational complexity of Nash equilibria for (0,1) bimatrix games. Inf. Process. Lett. 94(3), 145\u2013150 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9523_CR5","first-page":"765","volume-title":"Proceedings of the 18th Joint Conference on Artificial Intelligence","author":"V. Conitzer","year":"2003","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: Proceedings of the 18th Joint Conference on Artificial Intelligence, pp.\u00a0765\u2013771 (2003)"},{"issue":"2","key":"9523_CR6","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.geb.2008.02.015","volume":"63","author":"V. Conitzer","year":"2008","unstructured":"Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games Econ. Behav. 63(2), 621\u2013641 (2008)","journal-title":"Games Econ. Behav."},{"key":"9523_CR7","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/800157.805047","volume-title":"Proceeding of the 3rd Annual ACM Symposium on Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceeding of the 3rd Annual ACM Symposium on Theory of Computing, pp.\u00a0151\u2013158 (1971)"},{"issue":"1","key":"9523_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9523_CR9","doi-asserted-by":"crossref","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K. Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"key":"9523_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-16170-4_1","volume-title":"Proceedings of the 3rd International Symposium on Algorithmic Game Theory","author":"A. Fiat","year":"2010","unstructured":"Fiat, A., Papadimitriou, C.H.: When players are not expectation maximizers. In: Proceedings of the 3rd International Symposium on Algorithmic Game Theory. Lecture Notes in Computer Science, vol.\u00a06386, pp.\u00a01\u201314. Springer, Berlin (2010)"},{"key":"9523_CR11","first-page":"10","volume-title":"Proceedings of the 8th Annual ACM Symposium on Theory of Computing","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some $\\mathcal{NP}$ -complete geometric problems. In: Proceedings of the 8th Annual ACM Symposium on Theory of Computing, pp.\u00a010\u201322 (1976)"},{"key":"9523_CR12","volume-title":"Computers and Intractability\u2014A Guide to the Theory of $\\mathcal{NP}$ -Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability\u2014A Guide to the Theory of $\\mathcal{NP}$ -Completeness. Freeman, New York (1979)"},{"issue":"1","key":"9523_CR13","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I. Gilboa","year":"1989","unstructured":"Gilboa, I., Zemel, E.: Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. 1(1), 80\u201393 (1989)","journal-title":"Games Econ. Behav."},{"key":"9523_CR14","unstructured":"Koutsoupias, E.: Personal communication during the 2nd International Symposium on Algorithmic Game Theory, Paphos, Cyprus, October 2009"},{"key":"9523_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/978-3-540-77105-0_51","volume-title":"Proceedings of the 3rd International Workshop on Internet and Network Economics","author":"M. Mavronicolas","year":"2007","unstructured":"Mavronicolas, M., Monien, B., Wagner, K.K.: Weighted Boolean formula games. In: Proceedings of the 3rd International Workshop on Internet and Network Economics. Lecture Notes in Computer Science, vol.\u00a04858, pp.\u00a0469\u2013481. Springer, Berlin (2007)"},{"issue":"2","key":"9523_CR16","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1016\/j.geb.2009.10.003","volume":"68","author":"A. McLennan","year":"2010","unstructured":"McLennan, A., Tourky, R.: Simple complexity from imitation games. Games Econ. Behav. 68(2), 683\u2013688 (2010)","journal-title":"Games Econ. Behav."},{"key":"9523_CR17","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J.F. Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium points in n-person games. Proc. Natl. Acad. Sci. USA 36, 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"2","key":"9523_CR18","doi-asserted-by":"crossref","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"issue":"3","key":"9523_CR19","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9523-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9523-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9523-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:26Z","timestamp":1558698866000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9523-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,12]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9523"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9523-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,12]]}}}