RECORD
Parameterized complexity of games with monotonically ordered {\omega}-regular objectives
Computer Science and Game Theory · Submitted 19 Jul 2017
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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\"uchi, coB\"uchi 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | In this framework, Player 1 wins if he can ensure that all objectives are satisfied against any behavior of Player 2. | background 1.00 | 0.06 | 0.02 | asserted 1.00 |
| s2 | 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. | background 0.99 | 0.05 | 0.02 | asserted 0.70 |
| s3 | 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. | background 1.00 | 0.04 | 0.02 | hedged possibility 0.59 |
| s4 | 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. | contribution 0.90 | 0.68 | 0.04 | asserted 0.94 |
| s5 | 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. | contribution 0.91 | 0.54 | 0.09 | asserted 0.71 |
| s6 | 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. | result 0.87 | 0.96 | 0.76 | asserted 1.00 |
| s7 | We also provide polynomial time algorithms for B\"uchi, coB\"uchi and explicit Muller objectives for a large subclass of monotonic preorders that includes among others the lexicographic preorder. | result 0.86 | 0.96 | 0.15 | asserted 1.00 |
| s8 | In the particular case of lexicographic preorder, we also study the complexity of computing the values and the memory requirements of optimal strategies. | contribution 0.98 | 0.93 | 0.06 | asserted 0.93 |
What was examined, and what was not
- arXiv listing abstract v4
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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\"uchi, coB\"uchi 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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.