{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:29:29Z","timestamp":1770064169456,"version":"3.49.0"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030794156","type":"print"},{"value":"9783030794163","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79416-3_1","type":"book-chapter","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T18:03:46Z","timestamp":1623866626000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Computational Complexity of Multi-player Evolutionarily Stable Strategies"],"prefix":"10.1007","author":[{"given":"Manon","family":"Blanc","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1155-8072","authenticated-orcid":false,"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Adamaszek, A., Miltzow, T.: The art gallery problem is $$\\exists \\mathbb{R}$$-complete. In: STOC 2018, pp. 65\u201373. ACM (2018). https:\/\/doi.org\/10.1145\/3188745.3188868","DOI":"10.1145\/3188745.3188868"},{"key":"1_CR2","doi-asserted-by":"publisher","unstructured":"Accinelli, E., Martins, F., Oviedo, J.: Evolutionary game theory: a generalization of the ESS definition. Int. Game Theory Rev. 21(4), 1950005 (19 pages) (2019). https:\/\/doi.org\/10.1142\/S0219198919500051","DOI":"10.1142\/S0219198919500051"},{"issue":"5","key":"1_CR3","doi-asserted-by":"publisher","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"E Allender","year":"2009","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. SIAM J. Comput. 38(5), 1987\u20132006 (2009). https:\/\/doi.org\/10.1137\/070697926","journal-title":"SIAM J. Comput."},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-030-30473-7_11","volume-title":"Algorithmic Game Theory","author":"MLT Berthelsen","year":"2019","unstructured":"Berthelsen, M.L.T., Hansen, K.A.: On the computational complexity of decision problems about multi-player Nash equilibria. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 153\u2013167. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30473-7_11"},{"key":"1_CR5","doi-asserted-by":"publisher","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, pp. 17:1\u201317:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.17","DOI":"10.4230\/LIPIcs.STACS.2016.17"},{"key":"1_CR6","doi-asserted-by":"publisher","unstructured":"Bil\u00f3, V., Mavronicolas, M.: $$\\exists \\mathbb{R}$$-complete decision problemsabout symmetric Nash equilibria in symmetric multi-player games. In: Vollmer, H., Vall\u00e9, B. (eds.) STACS 2017. LIPIcs, vol.\u00a066, pp.13:1\u201313:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.13","DOI":"10.4230\/LIPIcs.STACS.2017.13"},{"key":"1_CR7","doi-asserted-by":"publisher","unstructured":"Blum, L., Schub, M., Smale, S.: On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc. 21, 1\u201346 (1989). https:\/\/doi.org\/10.1090\/S0273-0979-1989-15750-9","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"1_CR8","doi-asserted-by":"publisher","unstructured":"Complexity and Real Computation. Springer, New York (1998). https:\/\/doi.org\/10.1007\/978-1-4612-0701-6","DOI":"10.1007\/978-1-4612-0701-6"},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1016\/S0304-3975(00)00323-6","volume":"262","author":"B Borchert","year":"2001","unstructured":"Borchert, B., Silvestri, R.: Dot operators. Theor. Comput. Sci. 262(1), 501\u2013523 (2001). https:\/\/doi.org\/10.1016\/S0304-3975(00)00323-6","journal-title":"Theor. Comput. Sci."},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"B\u00fcrgisser, P., Cucker, F.: Exotic quantifiers, complexity classes, and complete problems. Foundations Comput. Math. 9, 135\u2013170 (2009). https:\/\/doi.org\/10.1007\/s10208-007-9006-9","DOI":"10.1007\/s10208-007-9006-9"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1007\/BF02460000","volume":"59","author":"M Broom","year":"1997","unstructured":"Broom, M., Cannings, C., Vickers, G.T.: Multi-player matrix games. Bltn Mathcal Biology 59, 931\u2013952 (1997). https:\/\/doi.org\/10.1007\/BF02460000","journal-title":"Bltn Mathcal Biology"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Broom, M., Rycht\u00e1\u0159, J.: Game-Theoretical Models in Biology. Chapman and Hall (2013)","DOI":"10.1201\/b14069"},{"key":"1_CR13","doi-asserted-by":"publisher","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 460\u2013467 (1988). https:\/\/doi.org\/10.1145\/62212.62257","DOI":"10.1145\/62212.62257"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1287\/moor.2018.0945","volume":"44","author":"V Conitzer","year":"2019","unstructured":"Conitzer, V.: The exact computational complexity of evolutionarily stable strategies. Math. Oper. Res. 44(3), 783\u2013792 (2019). https:\/\/doi.org\/10.1287\/moor.2018.0945","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1_CR15","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). https:\/\/doi.org\/10.1016\/j.geb.2008.02.015","journal-title":"Games Econ. Behav."},{"issue":"5","key":"1_CR16","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1093\/comjnl\/36.5.400","volume":"36","author":"F Cucker","year":"1993","unstructured":"Cucker, F.: On the complexity of quantifier elimination: the structural approach. Comput. J. 36(5), 400\u2013408 (1993). https:\/\/doi.org\/10.1093\/comjnl\/36.5.400","journal-title":"Comput. J."},{"issue":"6","key":"1_CR17","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/BF01301968","volume":"29","author":"F Cucker","year":"1996","unstructured":"Cucker, F., Matamala, M.: On digital nondeterminism. Math. Syst. Theory 29(6), 635\u2013647 (1996). https:\/\/doi.org\/10.1007\/BF01301968","journal-title":"Math. Syst. Theory"},{"key":"1_CR18","doi-asserted-by":"publisher","unstructured":"Dobbins, M., Kleist, L., Miltzow, T., Rz\u0105\u017cewski, P.: $$\\forall \\exists \\mathbb{R}$$-completeness and area-universality. In: WG 2018. pp. 164\u2013175 (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_14","DOI":"10.1007\/978-3-030-00256-5_14"},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Etessami, K., Lochbihler, A.: The computational complexity of evolutionary stable strategies. Int. J. Game Theor. 37, 93\u2013113 (2007). https:\/\/doi.org\/10.1007\/s00182-007-0095-0","DOI":"10.1007\/s00182-007-0095-0"},{"key":"1_CR20","doi-asserted-by":"publisher","unstructured":"Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: $$\\exists \\mathbb{R}$$-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput. 6(1), 1:1\u20131:23 (2018). https:\/\/doi.org\/10.1145\/3175494","DOI":"10.1145\/3175494"},{"issue":"1","key":"1_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 Economic Behav. 1(1), 80\u201393 (1989). https:\/\/doi.org\/10.1016\/0899-8256(89)90006-7","journal-title":"Games Economic Behav."},{"key":"1_CR22","doi-asserted-by":"publisher","unstructured":"Gimbert, H., Paul, S., Srivathsan, B.: A bridge between polynomial optimization and games with imperfect recall. In: Seghrouchni, A.E.F., Sukthankar, G., An, B., Yorke-Smith, N. (eds.) AAMAS 2020, pp. 456\u2013464. International Foundation for Autonomous Agents and Multiagent Systems (2020). https:\/\/doi.org\/10.5555\/3398761.3398818","DOI":"10.5555\/3398761.3398818"},{"issue":"1","key":"1_CR23","doi-asserted-by":"publisher","first-page":"92","DOI":"10.2307\/2275252","volume":"59","author":"JB Goode","year":"1994","unstructured":"Goode, J.B.: Accessible telephone directories. J. Symbolic Logic 59(1), 92\u2013105 (1994). https:\/\/doi.org\/10.2307\/2275252","journal-title":"J. Symbolic Logic"},{"issue":"7","key":"1_CR24","doi-asserted-by":"publisher","first-page":"1554","DOI":"10.1007\/s00224-018-9887-9","volume":"63","author":"KA Hansen","year":"2018","unstructured":"Hansen, K.A.: The real computational complexity of minmax value and equilibrium refinements in multi-player games. Theory Comput. Syst. 63(7), 1554\u20131571 (2018). https:\/\/doi.org\/10.1007\/s00224-018-9887-9","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"1_CR25","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/0022-5193(79)90058-4","volume":"81","author":"J Hofbauer","year":"1979","unstructured":"Hofbauer, J., Schuster, P., Sigmund, K.: A note on evolutionary stable strategies and game dynamics. Journal of Theoretical Biology 81(3), 609\u2013612 (1979). https:\/\/doi.org\/10.1016\/0022-5193(79)90058-4","journal-title":"Journal of Theoretical Biology"},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Ko, K.I., Lin, C.L.: On the complexity of min-max optimization problems and their approximation. In: AYDU, D.Z., Pardalos, P.M. (eds.) Minimax and Applications, pp. 219\u2013239. Springer, Boston (1995). https:\/\/doi.org\/10.1007\/978-1-4613-3557-3_15","DOI":"10.1007\/978-1-4613-3557-3_15"},{"issue":"1","key":"1_CR27","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-5193(74)90110-6","volume":"47","author":"J Maynard Smith","year":"1974","unstructured":"Maynard Smith, J.: The theory of games and the evolution of animal conflicts. J. Theor. Biol. 47(1), 209\u2013221 (1974). https:\/\/doi.org\/10.1016\/0022-5193(74)90110-6","journal-title":"J. Theor. Biol."},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1038\/246015a0","volume":"246","author":"J Maynard Smith","year":"1973","unstructured":"Maynard Smith, J., Price, G.: The logic of animal conflict. Nature 246, 15\u201318 (1973)","journal-title":"Nature"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Milchtaich, I.: Static Stability in Games. Working Papers 2008\u201304, Bar-Ilan University, Department of Economics (2008). https:\/\/ideas.repec.org\/p\/biu\/wpaper\/2008-04.html","DOI":"10.2139\/ssrn.1176648"},{"key":"1_CR30","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BFb0082792","volume-title":"Topology and Geometry \u2014 Rohlin Seminar","author":"NE Mnev","year":"1988","unstructured":"Mnev, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Viro, O.Y., Vershik, A.M. (eds.) Topology and Geometry \u2014 Rohlin Seminar. LNM, vol. 1346, pp. 527\u2013543. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/BFb0082792"},{"issue":"54","key":"1_CR31","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). https:\/\/doi.org\/10.2307\/1969529","journal-title":"Ann. Math."},{"key":"1_CR32","unstructured":"Nisan, N.: A note on the computational hardness of evolutionary stable strategies. iN: Electronic Colloquium on Computational Complexity (ECCC), vol. 13, no. 076 (2006). http:\/\/eccc.hpi-web.de\/eccc-reports\/2006\/TR06-076\/index.html"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF00277103","volume":"19","author":"G Palm","year":"1984","unstructured":"Palm, G.: Evolutionary stable strategies and game dynamics for n-person games. J. Mathe. Biol. 19, 329\u2013334 (1984). https:\/\/doi.org\/10.1007\/BF00277103","journal-title":"J. Mathe. Biol."},{"key":"1_CR34","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). https:\/\/doi.org\/10.1007\/978-3-642-11805-0_32"},{"key":"1_CR35","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, New York (2013)"},{"issue":"2","key":"1_CR36","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/s00224-015-9662-0","volume":"60","author":"M Schaefer","year":"2015","unstructured":"Schaefer, M., \u0160tefankovi\u010d, D.: Fixed points, nash equilibria, and the existential theory of the reals. Theory Comput. Syst. 60(2), 172\u2013193 (2015). https:\/\/doi.org\/10.1007\/s00224-015-9662-0","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"1_CR37","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0025-5564(78)90077-9","volume":"40","author":"PD Taylor","year":"1978","unstructured":"Taylor, P.D., Jonker, L.B.: Evolutionary stable strategies and game dynamics. Math. Biosci. 40(1), 145\u2013156 (1978). https:\/\/doi.org\/10.1016\/0025-5564(78)90077-9","journal-title":"Math. Biosci."},{"key":"1_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/3-540-16486-3_112","volume-title":"Structure in Complexity Theory","author":"S Zachos","year":"1986","unstructured":"Zachos, S.: Probabilistic quantifiers, adversaries, and complexity classes: an overview. In: Selman, A.L. (ed.) Structure in Complexity Theory. LNCS, vol. 223, pp. 383\u2013400. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/3-540-16486-3_112"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79416-3_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T23:19:41Z","timestamp":1623971981000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79416-3_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030794156","9783030794163"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79416-3_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"17 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CSR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computer Science Symposium in Russia","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sochi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Russia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"csr2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/logic.pdmi.ras.ru\/csr2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}