DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2022.8

Finite-Memory Strategies in Two-Player Infinite Games

Authors: Patricia Bouyer, Stéphane Le Roux, and Nathan Thomasset

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract

We study infinite two-player win/lose games (A,B,W) where A,B are finite and W ⊆ (A×B)^ω. At each round Player 1 and Player 2 concurrently choose one action in A and B, respectively. Player 1 wins iff the generated sequence is in W. Each history h ∈ (A×B)^* induces a game (A,B,W_h) with W_h : = {ρ ∈ (A×B)^ω ∣ h ρ ∈ W}. We show the following: if W is in Δ⁰₂ (for the usual topology), if the inclusion relation induces a well partial order on the W_h’s, and if Player 1 has a winning strategy, then she has a finite-memory winning strategy. Our proof relies on inductive descriptions of set complexity, such as the Hausdorff difference hierarchy of the open sets. Examples in Σ⁰₂ and Π⁰₂ show some tightness of our result. Our result can be translated to games on finite graphs: e.g. finite-memory determinacy of multi-energy games is a direct corollary, whereas it does not follow from recent general results on finite memory strategies.

Cite as

Patricia Bouyer, Stéphane Le Roux, and Nathan Thomasset. Finite-Memory Strategies in Two-Player Infinite Games. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.CSL.2022.8,
  author =	{Bouyer, Patricia and Le Roux, St\'{e}phane and Thomasset, Nathan},
  title =	{{Finite-Memory Strategies in Two-Player Infinite Games}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.8},
  URN =		{urn:nbn:de:0030-drops-157285},
  doi =		{10.4230/LIPIcs.CSL.2022.8},
  annote =	{Keywords: Two-player win/lose games, Infinite trees, Finite-memory winning strategies, Well partial orders, Hausdorff difference hierarchy}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2019.9

Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism

Authors: Patricia Bouyer and Nathan Thomasset

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

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.

Cite as

Patricia Bouyer and Nathan Thomasset. Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.MFCS.2019.9,
  author =	{Bouyer, Patricia and Thomasset, Nathan},
  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 =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.9},
  URN =		{urn:nbn:de:0030-drops-109532},
  doi =		{10.4230/LIPIcs.MFCS.2019.9},
  annote =	{Keywords: Multiplayer games, Nash equilibria, partial information}
}

Search Results

Documents authored by Thomasset, Nathan

Finite-Memory Strategies in Two-Player Infinite Games

Abstract

Cite as

Nash Equilibria in Games over Graphs Equipped with a Communication Mechanism

Abstract

Cite as

Thanks for your feedback!

Could not send message