Algorithms for Equilibria in Concurrent Stopping Games
2026-07-27 • Computer Science and Game Theory
Computer Science and Game TheoryMultiagent Systems
AI summaryⓘ
The authors study multi-agent games where players act at the same time, focusing on whether certain types of stable solutions (Nash equilibria) with specified payoffs exist. They show that exactly deciding this is impossible (undecidable) even in simple cases, so they explore approximate solutions that can be found by an algorithm running in exponential time. They also examine a newer idea called extreme risk-sensitive equilibria, where players evaluate potential outcomes by best or worst payoffs, and prove the problem of finding such equilibria with certain payoffs is easier (NP-complete). Their work clarifies when these equilibrium problems can be practically solved.
Concurrent gamesNash equilibriumConstrained existence problemApproximate Nash equilibrium (ε-NE)Stopping gamesExtreme risk-sensitive equilibrium (XRSE)Computational complexityNP-completePSPACE-hardTurn-based games
Authors
Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini
Abstract
Concurrent games are a standard model for multi-agent systems, with Nash equilibrium as their central solution concept. The associated \emph{constrained existence problem}---does a game admit a Nash equilibrium whose expected payoff lies within a prescribed interval for every player?---is undecidable, and remains so even for 10-player \emph{stopping} games, in which a terminal state is reached almost surely under every strategy profile. We give two routes to tractability. We first relax exactness and consider the problem of approximate constrained existence problem, parametrised by $\varepsilon$-NE, which decides whether an \(\varepsilon\)-Nash equilibrium with the prescribed payoffs exists. The algorithm runs in exponential time, and only polynomially in the bit-size of \(\varepsilon\). We complement it with a \PSPACE-hardness lower bound that holds already for turn-based games, and for pure equilibria as well. We then relax the solution concept, turning to \emph{extreme risk-sensitive equilibria} (XRSE), recently introduced for turn-based stochastic games. Here the players are partitioned into optimists and pessimists, who evaluate a strategy profile by the best, respectively the worst, payoff attainable with positive probability, instead of the expected payoff. We prove that the constrained existence problem for XRSE is \NP-complete on concurrent games, as for turn-based games.