Stochastic limit-average games are in EXPTIME

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.


Published in:
International Journal Of Game Theory, 37, 219-234
Year:
2008
Keywords:
Laboratories:




 Record created 2010-11-30, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)