{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T08:59:23Z","timestamp":1768467563830,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,2,6]],"date-time":"2013-02-06T00:00:00Z","timestamp":1360108800000},"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-9446-3","type":"journal-article","created":{"date-parts":[[2013,2,5]],"date-time":"2013-02-05T08:13:03Z","timestamp":1360051983000},"page":"479-490","source":"Crossref","is-referenced-by-count":7,"title":["Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)"],"prefix":"10.1007","volume":"54","author":[{"given":"Panagiota N.","family":"Panagopoulou","sequence":"first","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,2,6]]},"reference":[{"key":"9446_CR1","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0024-3795(94)90357-3","volume":"199","author":"I. Alth\u00f6fer","year":"1994","unstructured":"Alth\u00f6fer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra Appl. 199, 339\u2013355 (1994)","journal-title":"Linear Algebra Appl."},{"key":"9446_CR2","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/978-3-642-24829-0_18","volume-title":"Proceedings of the 4th International Symposium on Algorithmic Game Theory (SAGT 2011)","author":"P.N. Panagopoulou","year":"2011","unstructured":"Panagopoulou, P.N., Spirakis, P.G.: Random bimatrix games are asymptotically easy to solve (a simple proof). In: Proceedings of the 4th International Symposium on Algorithmic Game Theory (SAGT 2011), pp.\u00a0190\u2013199 (2011)"},{"key":"9446_CR3","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1109\/SFCS.2005.52","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905)","author":"I. B\u00e1r\u00e1ny","year":"2005","unstructured":"B\u00e1r\u00e1ny, I., Vempala, S., Vetta, A.: Nash equilibria in random games. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp.\u00a0123\u2013131 (2005)"},{"key":"9446_CR4","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906)","author":"X. Chen","year":"2005","unstructured":"Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906) (2005)"},{"key":"9446_CR5","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: approximation and smoothed complexity. In: Electronic Colloquium on Computational Complexity (ECCC) (2006)"},{"key":"9446_CR6","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","author":"C. Daskalakis","year":"2005","unstructured":"Daskalakis, C., Papadimitriou, C.: Three-player games are hard. In: Electronic Colloquium on Computational Complexity (ECCC) (2005)"},{"key":"9446_CR7","first-page":"71","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906)","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906), pp.\u00a071\u201378 (2006)"},{"key":"9446_CR8","first-page":"61","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906)","author":"P. Goldberg","year":"2006","unstructured":"Goldberg, P., Papadimitriou, C.: Reducibility among equilibrium problems. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906), pp.\u00a061\u201370 (2006)"},{"key":"9446_CR9","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"9446_CR10","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"C.E. Lemke","year":"1965","unstructured":"Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Manag. Sci. 11, 681\u2013689 (1965)","journal-title":"Manag. Sci."},{"key":"9446_CR11","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke","year":"1964","unstructured":"Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. J. Soc. Ind. Appl. Math. 12, 413\u2013423 (1964)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9446_CR12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/779928.779933","volume-title":"Proceedings of the 4th ACM Conference on Electronic Commerce (EC\u201903)","author":"R.J. Lipton","year":"2003","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC\u201903), pp.\u00a036\u201341 (2003)"},{"key":"9446_CR13","doi-asserted-by":"crossref","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Noncooperative games. Ann. Math. 54, 289\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"9446_CR14","volume-title":"Proceedings of the 4th Czechoslovakian Symposium on Combinatorics","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H.: On inefficient proofs of existence and complexity classes. In: Proceedings of the 4th Czechoslovakian Symposium on Combinatorics (1991)"},{"key":"9446_CR15","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1109\/FOCS.2004.28","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201904)","author":"R. Savani","year":"2004","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 (FOCS\u201904), pp.\u00a0258\u2013267 (2004)"},{"key":"9446_CR16","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/978-3-540-77105-0_8","volume-title":"Proceedings of the 3rd Workshop on Internet and Network Economics (WINE\u201907)","author":"H. Tsaknakis","year":"2007","unstructured":"Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. In: Proceedings of the 3rd Workshop on Internet and Network Economics (WINE\u201907), pp.\u00a042\u201356 (2007)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9446-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9446-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9446-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:24Z","timestamp":1558698864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9446-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,6]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9446"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9446-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,6]]}}}