Exact Algorithms for Solving Stochastic Games

2012/02/17 by Hansen, Kristoffer Arnsfelt, Koucky, Michal, Lauritzen, Niels +2 · 3 citations
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1202.3898

Abstract

Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games.

Cited by

• Value-Set Iteration: Computing Optimal Correlated Equilibria in Infinite-Horizon Multi-Player Stochastic Games
• Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games
• Stochastic Games with Limited Public Memory

Related

• New algorithms for solving stochastic games
• On the computational complexity of solving stochastic mean-payoff games
• Simple Recursive Games
• A Potential Reduction Algorithm for Two-person Zero-sum Mean Payoff Stochastic Games
• A tutorial on Zero-sum Stochastic Games