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 AlgorithmsArticle

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

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

19 Documents citing this article

Jan Křetínský;Tobias Meggendorfer;Maximilian Weininger, arXiv (Cornell University), Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives, pp. 1-14, 2023, Boston, MA, USA, 10.1109/lics56636.2023.10175771, https://arxiv.org/abs/2304.09930.

John Fearnley;Sanjay Jain;Bart de Keijzer;Sven Schewe;Frank Stephan;et al., 2019, An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space, arXiv (Cornell University), 21, 3, pp. 325-349, 10.1007/s10009-019-00509-3, https://arxiv.org/abs/1703.01296.

Tom van Dijk, 2019, A Parity Game Tale of Two Counters, arXiv (Cornell University), 305, pp. 107-122, 10.4204/eptcs.305.8.

Kousha Etessami;Dominik Wojtczak;Mihalis Yannakakis, 2018, Recursive stochastic games with positive rewards, Theoretical Computer Science, 777, pp. 308-328, 10.1016/j.tcs.2018.12.018, https://doi.org/10.1016/j.tcs.2018.12.018.

John Fearnley, arXiv (Cornell University), Efficient Parallel Strategy Improvement for Parity Games, pp. 137-154, 2017, 10.1007/978-3-319-63390-9_8, https://arxiv.org/abs/1705.02313.

John Fearnley;Sanjay Jain;Sven Schewe;Frank Stephan;Dominik Wojtczak, arXiv (Cornell University), An ordered approach to solving parity games in quasi polynomial time and quasi linear space, pp. 112-121, 2017, Santa Barbara CA USA, 10.1145/3092282.3092286, https://arxiv.org/abs/1703.01296.

David Avis;Oliver Friedmann, 2016, An exponential lower bound for Cunningham’s rule, arXiv (Cornell University), 161, 1-2, pp. 271-305, 10.1007/s10107-016-1008-4, https://arxiv.org/abs/1305.3944.

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

Jeroen J. A. Keiren, Lecture notes in computer science, Benchmarks for Parity Games, pp. 127-142, 2015, 10.1007/978-3-319-24644-4_9, https://doi.org/10.1007/978-3-319-24644-4_9.

John Fearnley;Rahul Savani, arXiv (Cornell University), The Complexity of the Simplex Method, 2015, Portland Oregon USA, 10.1145/2746539.2746558, https://arxiv.org/abs/1404.0605.

Sven Schewe;Ashutosh Trivedi;Thomas Varghese, arXiv (Cornell University), Symmetric Strategy Improvement, pp. 388-400, 2015, 10.1007/978-3-662-47666-6_31, https://arxiv.org/abs/1501.06484.

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

Thomas Dueholm Hansen;Uri Zwick, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm, pp. 209-218, 2015, Portland Oregon USA, 10.1145/2746539.2746557.

Arnold Beckmann;Pavel Pudlák;Neil Thapen, 2014, Parity Games and Propositional Proofs, CiteSeer X (The Pennsylvania State University), 15, 2, pp. 1-30, 10.1145/2579822, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.882.8292.

Arnold Beckmann;Pavel Pudlák;Neil Thapen, CiteSeer X (The Pennsylvania State University), Parity Games and Propositional Proofs, pp. 111-122, 2013, 10.1007/978-3-642-40313-2_12, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.882.8292.

Dimiter Milushev;Dave Clarke, Lirias (KU Leuven), Incremental Hyperproperty Model Checking via Games, pp. 247-262, 2013, 10.1007/978-3-642-41488-6_17, https://lirias.kuleuven.be/handle/123456789/410797.

Oliver Friedmann, 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, https://doi.org/10.1016/j.dam.2013.02.007.

Thomas Dueholm Hansen;Peter Bro Miltersen;Uri Zwick, 2013, Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor, arXiv (Cornell University), 60, 1, pp. 1-16, 10.1145/2432622.2432623, https://arxiv.org/abs/1008.0530.

Oliver Friedmann, Lecture notes in computer science, A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games, pp. 192-206, 2011, 10.1007/978-3-642-20807-2_16.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1998 times.

This article's PDF has been downloaded 339 times.