1 Search Results for "Bellier, Dylan"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.31
Dependency Matrices for Multiplayer Strategic Dependencies

Authors: Dylan Bellier, Sophie Pinchinat, and François Schwarzentruber

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
In multi-player games, players take their decisions on the basis of their knowledge about what other players have done, or currently do, or even, in some cases, will do. An ability to reason in games with temporal dependencies between players' decisions is a challenging topic, in particular because it involves imperfect information. In this work, we propose a theoretical framework based on dependency matrices that includes many instances of strategic dependencies in multi-player imperfect information games. For our framework to be well-defined, we get inspiration from quantified linear-time logic where each player has to label the timeline with truth values of the propositional variable she owns. We study the problem of the existence of a winning strategy for a coalition of players, show it is undecidable in general, and exhibit an interesting subclass of dependency matrices that makes the problem decidable: the class of perfect-information dependency matrices.
Cite as

Dylan Bellier, Sophie Pinchinat, and François Schwarzentruber. Dependency Matrices for Multiplayer Strategic Dependencies. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bellier_et_al:LIPIcs.FSTTCS.2022.31,
  author =	{Bellier, Dylan and Pinchinat, Sophie and Schwarzentruber, Fran\c{c}ois},
  title =	{{Dependency Matrices for Multiplayer Strategic Dependencies}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{31:1--31:21},
  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 =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.31},
  URN =		{urn:nbn:de:0030-drops-174230},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.31},
  annote =	{Keywords: Temporal dependency, Delay games, Strategic reasoning, Temporal logic}
}
  • Refine by Author
  • 1 Bellier, Dylan
  • 1 Pinchinat, Sophie
  • 1 Schwarzentruber, François

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Modal and temporal logics

  • Refine by Keyword
  • 1 Delay games
  • 1 Strategic reasoning
  • 1 Temporal dependency
  • 1 Temporal logic

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 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