首页    期刊浏览 2024年11月23日 星期六
登录注册

文章基本信息

  • 标题:Reactive Synthesis Without Regret
  • 本地全文:下载
  • 作者:Paul Hunter ; Guillermo A. P{\'e}rez ; Jean-Fran{\c{c}}ois Raskin
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:42
  • 页码:114-127
  • DOI:10.4230/LIPIcs.CONCUR.2015.114
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Quantitative games; regret; verification; synthesis; game theory
国家哲学社会科学文献中心版权所有