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.CSL.2022.10
URN: urn:nbn:de:0030-drops-157306
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15730/
Brice, Léonard ;
Raskin, Jean-François ;
van den Bogaard, Marie
On the Complexity of SPEs in Parity Games
Abstract
We study the complexity of problems related to subgame-perfect equilibria (SPEs) in infinite duration non zero-sum multiplayer games played on finite graphs with parity objectives. We present new complexity results that close gaps in the literature. Our techniques are based on a recent characterization of SPEs in prefix-independent games that is grounded on the notions of requirements and negotiation, and according to which the plays supported by SPEs are exactly the plays consistent with the requirement that is the least fixed point of the negotiation function. The new results are as follows. First, checking that a given requirement is a fixed point of the negotiation function is an NP-complete problem. Second, we show that the SPE constrained existence problem is NP-complete, this problem was previously known to be ExpTime-easy and NP-hard. Third, the SPE constrained existence problem is fixed-parameter tractable when the number of players and of colors are parameters. Fourth, deciding whether some requirement is the least fixed point of the negotiation function is complete for the second level of the Boolean hierarchy. Finally, the SPE-verification problem - that is, the problem of deciding whether there exists a play supported by a SPE that satisfies some LTL formula - is PSpace-complete, this problem was known to be ExpTime-easy and PSpace-hard.
BibTeX - Entry
@InProceedings{brice_et_al:LIPIcs.CSL.2022.10,
author = {Brice, L\'{e}onard and Raskin, Jean-Fran\c{c}ois and van den Bogaard, Marie},
title = {{On the Complexity of SPEs in Parity Games}},
booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
pages = {10:1--10:17},
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/opus/volltexte/2022/15730},
URN = {urn:nbn:de:0030-drops-157306},
doi = {10.4230/LIPIcs.CSL.2022.10},
annote = {Keywords: Games on graphs, subgame-perfect equilibria, parity objectives}
}
|
Keywords: |
|
Games on graphs, subgame-perfect equilibria, parity objectives |
|
Collection: |
|
30th EACSL Annual Conference on Computer Science Logic (CSL 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
27.01.2022 |
