# 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/EECS-2006-143

November 8, 2006

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-143.pdf

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

BibTeX citation:

@techreport{Chatterjee:EECS-2006-143, 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 = {2006}, Month = {Nov}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-143.html}, Number = {UCB/EECS-2006-143}, Abstract = {The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within \epsilon in time exponential in polynomial in the size of the game times polynomial in logarithmic in 1/\epsilon, for all \epsilon>0.} }

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 2006 %8 November 8 %@ UCB/EECS-2006-143 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-143.html %F Chatterjee:EECS-2006-143