*banner
 

Stochastic Limit-Average Games are in EXPTIME
Krishnendu Chatterjee, Rupak Majumdar, Tom Henzinger

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

Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess