3 Search Results for "Thomasset, Nathan"

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-dev.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
Invited Talk
DOI: 10.4230/LIPIcs.TIME.2019.3
On the Computation of Nash Equilibria in Games on Graphs (Invited Talk)

Authors: Patricia Bouyer

Published in: LIPIcs, Volume 147, 26th International Symposium on Temporal Representation and Reasoning (TIME 2019)

Abstract
In this talk, I will show how one can characterize and compute Nash equilibria in multiplayer games played on graphs. I will present in particular a construction, called the suspect game construction, which allows to reduce the computation of Nash equilibria to the computation of winning strategies in a two-player zero-sum game.
Cite as

Patricia Bouyer. On the Computation of Nash Equilibria in Games on Graphs (Invited Talk). In 26th International Symposium on Temporal Representation and Reasoning (TIME 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 147, pp. 3:1-3:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bouyer:LIPIcs.TIME.2019.3,
  author =	{Bouyer, Patricia},
  title =	{{On the Computation of Nash Equilibria in Games on Graphs}},
  booktitle =	{26th International Symposium on Temporal Representation and Reasoning (TIME 2019)},
  pages =	{3:1--3:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-127-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{147},
  editor =	{Gamper, Johann and Pinchinat, Sophie and Sciavicco, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2019.3},
  URN =		{urn:nbn:de:0030-drops-113616},
  doi =		{10.4230/LIPIcs.TIME.2019.3},
  annote =	{Keywords: Multiplayer games, Nash equilibria}
}
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-dev.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}
}
  • Refine by Author
  • 3 Bouyer, Patricia
  • 2 Thomasset, Nathan
  • 1 Le Roux, Stéphane

  • Refine by Classification
  • 3 Theory of computation → Verification by model checking
  • 2 Theory of computation
  • 2 Theory of computation → Solution concepts in game theory

  • Refine by Keyword
  • 2 Multiplayer games
  • 2 Nash equilibria
  • 1 Finite-memory winning strategies
  • 1 Hausdorff difference hierarchy
  • 1 Infinite trees
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact