{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T17:53:39Z","timestamp":1790790819072,"version":"4.1.0"},"reference-count":25,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,10,3]],"date-time":"2011-10-03T00:00:00Z","timestamp":1317600000000},"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>This paper presents a new exponential lower bound for the two most popular deterministic variants of the strategy improvement algorithms for solving parity, mean payoff, discounted payoff and simple stochastic games. The first variant improves every node in each step maximizing the current valuation locally, whereas the second variant computes the globally optimal improvement in each step. We outline families of games on which both variants require exponentially many strategy iterations.<\/jats:p>","DOI":"10.2168\/lmcs-7(3:23)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":18,"title":["An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms"],"prefix":"10.46298","volume":"Volume 7, Issue 3","author":[{"given":"Oliver","family":"Friedmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25203","published-online":{"date-parts":[[2011,10,3]]},"reference":[{"issue":"2","key":"10.2168\/LMCS-7(3:23)2011_BjoerklundVorobyov\/2007","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.dam.2006.04.029","volume":"155","author":"Henrik Bj\u00f6rklund and Sergei Vorobyov","year":"2007","journal-title":"Discrete Appl. Math."},{"key":"10.2168\/LMCS-7(3:23)2011_condon92thecomplexity","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"Anne Condon","year":"1992","journal-title":"Information and Computation"},{"key":"10.2168\/LMCS-7(3:23)2011_focs91*368","doi-asserted-by":"crossref","unstructured":"E. Emerson and C. Jutla. Tree automata,\u00ce\u00bc-calculus and determinacy. InProc. 32nd Symp. on Foundations of Computer Science, pages 368-377, San Juan, 1991. IEEE.","DOI":"10.1109\/SFCS.1991.185392"},{"key":"10.2168\/LMCS-7(3:23)2011_Emerson93a","doi-asserted-by":"crossref","unstructured":"E. Emerson, C. Jutla, and A. Sistla. On model-checking for fragments ofu-calculus. InProc. 5th Conf. on CAV, CAV'93, volume 697 of LNCS, pages 385-396. Springer, 1993.","DOI":"10.1007\/3-540-56922-7_32"},{"key":"10.2168\/LMCS-7(3:23)2011_EhMy1979","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"A. Ehrenfeucht and J. Mycielski","year":"1979","journal-title":"Internat. J. Game Theory"},{"key":"10.2168\/LMCS-7(3:23)2011_pgsolver","unstructured":"Oliver Friedmann and Martin Lange. ThePGSolvercollection of parity game solvers, 2009. University of Munich. Available from http:\/\/www.tcs.ifi.lmu.de\/pgsolver."},{"key":"10.2168\/LMCS-7(3:23)2011_FriedmannLangePract09","doi-asserted-by":"crossref","unstructured":"Oliver Friedmann and Martin Lange. Solving parity games in practice. InATVA, pages 182-196, 2009.","DOI":"10.1007\/978-3-642-04761-9_15"},{"key":"10.2168\/LMCS-7(3:23)2011_FriedmannRecursive2010","unstructured":"O. Friedmann. Recursive solving of parity games requires exponential time. A preprint available from http:\/\/www.tcs.ifi.lmu.de\/friedman, 2010."},{"issue":"3","key":"10.2168\/LMCS-7(3:23)2011_FriedmannIJFCS2010","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1142\/S0129054110007246","volume":"21","author":"Oliver Friedmann","year":"2010","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.2168\/LMCS-7(3:23)2011_lncs2500","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, W. Thomas, and Th. Wilke, editors.Automata, Logics, and Infinite Games, LNCS. Springer, 2002. A. J. Hofmann and R. M. Karp. On nonterminating stochastic games.Management Science, 12(5):359-370, 1966.","DOI":"10.1287\/mnsc.12.5.359"},{"key":"10.2168\/LMCS-7(3:23)2011_howard\/1960","unstructured":"Ronald Howard.Dynamic Programming and Markov Processes. The M.I.T. Press, 1960."},{"key":"10.2168\/LMCS-7(3:23)2011_JPZ06","doi-asserted-by":"crossref","unstructured":"M. Jurdzi\u00cc\u00a4ski, M. Paterson, and U. Zwick. A deterministic subexponential algorithm for solving parity games. InProc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithm, SODA'06, pages 117-123. ACM, 2006.","DOI":"10.1145\/1109557.1109571"},{"issue":"3","key":"10.2168\/LMCS-7(3:23)2011_Jurdzinski\/98","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdznski","year":"1998","journal-title":"Inf. Process. Lett."},{"key":"10.2168\/LMCS-7(3:23)2011_Jurdzinski\/00","doi-asserted-by":"crossref","unstructured":"M. Jurdzinski. Small progress measures for solving parity games. In H. Reichel and S. Tison, editors,Proc. 17th Ann. Symp. on Theo. Aspects of Computer Science, STACS'00, volume 1770 ofLNCS, pages 290-301. Springer, 2000.","DOI":"10.1007\/3-540-46541-3_24"},{"key":"10.2168\/LMCS-7(3:23)2011_khachiyan79lp","first-page":"191","volume":"20","author":"Leonid Khachiyan","year":"1979","journal-title":"Soviet Math. Dokl."},{"key":"10.2168\/LMCS-7(3:23)2011_MadaniTZ10","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721849"},{"key":"10.2168\/LMCS-7(3:23)2011_puri\/phd","unstructured":"Anuj Puri.Theory of Hybrid Systems and Discrete Event Systems. PhD thesis, University of California, Berkeley, 1995."},{"key":"10.2168\/LMCS-7(3:23)2011_Schewe\/07\/Parity","doi-asserted-by":"crossref","unstructured":"Sven Schewe. Solving parity games in big steps. InProc. FST TCS. Springer-Verlag, 2007.","DOI":"10.1007\/978-3-540-77050-3_37"},{"key":"10.2168\/LMCS-7(3:23)2011_conf\/csl\/Schewe08","doi-asserted-by":"crossref","unstructured":"S. Schewe. An optimal strategy improvement algorithm for solving parity and payoff games. In17th Annual Conference on Computer Science Logic (CSL 2008), 2008.","DOI":"10.1007\/978-3-540-87531-4_27"},{"key":"10.2168\/LMCS-7(3:23)2011_StevensStirling98","doi-asserted-by":"crossref","unstructured":"P. Stevens and C. Stirling. Practical model-checking using games. In B. Steffen, editor,Proc. 4th Int. Conf. on Tools and Alg. for the Constr. and Analysis of Systems, TACAS'98, volume 1384 ofLNCS, pages 85-101. Springer, 1998.","DOI":"10.1007\/BFb0054166"},{"key":"10.2168\/LMCS-7(3:23)2011_Stirling95","doi-asserted-by":"crossref","unstructured":"C. Stirling. Local model checking games. InProc. 6th Conf. on Concurrency Theory, CONCUR'95, volume 962 ofLNCS, pages 1-11. Springer, 1995.","DOI":"10.1007\/3-540-60218-6_1"},{"key":"10.2168\/LMCS-7(3:23)2011_conf\/cav\/VogeJ00","doi-asserted-by":"crossref","unstructured":"J. V\u00f6ge and M. Jurdzinski. A discrete strategy improvement algorithm for solving parity games. InProc. 12th Int. Conf. on Computer Aided Verification, CAV'00, volume 1855 ofLNCS, pages 202-215. Springer, 2000.","DOI":"10.1007\/10722167_18"},{"key":"10.2168\/LMCS-7(3:23)2011_voege\/phd","unstructured":"Jens V\u00f6ge.Strategiesynthese f\u00fcr Parit\u00e4tsspiele auf endlichen Graphen. PhD thesis, University of Aachen, 2000."},{"issue":"1-2","key":"10.2168\/LMCS-7(3:23)2011_TCS::Zielonka1998","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0304-3975(98)00009-7","volume":"200","author":"W. Zielonka","year":"1998","journal-title":"TCS"},{"issue":"1-2","key":"10.2168\/LMCS-7(3:23)2011_zwickpaterson\/1996","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"Uri Zwick and Mike Paterson","year":"1996","journal-title":"Theoretical Computer Science"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1026\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1026\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:03:20Z","timestamp":1747159400000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,3]]},"references-count":25,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(3:23)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1106.0778","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1106.0778","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1703.01296","asserted-by":"subject"},{"id-type":"doi","id":"10.1145\/3092282.3092286","asserted-by":"subject"},{"id-type":"doi","id":"10.17638\/03023722","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1703.01296","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,3]]},"article-number":"1026"}}