A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
From MaRDI portal
Publication:2417852
DOI10.1016/j.ic.2019.03.005zbMath1425.91045arXiv1508.03431WikidataQ128185774 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
zero-sum games; stochastic games; perfect information; equilibrium computation; pseudo-polynomial algorithm
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
91A05: 2-person games
91A43: Games involving graphs
91A15: Stochastic games, stochastic differential games
Related Items
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, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
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
