On the Complexity of Nash Equilibrium Reoptimization

Andrea Celli, Alberto Marchesi, Nicola Gatti

Introduction

In game theory, finding a Nash Equilibrium (NE) is a fundamental challenge, categorized as PPAD-complete. Identifying an optimal NE—one that maximizes social welfare or a specific player's payoff—is even more difficult, falling into the NP-hard category. However, real-world games are rarely static; payoffs shift, and available actions change over time. This paper investigates the reoptimization problem: can we leverage a known optimal NE from a previous version of a game to efficiently find the optimal NE for a slightly modified version?

The Reoptimization Framework

The authors formalize this problem as $RE-NE(\pi, \mu)$, where $\pi$ represents the target property (e.g., maximizing social welfare) and $\mu$ represents the type of modification. Modifications considered include changing a single payoff, adding an action, or removing an action.

Figure 1: An example of a game modification where a single payoff in Γ is adjusted by δ to create Γ'.

To analyze the complexity, the researchers used mathematical reductions from NP-complete problems like SAT and SET-COVER. They demonstrated that even minimal changes to a game, such as the one illustrated above, do not simplify the search for a new optimal equilibrium.

Hardness and Inapproximability

The core finding is sobering: prior knowledge does not alleviate the computational burden for exact solutions. Even with a tiny modification, finding the new optimal NE remains NP-hard across all studied properties and modification types.

Furthermore, this hardness extends to approximations. The problems are proven to be "inapproximable," meaning they cannot be solved within any polynomial factor (Poly-APX) or logarithmic factor (Log-APX) for support size, unless P=NP.

Figure 3: Summary of complexity results for reoptimizing various properties under different game modifications (PAYOFF, ADD, REM).

Practical Implications: A Silver Lining

While the news for finding optimal NEs is negative, the paper offers a practical shortcut for finding approximate NEs. The authors prove that an exact NE of the original game serves as a robust approximate NE for the modified game.

Specifically, if payoffs change by at most $\delta$, the original NE is guaranteed to be a $\delta$-well-supported NE in the new game. Remarkably, for $\delta < 0.3393$, simply reusing the old solution provides better theoretical guarantees than running the best-known polynomial-time approximation algorithms on the new game.

Conclusion

This research establishes that reoptimization does not provide a "free lunch" for finding optimal Nash Equilibria in the worst case. However, the utility of the original equilibrium as a high-quality approximation offers a significant practical advantage for dynamic systems. Future work may explore whether specific game structures, such as those found in Security Games, might bypass these general hardness results.

Summary updated

BibTeX
@inproceedings{celli2017complexity,
  author = {Andrea Celli and Alberto Marchesi and Nicola Gatti},
  title = {{On the Complexity of Nash Equilibrium Reoptimization}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
}
Figure