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

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

doi:10.4230/LIPIcs.STACS.2014.199

Document

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

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

Part of: Volume: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-03-05

PDF

File

PDF

LIPIcs.STACS.2014.199.pdf

Filesize: 0.82 MB
15 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2014.199
URN: urn:nbn:de:0030-drops-44589

Subject Classification

Keywords

two-player games on graphs
Markov decision processes
quantitative objectives
synthesis
worst-case and expected value
mean-payoff
shortest path

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Véronique Bruyère, Emmanuel Filiot, Mickael Randour, and Jean-François Raskin. Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 199-213, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.STACS.2014.199

Author Details

Véronique Bruyère

Emmanuel Filiot

Mickael Randour

Jean-François Raskin

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail