{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:59:16Z","timestamp":1743109156818,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":18,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_30","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:37:51Z","timestamp":1214505471000},"page":"53-57","source":"Crossref","is-referenced-by-count":0,"title":["Approximations of Bimatrix Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Spyros","family":"Kontogiannis","sequence":"first","affiliation":[]},{"given":"Panagiota","family":"Panagopoulou","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1_30","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 Algebr. Appl. 199, 339\u2013355 (1994)","journal-title":"Linear Algebr. Appl."},{"key":"30_CR2_30","unstructured":"Bosse, H., Byrka, J., Markakis, E.: New Algorithms for Approximate Nash Equilibria in Bimatrix Games. In: LNCS Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), San Diego, 12\u201314\u00a0December 2007"},{"key":"30_CR3_30","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'06). Berkeley, 21\u201324\u00a0October 2005","DOI":"10.1109\/FOCS.2006.69"},{"key":"30_CR4_30","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: Approximation and smoothed complexity. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), Berkeley, 21\u201324\u00a0October 2006","DOI":"10.1109\/FOCS.2006.20"},{"key":"30_CR5_30","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a\u00a0Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), pp. 71\u201378. Seattle, 21\u201323\u00a0May 2006","DOI":"10.1145\/1132516.1132527"},{"key":"30_CR6_30","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.: A\u00a0note on approximate Nash equilibria. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE'06), pp. 297\u2013306. Patras, 15\u201317\u00a0December 2006","DOI":"10.1007\/11944874_27"},{"key":"30_CR7_30","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C: Progress in approximate Nash equilibrium. In: Proceedings of the 8th ACM Conference on Electronic Commerce (EC07), San Diego, 11\u201315\u00a0June 2007","DOI":"10.1145\/1250910.1250962"},{"key":"30_CR8_30","unstructured":"Daskalakis, C., Papadimitriou, C.: Three-player games are hard. In: Electronic Colloquium on Computational Complexity (ECCC) (2005)"},{"key":"30_CR9_30","unstructured":"Kannan, R., Theobald, T.: Games of fixed rank: A\u00a0hierarchy of bimatrix games. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7\u20139 January 2007"},{"key":"30_CR10_30","doi-asserted-by":"crossref","unstructured":"Kontogiannis, S., Panagopoulou, P.N., Spirakis, P.G.: Polynomial algorithms for approximating Nash equilibria of bimatrix games. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE'06), pp. 286\u2013296. Patras, 15\u201317\u00a0December 2006","DOI":"10.1007\/11944874_26"},{"key":"30_CR11_30","unstructured":"Kontogiannis, S., Spirakis, P.G.: Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A: Algorithms and Complexity), Wroclaw, 9\u201313\u00a0July 2007"},{"key":"30_CR12_30","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.\u00a0Soc. Indust. Appl. Math. 12, 413\u2013423 (1964)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"30_CR13_30","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'03), pp. 36\u201341. San Diego, 9\u201313\u00a0June 2003","DOI":"10.1145\/779928.779933"},{"key":"30_CR14_30","doi-asserted-by":"publisher","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":"30_CR15_30","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 1990, Prachatice (1991)","DOI":"10.1016\/S0167-5060(08)70637-X"},{"key":"30_CR16_30","doi-asserted-by":"crossref","unstructured":"Savani, R., von Stengel, B.: Exponentially many steps for finding a\u00a0nash equilibrium in a\u00a0bimatrix game. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 258\u2013267. Rome, 17\u201319\u00a0October 2004","DOI":"10.1109\/FOCS.2004.28"},{"key":"30_CR17_30","unstructured":"Tsaknakis, H., Spirakis, P.: An Optimization Approach for Approximate Nash Equilibria. In: LNCS Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), also in the Electronic Colloquium on Computational Complexity, (ECCC), TR07-067 (Revision), San Diego, 12\u201314\u00a0December 2007"},{"key":"30_CR18_30","volume-title":"Theory of Games and Economic Behavior","author":"J. von Neumann","year":"1944","unstructured":"von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ (1944)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T21:32:57Z","timestamp":1738272777000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_30"}},"subtitle":["2003; Lipton, Markakis, Mehta 2006; Daskalaskis, Mehta, Papadimitriou 2006; Kontogiannis, Panagopoulou, Spirakis"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_30","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}