Highlights Conference 2024 Conference Abstract
Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents
- Mathieu Sassolas
In the modeling of fair exchange protocols between several agents, the intended behavior of each agent should yield an execution where everyone obtains all the messages (e. g. signatures on a contract). Malicious agents may however try to prevent others to reach their goals, as long as they themselves do achieve their objective. Furthermore, nothing prevents several agents to team up together to the detriment of another. In this presentation, we argue that a "safe" protocol can be adequately be modeled using the concept of Strong Secure Equilibria (SSE): Strong because it is immune to a coalition of agents, and Secure because agents would harm others even if they get no benefit from it, as long as themselves are not harmed. Under the assumption that agents are rational and would not discard their benefit to harm others, no one should deviate from the intended behavior. We study SSE in the context of games on graphs when the objective of each player is given by an $\omega$-regular language. We are concerned with two (groups of) problems: checking whether a given set of strategy profiles only contains SSEs, and deciding the existence of an SSE profile. Several variants are studied depending on how objectives and strategy profiles are provided. We provide tight complexity bounds and provide complexities for a fixed number of players. This presentation is based on submitted joint work with Léonard Brice (ULB), Jean-François Raskin (ULB), Guillaume Scerri (ENS Paris-Saclay), and Marie Van Den Bogaard (UGE).