{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T12:55:16Z","timestamp":1762606516862,"version":"3.41.2"},"reference-count":59,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,9,28]],"date-time":"2011-09-28T00:00:00Z","timestamp":1317168000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We analyse the computational complexity of finding Nash equilibria in turn-based stochastic multiplayer games with omega-regular objectives. We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game G, does there exist a Nash equilibrium of G where Player 0 wins with probability 1? Moreover, this problem remains undecidable when restricted to pure strategies or (pure) strategies with finite memory. One way to obtain a decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSPACE respectively. Finally, we single out a special case of the general problem that, in many cases, admits an efficient solution. In particular, we prove that deciding the existence of an equilibrium in which each player either wins or loses with probability 1 can be done in polynomial time for games where the objective of each player is given by a parity condition with a bounded number of priorities.<\/jats:p>","DOI":"10.2168\/lmcs-7(3:20)2011","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T13:45:24Z","timestamp":1415972724000},"source":"Crossref","is-referenced-by-count":21,"title":["The Complexity of Nash Equilibria in Stochastic Multiplayer Games"],"prefix":"10.46298","volume":"Volume 7, Issue 3","author":[{"given":"Michael","family":"Ummels","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5560-0546","authenticated-orcid":false,"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2011,9,28]]},"reference":[{"key":"10.2168\/LMCS-7(3:20)2011_AllenderBKM09","doi-asserted-by":"crossref","unstructured":"E. Allender, P. B\u00fcrgisser, J. Kjeldgaard-Pedersen, and P. B. Miltersen. On the complexity of numerical analysis.SIAM Journal on Computing, 38 (5): 1987-2006, 2009.","DOI":"10.1137\/070697926"},{"key":"10.2168\/LMCS-7(3:20)2011_AnderssonM09","doi-asserted-by":"crossref","unstructured":"D. Andersson and P. B. Miltersen. The complexity of solving stochastic games on graphs. InProceedings of the 20th International Symposium on Algorithms and Computation, ISAAC 2009, volume 5878 of LNCS, pages 112-121. Springer-Verlag, 2009.","DOI":"10.1007\/978-3-642-10631-6_13"},{"key":"10.2168\/LMCS-7(3:20)2011_Aumann81","unstructured":"R. J. Aumann. Survey of repeated games. InEssays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern, pages 11-42. Bibliographisches Institut Mannheim\/Wien\/Z\u00fcrich, 1981."},{"key":"10.2168\/LMCS-7(3:20)2011_BaierK08","unstructured":"C. Baier and J.-P. Katoen.Principles of Model Checking. MIT Press, 2008."},{"key":"10.2168\/LMCS-7(3:20)2011_Bellman57","unstructured":"R. E. Bellman.Dynamic Programming. Princeton University Press, 1957."},{"key":"10.2168\/LMCS-7(3:20)2011_BewleyK78","doi-asserted-by":"crossref","unstructured":"T. Bewley and E. Kohlberg. On stochastic games with stationary optimal strategies.Mathematics of Operations Research, 3(2): 104-125, 1978.","DOI":"10.1287\/moor.3.2.104"},{"key":"10.2168\/LMCS-7(3:20)2011_BjorklundV05","doi-asserted-by":"crossref","unstructured":"H. Bj\u00f6rklund and S. Vorobyov. Combinatorial structure and randomized subexponential algorithms for infinite games.Theoretical Computer Science, 349: 347-360, 2005.","DOI":"10.1016\/j.tcs.2005.07.041"},{"key":"10.2168\/LMCS-7(3:20)2011_BussH91","doi-asserted-by":"crossref","unstructured":"S. R. Buss and L. Hay. On truth-table reducibility to SAT.Information and Computation, 91(1): 86-102, 1991.","DOI":"10.1016\/0890-5401(91)90075-D"},{"key":"10.2168\/LMCS-7(3:20)2011_Canny88","doi-asserted-by":"crossref","unstructured":"J. Canny. Some algebraic and geometric computations in PSPACE. InProceedings of the 20th annual ACMSymposium on Theory of Computing, STOC '88, pages 460-469. ACM Press, 1988.","DOI":"10.1145\/62212.62257"},{"key":"10.2168\/LMCS-7(3:20)2011_Chatterjee07a","doi-asserted-by":"crossref","unstructured":"K. Chatterjee. Stochastic M\u00fcller games are PSPACE-complete. InProceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007, volume 4855 of LNCS, pages 436-448. Springer-Verlag, 2007.","DOI":"10.1007\/978-3-540-77050-3_36"},{"key":"10.2168\/LMCS-7(3:20)2011_de Alfaro","doi-asserted-by":"crossref","unstructured":", Henzinger, and Kupferman]AlfaroHK07 L. de Alfaro, T. A. Henzinger, and O. Kupferman. Concurrent reachability games.Theoretical Computer Science, 386 (3): 188-217, 2007.","DOI":"10.1016\/j.tcs.2007.07.008"},{"key":"10.2168\/LMCS-7(3:20)2011_ChenDT09","doi-asserted-by":"crossref","unstructured":"X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria.Journal of the ACM, 56 (3), 2009.","DOI":"10.1145\/1516512.1516516"},{"key":"10.2168\/LMCS-7(3:20)2011_Condon92","doi-asserted-by":"crossref","unstructured":"A. Condon. The complexity of stochastic games.Information and Computation, 96(2): 203-224, 1992.","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"10.2168\/LMCS-7(3:20)2011_ConitzerS03","unstructured":"V. Conitzer and T. Sandholm. Complexity results about Nash equilibria. InProceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI 2003, pages 765-771. Morgan Kaufmann, 2003."},{"key":"10.2168\/LMCS-7(3:20)2011_CourcoubetisY95","doi-asserted-by":"crossref","unstructured":"C. A. Courcoubetis and M. Yannakakis. The complexity of probabilistic verification.Journal of the ACM, 42 (4):857-907, 1995.","DOI":"10.1145\/210332.210339"},{"key":"10.2168\/LMCS-7(3:20)2011_CourcoubetisY98","doi-asserted-by":"crossref","unstructured":"C. A. Courcoubetis and M. Yannakakis. Markov decision processes and regular events.IEEE Transactions on Automatic Control, 43 (10): 1399-1418, 1998.","DOI":"10.1109\/9.720497"},{"issue":"1","key":"10.2168\/LMCS-7(3:20)2011_DaskalakisGP09","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis, P. W. Goldberg, and C. H.","year":"2009","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-7(3:20)2011_Alfaro97","unstructured":"L. de Alfaro.Formal Verification of Probabilistic Systems. PhD thesis, Stanford University, 1997."},{"key":"10.2168\/LMCS-7(3:20)2011_Alfaro98","doi-asserted-by":"crossref","unstructured":"L. de Alfaro. How to specify and verify the long-run average behavior of probabilistic systems. InProceedings of the 13th IEEE Symposium on Logic in Computer Science, LICS '98, pages 454-465. IEEE Computer Society Press, 1998.","DOI":"10.1109\/LICS.1998.705679"},{"key":"10.2168\/LMCS-7(3:20)2011_AlfaroH00","doi-asserted-by":"crossref","unstructured":"L. de Alfaro and T. A. Henzinger. Concurrent omega-regular games. InProceedings of the 15th IEEE Symposium on Logic in Computer Science, LICS 2000, pages 141-154. IEEE Computer Society Press, 2000.","DOI":"10.1109\/LICS.2000.855763"},{"issue":"3","key":"10.2168\/LMCS-7(3:20)2011_AlfaroHK07","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.tcs.2007.07.008","volume":"386","author":"L. de Alfaro, T. A. Henzinger, and O. Ku","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"10.2168\/LMCS-7(3:20)2011_de Alfaro","doi-asserted-by":"crossref","unstructured":", Henzinger, and Kupferman]AlfaroHK07 L. de Alfaro, T. A. Henzinger, and O. Kupferman. Concurrent reachability games.Theoretical Computer Science, 386 (3): 188-217, 2007.","DOI":"10.1016\/j.tcs.2007.07.008"},{"key":"10.2168\/LMCS-7(3:20)2011_EmersonJ91","doi-asserted-by":"crossref","unstructured":"E. A. Emerson and C. S. Jutla. Tree automata, mu-calculus and determinacy (extended abstract). InProceedings of the 32nd Annual Symposium on Foundations of Computer Science, FoCS '91, pages 368-377. IEEE Computer Society Press, 1991.","DOI":"10.1109\/SFCS.1991.185392"},{"issue":"1","key":"10.2168\/LMCS-7(3:20)2011_EmersonJ99","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1137\/S0097539793304741","volume":"29","author":"E. A. Emerson and C. S. Jutla","year":"199","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"10.2168\/LMCS-7(3:20)2011_EtessamiY10","doi-asserted-by":"crossref","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K. Etessami and M. Yannakakis","year":"2010","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"10.2168\/LMCS-7(3:20)2011_EtessamiKVY08","volume":"4","author":"K. Etessami, M. Z. Kwiatkowska, M. Y. Va","year":"2008","journal-title":"Logical Methods in Computer Science"},{"key":"10.2168\/LMCS-7(3:20)2011_FilarV97","doi-asserted-by":"crossref","unstructured":"J. Filar and K. Vrieze.Competitive Markov decision processes. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"10.2168\/LMCS-7(3:20)2011_Friedmann09","doi-asserted-by":"crossref","unstructured":"O. Friedmann. An exponential lower bound for the parity game strategy improvement algorithm as we know it. InProceedings of the 24th IEEE Symposium on Logic in Computer Science, LICS 2009, pages 145-156. IEEE Computer Society Press, 2009.","DOI":"10.1109\/LICS.2009.27"},{"key":"10.2168\/LMCS-7(3:20)2011_GareyGJ76","doi-asserted-by":"crossref","unstructured":"M. R. Garey, R. L. Graham, and D. S. Johnson. Some NP-complete geometric problems. InProceedings of the 8th Annual ACMSymposium on Theory of Computing, STOC '76, pages 10-22. ACM Press, 1976.","DOI":"10.1145\/800113.803626"},{"key":"10.2168\/LMCS-7(3:20)2011_GimbertH09","doi-asserted-by":"crossref","unstructured":"H. Gimbert and F. Horn. Solving simple stochastic games with few random vertices.Logical Methods in Computer Science, 5(2), 2009.","DOI":"10.2168\/LMCS-5(2:9)2009"},{"key":"10.2168\/LMCS-7(3:20)2011_GimbertH10","doi-asserted-by":"crossref","unstructured":"H. Gimbert and F. Horn. Solving simple stochastic tail games. InProceedings of the 21st ACM-SIAMSymposium on Discrete Algorithms, SODA 2010, pages 847-862. ACM Press, 2010.","DOI":"10.1137\/1.9781611973075.69"},{"key":"10.2168\/LMCS-7(3:20)2011_GraedelTW02","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, W. Thomas, and T. Wilke, editors.Automata, Logics, and Infinite Games, volume 2500 of LNCS. Springer-Verlag, 2002.","DOI":"10.1007\/3-540-36387-4"},{"key":"10.2168\/LMCS-7(3:20)2011_HanssonJ94","doi-asserted-by":"crossref","unstructured":"H. Hansson and B. Jonsson. A logic for reasoning about time and reliability.Formal Aspects of Computing, 6 (5): 512-535, 1994.","DOI":"10.1007\/BF01211866"},{"key":"10.2168\/LMCS-7(3:20)2011_Hemachandra89","doi-asserted-by":"crossref","unstructured":"L. A. Hemachandra. The strong exponential hierarchy collapses.Journal of Computer and System Sciences, 39 (3): 299-322, 1989.","DOI":"10.1016\/0022-0000(89)90025-1"},{"key":"10.2168\/LMCS-7(3:20)2011_Horn08","unstructured":"F. Horn.Random Games. PhD thesis, Universit\u00e9 Paris 7, 2008a."},{"key":"10.2168\/LMCS-7(3:20)2011_Horn08a","unstructured":"F. Horn. Explicit Muller games are PTIME. InProceedings of the 28th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, volume 2 ofLeibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2008b."},{"key":"10.2168\/LMCS-7(3:20)2011_HunterD05","doi-asserted-by":"crossref","unstructured":"P. Hunter and A. Dawar. Complexity bounds for regular games. InProceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS 2005, volume 3618 of LNCS, pages 495-506. Springer-Verlag, 2005.","DOI":"10.1007\/11549345_43"},{"key":"10.2168\/LMCS-7(3:20)2011_Immerman81","doi-asserted-by":"crossref","unstructured":"N. Immerman. Number of quantifiers is better than number of tape cells.Journal of Computer and System Sciences, 22 (3): 384-406, 1981.","DOI":"10.1016\/0022-0000(81)90039-8"},{"key":"10.2168\/LMCS-7(3:20)2011_Jurdzinski98","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u00cc\u00a4ski. Deciding the winner in parity games is in UPcapco-UP.Information Processing Letters, 68 (3): 119-124, 1998.","DOI":"10.1016\/S0020-0190(98)00150-1"},{"issue":"5","key":"10.2168\/LMCS-7(3:20)2011_JurdzinskiPZ08","first-page":"1519","volume":"38","author":"M. Jurdzi\u00cc\u00a4ski, M. Paterson, and U","year":"2008","journal-title":"SIAM Journal on Computing"},{"issue":"2-3","key":"10.2168\/LMCS-7(3:20)2011_Klarlund94","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0168-0072(94)90086-8","volume":"69","author":"N. Klarlund","year":"1994","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"10.2168\/LMCS-7(3:20)2011_MaitraS98","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s001820050071","volume":"27","author":"A. P. Maitra and W. D. Sudderth","year":"1998","journal-title":"International Journal of Game Theory"},{"issue":"4","key":"10.2168\/LMCS-7(3:20)2011_Martin98","doi-asserted-by":"crossref","first-page":"1565","DOI":"10.2307\/2586667","volume":"63","author":"D. A. Martin","year":"1998","journal-title":"Journal of Symbolic Logic"},{"key":"10.2168\/LMCS-7(3:20)2011_McIverM02","doi-asserted-by":"crossref","unstructured":"A. McIver and C. Morgan. Games, probability and the quantitative\u00ce\u00bc-calculus. InProceedings of the 9th International Conference on Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2002, volume 2514 of LNCS, pages 292-310. Springer-Verlag, 2002.","DOI":"10.1007\/3-540-36078-6_20"},{"issue":"2","key":"10.2168\/LMCS-7(3:20)2011_McNaughton93","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0168-0072(93)90036-D","volume":"65","author":"R. McNaughton","year":"1993","journal-title":"Annals of Pure and Applied Logic"},{"key":"10.2168\/LMCS-7(3:20)2011_Mostowski91a","unstructured":"A. W. Mostowski. Games with forbidden positions. Technical Report 78, Instytut Matematyki, Uniwersytet Gdanski, Poland, 1991."},{"key":"10.2168\/LMCS-7(3:20)2011_Nash50","doi-asserted-by":"crossref","unstructured":"J. F. Nash, Jr. Equilibrium points inN-person games.Proceedings of the National Academy of Sciences of the USA, 36: 48-49, 1950.","DOI":"10.1073\/pnas.36.1.48"},{"key":"10.2168\/LMCS-7(3:20)2011_NeymanS03","doi-asserted-by":"crossref","unstructured":"A. Neyman and S. Sorin, editors.Stochastic Games and Applications, volume 570 ofNATOScience Series C. Springer-Verlag, 2003.","DOI":"10.1007\/978-94-010-0189-2"},{"key":"10.2168\/LMCS-7(3:20)2011_OsborneR94","unstructured":"M. J. Osborne and A. Rubinstein.A Course in Game Theory. MIT Press, 1994."},{"key":"10.2168\/LMCS-7(3:20)2011_Shapley53","doi-asserted-by":"crossref","unstructured":"L. S. Shapley. Stochastic games.Proceedings of the National Academy of Sciences of the USA, 39: 1095-1100, 1953.","DOI":"10.1073\/pnas.39.10.1095"},{"key":"10.2168\/LMCS-7(3:20)2011_Thomas90","doi-asserted-by":"crossref","unstructured":"W. Thomas. Automata on infinite objects. InHandbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 133-192. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"10.2168\/LMCS-7(3:20)2011_Ummels05","doi-asserted-by":"crossref","unstructured":"M. Ummels. Rational behaviour and strategy construction in infinite multiplayer games. Diploma Thesis, RWTH Aachen University, 2005.","DOI":"10.1007\/11944836_21"},{"key":"10.2168\/LMCS-7(3:20)2011_Ummels08","doi-asserted-by":"crossref","unstructured":"M. Ummels. The complexity of Nash equilibria in infinite multiplayer games. InProceedings of the 11th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2008, volume 4962 of LNCS, pages 20-34. Springer-Verlag, 2008.","DOI":"10.1007\/978-3-540-78499-9_3"},{"key":"10.2168\/LMCS-7(3:20)2011_Ummels10","doi-asserted-by":"crossref","unstructured":"M. Ummels.Stochastic Multiplayer Games: Theory and Algorithms. PhD thesis, RWTH Aachen University, 2010.","DOI":"10.5117\/9789085550402"},{"key":"10.2168\/LMCS-7(3:20)2011_UmmelsW09a","doi-asserted-by":"crossref","unstructured":"M. Ummels and D. Wojtczak. Decision problems for Nash equilibria in stochastic games. InProceedings of the 18th Annual Conference of the European Association for Computer Science Logic, CSL '09, volume 5771 of LNCS, pages 515-529. Springer-Verlag, 2009.","DOI":"10.1007\/978-3-642-04027-6_37"},{"key":"10.2168\/LMCS-7(3:20)2011_VoegeJ00","doi-asserted-by":"crossref","unstructured":"J. V\u00f6ge and M. Jurdzinski. A discrete strategy improvement algorithm for solving parity games. InProceedings of the 12th International Conference on Computer Aided Verification, CAV 2000, volume 1855 of LNCS, pages 202-215. Springer-Verlag, 2000.","DOI":"10.1007\/10722167_18"},{"key":"10.2168\/LMCS-7(3:20)2011_Wagner90","doi-asserted-by":"crossref","unstructured":"K. W. Wagner. Bounded query classes.SIAM Journal on Computing, 19 (5):833-846, 1990.","DOI":"10.1137\/0219058"},{"key":"10.2168\/LMCS-7(3:20)2011_Zielonka98","doi-asserted-by":"crossref","unstructured":"W. Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees.Theoretical Computer Science, 200(1-2): 135-183, 1998.","DOI":"10.1016\/S0304-3975(98)00009-7"},{"key":"10.2168\/LMCS-7(3:20)2011_Zielonka04","doi-asserted-by":"crossref","unstructured":"W. Zielonka. Perfect-information stochastic parity games. InProceedings of the 7th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2004, volume 2987 of LNCS, pages 499-513. Springer-Verlag, 2004.","DOI":"10.1007\/978-3-540-24727-2_35"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1209\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1209\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:03:18Z","timestamp":1747159398000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,28]]},"references-count":59,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(3:20)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1109.4017","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1109.4017","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,9,28]]},"article-number":"1209"}}