Stochastic limit-average games are in EXPTIME
Chatterjee, Krishnendu; Majumdar, Rupak; Henzinger, Thomas A.
2008

Abstract

The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within e in time exponential in a polynomial in the size of the game times polynomial in logarithmic in 1/epsilon, for all epsilon > 0.

Details

Title Stochastic limit-average games are in EXPTIME
Author(s) Chatterjee, Krishnendu ; Majumdar, Rupak ; Henzinger, Thomas A.
Published in International Journal Of Game Theory
Volume 37
Pages 219-234
Date 2008
Keywords
DOI https://doi.org/10.1007/s00182-007-0110-5
Other identifier(s) View record in Web of Science
Laboratories MTC
Record Appears in Scientific production and competences > I&C - School of Computer and Communication Sciences > IC Archives > MTC - Models and Theory of Computation Laboratory
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date 2010-11-30

Actions