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.CSL.2018.10
URN: urn:nbn:de:0030-drops-96774
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9677/
Go to the corresponding LIPIcs Volume Portal

Basset, Nicolas ; Jecker, Ismaël ; Pauly, Arno ; Raskin, Jean-François ; Van den Bogaard, Marie

Beyond Admissibility: Dominance Between Chains of Strategies

pdf-format:
LIPIcs-CSL-2018-10.pdf (0.6 MB)

Abstract

Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case.
We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.

BibTeX - Entry

@InProceedings{basset_et_al:LIPIcs:2018:9677,
  author =	{Nicolas Basset and Isma{\"e}l Jecker and Arno Pauly and Jean-Fran{\c{c}}ois Raskin and Marie Van den Bogaard},
  title =	{{Beyond Admissibility: Dominance Between Chains of Strategies}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9677},
  URN =		{urn:nbn:de:0030-drops-96774},
  doi =		{10.4230/LIPIcs.CSL.2018.10},
  annote =	{Keywords: dominated strategies, admissible strategies, games played on finite graphs, reactive synthesis, reachability games, safety games, cofinal, order theor}
}

Keywords: dominated strategies, admissible strategies, games played on finite graphs, reactive synthesis, reachability games, safety games, cofinal, order theor
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

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