Finding equilibria: easier for optimists, easiest for pessimists

Speaker:
Organiser:
Shibashis Guha
Date:
Wednesday, 3 Dec 2025, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
Category:
Abstract

In multiplayer games played on graphs, as soon as randomness is involved (because the game is stochastic or because the players are allowed to randomise their strategies), deciding the existence of a Nash equilibrium that satisfies a given constraint, for example such that the players' payoffs lie in specified intervals, is undecidable in all reasonable settings. However, these results rely on a definition of Nash equilibria that implies that each player intends to maximise their expected payoff, which is not always the most rational behaviour: their tolerance to risk may vary. In this talk, we consider the pessimistic risk measure, which interprets randomness by considering the worst possible scenario, and its dual, the optimistic risk measure. We define from those notions a new notion of equilibrium, the extreme risk-sensitive equilibrium, and show that the constrained existence problem of such an equilibrium is decidable.

Short Bio:
Léonard Brice recently completed a PhD in theoretical computer science in the Free university of Brussels, and is now starting a post-doc at the Institute of Science and Technology Austria, with Thomas Henzinger. His research focuses on multiplayer games, in particular games played on graphs, toward applications to multi-agent systems.