On the computational complexity of solving stochastic mean-payoff games

2008/12/02 by Gurvich, Vladimir, Miltersen, Peter Bro
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.0812.0486

Abstract

We consider some well-known families of two-player, zero-sum, perfect information games that can be viewed as special cases of Shapley's stochastic games. We show that the following tasks are polynomial time equivalent: - Solving simple stochastic games. - Solving stochastic mean-payoff games with rewards and probabilities given in unary. - Solving stochastic mean-payoff games with rewards and probabilities given in binary.

Related

• Universal Complexity Bounds Based on Value Iteration for Stochastic Mean Payoff Games and Entropy Games
• Exact Algorithms for Solving Stochastic Games
• Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems
• A Convex Programming-based Algorithm for Mean Payoff Stochastic Games with Perfect Information
• A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions