Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games

DOI10.4230/LIPICS.STACS.2014.199MaRDI QIDQ2965484zbMATHOpenAlexFDO

Authors Véronique Bruyère, Emmanuel Filiot, Mickael Randour, Jean-François Raskin

Publication date 3 March 2017

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

zbMATH Keywords

synthesisshortest pathMarkov decision processesmean-payoffworst-case and expected valuequantitative objectivestwo-player games on graphs

Mathematics Subject Classification ID

2-person games (91A05) Markov and semi-Markov decision processes (90C40) Games involving graphs (91A43)

Abstract: We extend the quantitative synthesis framework by going beyond the worst-case. On the one hand, classical analysis of two-player games involves an adversary (modeling the environment of the system) which is purely antagonistic and asks for strict guarantees. On the other hand, stochastic models like Markov decision processes represent situations where the system is faced to a purely randomized environment: the aim is then to optimize the expected payoff, with no guarantee on individual outcomes. We introduce the beyond worst-case synthesis problem, which is to construct strategies that guarantee some quantitative requirement in the worst-case while providing an higher expected value against a particular stochastic model of the environment given as input. This problem is relevant to produce system controllers that provide nice expected performance in the everyday situation while ensuring a strict (but relaxed) performance threshold even in the event of very bad (while unlikely) circumstances. We study the beyond worst-case synthesis problem for two important quantitative settings: the mean-payoff and the shortest path. In both cases, we show how to decide the existence of finite-memory strategies satisfying the problem and how to synthesize one if one exists. We establish algorithms and we study complexity bounds and memory requirements.

Recommendations

• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games
• On equilibria in quantitative games with reachability/safety objectives
• Quantitative verification and strategy synthesis for stochastic games
• Equilibria in quantitative reachability games
• On satisficing in quantitative games
• scientific article; zbMATH DE number 3991306
• On (Subgame Perfect) Secure Equilibrium in Quantitative Reachability Games
• Expectations or guarantees? I want it all! A crossroad between games and MDPs
• Mathematical Foundations of Computer Science 2003
• Quantitative games under failures

Cited in

(14)

• Threshold constraints with guarantees for parity objectives in Markov decision processes
• On satisficing in quantitative games
• Expectations or guarantees? I want it all! A crossroad between games and MDPs
• QUASY: quantitative synthesis tool
• Percentile queries in multi-dimensional Markov decision processes
• Learning-based mean-payoff optimization in an unknown MDP under omega-regular constraints
• The odds of staying on budget
• Looking at mean-payoff and total-payoff through windows
• scientific article; zbMATH DE number 7561341 (Why is no real title available?)
• Multidimensional beyond worst-case and almost-sure problems for mean-payoff objectives
• Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
• Minimizing expected cost under hard Boolean constraints, with applications to quantitative synthesis
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games
• Compositional strategy synthesis for stochastic games with multiple objectives

This page was built for publication: Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games

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