{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T15:21:17Z","timestamp":1725895277375},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642339950"},{"type":"electronic","value":"9783642339967"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33996-7_9","type":"book-chapter","created":{"date-parts":[[2012,10,6]],"date-time":"2012-10-06T03:27:01Z","timestamp":1349494021000},"page":"96-107","source":"Crossref","is-referenced-by-count":0,"title":["Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques"],"prefix":"10.1007","author":[{"given":"Kord","family":"Eickmeyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristoffer Arnstfelt","family":"Hansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Verbin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.geb.2009.04.016","volume":"70","author":"C. Borgs","year":"2010","unstructured":"Borgs, C., Chayes, J., Immorlica, N., Kalai, A.T., Mirrokni, V., Papadimitriou, C.: The myth of the folk theorem. Games and Economic Behavior\u00a070(1), 34\u201343 (2010); Special Issue In Honor of Ehud Kalai","journal-title":"Games and Economic Behavior"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1007\/978-3-540-92185-1_74","volume-title":"Internet and Network Economics","author":"K.A. Hansen","year":"2008","unstructured":"Hansen, K.A., Hansen, T.D., Miltersen, P.B., S\u00f8rensen, T.B.: Approximability and Parameterized Complexity of Minmax Values. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol.\u00a05385, pp. 684\u2013695. Springer, Heidelberg (2008)"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Young, N.E.: Simple strategies for large zero-sum games with applications to complexity theory. In: STOC 1994, pp. 734\u2013740. ACM Press (1994)","DOI":"10.1145\/195058.195447"},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing\u00a039(1), 195\u2013259 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X. Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56, 14:1\u201314:57 (2009)","journal-title":"J. ACM"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: EC 2003, pp. 36\u201341. ACM (2003)","DOI":"10.1145\/779928.779933"},{"issue":"4","key":"9_CR7","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"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511814068"},{"issue":"4","key":"9_CR9","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M. Jerrum","year":"1992","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. Random Structures & Algorithms\u00a03(4), 347\u2013359 (1992)","journal-title":"Random Structures & Algorithms"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L. Ku\u010dera","year":"1995","unstructured":"Ku\u010dera, L.: Expected complexity of graph partitioning problems. Discrete Appl. Math.\u00a057, 193\u2013212 (1995)","journal-title":"Discrete Appl. Math."},{"issue":"3-4","key":"9_CR11","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. Random Structures & Algorithms\u00a013(3-4), 457\u2013466 (1998)","journal-title":"Random Structures & Algorithms"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A","volume":"16","author":"U. Feige","year":"2000","unstructured":"Feige, U., Krauthgamer, R.: Finding and certifying a large hidden clique in a semirandom graph. Random Structures & Algorithms\u00a016, 195\u2013208 (2000)","journal-title":"Random Structures & Algorithms"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/A:1008374125234","volume":"20","author":"A. Juels","year":"2000","unstructured":"Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Designs, Codes and Cryptography\u00a020, 269\u2013280 (2000)","journal-title":"Designs, Codes and Cryptography"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S.S., Xiao, Y.: Statistical algorithms and a lower bound for planted clique. Technical Report 064, ECCC (2012)","DOI":"10.1145\/2488608.2488692"},{"issue":"1","key":"9_CR15","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 Journal on Computing\u00a040(1), 79\u201391 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"9_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 and RANDOM 2009. LNCS, vol.\u00a05687, pp. 673\u2013685. Springer, Heidelberg (2009)"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate nash equilibria. In: EC 2007, pp. 355\u2013358. ACM (2007)","DOI":"10.1145\/1250910.1250962"},{"key":"9_CR18","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about nash equilibria. In: IJCAI 2003, pp. 765\u2013771. Morgan Kaufmann (2003)"},{"issue":"1","key":"9_CR19","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 Economic Behavior\u00a01(1), 80\u201393 (1989)","journal-title":"Games and Economic Behavior"},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-22935-0_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P. Austrin","year":"2011","unstructured":"Austrin, P., Braverman, M., Chlamt\u00e1\u010d, E.: Inapproximability of NP-Complete Variants of Nash Equilibrium. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2011. LNCS, vol.\u00a06845, pp. 13\u201325. Springer, Heidelberg (2011)"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042, 844\u2013856 (1995)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33996-7_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T00:20:57Z","timestamp":1557274857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33996-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642339950","9783642339967"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33996-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}