A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
DOI10.1007/s13235-016-0199-xzbMath1390.91037arXiv1508.03455OpenAlexW2245890606MaRDI QIDQ2636482
Endre Boros, Kazuhisa Makino, Vladimir A. Gurvich, Khaled M. Elbassioni
Publication date: 5 June 2018
Published in: Dynamic Games and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1508.03455
mean payoffcomputational game theoryundiscounted stochastic gamespotential transformationlimiting average payofflocal reward
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Stochastic games, stochastic differential games (91A15)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On canonical forms for zero-sum stochastic mean payoff games
- Stochastic limit-average games are in EXPTIME
- Solving systems of polynomial inequalities in subexponential time
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- The complexity of mean payoff games on graphs
- 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
- A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games
- Maximum-Minimum Sätze über Graphen
- A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
- The Complexity of Solving Stochastic Games on Graphs
- Successive Approximation Methods in Undiscounted Stochastic Games
- Algorithms for stochastic games ? A survey
- On the combinatorial and algebraic complexity of quantifier elimination
- The Complexity of Ergodic Mean-payoff Games
- Exact algorithms for solving stochastic games
- On Nonterminating Stochastic Games
- The Big Match
- Boundary Theory for Recurrent Markov Chains
- Stochastic Games
- Stochastic games
This page was built for publication: A potential reduction algorithm for two-person zero-sum mean payoff stochastic games