Finding equilibria: simpler for pessimists, simplest for optimists

Léonard Brice, Thomas A. Henzinger, K. S. Thejaswini

Introduction

In multi-agent stochastic systems—ranging from cyber-physical infrastructure to distributed software—agents rarely act with the perfect "rationality" of maximizing expected value. Instead, they exhibit varying risk appetites. A safety-critical system component is often designed to be risk-averse (pessimistic), while a malicious actor or a high-reward seeker might be risk-seeking (optimistic).

Traditionally, these behaviors are modeled using Entropic Risk (ER), which uses a parameter $\rho$ to scale between optimism and pessimism. However, this paper identifies a fundamental barrier: for multi-player games, determining if an equilibrium exists within a specific reward range (the constrained existence problem) is undecidable. To overcome this, the authors introduce Extreme Risk (XR), a qualitative measure that captures the essence of human-like risk perception while remaining computationally tractable.

The Extreme Risk Framework

Extreme Risk represents the limit cases of Entropic Risk as the risk parameter goes to infinity. The authors define two primary profiles:

  • Extreme Pessimists: These agents perceive their reward as the minimum payoff achievable with any positive probability.
  • Extreme Optimists: These agents perceive their reward as the maximum payoff achievable with any positive probability.

One of the most significant advantages of XR is that it is "probability-blind." It is indifferent to exact numerical probabilities, caring only whether an event has a non-zero chance of occurring. This makes it a robust model for systems where underlying probabilities are difficult to estimate or fluctuate over time.

Algorithmic Complexity and Key Results

The paper's central contribution is a mapping of the complexity landscape for finding Risk-Sensitive Equilibria (RSEs). The findings justify the paper's title by showing a clear hierarchy of difficulty:

1. The Hardness of Entropic Risk

The authors prove that the constrained existence problem for ER is undecidable for games with 10 or more players. Even when players are restricted to stationary (memoryless) strategies, the problem remains PSPACE-hard, making it impractical for general algorithmic solutions.

2. The Tractability of Extreme Risk

By shifting to the XR measure, the problem becomes decidable. The authors provide a constructive algorithm to find stationary RSEs and establish the following complexity bounds:

  • Pessimism is "Simpler": For games involving pessimists, the problem is NP-complete. This was established using reductions from 3SAT.
  • Optimism is "Simplest": If every player in the game is an extreme optimist, the complexity drops to PTIME-complete. These cases can be solved efficiently using attractor-based graph algorithms.

3. Existence and Memory

The authors prove that a stationary XR equilibrium always exists for games with non-negative terminal rewards. To prove that finite memory is sufficient, they developed a "labelling function" to track "anchored" players (those guaranteed a certain risk level), bounding the required memory to $O(3np)$.

Limitations and Future Work

While the XR framework provides a breakthrough in decidability, several areas remain open for exploration:

  • Reward Constraints: Current existence proofs assume non-negative terminal rewards. While the authors conjecture the results hold for negative rewards, this remains unproven.
  • Objective Types: The focus is currently on terminal nodes. Future work is required to see if these results extend to complex objectives like "mean payoff" or "discounted sum."
  • Concurrent Play: The current model assumes turn-based play. Extending XR to concurrent games—where players move simultaneously—is a known challenge the authors intend to address.
  • Subgame Perfection: Like standard Nash equilibria, RSEs can sometimes allow for "irrational" threats (e.g., punishing another player at one's own expense). Exploring subgame-perfect versions of these risk equilibria could provide a more realistic behavioral framework.

Conclusion

By moving from quantitative risk measures to qualitative "extreme" limits, this research provides a path out of undecidability. It demonstrates that modeling agents as extreme optimists or pessimists is not just a psychological approximation, but a powerful computational tool that makes finding equilibria in complex stochastic systems achievable.

Summary updated

Abstract

We consider simple stochastic games with terminal-node rewards and multiple players, who have differing perceptions of risk. Specifically, we study risk-sensitive equilibria (RSEs), where no player can improve their perceived reward -- based on their risk parameter -- by deviating from their strategy. We start with the entropic risk (ER) measure, which is widely studied in finance. ER characterises the players on a quantitative spectrum, with positive risk parameters representing optimists and negative parameters representing pessimists. Building on known results for Nash equilibira, we show that RSEs exist under ER for all games with non-negative terminal rewards. However, using similar techniques, we also show that the corresponding constrained existence problem -- to determine whether an RSE exists under ER with the payoffs in given intervals -- is undecidable. To address this, we introduce a new, qualitative risk measure -- called extreme risk (XR) -- which coincides with the limit cases of positively infinite and negatively infinite ER parameters. Under XR, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. Our first main result proves the existence of RSEs also under XR for non-negative terminal rewards. Our second main result shows that under XR the constrained existence problem is not only decidable, but NP-complete. Moreover, when all players are extreme optimists, the problem becomes PTIME-complete. Our algorithmic results apply to all rewards, positive or negative, establishing the first decidable fragment for equilibria in simple stochastic games with terminal objectives without restrictions on strategy types or number of players.
BibTeX
@inproceedings{brice2025finding,
  author = {Léonard Brice and Thomas A. Henzinger and K. S. Thejaswini},
  title = {{Finding equilibria: simpler for pessimists, simplest for optimists}},
  booktitle = {MFCS},
  year = {2025},
  doi = {10.4230/lipics.mfcs.2025.30},
}
Figure