文章基本信息

标题：Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
本地全文：下载
作者：V{\'e}ronique Bruy{\`e}re ; Emmanuel Filiot ; Mickael Randour 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：25
页码：199-213
DOI：10.4230/LIPIcs.STACS.2014.199
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：two-player games on graphs; Markov decision processes; quantitative objectives; synthesis; worst-case and expected value; mean-payoff; shortest path