Stochastic Limit-Average Games are in EXPTIME

2008/05/16 by Krishnendu Chatterjee, Chatterjee, Krishnendu, Rupak Majumdar +3 · 1 citation
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.GT

paper · pdf · doi:10.48550/arxiv.0805.2622

15 Pages

arxiv created 2008/05/16 · arxiv updated 2009/12/01

Abstract

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

Cited by

• Stochastic Games with Limited Public Memory

Related

• Constant Payoff Property in Zero-Sum Stochastic Games with a Finite Horizon
• General limit value in zero-sum stochastic games
• The asymptotic value in finite stochastic games
• Zero-Sum Stochastic Games with Partial Information and Average Payoff
• Zero-sum Stochastic Games: Limit Optimal Trajectories