A convex programming-based algorithm for mean payoff stochastic games with perfect information
From MaRDI portal
Publication:1686541
DOI10.1007/s11590-017-1140-yzbMath1380.91020arXiv1610.06681OpenAlexW2545791269MaRDI QIDQ1686541
Kazuhisa Makino, Endre Boros, Khaled M. Elbassioni, Vladimir A. Gurvich
Publication date: 15 December 2017
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.06681
Convex programming (90C25) 2-person games (91A05) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15)
Related Items
A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, 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
- 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
- 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
- Geometric algorithms and combinatorial optimization
- 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 pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
- Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
- Mean Cost Cyclical Games
- From Parity and Payoff Games to Linear Programming
- 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
- Polynomial algorithms in linear programming
- Algorithms for stochastic games ? A survey
- Deciding parity games in quasipolynomial time
- Mathematical Foundations of Computer Science 2004
- Stochastic Games with Perfect Information and Time Average Payoff
