Stochastic Limit-Average Games are in EXPTIME

Krishnendu Chatterjee, Rupak Majumdar, and Thomas A. Henzinger

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.

International Journal of Game Theory 37:219-234, 2008.

Download inofficial, sometimes updated PostScript / PDF document. © 2008 Springer.