Stochastic limit-average games are in EXPTIME

DOI10.1007/S00182-007-0110-5MaRDI QIDQ933752zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger

Publication date 25 July 2008

Published in International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.2622

zbMATH Keywords

computational complexitylimit-average payoffstochastic games

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15)

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 a polynomial in the size of the game times polynomial in logarithmic in $frac1epsilon$, for all $epsilon>0$.

Recommendations

• A Survey of Stochastic Games with Limsup and Liminf Objectives
• The complexity of solving stochastic games on graphs
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• Another sub-exponential algorithm for the simple stochastic game
• Exact algorithms for solving stochastic games

Cites work

• Algorithms for stochastic games ? A survey
• Algorithms in real algebraic geometry
• An orderfield property for stochastic games when one player controls transition probabilities
• Continuity of the value of competitive Markov decision processes
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 2013849 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• New results on quantifier elimination over real closed fields and applications to constraint databases
• Number of quantifiers is better than number of tape cells
• On Nonterminating Stochastic Games
• On the menbership problem for functional and multivalued dependencies in relational databases
• Stochastic games
• Stochastic Games
• Stochastic Games with Perfect Information and Time Average Payoff
• The Asymptotic Theory of Stochastic Games
• The Big Match
• The complexity of mean payoff games on graphs

Cited in

(20)

• Denumerable state stochastic games with limiting average payoff
• Acceptable strategy profiles in stochastic games
• Zero-sum stochastic games over the field of real algebraic numbers
• Qualitative analysis of concurrent mean-payoff games
• A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
• Approximating the value of a concurrent reachability game in the polynomial time hierarchy
• Graph Games and Reactive Synthesis
• Value Iteration
• Games through Nested Fixpoints
• A Survey of Stochastic Games with Limsup and Liminf Objectives
• A survey of stochastic -regular games
• New algorithms for solving zero-sum stochastic games
• Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
• Stochastic games
• Definable zero-sum stochastic games
• A formula for the value of a stochastic game
• Defense and security planning under resource uncertainty and multi‐period commitments
• Bounded-memory strategies in partial-information games
• Concurrent stochastic games with stateful-discounted and parity objectives: complexity and algorithms
• Computing uniformly optimal strategies in two-player stochastic games

This page was built for publication: Stochastic limit-average games are in EXPTIME

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q933752)