Citation
Krishnendu Chatterjee, Rupak Majumdar, Tom Henzinger. "Stochastic Limit-Average Games are in EXPTIME". Technical report, University of California, Berkeley, UCB/EECS-2006-143, November, 2006.

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.

Electronic downloads

• http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-143.html

• HTML

  Krishnendu Chatterjee, Rupak Majumdar, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/319.html"
  ><i>Stochastic Limit-Average Games are in
  EXPTIME</i></a>, Technical report,  University
  of California, Berkeley, UCB/EECS-2006-143, November, 2006.

• Plain text

  Krishnendu Chatterjee, Rupak Majumdar, Tom Henzinger.
  "Stochastic Limit-Average Games are in EXPTIME".
  Technical report,  University of California, Berkeley,
  UCB/EECS-2006-143, November, 2006.

• BibTeX

  @techreport{ChatterjeeMajumdarHenzinger06_StochasticLimitAverageGamesAreInEXPTIME,
      author = {Krishnendu Chatterjee and Rupak Majumdar and Tom
                Henzinger},
      title = {Stochastic Limit-Average Games are in EXPTIME},
      institution = {University of California, Berkeley},
      number = {UCB/EECS-2006-143},
      month = {November},
      year = {2006},
      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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/319.html}
  }
  

Posted by Christopher Brooks on 7 Jun 2007.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.