{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T21:34:39Z","timestamp":1770068079884,"version":"3.49.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2008,11,11]],"date-time":"2008-11-11T00:00:00Z","timestamp":1226361600000},"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 study Recursive Concurrent Stochastic Games (RCSGs), extending our recent\nanalysis of recursive simple stochastic games to a concurrent setting where the\ntwo players choose moves simultaneously and independently at each state. For\nmulti-exit games, our earlier work already showed undecidability for basic\nquestions like termination, thus we focus on the important case of single-exit\nRCSGs (1-RCSGs).\n  We first characterize the value of a 1-RCSG termination game as the least\nfixed point solution of a system of nonlinear minimax functional equations, and\nuse it to show PSPACE decidability for the quantitative termination problem. We\nthen give a strategy improvement technique, which we use to show that player 1\n(maximizer) has \\epsilon-optimal randomized Stackless &amp; Memoryless (r-SM)\nstrategies for all \\epsilon &gt; 0, while player 2 (minimizer) has optimal r-SM\nstrategies. Thus, such games are r-SM-determined. These results mirror and\ngeneralize in a strong sense the randomized memoryless determinacy results for\nfinite stochastic games, and extend the classic Hoffman-Karp strategy\nimprovement approach from the finite to an infinite state setting. The proofs\nin our infinite-state setting are very different however, relying on subtle\nanalytic properties of certain power series that arise from studying 1-RCSGs.\n  We show that our upper bounds, even for qualitative (probability 1)\ntermination, can not be improved, even to NP, without a major breakthrough, by\ngiving two reductions: first a P-time reduction from the long-standing\nsquare-root sum problem to the quantitative termination decision problem for\nfinite concurrent stochastic games, and then a P-time reduction from the latter\nproblem to the qualitative termination problem for 1-RCSGs.<\/jats:p>","DOI":"10.2168\/lmcs-4(4:7)2008","type":"journal-article","created":{"date-parts":[[2009,1,9]],"date-time":"2009-01-09T10:25:14Z","timestamp":1231496714000},"source":"Crossref","is-referenced-by-count":16,"title":["Recursive Concurrent Stochastic Games"],"prefix":"10.46298","volume":"Volume 4, Issue 4","author":[{"given":"Kousha","family":"Etessami","sequence":"first","affiliation":[]},{"given":"Mihalis","family":"Yannakakis","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2008,11,11]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1196\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1196\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:05:42Z","timestamp":1681243542000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,11]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-4(4:7)2008","relation":{"is-same-as":[{"id-type":"arxiv","id":"0810.3581","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.0810.3581","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1207.4577","asserted-by":"subject"},{"id-type":"doi","id":"10.4204\/eptcs.117.8","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11,11]]},"article-number":"1196"}}