3 octobre 2022

Catalin Dima (LACL)

Cooperative rational synthesis is the problem of computing a Nash equilibrium that satisfies the objective of a designated player, the “controller”. In this paper, we tackle this problem in the presence of several resources, where each action may increase or decrease some of the resources. We investigate the problem of synthesizing the controller strategy such that there exists an individually rational behavior of all the agents that satisfies the controller’s objective and does not deplete any of the resources.

We consider two types of agents: careless and careful. Careless agents only care for their temporal objective, while careful agents also pay attention not to deplete the system’s resource. We show that the problem is undecidable with at least two resources, and decidable for either a single resource or in the presence of a fixed upper bound on all the resources, and study the complexity for the decidable cases.