Stochastic limit-average games are in EXPTIME Journal Article

Author(s): Chatterjee, Krishnendu; Majumdar, Ritankar S; Henzinger, Thomas A
Article Title: Stochastic limit-average games are in EXPTIME
Abstract: The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within ε in time exponential in a polynomial in the size of the game times polynomial in logarithmic in 1/ε, for all ε > 0.
Keywords: stochastic games; limit-average payoff; computational complexity
Journal Title: International Journal of Game Theory
Volume: 37
Issue 2
ISSN: 1432-1270
Publisher: Springer  
Date Published: 2008-01-01
Start Page: 219
End Page: 234
DOI: 10.1007/s00182-007-0110-5
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work