We are happy to present Léonard Brice’s talk titled “Finding equilibria - simpler for pessimists, simplest for optimists”.
In this talk, we consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined considering that every player seeks to maximize their expected payoff, without considering their aversion or tolerance to risk.
We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature, albeit not in multiplayer settings, is the entropic risk measure, where each player has a real parameter that captures their risk-averseness. We introduce the extreme risk measure, which corresponds to the extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists.
We argue that it is particularly relevant in computer-related applications, as they can model interactions between secure systems and potential hackers. We prove that RSEs defined with such a risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for this risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players.
Léonard Brice is a PhD student in the Free University of Brussels, with Jean-François Raskin and Marie van den Bogaard. His researches revolve around verification and game theory, especially algorithms for equilibria in multiplayer graph games.