A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

DOI10.1016/j.ic.2019.03.005zbMath1425.91045arXiv1508.03431OpenAlexW2923722914WikidataQ128185774 ScholiaQ128185774MaRDI QIDQ2417852

Endre Boros, Kazuhisa Makino, Vladimir A. Gurvich, Khaled M. Elbassioni

Publication date: 29 May 2019

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

zero-sum gamesstochastic gamesperfect informationequilibrium computationpseudo-polynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) 2-person games (91A05) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15)

Related Items (4)

A potential reduction algorithm for two-person zero-sum mean payoff stochastic games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• On canonical forms for zero-sum stochastic mean payoff games
• Polynomial-time algorithms for energy games with special weight structures
• Another sub-exponential algorithm for the simple stochastic game
• Cyclical games with prohibitions
• Combinatorial structure and randomized subexponential algorithms for infinite games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Cyclic games and linear programming
• Reduction of stochastic parity to stochastic mean-payoff games
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Extensions of two person zero sum games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
• On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
• Mean Cost Cyclical Games
• Solving Simple Stochastic Games with Few Coin Toss Positions
• A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games
• Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
• A deterministic subexponential algorithm for solving parity games
• The Complexity of Solving Stochastic Games on Graphs
• New Results on Simple Stochastic Games
• Algorithms for stochastic games ? A survey
• A criterion and verification of the ergodicity of cyclic game forms
• Mathematical Foundations of Computer Science 2004
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Stochastic Games with Perfect Information and Time Average Payoff
• Boundary Theory for Recurrent Markov Chains

This page was built for publication: A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions