Friedmann, Oliver - 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
An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms

Authors: Friedmann, Oliver

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.


Source : oai:arXiv.org:1106.0778
DOI : 10.2168/LMCS-7(3:23)2011
Volume: Volume 7, Issue 3
Published on: October 3, 2011
Submitted on: November 5, 2010
Keywords: Computer Science - Computer Science and Game Theory,F.2.2


Share

Consultation statistics

This page has been seen 97 times.
This article's PDF has been downloaded 14 times.