Equilibria and Efficiency Loss in Games on Networks

Social networks are the substrate upon which we make and evaluate many of our daily decisions: our costs and benefits depend on whether-or how many of, or which of-our friends are willing to go to that restaurant, choose that cellular provider, already own that gaming platform. Much of the research on the "diffusion of innovation", for example, takes a game theoretic perspective on strategic decisions made by people embedded in a social context. Indeed, multiplayer games played on social networks, where the network\´s nodes correspond to the game\´s players, have proven to be fruitful models of many natural scenarios involving strategic interaction. In this paper, we embark on a mathematical and general exploration of the relationship between 2-person strategic interactions (a "base game") and a "networked" version of that same game. We formulate a generic mechanism for superimposing a symmetric 2-player base game M on a social network G: each node of G chooses a single strategy from M and simultaneously plays that strategy against each of its neighbors in G, receiving as its payoff the sum of the payoffs from playing M against each neighbor. We denote the networked game that results by M oplus G. We are broadly interested in the relationship between properties of M and of M oplus G: how does the character of strategic interaction change when it is embedded in a social network? We focus on two particular properties: the (pure) price of anarchy and the existence of pure Nash equilibria. We show tight results on the relationship between the price of anarchy in M and MoplusG in coordination games. We also show that, with some exceptions when G is bipartite, the existence or absence of pure Nash equilibria (and even the guaranteed convergence of best-response dynamics) in M and M oplus G are not entailed in either direction. Taken together, these results suggest that the process of superimposing M on a graph is a nontrivial operation that can have rich, but bounded, eff- ects on the strategic environment.