# Stochastic Limit-Average Games are in EXPTIME

### Krishnendu Chatterjee, Rupak Majumdar and Thomas A. Henzinger

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-05-1405

August 2005

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1405.pdf

The value of a finite-state stochastic game with limit-average objectives can be approximated to within epsilon in time exponential in the size of the game and logarithmic in 1/epsilon.

BibTeX citation:

@techreport{Chatterjee:CSD-05-1405, Author = {Chatterjee, Krishnendu and Majumdar, Rupak and Henzinger, Thomas A.}, Title = {Stochastic Limit-Average Games are in EXPTIME}, Institution = {EECS Department, University of California, Berkeley}, Year = {2005}, Month = {Aug}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5247.html}, Number = {UCB/CSD-05-1405}, Abstract = {The value of a finite-state stochastic game with limit-average objectives can be approximated to within epsilon in time exponential in the size of the game and logarithmic in 1/epsilon.} }

EndNote citation:

%0 Report %A Chatterjee, Krishnendu %A Majumdar, Rupak %A Henzinger, Thomas A. %T Stochastic Limit-Average Games are in EXPTIME %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-05-1405 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5247.html %F Chatterjee:CSD-05-1405