A note on the approximation of mean-payoff games

DOI10.1016/J.IPL.2014.02.010MaRDI QIDQ2446598zbMATH OpenOpenAlexFDO

Authors Raffaella Gentilini

Publication date 17 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.02.010

zbMATH Keywords

approximation algorithmsmean-payoff games

Mathematics Subject Classification ID

Approximation algorithms (68W25) 2-person games (91A05) Games involving graphs (91A43)

Recommendations

• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• The complexity of mean payoff games on graphs
• Potential theory for mean payoff games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Faster algorithms for mean-payoff games

Cites work

• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Automated analysis of real-time scheduling using graph games
• Better Quality in Synthesis through Quantitative Objectives
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Cyclical games with prohibitions
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Extensions of two person zero sum games
• Faster algorithms for mean-payoff games
• From Parity and Payoff Games to Linear Programming
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Mean cost cyclical games
• On canonical forms for zero-sum stochastic mean payoff games
• On the equilibria of alternating move games
• Optimal search for rationals
• Positional strategies for mean payoff games
• Quantitative Languages
• Quantitative Languages Defined by Functional Automata
• Results on the propositional \(\mu\)-calculus
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Stochastic mean payoff games: smoothed analysis and approximation schemes
• The complexity of mean payoff games on graphs
• The Cost of Traveling between Languages

Cited in

(5)

• Looking at mean payoff through foggy windows
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• A note on contribution games with loss functions
• Some remarks on mean field games
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria

This page was built for publication: A note on the approximation of mean-payoff games

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