2026-07-22T05:57:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17423 2024-03-06T10:59:43Z ddc:004 open_access

Dependency Matrices for Multiplayer Strategic Dependencies Bellier, Dylan Pinchinat, Sophie Schwarzentruber, François Temporal dependency Delay games Strategic reasoning Temporal logic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dylan Bellier and Sophie Pinchinat and François Schwarzentruber 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.31 urn:nbn:de:0030-drops-174230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.31 eng https://creativecommons.org/licenses/by/4.0/legalcode