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.
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.
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