Reactive synthesis without regret

DOI10.1007/S00236-016-0268-ZzbMATH Open1364.68263arXiv1504.01708OpenAlexW2964263597MaRDI QIDQ520338FDOQ520338

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

Publication date: 3 April 2017

Published in: Acta Informatica (Search for Journal in Brave)

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. We also establish relations between the latter version and other problems studied in the literature.

Full work available at URL: https://arxiv.org/abs/1504.01708

Recommendations

• Reactive Synthesis Without Regret
• Minimizing regret in discounted-sum games
• Iterated regret minimization in game graphs
• scientific article; zbMATH DE number 1944045
• On the synthesis of strategies in infinite games

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites Work

• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Regret in Decision Making under Uncertainty
• Model Checking Probabilistic Timed Automata with One or Two Clocks
• Shortest paths without a map
• Positional strategies for mean payoff games
• Synthesizing robust systems
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Title not available (Why is that?)
• From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
• Generalized mean-payoff and energy games
• Mean-Payoff Games with Partial-Observation
• Energy and Mean-Payoff Games with Imperfect Information
• Reasoning about online algorithms with weighted automata
• Quantitative languages
• Solving Games Without Determinization
• Faster algorithms for mean-payoff games
• The disjoint shortest paths problem
• Iterated Regret Minimization in Game Graphs
• First-cycle games
• Doomsday equilibria for omega-regular games
• Exact and Approximate Determinization of Discounted-Sum Automata
• Iterated regret minimization: a new solution concept

Cited In (8)

• Token Games and History-Deterministic Quantitative-Automata
• A framework for the competitive analysis of model predictive controllers
• On the comparison of discounted-sum automata with multiple discount factors
• Adapting to the behavior of environments with bounded memory
• Title not available (Why is that?)
• Reactive Synthesis Without Regret
• Quantitative vs. weighted automata
• Explainable Reactive Synthesis

This page was built for publication: Reactive synthesis without regret

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520338)