{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T23:09:12Z","timestamp":1778454552925,"version":"3.51.4"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032186591","type":"print"},{"value":"9783032186607","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-18660-7_20","type":"book-chapter","created":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T22:33:28Z","timestamp":1778452408000},"page":"374-391","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Complexity of\u00a0Stationary Nash Equilibria in\u00a0Discounted Perfect Information Stochastic Games"],"prefix":"10.1007","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"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-5625-6953","authenticated-orcid":false,"given":"Xinhao","family":"Nie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,5,1]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","unstructured":"Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In: ISAAC. Lecture Notes in Computer Science, vol.\u00a05878, pp. 112\u2013121. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_13","DOI":"10.1007\/978-3-642-10631-6_13"},{"key":"20_CR2","doi-asserted-by":"publisher","unstructured":"Batziou, E., Fearnley, J., Gordon, S., Mehta, R., Savani, R.: Monotone contractions. In: STOC, pp. 507\u2013517. ACM (2025). https:\/\/doi.org\/10.1145\/3717823.3718175","DOI":"10.1145\/3717823.3718175"},{"issue":"2","key":"20_CR3","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0747-7171(85)80013-4","volume":"1","author":"A Borodin","year":"1985","unstructured":"Borodin, A., Fagin, R., Hopcroft, J.E., Tompa, M.: Decreasing the nesting depth of expressions involving square roots. J. Symb. Comput. 1(2), 169\u2013188 (1985). https:\/\/doi.org\/10.1016\/S0747-7171(85)80013-4","journal-title":"J. Symb. Comput."},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 14:1\u201314:57 (2009). https:\/\/doi.org\/10.1145\/1516512.1516516","DOI":"10.1145\/1516512.1516516"},{"issue":"2","key":"20_CR5","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Inf. Comput. 96(2), 203\u2013224 (1992). https:\/\/doi.org\/10.1016\/0890-5401(92)90048-K","journal-title":"Inf. Comput."},{"issue":"1","key":"20_CR6","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). https:\/\/doi.org\/10.1137\/070699652","journal-title":"SIAM J. Comput."},{"key":"20_CR7","unstructured":"Daskalakis, C., Golowich, N., Zhang, K.: The complexity of Markov equilibrium in stochastic games. In: Neu, G., Rosasco, L. (eds.) Proceedings of Thirty Sixth Conference on Learning Theory. Proceedings of Machine Learning Research, vol.\u00a0195, pp. 4180\u20134234. PMLR (12\u201315 Jul 2023)"},{"key":"20_CR8","doi-asserted-by":"publisher","unstructured":"Deligkas, A., Fearnley, J., Hollender, A., Melissourgos, T.: Pure-circuit: Strong inapproximability for PPAD. In: FOCS, pp. 159\u2013170. IEEE (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00022","DOI":"10.1109\/FOCS54457.2022.00022"},{"key":"20_CR9","doi-asserted-by":"publisher","unstructured":"Deng, X., Li, N., Mguni, D., Wang, J., Yang, Y.: On the complexity of computing Markov perfect equilibrium in general-sum stochastic games. Nat. Sci. Rev. 10(1), nwac256 (2022). https:\/\/doi.org\/10.1093\/nsr\/nwac256","DOI":"10.1093\/nsr\/nwac256"},{"issue":"6","key":"20_CR10","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). https:\/\/doi.org\/10.1137\/080720826","journal-title":"SIAM J. Comput."},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2020.05.007","volume":"114","author":"J Fearnley","year":"2020","unstructured":"Fearnley, J., Gordon, S., Mehta, R., Savani, R.: Unique end of potential line. J. Comput. Syst. Sci. 114, 1\u201335 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2020.05.007","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"20_CR12","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF00935890","volume":"34","author":"JA Filar","year":"1981","unstructured":"Filar, J.A.: Ordered field property for stochastic games when the player who controls transitions changes from state to state. J. Optim. Theory Appl. 34(4), 503\u2013515 (1981). https:\/\/doi.org\/10.1007\/BF00935890","journal-title":"J. Optim. Theory Appl."},{"key":"20_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4054-9","volume-title":"Competitive Markov decision processes","author":"J Filar","year":"1996","unstructured":"Filar, J., Vrieze, K.: Competitive Markov decision processes. Springer-Verlag, Berlin, Heidelberg (1996)"},{"key":"20_CR14","doi-asserted-by":"publisher","unstructured":"Filos-Ratsikas, A., Hansen, K.A., H\u00f8gh, K., Hollender, A.: FIXP-membership via convex optimization: Games, cakes, and markets. SIAM J. Comput. FOCS21\u201330\u2013FOCS21\u201384 (2023). https:\/\/doi.org\/10.1137\/22M1472656","DOI":"10.1137\/22M1472656"},{"key":"20_CR15","doi-asserted-by":"publisher","unstructured":"Filos-Ratsikas, A., Hansen, K.A., H\u00f8gh, K., Hollender, A.: PPAD-membership for problems with exact rational solutions: a general approach via convex optimization. In: STOC, pp. 1204\u20131215. ACM (2024). https:\/\/doi.org\/10.1145\/3618260.3649645","DOI":"10.1145\/3618260.3649645"},{"key":"20_CR16","doi-asserted-by":"publisher","unstructured":"Fink, A.M.: Equilibrium in a stochastic $$n$$-person game. J. Sci. Hiroshima Univ. Ser. A-I Math. 28(1), 89\u201393 (1964). https:\/\/doi.org\/10.32917\/hmj\/1206139508","DOI":"10.32917\/hmj\/1206139508"},{"key":"20_CR17","doi-asserted-by":"publisher","unstructured":"Hansen, K.A., Nie, X.: On the complexity of stationary Nash equilibria in discounted perfect information stochastic games (2025). https:\/\/doi.org\/10.48550\/arXiv.2510.11550","DOI":"10.48550\/arXiv.2510.11550"},{"key":"20_CR18","doi-asserted-by":"publisher","unstructured":"Jin, Y., Muthukumar, V., Sidford, A.: The complexity of infinite-horizon general-sum stochastic games. In: ITCS. LIPIcs, vol.\u00a0251, pp. 76:1\u201376:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2023.76","DOI":"10.4230\/LIPICS.ITCS.2023.76"},{"issue":"7","key":"20_CR19","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1287\/mnsc.11.7.681","volume":"11","author":"CE Lemke","year":"1965","unstructured":"Lemke, C.E.: Bimatrix equilibrium points and mathematical programming. Manage. Sci. 11(7), 681\u2013689 (1965). https:\/\/doi.org\/10.1287\/mnsc.11.7.681","journal-title":"Manage. Sci."},{"key":"20_CR20","doi-asserted-by":"publisher","unstructured":"Neyman, A., Sorin, S.: Stochastic Games and Applications. Kluwer Academic Publishers, nato asi series edn. (2003). https:\/\/doi.org\/10.1007\/978-94-010-0189-2","DOI":"10.1007\/978-94-010-0189-2"},{"issue":"3","key":"20_CR21","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/BF00935250","volume":"33","author":"T Parthasarathy","year":"1981","unstructured":"Parthasarathy, T., Raghavan, T.E.S.: An orderfield property for stochastic games when one player controls transition probabilities. J. Optim. Theory Appl. 33(3), 374\u2013392 (1981). https:\/\/doi.org\/10.1007\/BF00935250","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"20_CR22","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1137\/15M1039274","volume":"47","author":"A Rubinstein","year":"2018","unstructured":"Rubinstein, A.: Inapproximability of Nash equilibrium. SIAM J. Comput. 47(3), 917\u2013959 (2018). https:\/\/doi.org\/10.1137\/15M1039274","journal-title":"SIAM J. Comput."},{"issue":"10","key":"20_CR23","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. 39(10), 1095\u20131100 (1953). https:\/\/doi.org\/10.1073\/pnas.39.10.1095","journal-title":"Proc. Natl. Acad. Sci."},{"key":"20_CR24","doi-asserted-by":"publisher","unstructured":"Takahashi, M.: Equilibrium points of stochastic non-cooperative $$n$$-person games. J. Sci. Hiroshima Univ. Ser. A-I (Math.) 28(1), 95\u201399 (1964). https:\/\/doi.org\/10.32917\/hmj\/1206139509","DOI":"10.32917\/hmj\/1206139509"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0885-064X(92)90003-T","volume":"8","author":"P Tiwari","year":"1992","unstructured":"Tiwari, P.: A problem that is easier to solve on the unit-cost algebraic RAM. J. Complex. 8(4), 393\u2013397 (1992). https:\/\/doi.org\/10.1016\/0885-064X(92)90003-T","journal-title":"J. Complex."},{"key":"20_CR26","unstructured":"Zinkevich, M., Greenwald, A., Littman, M.: Cyclic equilibria in Markov games. In: Weiss, Y., Sch\u00f6lkopf, B., Platt, J. (eds.) Advances in Neural Information Processing Systems, vol.\u00a018. MIT Press (2005)"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-18660-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,10]],"date-time":"2026-05-10T22:33:30Z","timestamp":1778452410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-18660-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032186591","9783032186607"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-18660-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"New Brunswick, NJ","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wine2025.cs.rutgers.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}