{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:24:33Z","timestamp":1770071073372,"version":"3.49.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319666990","type":"print"},{"value":"9783319667003","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-66700-3_10","type":"book-chapter","created":{"date-parts":[[2017,8,18]],"date-time":"2017-08-18T12:38:47Z","timestamp":1503059927000},"page":"119-130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1155-8072","authenticated-orcid":false,"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,19]]},"reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0165-1765(91)90179-O","volume":"36","author":"K Basu","year":"1991","unstructured":"Basu, K., Weibull, J.W.: Strategy subsets closed under rational behavior. Econ. Lett. 36(2), 141\u2013146 (1991)","journal-title":"Econ. Lett."},{"key":"10_CR2","unstructured":"Benisch, M., Davis, G.B., Sandholm, T.: Algorithms for rationalizability and CURB sets. In: Proceedings of the Twenty-First National Conference on Artificial Intelligence, pp. 598\u2013604. AAAI Press (2006)"},{"key":"10_CR3","unstructured":"Bil\u00f2, V., Mavronicolas, M.: A catalog of $$\\exists \\mathbb{R}$$-complete decision problems about Nash equilibria in multi-player games. In: Ollinger, N., Vollmer, H. (eds.) STACS 2016. LIPIcs, vol. 47, p. 17:1\u201317:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer, J.: Computing sums of radicals in polynomial time. In: 32nd Annual Symposium on Foundations of Computer Science (FOCS 1991), pp. 670\u2013677. IEEE Computer Society Press (1991)","DOI":"10.1109\/SFCS.1991.185434"},{"issue":"1","key":"10_CR5","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 Econ. Behav. 70(1), 34\u201343 (2010)","journal-title":"Games Econ. Behav."},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01768703","volume":"8","author":"V Bubelis","year":"1979","unstructured":"Bubelis, V.: On equilibria in finite games. Int. J. Game Theor. 8(2), 65\u201379 (1979)","journal-title":"Int. J. Game Theor."},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10208-007-9006-9","volume":"9","author":"P B\u00fcrgisser","year":"2009","unstructured":"B\u00fcrgisser, P., Cucker, F.: Exotic quantifiers, complexity classes, and complete problems. Found. Comput. Math. 9(2), 135\u2013170 (2009)","journal-title":"Found. Comput. Math."},{"issue":"3","key":"10_CR8","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1006\/jcss.1998.1608","volume":"58","author":"JF Buss","year":"1999","unstructured":"Buss, J.F., Frandsen, G.S., Shallit, J.O.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58(3), 572\u2013596 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Canny, J.F.: Some algebraic and geometric computations in PSPACE. In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), pp. 460\u2013467. ACM (1988)","DOI":"10.1145\/62212.62257"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 261\u2013272. IEEE Computer Society Press (2006)","DOI":"10.1109\/FOCS.2006.69"},{"issue":"2","key":"10_CR11","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 Econ. Behav. 63(2), 621\u2013641 (2008)","journal-title":"Games Econ. Behav."},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01769861","volume":"13","author":"E van Damme","year":"1984","unstructured":"van Damme, E.: A relation between perfect equilibria in extensive form games and proper equilibria in normal form games. Int. J. Game Theor. 13, 1\u201313 (1984)","journal-title":"Int. J. Game Theor."},{"issue":"1","key":"10_CR13","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 J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10_CR14","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1287\/moor.28.3.424.16397","volume":"28","author":"RS Datta","year":"2003","unstructured":"Datta, R.S.: Universality of Nash equilibria. Math. Oper. Res. 28(3), 424\u2013432 (2003)","journal-title":"Math. Oper. Res."},{"key":"10_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-662-44803-8_20","volume-title":"Algorithmic Game Theory","author":"K Etessami","year":"2014","unstructured":"Etessami, K., Hansen, K.A., Miltersen, P.B., S\u00f8rensen, T.B.: The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form. In: Lavi, R. (ed.) SAGT 2014. LNCS, vol. 8768, pp. 231\u2013243. Springer, Heidelberg (2014). doi:10.1007\/978-3-662-44803-8_20"},{"issue":"6","key":"10_CR16","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-662-47672-7_45","volume-title":"Automata, Languages, and Programming","author":"J Garg","year":"2015","unstructured":"Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 554\u2013566. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-47672-7_45"},{"key":"10_CR18","unstructured":"Gatti, N., Panozzo, F.: New results on the verification of Nash refinements for extensive-form games. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), pp. 813\u2013820. International Foundation for Autonomous Agents and Multiagent Systems (2012)"},{"issue":"1","key":"10_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 Econ. Behav. 1(1), 80\u201393 (1989)","journal-title":"Games Econ. Behav."},{"issue":"1\u20132","key":"10_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"DY Grigor\u2019Ev","year":"1988","unstructured":"Grigor\u2019Ev, D.Y., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1\u20132), 37\u201364 (1988)","journal-title":"J. Symb. Comput."},{"key":"10_CR21","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":"KA 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. 5385, pp. 684\u2013695. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-92185-1_74"},{"key":"10_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-642-16170-4_18","volume-title":"Algorithmic Game Theory","author":"KA Hansen","year":"2010","unstructured":"Hansen, K.A., Miltersen, P.B., S\u00f8rensen, T.B.: The computational complexity of trembling hand perfection and other equilibrium refinements. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 198\u2013209. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-16170-4_18"},{"issue":"4","key":"10_CR23","doi-asserted-by":"publisher","first-page":"863","DOI":"10.2307\/1912767","volume":"50","author":"DM Kreps","year":"1982","unstructured":"Kreps, D.M., Wilson, R.: Sequential equilibria. Econometrica 50(4), 863\u2013894 (1982)","journal-title":"Econometrica"},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01769254","volume":"15","author":"RB Myerson","year":"1978","unstructured":"Myerson, R.B.: Refinements of the Nash equilibrium concept. Int. J. Game Theor. 15, 133\u2013154 (1978)","journal-title":"Int. J. Game Theor."},{"issue":"54","key":"10_CR25","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"2","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 2(54), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"10_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing","author":"M Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 334\u2013344. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-11805-0_32"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-1-4614-0110-0_24","volume-title":"Thirty Essays on Geometric Graph Theory","author":"M Schaefer","year":"2013","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer, Heidelberg (2013). doi:10.1007\/978-1-4614-0110-0_24"},{"issue":"2","key":"10_CR28","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s00224-015-9662-0","volume":"60","author":"M Schaefer","year":"2017","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Fixed points, Nash equilibria, and the existential theory of the reals. Theor. Comput. Syst. 60(2), 172\u2013193 (2017)","journal-title":"Theor. Comput. Syst."},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF01766400","volume":"4","author":"R Selten","year":"1975","unstructured":"Selten, R.: A reexamination of the perfectness concept for equilibrium points in extensive games. Int. J. Game Theor. 4, 25\u201355 (1975)","journal-title":"Int. J. Game Theor."},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Gritzmann, P., Sturmfels, B. (eds.) Applied Geometry And Discrete Mathematics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 531\u2013554. DIMACS\/AMS (1990)","DOI":"10.1090\/dimacs\/004\/41"},{"key":"10_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58242-4","volume-title":"Stability and Perfection of Nash Equilibria","author":"E van Damme","year":"1991","unstructured":"van Damme, E.: Stability and Perfection of Nash Equilibria, 2nd edn. Springer, Heidelberg (1991)","edition":"2"},{"issue":"4","key":"10_CR32","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1007\/BF01095637","volume":"34","author":"NN Vorob\u2019ev","year":"1986","unstructured":"Vorob\u2019ev, N.N.: Estimates of real roots of a system of algebraic equations. J. Sov. Math. 34(4), 1754\u20131762 (1986)","journal-title":"J. Sov. Math."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66700-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T23:26:38Z","timestamp":1750807598000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-66700-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319666990","9783319667003"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66700-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"19 August 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"L'Aquila","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cs.gssi.infn.it\/sagt2017","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}