Rational Synthesis Under Imperfect Information

Authors: Emmanuel Filiot, Raffaella Gentilini and Jean-Francois Raskin

Paper Information

Title:Rational Synthesis Under Imperfect Information
Authors:Emmanuel Filiot, Raffaella Gentilini and Jean-Francois Raskin
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:N player games, non-zero sum games, Nash equilibrium, Rational synthesis

ABSTRACT. In this paper, we study the rational synthesis problem for multi-player non zero-sum games played on finite graphs for omega-regular objectives. Rationality is formalized by the concept of Nash equilibrium (NE). Contrary to previous works, we consider in this work the more general and more practically relevant case where players are imperfectly informed. In sharp contrast with the perfect information case, NE are not guaranteed to exist in this more general setting. This motivates the study of the NE existence problem. We show that this problem is ExpTime-C for parity objectives in the two-player case (even if both players are imperfectly informed) and undecidable for more than 2 players. We then study the rational synthesis problem and show that the problem is also ExpTime-C for two imperfectly informed players and undecidable for more than 3 players. As the rational synthesis problem considers a system (Player 0) playing against a rational environment (composed of k players), we also consider the natural case where only Player 0 is imperfectly informed about the state of the environment (and the environment is considered as perfectly informed). In this case, we show that the ExpTime-C result holds when k is arbitrary but fixed. We also analyse the complexity when k is part of the input.

Talk:Jul 09 14:40 (Session 49D)