The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and omega-regular Objectives
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913941640183808 |
|---|---|
| author | Bruyère, Véronique Raskin, Jean-François Reynouard, Alexis Bogaard, Marie Van Den |
| author_facet | Bruyère, Véronique Raskin, Jean-François Reynouard, Alexis Bogaard, Marie Van Den |
| contents | This paper studies the rational synthesis problem for multi-player games played on graphs when rational players are following subgame perfect equilibria. In these games, one player, the system, declares his strategy upfront, and the other players, composing the environment, then rationally respond by playing strategies forming a subgame perfect equilibrium. We study the complexity of the rational synthesis problem when the players have ω-regular objectives encoded as parity objectives. Our algorithm is based on an encoding into a three-player game with imperfect information, showing that the problem is in 2ExpTime. When the number of environment players is fixed, the problem is in ExpTime and is NP- and coNP-hard. Moreover, for a fixed number of players and reachability objectives, we get a polynomial algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08547 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and omega-regular Objectives Bruyère, Véronique Raskin, Jean-François Reynouard, Alexis Bogaard, Marie Van Den Computer Science and Game Theory This paper studies the rational synthesis problem for multi-player games played on graphs when rational players are following subgame perfect equilibria. In these games, one player, the system, declares his strategy upfront, and the other players, composing the environment, then rationally respond by playing strategies forming a subgame perfect equilibrium. We study the complexity of the rational synthesis problem when the players have ω-regular objectives encoded as parity objectives. Our algorithm is based on an encoding into a three-player game with imperfect information, showing that the problem is in 2ExpTime. When the number of environment players is fixed, the problem is in ExpTime and is NP- and coNP-hard. Moreover, for a fixed number of players and reachability objectives, we get a polynomial algorithm. |
| title | The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and omega-regular Objectives |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2412.08547 |