ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games

Ali Asadi, Léonard Brice, Krishnendu Chatterjee, K. S. Thejaswini

Abstract

In the study of multi-player stochastic games played on graphs, finding an exact Nash equilibrium (NE) is known to be $\exists\mathbb{R}$-complete, a complexity class that often involves irrational numbers and is notoriously difficult to compute. This paper investigates the computational complexity of finding $\epsilon$-approximate stationary Nash equilibria. The authors demonstrate that by relaxing the requirement from exact to approximate equilibria, the problem becomes more tractable, placing it within the complexity class $\text{FNP}^{\text{NP}}$ and proving that it remains NP-hard. This work provides a significant bridge between the continuous nature of game-theoretic equilibria and discrete computational representations.

Introduction

Multi-player stochastic graph games serve as a fundamental model for multi-agent systems where players navigate a graph-based environment. In these games, transitions between states are determined by both player choices and random chance. Each player aims to maximize their individual expected payoff. A Nash Equilibrium (NE) represents a stable strategy profile where no single player can improve their payoff by unilaterally changing their strategy.

While the existence of stationary NE in these games is guaranteed, the "constrained existence" problem—determining if an NE exists within specific payoff bounds—is extremely challenging. For stationary strategies, where actions depend only on the current state, this problem is $\exists\mathbb{R}$-complete. This implies that exact solutions may require representing numbers that are impossible to handle with standard binary representations. This paper shifts the focus toward $\epsilon$-Nash equilibria ($\epsilon$-NE), where players are satisfied if they are within a small margin $\epsilon$ of their optimal payoff.

Methodology

The authors utilize several theoretical frameworks to bridge the gap between real-valued probabilities and polynomial-time computation:

1. Floating-Point Representations

A primary hurdle in exact NE computation is the potential for double-exponentially small probabilities (e.g., $1/2^{2^n}$). The authors employ floating-point representations to encode these tiny values succinctly. By using a polynomial number of bits to represent the exponent, they can handle the extreme precision required for near-optimal strategies without the exponential overhead of standard fixed-point binary.

2. Continuity and Perturbation Analysis

Building on foundational work by Solan, the authors perform a continuity analysis to show that the game's payoffs are relatively stable. They prove that small perturbations in transition probabilities—such as those introduced by rounding to a floating-point format—result in only minor changes to the overall expected payoffs. This stability is what allows $\epsilon$-approximations to remain meaningful.

3. Verification via MDP Reduction

To determine if a guessed strategy profile constitutes an $\epsilon$-NE, the authors reduce the problem to a series of Markov Decision Processes (MDPs). When the strategies of all other players are fixed, the game becomes a single-agent optimization problem for the remaining player. This reduction allows the verification step to be performed efficiently using an NP oracle, placing the search problem in $\text{FNP}^{\text{NP}}$.

4. Hardness Gadgets

To establish complexity lower bounds, the authors construct intricate game "gadgets." These constructions are used to reduce the 3SAT problem to the $\epsilon$-NE problem, proving NP-hardness. Additionally, they developed a specific 5-player game gadget to demonstrate that double-exponentially small probabilities are indeed necessary for exact equilibria in some cases.

Key Insights and Results

Complexity Shift

The most significant insight of this research is that moving from exact to $\epsilon$-approximate equilibria shifts the complexity from the Existential Theory of the Reals ($\exists\mathbb{R}$) down into the polynomial hierarchy. This transition represents a major step toward making the computation of equilibria in complex stochastic systems practically feasible.

Tightness of Probability Bounds

Previous research suggested that very small probabilities might be required for equilibria, but often required seven or more players to prove this. This paper improves that result, showing that even in a 5-player game, an exact stationary NE might require probabilities as small as $1/2^{2^n}$. This justifies the necessity of the floating-point approach used in their upper-bound proof.

Formal Bounds

  • Upper Bound: The problem of finding an $\epsilon$-NE that satisfies specific payoff constraints is in $\text{FNP}^{\text{NP}}$.
  • Lower Bound: The decision version of the approximate equilibrium problem is NP-hard.

Conclusion and Future Work

This paper clarifies the computational landscape of stochastic graph games by providing tighter complexity bounds for approximate equilibria. However, a gap remains between the NP-hard lower bound and the $\text{FNP}^{\text{NP}}$ upper bound. Future research may determine if the problem is truly NP-complete or if the NP oracle is a fundamental requirement.

Furthermore, the authors propose a "Fixed-Point Conjecture," suggesting that for any game with an $\epsilon$-NE, there may exist one representable in standard fixed-point notation with a polynomial number of bits. If this conjecture holds, it would likely reduce the complexity of the problem further, potentially placing it firmly within NP.

Summary updated

BibTeX
@inproceedings{asadi2025stationary,
  author = {Ali Asadi and Léonard Brice and Krishnendu Chatterjee and K. S. Thejaswini},
  title = {{ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games}},
  booktitle = {FSTTCS},
  year = {2025},
  doi = {10.4230/lipics.fsttcs.2025.9},
}
Figure