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.CONCUR.2015.114
URN: urn:nbn:de:0030-drops-53675
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5367/
Go to the corresponding LIPIcs Volume Portal

Hunter, Paul ; Pérez, Guillermo A. ; Raskin, Jean-François

Reactive Synthesis Without Regret

pdf-format:
7.pdf (0.5 MB)

Abstract

Two-player zero-sum games of infinite duration and their quantitative versions are used in verification to model the interaction between a controller (Eve) and its environment (Adam). The question usually addressed is that of the existence (and computability) of a strategy for Eve that can maximize her payoff against any strategy of Adam. In this work, we are interested in strategies of Eve that minimize her regret, i.e. strategies that minimize the difference between her actual payoff and the payoff she could have achieved if she had known the strategy of Adam in advance. We give algorithms to compute the strategies of Eve that ensure minimal regret against an adversary whose choice of strategy is (i) unrestricted, (ii) limited to positional strategies, or (iii) limited to word strategies, and show that the two last cases have natural modelling applications. We also show that our notion of regret minimization in which Adam is limited to word strategies generalizes the notion of good for games introduced by Henzinger and Piterman, and is related to the notion of determinization by pruning due to Aminof, Kupferman and Lampert.

BibTeX - Entry

@InProceedings{hunter_et_al:LIPIcs:2015:5367,
  author =	{Paul Hunter and Guillermo A. P{\'e}rez and Jean-Fran{\c{c}}ois Raskin},
  title =	{{Reactive Synthesis Without Regret}},
  booktitle =	{26th International Conference on Concurrency Theory (CONCUR 2015)},
  pages =	{114--127},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-91-0},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{42},
  editor =	{Luca Aceto and David de Frutos Escrig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5367},
  URN =		{urn:nbn:de:0030-drops-53675},
  doi =		{10.4230/LIPIcs.CONCUR.2015.114},
  annote =	{Keywords: Quantitative games, regret, verification, synthesis, game theory}
}

Keywords: Quantitative games, regret, verification, synthesis, game theory
Collection: 26th International Conference on Concurrency Theory (CONCUR 2015)
Issue Date: 2015
Date of publication: 26.08.2015

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