{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:47:02Z","timestamp":1770972422367,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642229343","type":"print"},{"value":"9783642229350","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_2","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"13-25","source":"Crossref","is-referenced-by-count":6,"title":["Inapproximability of NP-Complete Variants of Nash Equilibrium"],"prefix":"10.1007","author":[{"given":"Per","family":"Austrin","sequence":"first","affiliation":[]},{"given":"Mark","family":"Braverman","sequence":"additional","affiliation":[]},{"given":"Eden","family":"Chlamt\u00e1\u010d","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Austrin, P., Braverman, M., Chlamtac, E.: Inapproximability of NP-Complete Variants of Nash Equilibrium. arXiv:1104.3760 (2011)","DOI":"10.1007\/978-3-642-22935-0_2"},{"issue":"3-4","key":"2_CR2","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W","volume":"13","author":"N. Alon","year":"1998","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Rand. Struct. Algos.\u00a013(3-4), 457\u2013466 (1998)","journal-title":"Rand. Struct. Algos."},{"issue":"1","key":"2_CR3","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.tcs.2009.09.023","volume":"411","author":"H. Bosse","year":"2010","unstructured":"Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate nash equilibria in bimatrix games. Theor. Comput. Sci.\u00a0411(1), 164\u2013173 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-03685-9_31","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S.C. Brubaker","year":"2009","unstructured":"Brubaker, S.C., Vempala, S.S.: Random tensors and planted cliques. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 406\u2013419. Springer, Heidelberg (2009)"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player nash equilibria. J. ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"issue":"2","key":"2_CR6","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1016\/j.geb.2008.02.015","volume":"63","author":"V. Conitzer","year":"2008","unstructured":"Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games and Economic Behavior\u00a063(2), 621\u2013641 (2008)","journal-title":"Games and Economic Behavior"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate nash equilibria. In: ACM Conference on Electronic Commerce, pp. 355\u2013358 (2007)","DOI":"10.1145\/1250910.1250962"},{"issue":"17","key":"2_CR8","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.1016\/j.tcs.2008.12.031","volume":"410","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: A note on approximate Nash equilibria. Theor. Comput. Sci.\u00a0410(17), 1581\u20131588 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"2_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/S009753970240118X","volume":"32","author":"U. Feige","year":"2003","unstructured":"Feige, U., Krauthgamer, R.: The probable value of the lov\u00e1sz\u2013schrijver relaxations for maximum independent set. SIAM J. Comput.\u00a032(2), 345\u2013370 (2003)","journal-title":"SIAM J. Comput."},{"key":"2_CR10","unstructured":"Frieze, A.M., Kannan, R.: A new approach to the planted clique problem. In: FSTTCS, pp. 187\u2013198 (2008)"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Feder, T., Nazerzadeh, H., Saberi, A.: Approximating Nash equilibria using small-support strategies. In: ACM Conference on Electronic Commerce, pp. 352\u2013354 (2007)","DOI":"10.1145\/1250910.1250961"},{"key":"2_CR12","volume-title":"Game Theory","author":"D. Fudenberg","year":"1991","unstructured":"Fudenberg, D., Tirole, J.: Game Theory. MIT Press, Cambridge (1991)"},{"issue":"1","key":"2_CR13","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I. Gilboa","year":"1989","unstructured":"Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games and Econ. Behavior\u00a01(1), 80\u201393 (1989)","journal-title":"Games and Econ. Behavior"},{"issue":"1","key":"2_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1137\/090766991","volume":"40","author":"E. Hazan","year":"2011","unstructured":"Hazan, E., Krauthgamer, R.: How Hard Is It to Approximate the Best Nash Equilibrium?. SIAM J. Comput.\u00a040(1), 79\u201391 (2011)","journal-title":"SIAM J. Comput."},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: ACM Conference on Electronic Commerce, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/978-3-642-03685-9_50","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"L. Minder","year":"2009","unstructured":"Minder, L., Vilenchik, D.: Small clique detection and approximate nash equilibria. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 673\u2013685. Springer, Heidelberg (2009)"},{"issue":"3","key":"2_CR17","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. Comp. Sys. Sci.\u00a048(3), 498\u2013532 (1994)","journal-title":"J. Comp. Sys. Sci."},{"issue":"4","key":"2_CR18","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1080\/15427951.2008.10129172","volume":"5","author":"H. Tsaknakis","year":"2008","unstructured":"Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate nash equilibria. Internet Mathematics\u00a05(4), 365\u2013382 (2008)","journal-title":"Internet Mathematics"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T01:03:11Z","timestamp":1560474191000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}