Equilibria
When studying multiplayer games, where the players' objectives may overlap, a natural question is to ask whether there exists a stable situation, where no player has an incentive to deviate. Such situations are called equilibria.
Nash equilibria
The most classical notion of equilibrium is the Nash equilibrium, where no player can improve their outcome by changing their own strategy, if the other players keep their strategies fixed. Nash equilibria were extensively studied in the literature. However, I contributed to this line of work with results about the complexity of Nash equilibria in energy and in discounted-sum games (MFCS 2023). More recently, we studied the complexity of stationary Nash equilibria in stochastic games, by proposing a new approximation algorithm (FSTTCS 2025).
- L. Brice, J.-F. Raskin, M. van den Bogaard, "Rational Verification and Checking for Nash and Subgame-perfect Equilibria in Graph Games", MFCS 2023 (ArXiv)
- A. Asadi, L. Brice, K. Chatterjee, K. S. Thejaswini, "ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games", FSTTCS 2025 (ArXiv)
Subgame-perfect equilibria
An significant part of my PhD focused on a refinement of Nash equilibria, called subgame-perfect equilibria (SPEs). Those are defined as Nash equilibria with the additional requirement that the strategies that the players plan to follow, after any possible history of the game, must also form a Nash equilibrium in the subgame. With J.-F. Raskin and M. van den Bogaard, we defined the negotiation function (LMCS 2023), a conceptual and algorithmic tool to characterise the set of SPE outcomes in a game. That lead to results about the complexity of SPEs in parity games (CSL 2022) and mean-payoff games (ICALP 2022). We also studied related rational verification problems in those games, as well as in energy and discounted-sum games (MFCS 2023).
- L. Brice, J.-F. Raskin, M. van den Bogaard, "Subgame-perfect Equilibria in Mean-payoff Games", CONCUR 2021 (ArXiv) and LMCS 2023 (ArXiv)
- L. Brice, J.-F. Raskin, M. van den Bogaard, "On the Complexity of SPEs in Parity Games", CSL 2022 (ArXiv)
- L. Brice, J.-F. Raskin, M. van den Bogaard, "The Complexity of SPEs in Mean-payoff Games", ICALP 2022 (ArXiv)
- L. Brice, J.-F. Raskin, M. van den Bogaard, "Rational Verification and Checking for Nash and Subgame-perfect Equilibria in Graph Games", MFCS 2023 (ArXiv)
Strong secure equilibria
With my PhD advisors and in collaboration with M. Sassolas and G. Scerri, we studied possible applications of game theory to the design of secure communication protocols. In that context, we introduced a new notion of equilibrium, called strong secure equilibrium (CSF 2025). A strong secure equilibrium is a strategy profile from which no coalition of players can deviate in a way that decreases the payoff of another player, without decreasing the payoff of any player in the coalition. We studied the complexity of those problems in multiplayer games with payoffs defined with a parity condition, or with an external parity automaton.
- L. Brice, J.-F. Raskin, M. Sassolas, G. Scerri, M. van den Bogaard, "Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents", CSF 2025 (ArXiv)
Risk-sensitive equilibria
In collaboration with T. Henzinger and K. Thejaswini, we studied a new notion of equilibrium, called risk-sensitive equilibrium (MFCS 2025). This concept is relevant in stochastic games, or when players are allowed to use randomised strategies. In such situation, one usually considers the expected payoff of a player, but that does not capture the risk that the player is willing to take. Risk-sensitive equilibria are defined from a partition of players, assuming that some are pessimists, and some optimists; they are strategy profiles from which no pessimist can improve their worst-case payoff, and no optimist can improve their best-case payoff.
- L. Brice, T. Henzinger, K. S. Thejaswini, "Finding equilibria: simpler for pessimists, simplest for optimists", MFCS 2025 (ArXiv)