Outlet Title

24th International Conference on Autonomous Agents and Multiagent Systems

Document Type

Conference Proceeding

Publication Date

5-2025

Abstract

Aggregate games, first conceptualized by Nobel laureate Reinhard Selten in 1970, model the decision-making of interdependent agents where each agent’s utility depends on their own action and the aggregation of everyone’s actions. We consider computational questions on pure Nash equilibrium (PNE) and pure strong Nash equilibrium (SNE) for aggregate games. On the way, we define a new subclass of aggregate games we call additive aggregate games, which encompasses popular games like congestion games, anonymous games, Schelling games, etc. We show that PNE existence is NPcomplete for very simple cases of additive aggregate games. We devise an efficient aggregate-space algorithm for determining the existence of a PNE and computing one (if exists) for bounded aggregate space. For SNE, we show that SNE recognition is co-NPcomplete and SNE existence is Σ^𝑃_2-complete, even for simple types of additive aggregate games. For large classes of aggregate games, 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 well-studied subclasses of aggregate games and show how our computational schemes can shed new light into these games.

Download

Share

COinS