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

DOI10.4230/LIPICS.STACS.2014.199zbMATH Open1360.91042arXiv1309.5439OpenAlexW2962750855MaRDI QIDQ2965484FDOQ2965484

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

Publication date: 3 March 2017

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.

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

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

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)

Cited In (9)

• Percentile queries in multi-dimensional Markov decision processes
• Compositional strategy synthesis for stochastic games with multiple objectives
• Looking at mean-payoff and total-payoff through windows
• Markov automata with multiple objectives
• The Odds of Staying on Budget
• Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints
• Title not available (Why is that?)
• Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games

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)