{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:22:01Z","timestamp":1742919721815,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":9,"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_79","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:50Z","timestamp":1214505410000},"page":"166-168","source":"Crossref","is-referenced-by-count":0,"title":["Complexity 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":"79_CR1_79","unstructured":"Chen, X., Deng, X.: 3-Nash is ppad-complete. ECCC, TR05\u2013134 (2005)"},{"key":"79_CR2_79","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash-equilibrium. In: FOCS'06, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp.\u00a0261\u2013272","DOI":"10.1109\/FOCS.2006.69"},{"key":"79_CR3_79","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.H.: Computing Nash equilibria: approximation and smoothed complexity. In: FOCS'06, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, pp.\u00a0603\u2013612","DOI":"10.1109\/FOCS.2006.20"},{"key":"79_CR4_79","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.\u00a071\u201378","DOI":"10.1145\/1132516.1132527"},{"key":"79_CR5_79","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Three-player games are hard. ECCC, TR05\u2013139 (2005)"},{"key":"79_CR6_79","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Papadimitriou, C.H.: Reducibility among equilibrium problems. In: STOC'06, Proceedings of the 38th ACM Symposium on Theory of Computing, 2006, pp.\u00a061\u201370","DOI":"10.1145\/1132516.1132526"},{"key":"79_CR7_79","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N. Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comp. Sci. 81, 317\u2013324 (1991)","journal-title":"Theor. Comp. Sci."},{"key":"79_CR8_79","doi-asserted-by":"crossref","unstructured":"Nash, J.F.: Equilibrium point in n-person games. In: Proceedings of the National Academy of the USA, vol.\u00a036, issue\u00a01, pp.\u00a048\u201349 (1950)","DOI":"10.1073\/pnas.36.1.48"},{"key":"79_CR9_79","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.\u00a0Comp. Syst. Sci. 48, 498\u2013532 (1994)","journal-title":"J. Comp. Syst. Sci."}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_79","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:07:58Z","timestamp":1662170878000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_79"}},"subtitle":["2006; Chen, Deng"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_79","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}