License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.34
URN: urn:nbn:de:0030-drops-170973
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17097/
Go to the corresponding LIPIcs Volume Portal

Almagor, Shaull ; Guendelman, Shai

Concurrent Games with Multiple Topologies

pdf-format:
LIPIcs-CONCUR-2022-34.pdf (0.8 MB)

Abstract

Concurrent multi-player games with ω-regular objectives are a standard model for systems that consist of several interacting components, each with its own objective. The standard solution concept for such games is Nash Equilibrium, which is a "stable" strategy profile for the players.
In many settings, the system is not fully observable by the interacting components, e.g., due to internal variables. Then, the interaction is modelled by a partial information game. Unfortunately, the problem of whether a partial information game has an NE is not known to be decidable. A particular setting of partial information arises naturally when processes are assigned IDs by the system, but these IDs are not known to the processes. Then, the processes have full information about the state of the system, but are uncertain of the effect of their actions on the transitions.
We generalize the setting above and introduce Multi-Topology Games (MTGs) - concurrent games with several possible topologies, where the players do not know which topology is actually used. We show that extending the concept of NE to these games can take several forms. To this end, we propose two notions of NE: Conservative NE, in which a player deviates if she can strictly add topologies to her winning set, and Greedy NE, where she deviates if she can win in a previously-losing topology. We study the properties of these NE, and show that the problem of whether a game admits them is decidable.

BibTeX - Entry

@InProceedings{almagor_et_al:LIPIcs.CONCUR.2022.34,
  author =	{Almagor, Shaull and Guendelman, Shai},
  title =	{{Concurrent Games with Multiple Topologies}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17097},
  URN =		{urn:nbn:de:0030-drops-170973},
  doi =		{10.4230/LIPIcs.CONCUR.2022.34},
  annote =	{Keywords: Concurrent games, Nash Equilibrium, Symmetry, Partial information}
}

Keywords: Concurrent games, Nash Equilibrium, Symmetry, Partial information
Collection: 33rd International Conference on Concurrency Theory (CONCUR 2022)
Issue Date: 2022
Date of publication: 06.09.2022

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