A Study on the Stability and Efficiency of Graphical Games with Unbounded Treewidth

Graphical games (GG) provide compact representations of multiplayer games involving large populations of agents when influences among them have some locality property. The no-tion of pure Nash equilibrium (PNE), not requiring random-ized strategies, is a fundamental stability concept. However, recent results show that for many natural topologies, a PNE is very unlikely to exist when the number of agents is large, which challenges the relevance of PNE in large GG. In this paper, we investigate how far we can get from the notion of individual stability captured by the concept of PNE, by only requiring agents to be almost in best-response (-Nash), or by requiring almost all agents to be in best-response. We study these approximated notions of PNE for different topologies, including graphs with unbounded treewidth, like grids. This makes the problem computation-nally very challenging and requires the comparison and use of several algorithmic solutions. Our results reveal surpris-ingly good asymptotic properties, tempering the claim that individual stability is not a relevant notion for large GG. Finally, as approximated PNE provide various tradeoffs be-tween stability and social utility maximization, we propose an approach to construct a minimal-size e-covering of all feasible Pareto-dominant tradeoffs