Paper Info
Title
Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games.
Abstract
Classical analysis of two-player quantitative games involves an adversary (modeling the environment of the system) which is purely antagonistic and asks for strict guarantees while Markov decision processes model systems facing 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. We consider both the mean-payoff value problem and the shortest path problem. 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.
Year
DOI
Venue
2014
10.4230/LIPIcs.STACS.2014.199
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
two-player games on graphs,Markov decision processes,quantitative objectives,synthesis,worst-case and expected value,mean-payoff,shortest path
Conference
25
ISSN
Citations 
PageRank 
1868-8969
9
0.51
References 
Authors
19
4
Name
Order
Citations
PageRank
Véronique Bruyère142943.59
Emmanuel Filiot221724.98
Mickael Randour3748.36
Jean-François Raskin41735100.15