{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:28:24Z","timestamp":1725474504889},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540681380"},{"type":"electronic","value":"9783540681410"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944874_24","type":"book-chapter","created":{"date-parts":[[2006,11,27]],"date-time":"2006-11-27T18:41:09Z","timestamp":1164652869000},"page":"262-273","source":"Crossref","is-referenced-by-count":23,"title":["Sparse Games Are Hard"],"prefix":"10.1007","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Goldberg, P., Papadimitriou, C.: Reducibility among equilibrium problems. In: STOC 2006 (2006)","key":"24_CR1","DOI":"10.1145\/1132516.1132526"},{"doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a nash equilibrium. In: STOC 2006 (2006)","key":"24_CR2","DOI":"10.1145\/1132516.1132527"},{"doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 498\u2013532 (1994)","key":"24_CR3","DOI":"10.1016\/S0022-0000(05)80063-7"},{"unstructured":"Chen, X., Deng, X.: 3-nash is ppad-complete. In: ECCC, TR05-134 (2005)","key":"24_CR4"},{"unstructured":"Daskalakis, C., Papadimitriou, C.: Three-player games are hard. In: ECCC, TR05-139 (2005)","key":"24_CR5"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player nash-equilibrium. In: FOCS 2006 (2006)","key":"24_CR6","DOI":"10.1109\/FOCS.2006.69"},{"doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.H.: Computing nash equilibria: Approximation and smoothed complexity. In: FOCS 2006 (2006)","key":"24_CR7","DOI":"10.1109\/FOCS.2006.20"},{"doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: ACM EC 2003, pp. 36\u201341 (2003)","key":"24_CR8","DOI":"10.1145\/779928.779933"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"D.A. Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM\u00a051, 385\u2013463 (2004)","journal-title":"J. ACM"},{"unstructured":"Barany, I., Vempala, S., Vetta, A.: Nash equilibria in random games. In: FOCS 2005 (2005)","key":"24_CR10"},{"unstructured":"Chen, X., Teng, S.H., Valiant, P.A.: The approximation complexity of win-lose games. Tsinghua-BU-MIT (manuscript, 2006)","key":"24_CR11"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J. Nash","year":"1950","unstructured":"Nash, J.: Equilibrium point in n-person games. Proceedings of the National Academy of the USA\u00a036, 48\u201349 (1950)","journal-title":"Proceedings of the National Academy of the USA"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/11841036_23","volume-title":"Algorithms \u2013 ESA 2006","author":"B. Codenotti","year":"2006","unstructured":"Codenotti, B., Leoncini, M., Resta, G.: Efficient computation of nash equilibria for very sparse win-lose bimatrix games. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 232\u2013243. Springer, Heidelberg (2006)"}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944874_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T17:08:40Z","timestamp":1558285720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944874_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540681380","9783540681410"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11944874_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}