The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and ω \omega -regular Objectives
Véronique Bruyère, Jean-François Raskin, Alexis Reynouard, Marie Van Den Bogaard · 2024
Read The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and ω \omega -regular Objectives by Véronique Bruyère, Jean-François Raskin, Alexis Reynouard, Marie Van Den Bogaard (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08547.txt.
Introduction
Véronique Bruyère, Jean-François Raskin, Alexis Reynouard, and Marie Van Den Bogaard wrote this paper in two thousand twenty-four. It studies how to build a system that holds its own when rational foes reply with subgame perfect play.
In these graph games one player, the system, states its plan first. The rest, the environment, then answer with strategies in subgame perfect equilibrium. Goals are ω-regular, given as parity conditions. The authors encode the task as a three-player game with hidden facts, which puts the cost in double-exponential time. With the foe count fixed, the cost drops a class, though the task stays hard both ways. For reach goals with fixed players, a fast method exists.
Catalog record
| CREATOR | Véronique Bruyère, Jean-François Raskin, Alexis Reynouard, Marie Van Den Bogaard |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 197 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08547