License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.29
URN: urn:nbn:de:0030-drops-95673
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9567/
Bruyère, Véronique ;
Hautem, Quentin ;
Raskin, Jean-François
Parameterized complexity of games with monotonically ordered omega-regular objectives
Abstract
In recent years, two-player zero-sum games with multiple objectives have received a lot of interest as a model for the synthesis of complex reactive systems. In this framework, Player 1 wins if he can ensure that all objectives are satisfied against any behavior of Player 2. When this is not possible to satisfy all the objectives at once, an alternative is to use some preorder on the objectives according to which subset of objectives Player 1 wants to satisfy. For example, it is often natural to provide more significance to one objective over another, a situation that can be modelled with lexicographically ordered objectives for instance. Inspired by recent work on concurrent games with multiple omega-regular objectives by Bouyer et al., we investigate in detail turned-based games with monotonically ordered and omega-regular objectives. We study the threshold problem which asks whether player 1 can ensure a payoff greater than or equal to a given threshold w.r.t. a given monotonic preorder. As the number of objectives is usually much smaller than the size of the game graph, we provide a parametric complexity analysis and we show that our threshold problem is in FPT for all monotonic preorders and all classical types of omega-regular objectives. We also provide polynomial time algorithms for Büchi, coBüchi and explicit Muller objectives for a large subclass of monotonic preorders that includes among others the lexicographic preorder. In the particular case of lexicographic preorder, we also study the complexity of computing the values and the memory requirements of optimal strategies.
BibTeX - Entry
@InProceedings{bruyre_et_al:LIPIcs:2018:9567,
author = {V{\'e}ronique Bruy{\`e}re and Quentin Hautem and Jean-Fran{\c{c}}ois Raskin},
title = {{Parameterized complexity of games with monotonically ordered omega-regular objectives}},
booktitle = {29th International Conference on Concurrency Theory (CONCUR 2018)},
pages = {29:1--29:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-087-3},
ISSN = {1868-8969},
year = {2018},
volume = {118},
editor = {Sven Schewe and Lijun Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9567},
URN = {urn:nbn:de:0030-drops-95673},
doi = {10.4230/LIPIcs.CONCUR.2018.29},
annote = {Keywords: two-player zero-sum games played on graphs, omega-regular objectives, ordered objectives, parameterized complexity}
}
|
Keywords: |
|
two-player zero-sum games played on graphs, omega-regular objectives, ordered objectives, parameterized complexity |
|
Collection: |
|
29th International Conference on Concurrency Theory (CONCUR 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
31.08.2018 |
