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.


    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

    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

    Consultation statistics

    This page has been seen 1050 times.
    This article's PDF has been downloaded 245 times.