Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Bordais, Benjamin; Bouyer, Patricia; Le Roux, Stéphane License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-174258

; ;

Playing (Almost-)Optimally in Concurrent Büchi and Co-Büchi Games



We study two-player concurrent stochastic games on finite graphs, with Büchi and co-Büchi objectives. The goal of the first player is to maximize the probability of satisfying the given objective. Following Martin’s determinacy theorem for Blackwell games, we know that such games have a value. Natural questions are then: does there exist an optimal strategy, that is, a strategy achieving the value of the game? what is the memory required for playing (almost-)optimally?
The situation is rather simple to describe for turn-based games, where positional pure strategies suffice to play optimally in games with parity objectives. Concurrency makes the situation intricate and heterogeneous. For most ω-regular objectives, there do indeed not exist optimal strategies in general. For some objectives (that we will mention), infinite memory might also be required for playing optimally or almost-optimally.
We also provide characterizations of local interactions of the players to ensure positionality of (almost-)optimal strategies for Büchi and co-Büchi objectives. This characterization relies on properties of game forms underpinning the formalism for defining local interactions of the two players. These well-behaved game forms are like elementary bricks which, when they behave well in isolation, can be assembled in graph games and ensure the good property for the whole game.

BibTeX - Entry

  author =	{Bordais, Benjamin and Bouyer, Patricia and Le Roux, St\'{e}phane},
  title =	{{Playing (Almost-)Optimally in Concurrent B\"{u}chi and Co-B\"{u}chi Games}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-174258},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.33},
  annote =	{Keywords: Concurrent Games, Optimal Strategies, B\"{u}chi Objective, co-B\"{u}chi Objective}

Keywords: Concurrent Games, Optimal Strategies, Büchi Objective, co-Büchi Objective
Seminar: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue date: 2022
Date of publication: 14.12.2022

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