License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.31
URN: urn:nbn:de:0030-drops-174230
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17423/
Bellier, Dylan ;
Pinchinat, Sophie ;
Schwarzentruber, François
Dependency Matrices for Multiplayer Strategic Dependencies
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.
BibTeX - Entry
@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.dagstuhl.de/opus/volltexte/2022/17423},
URN = {urn:nbn:de:0030-drops-174230},
doi = {10.4230/LIPIcs.FSTTCS.2022.31},
annote = {Keywords: Temporal dependency, Delay games, Strategic reasoning, Temporal logic}
}
