An Automata-Based Approach to Games with $ω$-Automatic Preferences
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912890579058688 |
|---|---|
| author | Bruyère, Véronique Filiot, Emmanuel Grandmont, Christophe Raskin, Jean-François |
| author_facet | Bruyère, Véronique Filiot, Emmanuel Grandmont, Christophe Raskin, Jean-François |
| contents | This paper studies multiplayer turn-based games on graphs in which player preferences are modeled as $ω$-automatic relations given by deterministic parity automata. This contrasts with most existing work, which focuses on specific reward functions. We conduct a computational analysis of these games, starting with the threshold problem in the antagonistic zero-sum case. As in classical games, we introduce the concept of value, defined here as the set of plays a player can guarantee to improve upon, relative to their preference relation. We show that this set is recognized by an alternating parity automaton APW of polynomial size. We also establish the computational complexity of several problems related to the concepts of value and optimal strategy, taking advantage of the $ω$-automatic characterization of value. Next, we shift to multiplayer games and Nash equilibria, and revisit the threshold problem in this context. Based on an APW construction again, we close complexity gaps left open in the literature, and additionally show that cooperative rational synthesis is $\mathsf{PSPACE}$-complete, while it becomes undecidable in the non-cooperative case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08549 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Automata-Based Approach to Games with $ω$-Automatic Preferences Bruyère, Véronique Filiot, Emmanuel Grandmont, Christophe Raskin, Jean-François Computer Science and Game Theory Formal Languages and Automata Theory This paper studies multiplayer turn-based games on graphs in which player preferences are modeled as $ω$-automatic relations given by deterministic parity automata. This contrasts with most existing work, which focuses on specific reward functions. We conduct a computational analysis of these games, starting with the threshold problem in the antagonistic zero-sum case. As in classical games, we introduce the concept of value, defined here as the set of plays a player can guarantee to improve upon, relative to their preference relation. We show that this set is recognized by an alternating parity automaton APW of polynomial size. We also establish the computational complexity of several problems related to the concepts of value and optimal strategy, taking advantage of the $ω$-automatic characterization of value. Next, we shift to multiplayer games and Nash equilibria, and revisit the threshold problem in this context. Based on an APW construction again, we close complexity gaps left open in the literature, and additionally show that cooperative rational synthesis is $\mathsf{PSPACE}$-complete, while it becomes undecidable in the non-cooperative case. |
| title | An Automata-Based Approach to Games with $ω$-Automatic Preferences |
| topic | Computer Science and Game Theory Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2602.08549 |