From Synthesis to Rational Synthesis: a Game-Theoretic Approach for Multi-Agent Systems
Date: Tue 9 Nov 2021
Speaker: Giuseppe Perelli
Title: From Synthesis to Rational Synthesis: a Game-Theoretic Approach for Multi-Agent Systems
Abstract: n Formal Methods, Synthesis is the problem of programming an intelligent agent and its interaction with the environment in a way that its behaviour is correct by construction, that is, it fulfills a given task/specification no matter how the environment reacts. The solution to this problem can be interpreted as the winning strategy in a suitably defined formal game.
Rational Synthesis is a recent evolution of Synthesis, in which the setting is not viewed as two monolithic blocks acting adversarially to each other, but rather a multitude of agents, each of them given with their own specification. This comes in handy to formally reason about Multi-Agent Systems (MAS): a well-established research area concerned with modeling actual scenarios for self-driving vehicles, smart factories, multi-robot systems in logistics, distributed computing, financial technology, and many other fields.
In terms of games, problems in MAS correspond to no longer maximizing an individual payoff against all possible environment's behaviours (two-player zero-sum), but rather synthesising a strategy profile that is in some sort of equilibrium, i.e., prevents agents to improve the payoff by deviating from it (multi-player nonzero-sum).
In this short seminar, I will give an overview of the Synthesis and Rational Synthesis problems, presenting the results and developments I contributed to the area, and showed how the game-theoretic setting comes in very handy for representing and solving them. Finally, I will outline some current and future directions I am taking within the field.