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

Secondary volumes: Selected Papers of the 24th IEEE Symposium on Logic in Computer Science (LICS 2009)

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, 2023, Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-14, 10.1109/lics56636.2023.10175771.

John Fearnley;Sanjay Jain;Bart de Keijzer;Sven Schewe;Frank Stephan;Dominik Wojtczak, 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.

Tom van Dijk, 2019, A Parity Game Tale of Two Counters, Electronic Proceedings in Theoretical Computer Science, 305, pp. 107-122, 10.4204/eptcs.305.8, https://doi.org/10.4204/eptcs.305.8.

Kousha Etessami;Dominik Wojtczak;Mihalis Yannakakis, 2018, Recursive stochastic games with positive rewards, Edinburgh Research Explorer, 777, pp. 308-328, 10.1016/j.tcs.2018.12.018, https://www.research.ed.ac.uk/en/publications/02566dcf-0540-4863-ba36-545c060930e4.

John Fearnley, 2017, Efficient Parallel Strategy Improvement for Parity Games, Lecture notes in computer science, pp. 137-154, 10.1007/978-3-319-63390-9_8.

John Fearnley;Sanjay Jain;Sven Schewe;Frank Stephan;Dominik Wojtczak, 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, pp. 112-121, 10.1145/3092282.3092286.

David Avis;Oliver Friedmann, 2016, An exponential lower bound for Cunningham’s rule, Mathematical Programming, 161, 1-2, pp. 271-305, 10.1007/s10107-016-1008-4.

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

Jeroen J. A. Keiren, 2015, Benchmarks for Parity Games, arXiv (Cornell University), pp. 127-142, 10.1007/978-3-319-24644-4_9, http://arxiv.org/abs/1407.3121.

John Fearnley;Rahul Savani, 2015, The Complexity of the Simplex Method, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pp. 201-208, 10.1145/2746539.2746558.

Sven Schewe;Ashutosh Trivedi;Thomas Varghese, 2015, Symmetric Strategy Improvement, Lecture notes in computer science, pp. 388-400, 10.1007/978-3-662-47666-6_31.

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

Thomas Dueholm Hansen;Uri Zwick, 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, pp. 209-218, 10.1145/2746539.2746557.

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

Arnold Beckmann;Pavel Pudlák;Neil Thapen, 2013, Parity Games and Propositional Proofs, Lecture notes in computer science, pp. 111-122, 10.1007/978-3-642-40313-2_12.

Dimiter Milushev;Dave Clarke, 2013, Incremental Hyperproperty Model Checking via Games, Lirias (KU Leuven), pp. 247-262, 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.

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, Journal of the ACM, 60, 1, pp. 1-16, 10.1145/2432622.2432623.

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

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 3563 times.

This article's PDF has been downloaded 550 times.