An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

Oliver Friedmann

doi:10.2168/LMCS-7(3:23)2011

Oliver Friedmann - An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

lmcs:1026 - Logical Methods in Computer Science, October 3, 2011, Volume 7, Issue 3 - https://doi.org/10.2168/LMCS-7(3:23)2011

An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

Authors: Oliver Friedmann

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.

https://doi.org/10.2168/LMCS-7(3:23)2011

Source: arXiv.org:1106.0778

Volume: Volume 7, Issue 3

Published on: October 3, 2011

Imported on: November 5, 2010

Keywords: Computer Science - Computer Science and Game Theory,F.2.2

Licence: arXiv.org - Non-exclusive license to distribute

Linked publications - datasets - softwares

Source : ScholeXplorer IsReferencedBy ARXIV 1703.01296 Source : ScholeXplorer IsReferencedBy DOI 10.1145/3092282.3092286 Source : ScholeXplorer IsReferencedBy DOI 10.17638/03023722 Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1703.01296 10.48550/arxiv.1703.01296 10.1145/3092282.3092286 10.1145/3092282.3092286 10.1145/3092282.3092286 1703.01296 10.17638/03023722 An ordered approach to solving parity games in quasi polynomial time and quasi linear space Fearnley, John ; Jain, Sanjay ; Schewe, Sven ; Stephan, Frank ; Wojtczak, Dominik ;

18 Documents citing this article

Source : OpenCitations

Avis, David; Friedmann, Oliver, 2016, An Exponential Lower Bound For Cunninghamâs Rule, Mathematical Programming, 161, 1-2, pp. 271-305, 10.1007/s10107-016-1008-4.

Beckmann, Arnold; Pudlรกk, Pavel; Thapen, Neil, 2014, Parity Games And Propositional Proofs, ACM Transactions On Computational Logic, 15, 2, pp. 1-30, 10.1145/2579822.

Beckmann, Arnold; Pudlรกk, Pavel; Thapen, Neil, 2013, Parity Games And Propositional Proofs, Mathematical Foundations Of Computer Science 2013, pp. 111-122, 10.1007/978-3-642-40313-2_12.

Etessami, Kousha; Wojtczak, Dominik; Yannakakis, Mihalis, 2019, Recursive Stochastic Games With Positive Rewards, Theoretical Computer Science, 777, pp. 308-328, 10.1016/j.tcs.2018.12.018.

Fearnley, John, 2017, Efficient Parallel Strategy Improvement For Parity Games, Computer Aided Verification, pp. 137-154, 10.1007/978-3-319-63390-9_8.

Fearnley, John; Jain, Sanjay; De Keijzer, Bart; Schewe, Sven; Stephan, Frank; Wojtczak, Dominik, 2019, An Ordered Approach To Solving Parity Games In Quasi-Polynomial Time And Quasi-Linear Space, International Journal On Software Tools For Technology Transfer, 21, 3, pp. 325-349, 10.1007/s10009-019-00509-3.

Fearnley, John; Jain, Sanjay; Schewe, Sven; Stephan, Frank; Wojtczak, Dominik, 2017, An Ordered Approach To Solving Parity Games In Quasi Polynomial Time And Quasi Linear Space, Proceedings Of The 24Th ACM SIGSOFT International SPIN Symposium On Model Checking Of Software, 10.1145/3092282.3092286.

Fearnley, John; Savani, Rahul, 2015, The Complexity Of The Simplex Method, Proceedings Of The Forty-Seventh Annual ACM Symposium On Theory Of Computing, 10.1145/2746539.2746558.

Friedmann, Oliver, 2011, A Subexponential Lower Bound For Zadehâs Pivoting Rule For Solving Linear Programs And Games, Integer Programming And Combinatoral Optimization, pp. 192-206, 10.1007/978-3-642-20807-2_16.

Friedmann, Oliver, 2013, A Superpolynomial Lower Bound For Strategy Iteration Based On Snare Memorization, Discrete Applied Mathematics, 161, 10-11, pp. 1317-1337, 10.1016/j.dam.2013.02.007.

Hansen, Thomas Dueholm; Miltersen, Peter Bro; Zwick, Uri, 2013, Strategy Iteration Is Strongly Polynomial For 2-Player Turn-Based Stochastic Games With A Constant Discount Factor, Journal Of The ACM, 60, 1, pp. 1-16, 10.1145/2432622.2432623.

Hansen, Thomas Dueholm; Zwick, Uri, 2015, An Improved Version Of The Random-Facet Pivoting Rule For The Simplex Algorithm, Proceedings Of The Forty-Seventh Annual ACM Symposium On Theory Of Computing, 10.1145/2746539.2746557.

Keiren, Jeroen, 2015, Benchmarks For Parity Games, Fundamentals Of Software Engineering, pp. 127-142, 10.1007/978-3-319-24644-4_9.

Milushev, Dimiter; Clarke, Dave, 2013, Incremental Hyperproperty Model Checking Via Games, Secure IT Systems, pp. 247-262, 10.1007/978-3-642-41488-6_17.

Schewe, Sven; Trivedi, Ashutosh; Varghese, Thomas, 2015, Symmetric Strategy Improvement, Automata, Languages, And Programming, pp. 388-400, 10.1007/978-3-662-47666-6_31.

Van Dijk, Tom, 2019, A Parity Game Tale Of Two Counters, Electronic Proceedings In Theoretical Computer Science, 305, pp. 107-122, 10.4204/eptcs.305.8.

Willemse, T. A. C.; Gazda, M., 2015, Parity Games, Encyclopedia Of Algorithms, pp. 1-8, 10.1007/978-3-642-27848-8_591-1.

Willemse, Tim A. C.; Gazda, Maciej, 2016, Parity Games, Encyclopedia Of Algorithms, pp. 1532-1537, 10.1007/978-1-4939-2864-4_591.

Share and export

Consultation statistics

This page has been seen 1050 times.

This article's PDF has been downloaded 245 times.