{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T13:41:48Z","timestamp":1742996508022,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":11,"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_258","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:34:22Z","timestamp":1214505262000},"page":"578-579","source":"Crossref","is-referenced-by-count":0,"title":["Non-approximability of Bimatrix Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"258_CR1_258","unstructured":"Chen, X., Deng, X.: 3-Nash is PPAD-complete. ECCC, TR05-134 (2005)"},{"key":"258_CR2_258","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: FOCS'06: Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 261\u2013272","DOI":"10.1109\/FOCS.2006.69"},{"key":"258_CR3_258","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.H.: Computing Nash equilibria: approximation and smoothed complexity. In: FOCS'06: Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp. 603\u2013612","DOI":"10.1109\/FOCS.2006.20"},{"key":"258_CR4_258","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a\u00a0Nash equilibrium. In: STOC'06: Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp. 71\u201378","DOI":"10.1145\/1132516.1132527"},{"key":"258_CR5_258","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Three-player games are hard. ECCC, TR05-139 (2005)"},{"key":"258_CR6_258","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Papadimitriou, C.H.: Reducibility among equilibrium problems. In: STOC'06: Proc. of the 38th ACM Symposium on Theory of Computing, 2006, pp. 61\u201370","DOI":"10.1145\/1132516.1132526"},{"key":"258_CR7_258","doi-asserted-by":"crossref","unstructured":"Lipton, R., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proc. of the 4th ACM conference on Electronic commerce, 2003, pp. 36\u201341","DOI":"10.1145\/779928.779933"},{"issue":"1","key":"258_CR8_258","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J.F. Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium point in n-person games. Proc. Natl. Acad. Sci. USA 36(1), 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"258_CR9_258","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J.\u00a0Comput. Syst. Sci. 48, 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"258_CR10_258","unstructured":"Savani, R., von Stengel, B.: Exponentially many steps for finding a\u00a0Nash equilibrium in a\u00a0bimatrix game. In: FOCS'04: Proc. of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 258\u2013267"},{"key":"258_CR11_258","first-page":"274","volume-title":"Foundations of Computational Mathematics","author":"D.A. Spielman","year":"2006","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms and heuristics: progress and open questions. In: Pardo, L.M., Pinkus, A., S\u00fcli, E., Todd, M.J. (eds.) Foundations of Computational Mathematics, pp. 274\u2013342. Cambridge University Press, Cambridge, UK (2006)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T03:19:49Z","timestamp":1662175189000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_258"}},"subtitle":["2006; Chen, Deng, Teng"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_258","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}