{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:23:26Z","timestamp":1747196606375,"version":"3.40.5"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319124353"},{"type":"electronic","value":"9783319124360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12436-0_11","type":"book-chapter","created":{"date-parts":[[2014,11,21]],"date-time":"2014-11-21T13:16:45Z","timestamp":1416575805000},"page":"90-99","source":"Crossref","is-referenced-by-count":0,"title":["Towards the Computation of a Nash Equilibrium"],"prefix":"10.1007","author":[{"given":"Yu","family":"Lu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,19]]},"reference":[{"issue":"2","key":"11_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"52","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The Complexity of Computing a Nash Equilibrium. Communications of the ACM 52(2), 89\u201397 (2009)","journal-title":"Communications of the ACM"},{"issue":"2","key":"11_CR2","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"2","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-Cooperative Games. Annals of Mathematics 2(2), 286\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1145\/322186.322201","volume":"27","author":"D Lichtenstein","year":"1980","unstructured":"Lichtenstein, D., Sipser, M.: GO Is Polynomial-Space Hard. Journal of the ACM 27(2), 393\u2013401 (1980)","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time (Preliminary Report). In: 5th Annual ACM Symposium on Theory of Computing, pp. 1\u20139. ACM (1973)","key":"11_CR4","DOI":"10.1145\/800125.804029"},{"issue":"2","key":"11_CR5","doi-asserted-by":"publisher","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 and Economic Behavior 63(2), 621\u2013641 (2008)","journal-title":"Games and Economic Behavior"},{"doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: Algorithms, games, and the internet. In: 33rd Annual ACM Symposium on Theory of Computing, pp. 749\u2013753 (2001)","key":"11_CR6","DOI":"10.1145\/380752.380883"},{"unstructured":"Luce, R.D., Raiffa, H.: Games and Decisions: Introduction and Critical Survey. Dover Publications (1989)","key":"11_CR7"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s001820100066","volume":"30","author":"F Chu","year":"2001","unstructured":"Chu, F., Halpern, J.: On the NP-completeness of finding an optimal strategy in games with common payoffs. International J. of Game Theory 30(1), 99\u2013106 (2001)","journal-title":"International J. of Game Theory"},{"issue":"1","key":"11_CR9","doi-asserted-by":"publisher","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 and Economic Behavior 1(1), 80\u201393 (1989)","journal-title":"Games and Economic Behavior"},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0899-8256(90)90010-R","volume":"2","author":"E Ben-porath","year":"1990","unstructured":"Ben-porath, E.: The complexity of computing a best response automaton in repeated games with mixed strategies. Games and Eco. Behavior 2(1), 1\u201312 (1990)","journal-title":"Games and Eco. Behavior"},{"issue":"4","key":"11_CR11","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/0899-8256(92)90035-Q","volume":"4","author":"D Koller","year":"1992","unstructured":"Koller, D., Megiddo, N.: The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior 4(4), 528\u2013552 (1992)","journal-title":"Games and Economic Behavior"},{"issue":"1","key":"11_CR12","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.dss.2004.08.007","volume":"39","author":"ML Littman","year":"2005","unstructured":"Littman, M.L., Stone, P.: A polynomial-time nash equilibrium algorithm for repeated games. Decision Support Systems 39(1), 55\u201366 (2005)","journal-title":"Decision Support Systems"},{"doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On complexity as bounded rationality. In: 26th Annual ACM Symposium on Theory of Computing, pp. 726\u2013733 (1994)","key":"11_CR13","DOI":"10.1145\/195058.195445"},{"issue":"1","key":"11_CR14","first-page":"103","volume":"8","author":"JH Nachbar","year":"1996","unstructured":"Nachbar, J.H., Zame, W.R.: Non-computable strategies and discounted repeated games. Economic Theory 8(1), 103\u2013122 (1996)","journal-title":"Economic Theory"},{"unstructured":"Chen, X., Deng, X.: 3-Nash is PPAD-complete. In: Electronic Colloquium on Computational Complexity (2005)","key":"11_CR15"},{"unstructured":"Daskalakis, C., Papadimitriou, C.H.: Three-Player Games Are Hard. In: Electronic Colloquium on Computational Complexity (2005)","key":"11_CR16"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the Complexity of Two-Player Nash Equilibrium. In: Electronic Colloquium on Computational Complexity (2006)","key":"11_CR17","DOI":"10.1109\/FOCS.2006.69"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56(3) (2009)","key":"11_CR18","DOI":"10.1145\/1516512.1516516"},{"doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Papadimitriou, C.H.: Reducibility Among Equilibrium Problems. In: 38th Annual ACM Symposium on Theory of Computing, pp. 61\u201370 (2006)","key":"11_CR19","DOI":"10.1145\/1132516.1132526"},{"issue":"2","key":"11_CR20","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"CE Lemke","year":"1964","unstructured":"Lemke, C.E., Howson, J.T.: Equilibrium Points of Bimatrix Games. Journal of the Society for Industrial and Applied Mathematics 12(2), 413\u2013423 (1964)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Stengel, B.V.: 45. In: Computing Equilibria for Two-Person Games, vol. 3, pp. 1723\u20131759. Springer (2002)","key":"11_CR21","DOI":"10.1016\/S1574-0005(02)03008-4"},{"doi-asserted-by":"crossref","unstructured":"Savani, R., von Stengel, B.: Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 258\u2013267 (2004)","key":"11_CR22","DOI":"10.1109\/FOCS.2004.28"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/11786986_45","volume-title":"Automata, Languages and Programming","author":"C Daskalakis","year":"2006","unstructured":"Daskalakis, C., Fabrikant, A., Papadimitriou, C.H.: The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 513\u2013524. Springer, Heidelberg (2006)"},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-642-02927-1_2","volume-title":"Automata, Languages and Programming","author":"CH Papadimitriou","year":"2009","unstructured":"Papadimitriou, C.H.: Algorithmic Game Theory: A Snapshot. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 3\u201311. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Daskalakis, C.: On the Complexity of Approximating a Nash Equilibrium. ACM Transactions on Algorithms 9(3) (2013)","key":"11_CR25","DOI":"10.1145\/2483699.2483703"},{"doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: 4th ACM Conference on Electronic Commerce, pp. 36\u201341 (2003)","key":"11_CR26","DOI":"10.1145\/779928.779933"},{"doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS\u2019s for Nash equilibrium. In: 41st Annual ACM Symposium on Theory of Computing, pp. 75\u201384. ACM (2009)","key":"11_CR27","DOI":"10.1145\/1536414.1536427"},{"issue":"1\u20132","key":"11_CR28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0004-3702(97)00023-4","volume":"94","author":"D Koller","year":"1997","unstructured":"Koller, D., Pfeffer, A.: Representations and solutions for game-theoretic problems. Artificial Intelligence 94(1\u20132), 167\u2013215 (1997)","journal-title":"Artificial Intelligence"},{"doi-asserted-by":"crossref","unstructured":"Shoham, Y., Leyton-Brown, K.: Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press (2008)","key":"11_CR29","DOI":"10.1017\/CBO9780511811654"},{"issue":"1","key":"11_CR30","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00199-009-0448-y","volume":"42","author":"T Roughgarden","year":"2010","unstructured":"Roughgarden, T.: Computing equilibria: a computational complexity perspective. Economic Theory 42(1), 193\u2013236 (2010)","journal-title":"Economic Theory"},{"unstructured":"Papadimitriou, C.H.: Algorithmic Game Theory. Cambridge Uni. Press (2007)","key":"11_CR31"},{"unstructured":"Daskalakis, C.: The Complexity of Nash Equilibria. PhD thesis, University of California, Berkeley (2004)","key":"11_CR32"}],"container-title":["Lecture Notes in Computer Science","Advances in Neural Networks \u2013 ISNN 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12436-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T20:11:49Z","timestamp":1747167109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-12436-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319124353","9783319124360"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12436-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}