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.MFCS.2019.9
URN: urn:nbn:de:0030-drops-109532
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10953/
Go to the corresponding LIPIcs Volume Portal

Bouyer, Patricia ; Thomasset, Nathan

Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism

pdf-format:
LIPIcs-MFCS-2019-9.pdf (0.5 MB)

Abstract

We study pure Nash equilibria in infinite-duration games on graphs, with partial visibility of actions but communication (based on a graph) among the players. We show that a simple communication mechanism consisting in reporting the deviator when seeing it and propagating this information is sufficient for characterizing Nash equilibria. We propose an epistemic game construction, which conveniently records important information about the knowledge of the players. With this abstraction, we are able to characterize Nash equilibria which follow the simple communication pattern via winning strategies. We finally discuss the size of the construction, which would allow efficient algorithmic solutions to compute Nash equilibria in the original game.

BibTeX - Entry

@InProceedings{bouyer_et_al:LIPIcs:2019:10953,
  author =	{Patricia Bouyer and Nathan Thomasset},
  title =	{{Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10953},
  URN =		{urn:nbn:de:0030-drops-109532},
  doi =		{10.4230/LIPIcs.MFCS.2019.9},
  annote =	{Keywords: Multiplayer games, Nash equilibria, partial information}
}

Keywords: Multiplayer games, Nash equilibria, partial information
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

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