On the Complexity of Nash Equilibrium Reoptimization

Andrea Celli, Alberto Marchesi, Nicola Gatti
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:601-610, 2017.

Abstract

We provide, to the best of our knowledge, the first study about reoptimization complexity of game-theoretical solutions. In a reoptimization problem, we are given an instance, its optimal solution, and a local modification, and we are asked to find the exact or an approximate so- lution to the modified instance. Reoptimiza- tion is crucial whenever an instance needs to be solved repeatedly and, at each repetition, its parameters may slightly change. In this paper, we focus on Nash equilibrium, being the cen- tral game-theoretical solution. We study the reoptimization of Nash equilibria satisfying some properties (i.e., maximizing/minimizing the social welfare, the utility of a player or the support size) for some different local modifica- tions of the game (i.e., modification of a pay- off or addition/removal of an action), show- ing that such problems are NP-hard. Further- more, we assess the approximation complex- ity of the aforementioned problems, showing that it matches the complexity of the origi- nal (non-reoptimization) problems. Finally, we show that, when finding a Nash equilibrium is thought as an optimization problem, reopti- mization is useful for finding approximate so- lutions. Specifically, it allows one to find $\epsilon$- Nash equilibria with smaller $\epsilon$ than that of the solutions returned by the best known approxi- mation algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-celli17a, title = {On the Complexity of {N}ash Equilibrium Reoptimization}, author = {Celli, Andrea and Marchesi, Alberto and Gatti, Nicola}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {601--610}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/celli17a/celli17a.pdf}, url = {https://proceedings.mlr.press/r15/celli17a.html}, abstract = {We provide, to the best of our knowledge, the first study about reoptimization complexity of game-theoretical solutions. In a reoptimization problem, we are given an instance, its optimal solution, and a local modification, and we are asked to find the exact or an approximate so- lution to the modified instance. Reoptimiza- tion is crucial whenever an instance needs to be solved repeatedly and, at each repetition, its parameters may slightly change. In this paper, we focus on Nash equilibrium, being the cen- tral game-theoretical solution. We study the reoptimization of Nash equilibria satisfying some properties (i.e., maximizing/minimizing the social welfare, the utility of a player or the support size) for some different local modifica- tions of the game (i.e., modification of a pay- off or addition/removal of an action), show- ing that such problems are NP-hard. Further- more, we assess the approximation complex- ity of the aforementioned problems, showing that it matches the complexity of the origi- nal (non-reoptimization) problems. Finally, we show that, when finding a Nash equilibrium is thought as an optimization problem, reopti- mization is useful for finding approximate so- lutions. Specifically, it allows one to find $\epsilon$- Nash equilibria with smaller $\epsilon$ than that of the solutions returned by the best known approxi- mation algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T On the Complexity of Nash Equilibrium Reoptimization %A Andrea Celli %A Alberto Marchesi %A Nicola Gatti %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-celli17a %I PMLR %P 601--610 %U https://proceedings.mlr.press/r15/celli17a.html %V R15 %X We provide, to the best of our knowledge, the first study about reoptimization complexity of game-theoretical solutions. In a reoptimization problem, we are given an instance, its optimal solution, and a local modification, and we are asked to find the exact or an approximate so- lution to the modified instance. Reoptimiza- tion is crucial whenever an instance needs to be solved repeatedly and, at each repetition, its parameters may slightly change. In this paper, we focus on Nash equilibrium, being the cen- tral game-theoretical solution. We study the reoptimization of Nash equilibria satisfying some properties (i.e., maximizing/minimizing the social welfare, the utility of a player or the support size) for some different local modifica- tions of the game (i.e., modification of a pay- off or addition/removal of an action), show- ing that such problems are NP-hard. Further- more, we assess the approximation complex- ity of the aforementioned problems, showing that it matches the complexity of the origi- nal (non-reoptimization) problems. Finally, we show that, when finding a Nash equilibrium is thought as an optimization problem, reopti- mization is useful for finding approximate so- lutions. Specifically, it allows one to find $\epsilon$- Nash equilibria with smaller $\epsilon$ than that of the solutions returned by the best known approxi- mation algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
Celli, A., Marchesi, A. & Gatti, N.. (2017). On the Complexity of Nash Equilibrium Reoptimization. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:601-610 Available from https://proceedings.mlr.press/r15/celli17a.html. Reissued by PMLR on 04 October 2026.

Related Material