Krishnendu Chatterjee and Rupak Majumdar and Thomas A. Henzinger

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-143

November 8, 2006

http://www2.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},
    Year= {2006},
    Month= {Nov},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-143.html
%F Chatterjee:EECS-2006-143