Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
From MaRDI portal
Publication:2461633
DOI10.1007/s00453-007-0175-3zbMath1131.91012OpenAlexW2030923287MaRDI QIDQ2461633
Publication date: 28 November 2007
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1527/
Linear programming (90C05) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items (20)
On canonical forms for zero-sum stochastic mean payoff games ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Solving Simple Stochastic Games ⋮ Continuous Positional Payoffs ⋮ ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP ⋮ On strategy improvement algorithms for simple stochastic games ⋮ Helly’s theorem: New variations and applications ⋮ A note on the approximation of mean-payoff games ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Automatizability and Simple Stochastic Games ⋮ A nested family of \(k\)-total effective rewards for positional games ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simple Stochastic Games with Few Random Vertices Are Easy to Solve ⋮ A non-iterative algorithm for generalized pig games
This page was built for publication: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
