On network games with coordinating and anti-coordinating agents

Network games are a useful model to study strategic interactions over interconnected systems. When the individual decisions are binary, agents might prefer one action over the other according to the number of friends that are playing it. For instance, in the spread of innovations and beliefs, as well as in contagion, individuals adopt the new strategy if enough neighbors are choosing it. On the other hand, if a resource is shared, as in traffic flows and division of work, too many people taking an action can be an incentive for the player to choose the opposite one. These two emblematic situations are modeled as network games with coordinating and anti-coordinating agents. Thanks to their wide use and the simplicity of their definition, network coordination and anti-coordination games have been largely studied in the literature and many results have been achieved when all the players have the same behavior. The thesis investigates what happens when some heterogeneity occurs. Specifically, the aim of the thesis is to find analytical conditions for the existence of Nash of equilibria in the most general case, namely when coordinating and anti-coordinating agents have heterogeneous thresholds and interact in the same network. In this study, we first demonstrated that the network coordination game, as well as the network anti-coordination, maintains its well-known potential property even if the players have heterogeneous thresholds. This is a very strong property: it not only does guarantee the existence of at least one Nash equilibrium, but it is sufficient to prove that the best response dynamics converges to the set of Nash equilibria with probability one in finite time regardless of the topology and the initial condition. Furthermore, we present a formulation of the games in terms of homogeneous threshold games with stubborn players. We also provide a complete characterization of the Nash equilibria of the threshold network anti-coordination game on a complete graph. The main result of the thesis is to provide a sufficient condition for the existence of Nash equilibria when the populations are mixed. In fact, if the set of the coordinating players is sufficiently cohesive, then the existence of at least one Nash equilibrium is guaranteed over any possible network.