{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:30Z","timestamp":1792111470917,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":20,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_30","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:52Z","timestamp":1461269032000},"page":"137-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximations of Bimatrix Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Paul Pavlos","family":"Spirakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul Pavlos","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul Pavlos","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"30_CR1532","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 (1994) On sparse approximations to randomized strategies and convex combinations. Linear Algebr Appl 199:339\u2013355","journal-title":"Linear Algebr Appl"},{"key":"30_CR1533","unstructured":"Bosse H, Byrka J, Markakis E (2007) New algorithms for approximate Nash equilibria in bimatrix games. In: Proceedings of the 3rd international workshop on internet and network economics (WINE 2007), San Diego, 12\u201314 Dec 2007. Lecture notes in computer science"},{"key":"30_CR1534","doi-asserted-by":"crossref","unstructured":"Chen X, Deng X (2005) Settling the complexity of 2-player Nash-equilibrium. In: Proceedings of the 47th annual IEEE symposium on foundations of computer science (FOCS\u201906), Berkeley, 21\u201324 Oct 2005","DOI":"10.1109\/FOCS.2006.69"},{"key":"30_CR1535","doi-asserted-by":"crossref","unstructured":"Chen X, Deng X, Teng S-H (2006) Computing Nash equilibria: approximation and smoothed complexity. In: Proceedings of the 47th annual IEEE symposium on foundations of computer science (FOCS\u201906), Berkeley, 21\u201324 Oct 2006","DOI":"10.1109\/FOCS.2006.20"},{"key":"30_CR1536","doi-asserted-by":"crossref","unstructured":"Daskalakis C, Goldberg P, Papadimitriou C (2006) The complexity of computing a Nash equilibrium. In: Proceedings of the 38th annual ACM symposium on theory of computing (STOC\u201906), Seattle, 21\u201323 May 2006, pp\u00a071\u201378","DOI":"10.1145\/1132516.1132527"},{"key":"30_CR1537","doi-asserted-by":"crossref","unstructured":"Daskalakis C, Mehta A, Papadimitriou C (2006) A note on approximate Nash equilibria. In: Proceedings of the 2nd workshop on internet and network economics (WINE\u201906), Patras, 15\u201317 Dec 2006, pp\u00a0297\u2013306","DOI":"10.1007\/11944874_27"},{"key":"30_CR1538","doi-asserted-by":"crossref","unstructured":"Daskalakis C, Mehta A, Papadimitriou C (2007) Progress in approximate Nash equilibrium. In: Proceedings of the 8th ACM conference on electronic commerce (EC07), San Diego, 11\u201315 June 2007","DOI":"10.1145\/1250910.1250962"},{"key":"30_CR1539","unstructured":"Daskalakis C, Papadimitriou C (2005) Three-player games are hard. In: Electronic colloquium on computational complexity (ECCC TR 05-139)"},{"key":"30_CR1540","doi-asserted-by":"crossref","unstructured":"Fearnley J, Goldberg PW, Savani R, Bjerre S\u00f8rensen T (2012) Approximate well-supported Nash equilibria below two-thirds. In: SAGT 2012, Barcelona, pp\u00a0108\u2013119","DOI":"10.1007\/978-3-642-33996-7_10"},{"key":"30_CR1541","unstructured":"Kannan R, Theobald T (2007) Games of fixed rank: a hierarchy of bimatrix games. In: Proceedings of the ACM-SIAM symposium on discrete algorithms, New Orleans, 7\u20139 Jan 2007"},{"key":"30_CR1542","doi-asserted-by":"crossref","unstructured":"Kontogiannis S, Panagopoulou PN, Spirakis PG (2006) Polynomial algorithms for approximating Nash equilibria of bimatrix games. In: Proceedings of the 2nd workshop on internet and network economics (WINE\u201906), Patras, 15\u201317 Dec 2006, pp\u00a0286\u2013296","DOI":"10.1007\/11944874_26"},{"issue":"4","key":"30_CR1543","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00453-008-9227-6","volume":"57","author":"S Kontogiannis","year":"2010","unstructured":"Kontogiannis S, Spirakis PG (2010) Well supported approximate equilibria in bimatrix games. Algorithmica 57(4):653\u2013667","journal-title":"Algorithmica"},{"key":"30_CR1544","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"CE Lemke","year":"1964","unstructured":"Lemke CE, Howson JT (1964) Equilibrium points of bimatrix games. J Soc Indust Appl Math 12:413\u2013423","journal-title":"J Soc Indust Appl Math"},{"key":"30_CR1545","doi-asserted-by":"crossref","unstructured":"Lipton RJ, Markakis E, Mehta A (2003) Playing large games using simple startegies. In: Proceedings of the 4th ACM conference on electronic commerce (EC\u201903), San Diego, 9\u201313 June 2003, pp\u00a036\u201341","DOI":"10.1145\/779928.779933"},{"key":"30_CR1546","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J Nash","year":"1951","unstructured":"Nash J (1951) Noncooperative games. Ann Math 54:289\u2013295","journal-title":"Ann Math"},{"key":"30_CR1547","volume-title":"Theory of games and economic behavior","author":"J von Neumann","year":"1944","unstructured":"von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton"},{"key":"30_CR1548","doi-asserted-by":"crossref","unstructured":"Papadimitriou CH (1991) On inefficient proofs of existence and complexity classes. In: Proceedings of the 4th Czechoslovakian symposium on combinatorics 1990, Prachatice","DOI":"10.1016\/S0167-5060(08)70637-X"},{"key":"30_CR1549","doi-asserted-by":"crossref","unstructured":"Savani R, von Stengel B (2004) 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), Rome, 17\u201319 Oct 2004, pp\u00a0258\u2013267","DOI":"10.1109\/FOCS.2004.28"},{"key":"30_CR1550","unstructured":"Tsaknakis H, Spirakis P (2007) An optimization approach for approximate Nash equilibria. In: Proceedings of the 3rd international workshop on internet and network economics (WINE 2007). Lecture notes in computer science. Also in J Internet Math 5(4):365\u2013382 (2008)"},{"key":"30_CR1551","doi-asserted-by":"crossref","unstructured":"Tsaknakis H, Spirakis PG (2010) Practical and efficient approximations of Nash equilibria for win-lose games based on graph spectra. In: WINE 2010, Stanford, pp\u00a0378\u2013390","DOI":"10.1007\/978-3-642-17572-5_31"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:51:08Z","timestamp":1792108268000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_30","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}