{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:50:29Z","timestamp":1757544629546,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            A\n            <jats:italic>decision problem<\/jats:italic>\n            about\n            <jats:italic>Nash equilibria<\/jats:italic>\n            is concerned with whether a given game has a Nash equilibrium with certain natural properties. We settle the complexity of such decision problems over multi-player games, establishing that (nearly) all decision problems that were before shown\n            <jats:italic>NP<\/jats:italic>\n            -complete over 2-player games in References [5, 12, 18] become \u2203\u211d-complete over multi-player games. \u2203\u211d [27] is the class capturing the complexity of deciding the\n            <jats:italic>Existential Theory of the Reals<\/jats:italic>\n            . Specifically, we present a simple, unifying, parametric polynomial time reduction from the problem of deciding, given a 3-player (symmetric) game, whether there is a (symmetric) Nash equilibrium where all strategies played with non-zero probability come from a given set, which was shown \u2203\u211d-complete in Reference [17]. By suitably working on the tuning parameters, our reduction delivers two extensive catalogs of \u2203\u211d-complete decision problems in multi-player games. The first addresses Nash equilibria in general games, while the second encompasses symmetric Nash equilibria in symmetric games. These results resolve completely the main open problem from Reference [17] to enlarge the class of \u2203\u211d-complete decision problems about (symmetric) Nash equilibria in multi-player (symmetric) games.\n          <\/jats:p>","DOI":"10.1145\/3456758","type":"journal-article","created":{"date-parts":[[2021,5,30]],"date-time":"2021-05-30T03:12:01Z","timestamp":1622344321000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["\u2203\u211d-complete Decision Problems about (Symmetric) Nash Equilibria in (Symmetric) Multi-player Games"],"prefix":"10.1145","volume":"9","author":[{"given":"V.","family":"Bil\u00f2","sequence":"first","affiliation":[{"name":"University of Salento, Italy"}]},{"given":"M.","family":"Mavronicolas","sequence":"additional","affiliation":[{"name":"University of Cyprus, Cyprus"}]}],"member":"320","published-online":{"date-parts":[[2021,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9523-7"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (LIPIcs)","volume":"47","author":"Bil\u00f2 Vittorio","year":"2016","unstructured":"Vittorio Bil\u00f2 and Marios Mavronicolas . 2016 . A catalog of -complete decision problems about Nash equilibria in multi-player games . In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (LIPIcs) , Vol. 47 . Schloss Dagstuhl, Leibniz Zentrum fuer Informatik, 17:1\u201317:13. Vittorio Bil\u00f2 and Marios Mavronicolas. 2016. A catalog of -complete decision problems about Nash equilibria in multi-player games. In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (LIPIcs), Vol. 47. Schloss Dagstuhl, Leibniz Zentrum fuer Informatik, 17:1\u201317:13."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (LIPIcs)","volume":"66","author":"Bil\u00f2 Vittorio","year":"2017","unstructured":"Vittorio Bil\u00f2 and Marios Mavronicolas . 2017 . -complete decision problems about symmetric Nash equilibria in symmetric multi-player games . In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (LIPIcs) , Vol. 66 . Schloss Dagstuhl, Leibniz Zentrum fuer Informatik, 13:1\u201313:14. Vittorio Bil\u00f2 and Marios Mavronicolas. 2017. -complete decision problems about symmetric Nash equilibria in symmetric multi-player games. In Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (LIPIcs), Vol. 66. Schloss Dagstuhl, Leibniz Zentrum fuer Informatik, 13:1\u201313:14."},{"key":"e_1_2_1_5_1","volume-title":"The complexity of computational problems about Nash equilibria in symmetric win-lose games. Algorithmica (Sept","author":"Bil\u00f2 Vittorio","year":"2020","unstructured":"Vittorio Bil\u00f2 and Marios Mavronicolas . 2020. The complexity of computational problems about Nash equilibria in symmetric win-lose games. Algorithmica (Sept . 2020 ). Vittorio Bil\u00f2 and Marios Mavronicolas. 2020. The complexity of computational problems about Nash equilibria in symmetric win-lose games. Algorithmica (Sept. 2020)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.03.036"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. ACM Press, 970\u2013982","author":"Braverman Mark","year":"2015","unstructured":"Mark Braverman , Young Kun-Ko , and Omri Weinstein . 2015 . Approximating the best Nash equilibrium in O(no(lgn)) time breaks the exponential time hypothesis . In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. ACM Press, 970\u2013982 . Mark Braverman, Young Kun-Ko, and Omri Weinstein. 2015. Approximating the best Nash equilibrium in O(no(lgn)) time breaks the exponential time hypothesis. In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms. ACM Press, 970\u2013982."},{"key":"e_1_2_1_8_1","first-page":"73","article-title":"Solutions of games by differential equations","volume":"24","author":"Brown George W.","year":"1950","unstructured":"George W. Brown and John von Neumann . 1950 . Solutions of games by differential equations . Contrib. Theor. Games, Ann. Math. Stud. 24 (1950), 73 \u2013 79 . George W. Brown and John von Neumann. 1950. Solutions of games by differential equations. Contrib. Theor. Games, Ann. Math. Stud.24 (1950), 73\u201379.","journal-title":"Contrib. Theor. Games, Ann. Math. Stud."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 20th ACM Symposium on Theory of Computing. ACM Press, 460\u2013467","author":"Canny John","year":"1988","unstructured":"John Canny . 1988 . Some algebraic and geometric computations in . In Proceedings of the 20th ACM Symposium on Theory of Computing. ACM Press, 460\u2013467 . John Canny. 1988. Some algebraic and geometric computations in . In Proceedings of the 20th ACM Symposium on Theory of Computing. ACM Press, 460\u2013467."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.01.010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.02.015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.06.001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958052"},{"key":"e_1_2_1_16_1","volume-title":"Johnson","author":"Garey Michael J.","year":"1979","unstructured":"Michael J. Garey and David S . Johnson . 1979 . Computers and Intractability \u2014 A Guide to the Theory of -Completeness. W. H. Freeman . Michael J. Garey and David S. Johnson. 1979. Computers and Intractability \u2014 A Guide to the Theory of -Completeness. W. H. Freeman."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3175494"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66700-3_10"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766991"},{"volume-title":"Topology and Geometry \u2013 Rohlin Seminar (Lecture Notes in Mathematics)","author":"Mn\u00ebv Nicolai E.","key":"e_1_2_1_21_1","unstructured":"Nicolai E. Mn\u00ebv . 1988. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties . In Topology and Geometry \u2013 Rohlin Seminar (Lecture Notes in Mathematics) , Vol. 1346 . Springer , 527\u2013543. Nicolai E. Mn\u00ebv. 1988. The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In Topology and Geometry \u2013 Rohlin Seminar (Lecture Notes in Mathematics), Vol. 1346. Springer, 527\u2013543."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11805-0_32"},{"volume-title":"Thirty Essays on Geometric Graph Theory","author":"Schaefer Marcus","key":"e_1_2_1_26_1","unstructured":"Marcus Schaefer . 2013. Realizability of graphs and linkages . In Thirty Essays on Geometric Graph Theory . Springer , 461\u2013482. Marcus Schaefer. 2013. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory. Springer, 461\u2013482."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-015-9662-0"},{"volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski Alfred","key":"e_1_2_1_28_1","unstructured":"Alfred Tarski . 1948. A Decision Method for Elementary Algebra and Geometry . RAND Corporation . Alfred Tarski. 1948. A Decision Method for Elementary Algebra and Geometry. RAND Corporation."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456758","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:26Z","timestamp":1750195886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,29]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3456758"],"URL":"https:\/\/doi.org\/10.1145\/3456758","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2021,5,29]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}