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

DOI10.1007/S11590-017-1140-YzbMATH Open1380.91020arXiv1610.06681OpenAlexW2545791269MaRDI QIDQ1686541FDOQ1686541

Kazuhisa Makino, Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Publication date: 15 December 2017

Published in: Optimization Letters (Search for Journal in Brave)

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.

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

Recommendations

• A pseudo-polynomial algorithm for mean payoff stochastic 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 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

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)

Cites Work

• The complexity of mean payoff games on graphs
• Geometric algorithms and combinatorial optimization
• Algorithms for stochastic games ? A survey
• Title not available (Why is that?)
• Polynomial algorithms in linear programming
• Title not available (Why is that?)
• A characterization of the minimum cycle mean in a digraph
• Positional strategies for mean payoff games
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Mean cost cyclical games
• A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
• The complexity of solving stochastic games on graphs
• Title not available (Why is that?)
• Stochastic Games with Perfect Information and Time Average Payoff
• Cyclical games with prohibitions
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Extensions of two person zero sum games
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• A deterministic subexponential algorithm for solving parity games
• On canonical forms for zero-sum stochastic mean payoff games
• Title not available (Why is that?)
• Reduction of stochastic parity to stochastic mean-payoff games
• Cyclic games and linear programming
• Polynomial-time algorithms for energy games with special weight structures
• Combinatorial structure and randomized subexponential algorithms for infinite games
• A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
• Mathematical Foundations of Computer Science 2004
• From Parity and Payoff Games to Linear Programming
• Title not available (Why is that?)
• Games for verification: Algorithmic issues
• Deciding parity games in quasipolynomial time

Cited In (2)

• 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

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)