{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:14:37Z","timestamp":1778498077170,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2018,9,18]],"date-time":"2018-09-18T00:00:00Z","timestamp":1537228800000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s00224-018-9887-9","type":"journal-article","created":{"date-parts":[[2018,9,18]],"date-time":"2018-09-18T04:58:24Z","timestamp":1537246704000},"page":"1554-1571","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games"],"prefix":"10.1007","volume":"63","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":[[2018,9,18]]},"reference":[{"issue":"2","key":"9887_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":"9887_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":"9887_CR3","unstructured":"Bil\u00f2, V., Mavronicolas, M.: A catalog of \u2203 \u211d ${\\exists {\\mathbb {R}}}$ -complete decision problems about Nash equilibria in multi-player games. In: Ollinger, N., Vollmer, H. (eds.) STACS 2016, LIPIcs, vol. 47, pp. 17:1\u201317:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"9887_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":"9887_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 and Economic Behavior 70(1), 34\u201343 (2010)","journal-title":"Games and Economic Behavior"},{"issue":"2","key":"9887_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 Theory 8(2), 65\u201379 (1979)","journal-title":"Int. J. Game Theory"},{"issue":"2","key":"9887_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":"9887_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":"9887_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":"9887_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":"9887_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 and Economic Behavior 63(2), 621\u2013641 (2008)","journal-title":"Games and Economic Behavior"},{"key":"9887_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01769861","volume":"13","author":"E Damme van","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 Theory 13, 1\u201313 (1984)","journal-title":"Int. J. Game Theory"},{"issue":"1","key":"9887_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":"9887_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":"9887_CR15","unstructured":"Etessami, K.: The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game of perfect recall. arXiv: 1408.1233 (2014)"},{"key":"9887_CR16","doi-asserted-by":"crossref","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 (2014)","DOI":"10.1007\/978-3-662-44803-8_20"},{"issue":"6","key":"9887_CR17","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":"9887_CR18","doi-asserted-by":"crossref","unstructured":"Farina, G., Gatti, N.: Extensive-form perfect equilibrium computation in two-player games. In: Singh, S.P., Markovitch, S. (eds.) Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 502\u2013508. AAAI Press (2017)","DOI":"10.1609\/aaai.v31i1.10571"},{"key":"9887_CR19","doi-asserted-by":"crossref","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 (2015)","DOI":"10.1007\/978-3-662-47672-7_45"},{"key":"9887_CR20","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":"9887_CR21","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 1(1), 80\u201393 (1989)","journal-title":"Games and Economic Behavior"},{"issue":"1\u20132","key":"9887_CR22","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":"9887_CR23","doi-asserted-by":"crossref","unstructured":"Hansen, K.A.: The real computational complexity of minmax value and equilibrium refinements in multi-player games. In: Bil\u00f2, V., Flammini, M. (eds.) SAGT 2017, LNCS, vol. 10504, pp. 119\u2013130. Springer (2017)","DOI":"10.1007\/978-3-319-66700-3_10"},{"key":"9887_CR24","doi-asserted-by":"crossref","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 (2008)","DOI":"10.1007\/978-3-540-92185-1_74"},{"key":"9887_CR25","doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Lund, T.B.: Computational complexity of proper equilibrium. In: Tardos, E., Elkind, E., Vohra, R. (eds.) ACM Conference on Electronic Commerce, EC \u201918, pp 113\u2013130. ACM, New York (2018)","DOI":"10.1145\/3219166.3219199"},{"key":"9887_CR26","doi-asserted-by":"crossref","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.C., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010, LNCS, vol. 6386, pp. 198\u2013209. Springer (2010)","DOI":"10.1007\/978-3-642-16170-4_18"},{"issue":"4","key":"9887_CR27","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":"9887_CR28","doi-asserted-by":"crossref","unstructured":"Kuhn, H.W.: Extensive games and the problem of information. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games II, pp 193\u2013216. Princeton University Press, Princeton (1953)","DOI":"10.1515\/9781400881970-012"},{"issue":"2","key":"9887_CR29","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/S0899-8256(05)80007-7","volume":"8","author":"JF Mertens","year":"1995","unstructured":"Mertens, J.F.: Two examples of strategic equilibrium. Games and Economic Behavior 8(2), 378\u2013388 (1995)","journal-title":"Games and Economic Behavior"},{"issue":"1","key":"9887_CR30","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s00199-009-0440-6","volume":"42","author":"PB Miltersen","year":"2010","unstructured":"Miltersen, P.B., S\u00f8rensen, T.B.: Computing a quasi-perfect equilibrium of a two-player game. Econ. Theory 42(1), 175\u2013192 (2010)","journal-title":"Econ. Theory"},{"key":"9887_CR31","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 Theory 15, 133\u2013154 (1978)","journal-title":"Int. J. Game Theory"},{"issue":"54","key":"9887_CR32","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":"9887_CR33","unstructured":"Nicola, G., Mario, G., Fabio, P.: Further results on verification problems in extensive-form games. Working Papers 347, University of Milano-Bicocca Department of Economics (2016)"},{"key":"9887_CR34","doi-asserted-by":"crossref","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 (2010)","DOI":"10.1007\/978-3-642-11805-0_32"},{"key":"9887_CR35","doi-asserted-by":"crossref","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_24"},{"issue":"2","key":"9887_CR36","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. Theory of Computing Systems 60(2), 172\u2013193 (2017)","journal-title":"Theory of Computing Systems"},{"key":"9887_CR37","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 Theory 4, 25\u201355 (1975)","journal-title":"Int. J. Game Theory"},{"key":"9887_CR38","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":"9887_CR39","doi-asserted-by":"crossref","unstructured":"S\u00f8rensen, T.B.: Computing a proper equilibrium of a bimatrix game. In: Faltings, B., Leyton-Brown, K., Ipeirotis, P. (eds.) ACM Conference on Electronic Commerce, EC \u201912, pp. 916\u2013928. ACM (2012)","DOI":"10.1145\/2229012.2229081"},{"key":"9887_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58242-4","volume-title":"Stability and Perfection of Nash Equilibria","author":"E Damme van","year":"1991","unstructured":"van Damme, E.: Stability and Perfection of Nash Equilibria, 2nd edn. Springer, Berlin (1991)","edition":"2nd edn."},{"issue":"4","key":"9887_CR41","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":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9887-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9887-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9887-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T17:52:30Z","timestamp":1751910750000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9887-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,18]]},"references-count":41,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9887"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9887-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,18]]},"assertion":[{"value":"18 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}