Stability in graphs and games

DOI10.4230/LIPICS.CONCUR.2016.10MaRDI QIDQ4608661zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Vojtech Forejt, Petr Novotný, Antonin Kučera

Publication date 21 March 2018

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

zbMATH Keywords

gamesmean-payoffstabilitywindow objectives

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Games involving graphs (91A43)

Abstract: We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system

Recommendations

• The complexity of mean payoff games on graphs
• Perfect-information stochastic mean-payoff parity games
• Reduction of stochastic parity to stochastic mean-payoff games
• The complexity of solving stochastic games on graphs
• Faster algorithms for mean-payoff parity games

Cited in

(2)

• Timed games with bounded window parity objectives
• Life is random, time is not: Markov decision processes with window objectives

This page was built for publication: Stability in graphs and games

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