Pure and Strong Nash Equilibrium Computation in Compactly Representable Aggregate Games

Jared Soundy, Mohammad T. Irfan, Hau Chan
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:4013-4033, 2025.

Abstract

Aggregate games model interdependent decision making when an agent’s utility depends on their own choice and the aggregation of everyone’s choices. We define a compactly representable subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We study computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE). We show that PNE existence is NP-complete for very simple cases of additive aggregate games. We devise an efficient algorithmic scheme for deciding the existence of a PNE and computing one (if it exists) for bounded aggregate space. We also give an approximation algorithm for a special type of additive aggregate games. For SNE, we show that SNE recognition is co-NP-complete and SNE existence is $\Sigma^P_2$-complete, even for simple types of additive aggregate games. For broad classes, we provide several novel and efficient aggregate-space algorithms for recognizing an SNE and deciding the existence of an SNE. Finally, we connect our results to several popular classes of games and show how our computational schemes can shed new light on these games.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-soundy25a, title = {Pure and Strong Nash Equilibrium Computation in Compactly Representable Aggregate Games}, author = {Soundy, Jared and Irfan, Mohammad T. and Chan, Hau}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {4013--4033}, year = {2025}, editor = {Chiappa, Silvia and Magliacane, Sara}, volume = {286}, series = {Proceedings of Machine Learning Research}, month = {21--25 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v286/main/assets/soundy25a/soundy25a.pdf}, url = {https://proceedings.mlr.press/v286/soundy25a.html}, abstract = {Aggregate games model interdependent decision making when an agent’s utility depends on their own choice and the aggregation of everyone’s choices. We define a compactly representable subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We study computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE). We show that PNE existence is NP-complete for very simple cases of additive aggregate games. We devise an efficient algorithmic scheme for deciding the existence of a PNE and computing one (if it exists) for bounded aggregate space. We also give an approximation algorithm for a special type of additive aggregate games. For SNE, we show that SNE recognition is co-NP-complete and SNE existence is $\Sigma^P_2$-complete, even for simple types of additive aggregate games. For broad classes, we provide several novel and efficient aggregate-space algorithms for recognizing an SNE and deciding the existence of an SNE. Finally, we connect our results to several popular classes of games and show how our computational schemes can shed new light on these games.} }
Endnote
%0 Conference Paper %T Pure and Strong Nash Equilibrium Computation in Compactly Representable Aggregate Games %A Jared Soundy %A Mohammad T. Irfan %A Hau Chan %B Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2025 %E Silvia Chiappa %E Sara Magliacane %F pmlr-v286-soundy25a %I PMLR %P 4013--4033 %U https://proceedings.mlr.press/v286/soundy25a.html %V 286 %X Aggregate games model interdependent decision making when an agent’s utility depends on their own choice and the aggregation of everyone’s choices. We define a compactly representable subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We study computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE). We show that PNE existence is NP-complete for very simple cases of additive aggregate games. We devise an efficient algorithmic scheme for deciding the existence of a PNE and computing one (if it exists) for bounded aggregate space. We also give an approximation algorithm for a special type of additive aggregate games. For SNE, we show that SNE recognition is co-NP-complete and SNE existence is $\Sigma^P_2$-complete, even for simple types of additive aggregate games. For broad classes, we provide several novel and efficient aggregate-space algorithms for recognizing an SNE and deciding the existence of an SNE. Finally, we connect our results to several popular classes of games and show how our computational schemes can shed new light on these games.
APA
Soundy, J., Irfan, M.T. & Chan, H.. (2025). Pure and Strong Nash Equilibrium Computation in Compactly Representable Aggregate Games. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:4013-4033 Available from https://proceedings.mlr.press/v286/soundy25a.html.

Related Material