License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.199
URN: urn:nbn:de:0030-drops-44589
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4458/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
16.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{bruyre_et_al:LIPIcs:2014:4458,
  author =	{V{\'e}ronique Bruy{\`e}re and Emmanuel Filiot and Mickael Randour and Jean-Fran{\c{c}}ois Raskin},
  title =	{{Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{199--213},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4458},
  URN =		{urn:nbn:de:0030-drops-44589},
  doi =		{10.4230/LIPIcs.STACS.2014.199},
  annote =	{Keywords: two-player games on graphs, Markov decision processes, quantitative objectives, synthesis, worst-case and expected value, mean-payoff, shortest path}
}

Keywords: two-player games on graphs, Markov decision processes, quantitative objectives, synthesis, worst-case and expected value, mean-payoff, shortest path
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI