Approximation schemes for stochastic mean payoff games with perfect information and few random positions
type: Item
instance of: scholarly article
title: Approximation schemes for stochastic mean payoff games with perfect information and few random positions
zbMATH Open document ID: 1417.91070
author: Endre Boros
author: Mahmoud Fouz
author: Kazuhisa Makino
author: Bodo Manthey
author: Khaled Elbassioni
author: Vladimir Gurvich
published in: Algorithmica
publication date: 2019-01-11T00:00:00Z
full work available at URL: approximation-schemes-for-stochastic-mean-payoff-games-with-perfect-information-and-few-random-positions(437d93e1-2938-4039-bb15-270b5c154293).html
Mathematics Subject Classification ID: 91A15
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7000136
zbMATH Keywords: stochastic mean payoff games
zbMATH Keywords: approximation schemes
zbMATH Keywords: approximation algorithms
zbMATH Keywords: Nash equilibrium
MaRDI profile type: Publication
OpenAlex ID: W2754286068
Wikidata QID: Q59527899
cites work: The Complexity of Solving Stochastic Games on Graphs
cites work: Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
cites work: A convex programming-based algorithm for mean payoff stochastic games with perfect information
cites work: A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
cites work: A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
cites work: Deciding parity games in quasipolynomial time
cites work: Q4633826
cites work: The Complexity of Ergodic Mean-payoff Games
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: Markov chain sensitivity measured by mean first passage times
cites work: The complexity of stochastic games
cites work: Q4287357
cites work: Another sub-exponential algorithm for the simple stochastic game
cites work: Positional strategies for mean payoff games
cites work: A note on the approximation of mean-payoff games
cites work: Q3245641
cites work: Simple Stochastic Games with Few Random Vertices Are Easy to Solve
cites work: Cyclic games and an algorithm to find minimax cycle means in directed graphs
cites work: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
cites work: Solving Simple Stochastic Games with Few Coin Toss Positions
cites work: Equilibrium points in n -person games
cites work: Non-cooperative games
cites work: Games for verification: Algorithmic issues
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Cyclical games with prohibitions
cites work: Stochastic Games with Perfect Information and Time Average Payoff
cites work: Q5611539
cites work: Extensions of two person zero sum games
cites work: Q4117607
cites work: Mean cost cyclical games
cites work: Q5417669
cites work: From Parity and Payoff Games to Linear Programming
cites work: Cyclic games and linear programming
cites work: The complexity of mean payoff games on graphs
DOI: 10.1007/S00453-017-0372-7
description: scientific article; zbMATH DE number 7000136