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

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