A convex programming-based algorithm for mean payoff stochastic games with perfect information

DOI10.1007/S11590-017-1140-YMaRDI QIDQ1686541zbMATH OpenOpenAlexFDO

Authors Endre Boros, Kazuhisa Makino, Khaled Elbassioni, Vladimir 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

zbMATH Keywords

convex programmingmean payoffperfect informationstochastic gamespseudo-polynomial algorithm

Mathematics Subject Classification ID

Convex programming (90C25) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Abstract: We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph $G=(V,E)$, with local rewards $$, and three types of positions: black $V_B$, white $V_W$, and random $V_R$ forming a partition of $V$. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, even when $|V_R|=0$. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this short note, we show that BWR-games can be solved via convex programming in pseudo-polynomial time if the number of random positions is a constant.

Recommendations

• A pumping algorithm for ergodic stochastic mean payoff games with perfect information
• Stochastic mean payoff games: smoothed analysis and approximation schemes
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions

Cites work

• scientific article; zbMATH DE number 3128733 (Why is no real title available?)
• scientific article; zbMATH DE number 3945887 (Why is no real title available?)
• scientific article; zbMATH DE number 3542195 (Why is no real title available?)
• scientific article; zbMATH DE number 3333895 (Why is no real title available?)
• A characterization of the minimum cycle mean in a digraph
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• A deterministic subexponential algorithm for solving parity games
• A pumping algorithm for ergodic stochastic mean payoff games with perfect information
• Algorithms for stochastic games ? A survey
• Combinatorial structure and randomized subexponential algorithms for infinite games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Cyclic games and linear programming
• Cyclical games with prohibitions
• Deciding parity games in quasipolynomial time
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Extensions of two person zero sum games
• From Parity and Payoff Games to Linear Programming
• Games for verification: Algorithmic issues
• Geometric algorithms and combinatorial optimization
• Mathematical Foundations of Computer Science 2004
• Mean cost cyclical games
• On canonical forms for zero-sum stochastic mean payoff games
• Polynomial algorithms in linear programming
• Positional strategies for mean payoff games
• Quantitative stochastic parity games
• Reduction of stochastic parity to stochastic mean-payoff games
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Stochastic Games with Perfect Information and Time Average Payoff
• The complexity of mean payoff games on graphs
• The complexity of solving stochastic games on graphs

Cited in

(3)

• Stochastic mean payoff games: smoothed analysis and approximation schemes
• A pumping algorithm for ergodic stochastic mean payoff games with perfect information
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions

This page was built for publication: A convex programming-based algorithm for mean payoff stochastic games with perfect information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686541)