On strategy improvement algorithms for simple stochastic games

• Published in: Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2011-09, Vol.9 (3), p.263-278
• Main Authors: Tripathi, Rahul, Valkanova, Elena, Anil Kumar, V.S.
• Format: Article
• Language: English
• Subjects: Algorithms; Computational complexity; Optimal strategies; Stochastic games; Strategy improvement algorithms
• ISSN: 1570-8667; 1570-8675
• DOI: 10.1016/j.jda.2011.03.007

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p ( s ) ∈ [ 0 , 1 ] . Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP ∩ coNP . However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O ( 2 n / n ) on the convergence time of the Hoffman–Karp algorithm, and a bound of O ( 2 0.78 n ) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.