Abstract 

Vikas K. Garg Tommi Jaakkola CSAIL, MIT CSAIL, MIT vgarg@csail.mit.edu tommi@csail.mit.eduAggregative games provide a rich abstraction to model strategic multi-agent interactions. We introducelocal aggregative games, where the payoff of each player is a function of its own action and theaggregate behavior of its neighbors in a connected digraph. We show the existence of a pure strategy-Nash equilibrium in such games when the payoff functions are convex or sub-modular. We provean information theoretic lower bound, in a value oracle model, on approximating the structure of thedigraph with non-negative monotone sub-modular cost functions on the edge set cardinality. We alsodefine a new notion of structural stability, and introduce ?-aggregative games that generalize localaggregative games and admit -Nash equilibrium that is stable with respect to small changes in somespecified graph property. Moreover, we provide algorithms for our models that can meaningfullyestimate the game structure and the parameters of the aggregator function from real voting data.