Laws of Large Numbers for Games on Sparse Random Networks

Abstract

Social networks play a crucial role in society by determining how ideas, behaviors, norms, and diseases spread. Applying the tools of game theory to social networks allows us to model how these processes occur. This approach gives policymakers a toolkit to target interventions with the aim of improving outcomes such as the total welfare of a group. However, this typically requires complete network data and substantial computational power, which is often not available or is expensive to procure. For this reason, researchers study lower-dimensional statistical graph formation models which resemble real-world networks. I study the properties of games played on networks sampled from these models. I first introduce standard results from random graph theory, and then describe the canonical results of game theory on networks. I detail several studies which investigate games played on networks sampled from random graphs. I then give novel results. I state and prove a weak law of large numbers for mean equilibrium behavior in a certain class of games on a canonical random graph model, and illustrate the result using a simulation. Then, I give simulations showing that my results generalize to networks that are sparse or that exhibit substantial homophily, both of which are natural in complex networks. I conjecture theoretical results corresponding to these simulation outcomes and give an analytical scheme to approximate the relationship between different groups' actions in homophilous graphs.