{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T04:16:33Z","timestamp":1741839393903,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642248283"},{"type":"electronic","value":"9783642248290"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24829-0_18","type":"book-chapter","created":{"date-parts":[[2011,10,3]],"date-time":"2011-10-03T13:11:38Z","timestamp":1317647498000},"page":"190-199","source":"Crossref","is-referenced-by-count":1,"title":["Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)"],"prefix":"10.1007","author":[{"given":"Panagiota N.","family":"Panagopoulou","sequence":"first","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","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 and Applications\u00a0199, 339\u2013355 (1994)","journal-title":"Linear Algebra and Applications"},{"key":"18_CR2","doi-asserted-by":"crossref","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 2005), pp. 123\u2013131 (2005)","DOI":"10.1109\/SFCS.2005.52"},{"key":"18_CR3","doi-asserted-by":"crossref","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 2006 (2005)","DOI":"10.1109\/FOCS.2006.69"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: Approximation and smoothed complexity. In: Electronic Colloquium on Computational Complexity, ECCC (2006)","DOI":"10.1109\/FOCS.2006.20"},{"key":"18_CR5","doi-asserted-by":"crossref","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 2006), pp. 71\u201378 (2006)","DOI":"10.1145\/1132516.1132527"},{"key":"18_CR6","unstructured":"Daskalakis, C., Papadimitriou, C.: Three-player games are hard. In: Electronic Colloquium on Computational Complexity, ECCC (2005)"},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Goldberg, P., Papadimitriou, C.: Reducibility among equilibrium problems. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006), pp. 61\u201370 (2006)","DOI":"10.1145\/1132516.1132526"},{"key":"18_CR8","doi-asserted-by":"publisher","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. Journal of the American Statistical Association\u00a058, 13\u201330 (1963)","journal-title":"Journal of the American Statistical Association"},{"key":"18_CR9","doi-asserted-by":"publisher","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. Management Science\u00a011, 681\u2013689 (1965)","journal-title":"Management Science"},{"key":"18_CR10","doi-asserted-by":"publisher","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. Indust. Appl. Math.\u00a012, 413\u2013423 (1964)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple startegies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC 2003), pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Noncooperative games. Annals of Mathematics\u00a054, 289\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On inefficient proofs of existence and complexity classes. In: Proceedings of the 4th Czechoslovakian Symposium on Combinatorics (1991)","DOI":"10.1016\/S0167-5060(08)70637-X"},{"key":"18_CR14","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 (FOCS 2004), pp. 258\u2013267 (2004)","DOI":"10.1109\/FOCS.2004.28"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-540-77105-0_8","volume-title":"Internet and Network Economics","author":"H. Tsaknakis","year":"2007","unstructured":"Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 42\u201356. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24829-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,12]],"date-time":"2025-03-12T11:09:35Z","timestamp":1741777775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24829-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642248283","9783642248290"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24829-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}