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

CREATORVéronique Bruyère, Jean-François Raskin, Alexis Reynouard, Marie Van Den Bogaard
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE197 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08547

Browse the full library · About the Tower of Babel