{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:45:05Z","timestamp":1766137505817,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T00:00:00Z","timestamp":1600473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T00:00:00Z","timestamp":1600473600000},"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":["Algorithmica"],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00453-020-00763-x","type":"journal-article","created":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T07:03:34Z","timestamp":1600499014000},"page":"447-530","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Complexity of Computational Problems About Nash Equilibria in Symmetric Win-Lose Games"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7848-4904","authenticated-orcid":false,"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,19]]},"reference":[{"key":"763_CR1","unstructured":"Abbott, T., Kane, D., Valiant, P.: On the complexity of two-player win-lose games. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Sciences, pp. 113\u2013122 (2005)"},{"issue":"1","key":"763_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.7155\/jgaa.00147","volume":"11","author":"L Addario-Berry","year":"2007","unstructured":"Addario-Berry, L., Olver, N., Vetta, A.: A polynomial time algorithm for finding Nash equilibria in planar win-lose games. J. Graph Algorithms Appl. 11(1), 309\u2013319 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"763_CR3","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Fanelli, A.: Computing exact and approximate Nash equilibria in 2-player games. In: Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management, Vol. 6124, pp. 58\u201369, Lecture Notes in Computer Science. Springer (2010)","DOI":"10.1007\/978-3-642-14355-7_7"},{"issue":"3","key":"763_CR4","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s00224-013-9523-7","volume":"54","author":"V Bil\u00f2","year":"2014","unstructured":"Bil\u00f2, V., Mavronicolas, M.: Complexity of rational and irrational Nash equilibria. Theory Comput. Syst. 54(3), 491\u2013527 (2014)","journal-title":"Theory Comput. Syst."},{"key":"763_CR5","unstructured":"Bil\u00f2, V., Mavronicolas, M.: A catalog of $$\\exists {\\mathbb{R}}$$-complete decision problems about Nash equilibria in multi-player games. In: Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science, Article No.\u00a017, vol.\u00a047, pp. 17:1\u201317:13, LIPIcs, Schloss Dagstuhl - Leibniz Zentrum fuer Informatik (2016)"},{"key":"763_CR6","unstructured":"Bil\u00f2, V., Mavronicolas, M.: $$\\exists {\\mathbb{R}}$$-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, Article No.\u00a013, vol.\u00a066, pp. 13:1\u201313:13, LIPIcs, Schloss Dagstuhl - Leibniz Zentrum fuer Informatik (2017)"},{"issue":"1\u20133","key":"763_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.tcs.2008.03.036","volume":"401","author":"V Bonifaci","year":"2008","unstructured":"Bonifaci, V., Di Orio, U., Laura, L.: The complexity of uniform Nash equilibria and related regular subgraph problems. Theor. Comput. Sci. 401(1\u20133), 144\u2013152 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"763_CR8","series-title":"Annals of Mathematics Studies","first-page":"73","volume-title":"Solutions of Games by Differential Equations. Contributions to the Theory of Games","author":"GW Brown","year":"1950","unstructured":"Brown, G.W., von Neumann, J.: Solutions of Games by Differential Equations. Contributions to the Theory of Games. Annals of Mathematics Studies, vol. 24, pp. 73\u201379. Princeton University Press, Princeton (1950)"},{"issue":"3","key":"763_CR9","doi-asserted-by":"publisher","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(3), 1\u201357 (2009)","journal-title":"J. ACM"},{"key":"763_CR10","unstructured":"Chen, X., Teng, S.-H., Valiant, P.: The Approximation complexity of win-lose games. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0159\u2013168 (2007)"},{"key":"763_CR11","doi-asserted-by":"crossref","unstructured":"Codenotti, B., Leoncini, M., Resta, G.: Efficient computation of Nash equilibria for very sparse win-lose bimatrix games. In: Proceedings of the 14th European Symposium on Algorithms, vol.\u00a04168, pp.\u00a0232\u2013243, Lecture Notes in Computer Science. Springer (2006)","DOI":"10.1007\/11841036_23"},{"issue":"3","key":"763_CR12","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.ipl.2005.01.010","volume":"94","author":"B Codenotti","year":"2005","unstructured":"Codenotti, B., \u0160tefankovi\u010d, D.: On the computational complexity of Nash equilibria for $$(0, 1)$$ bimatrix games. Inf. Process. Lett. 94(3), 145\u2013150 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"763_CR13","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."},{"issue":"1","key":"763_CR14","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."},{"key":"763_CR15","doi-asserted-by":"crossref","unstructured":"Datta, S., Krishnamurthy, N.: Some tractable win-lose games. In: Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation, vol.\u00a06648, pp. 365\u2013376, Lecture Notes in Computer Science. Springer (2011)","DOI":"10.1007\/978-3-642-20877-5_36"},{"issue":"6","key":"763_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":"763_CR17","series-title":"Annals of Mathematics Studies","first-page":"81","volume-title":"On Symmetric Games. Contributions to the Theory of Games","author":"D Gale","year":"1950","unstructured":"Gale, D., Kuhn, H.W., Tucker, A.W.: On Symmetric Games. Contributions to the Theory of Games. Annals of Mathematics Studies, vol. 24, pp. 81\u201387. Princeton University Press, Princeton (1950)"},{"key":"763_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of $${\\cal{NP}}$$-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of $${\\cal{NP}}$$-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"1","key":"763_CR19","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/3175494","volume":"6","author":"J Garg","year":"2018","unstructured":"Garg, J., Mehta, R., Vazirani, V.V., Yazdanbov, S.: $${\\cal{ETR}}$$-completeness for decision versions of multi-player (symmetric) Nash equilibria. ACM Trans. Econ. Comput. 6(1), 1:1\u20131:23 (2018)","journal-title":"ACM Trans. Econ. Comput."},{"issue":"1","key":"763_CR20","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."},{"key":"763_CR21","unstructured":"Griesmer, J.H., Hoffman, A.J., Robinson, A.: On symmetric bimatrix games. IBM research paper RC-959, IBM Corp., T.\u00a0J.\u00a0Watson Research Center (1963)"},{"key":"763_CR22","first-page":"385","volume":"54","author":"MJM Jansen","year":"1986","unstructured":"Jansen, M.J.M., Potters, J.A.M., Tijs, S.H.: Symmetrizations of two-person games. Methods Oper. Res. 54, 385\u2013402 (1986)","journal-title":"Methods Oper. Res."},{"key":"763_CR23","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01417212","volume":"36","author":"AP Jurg","year":"1992","unstructured":"Jurg, A.P., Jansen, M.J.M., Potters, J.A.M., Tijs, S.H.: A symmetrization for finite two-person games. Methods Models Oper. Res. 36, 111\u2013123 (1992)","journal-title":"Methods Models Oper. Res."},{"key":"763_CR24","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2016.04.013","volume":"634","author":"M Mavronicolas","year":"2016","unstructured":"Mavronicolas, M., Monien, B.: The complexity of equilibria for risk-modeling valuations. Theor. Comput. Sci. 634, 67\u201396 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"763_CR25","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.geb.2009.10.003","volume":"68","author":"A McLennan","year":"2010","unstructured":"McLennan, A., Tourky, R.: Simple complexity from imitation games. Games Econ. Behav. 68(2), 683\u2013688 (2010)","journal-title":"Games Econ. Behav."},{"issue":"1","key":"763_CR26","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.geb.2009.08.003","volume":"70","author":"A McLennan","year":"2010","unstructured":"McLennan, A., Tourky, R.: Imitation games and computation. Games Econ. Behav. 70(1), 4\u201311 (2010)","journal-title":"Games Econ. Behav."},{"key":"763_CR27","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 317\u2013324 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"763_CR28","doi-asserted-by":"crossref","unstructured":"Mehta, R., Vazirani, V.V., Yazdanbod, S.: Settling some open problems on 2-player symmetric Nash equilibria. In: Proceedings of the 8th International Symposium on Algorithmic Game Theory, vol.\u00a09347, pp. 272\u2013284, Lecture Notes in Computer Science. Springer (2015)","DOI":"10.1007\/978-3-662-48433-3_21"},{"key":"763_CR29","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"JF Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium points in $$n$$-person games. Proc. Natl. Acad. Sci. USA 36, 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"2","key":"763_CR30","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"JF Nash","year":"1951","unstructured":"Nash, J.F.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"issue":"3","key":"763_CR31","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"763_CR32","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1017\/CBO9780511800481.004","volume-title":"Algorithmic Game Theory","author":"CH Papadimitriou","year":"2007","unstructured":"Papadimitriou, C.H.: The complexity of finding Nash equilibria. In: Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V.V. (eds.) Algorithmic Game Theory, pp. 29\u201350. Cambridge University Press, Cambridge (2007)"},{"key":"763_CR33","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Zachos, S.: Two remarks on the power of counting. In: Proceedings of Theoretical Computer Science, 6th GI-Conference, vol.\u00a0145, pp. 269\u2013276, Lecture Notes in Computer Science. Springer (1983)","DOI":"10.1007\/BFb0036487"},{"issue":"2","key":"763_CR34","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 Comput. Syst. 60(2), 172\u2013193 (2017)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"763_CR35","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"763_CR36","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness for parity problems. In: Proceedings of the 11th Annual International Conference on Computing and Combinatorics, vol.\u00a03595, pp. 1\u20138, Lecture Notes in Computer Science. Springer (2005)","DOI":"10.1007\/11533719_1"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00763-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00763-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00763-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,19]],"date-time":"2021-09-19T00:51:02Z","timestamp":1632012662000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00763-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,19]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["763"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00763-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,9,19]]},"assertion":[{"value":"3 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}