Asynchronous Semianonymous Dynamics over Large-Scale Networks

Abstract. We analyze a class of stochastic processes, referred to as asynchronous and semianonymous dynamics (ASD), over directed labeled random networks. These processes are a natural tool to describe general best-response and noisy best-response dynamics in network games where each agent, at random times governed by independent Poisson clocks, can choose among a finite set of actions. The payoff is determined by the relative frequency of the different actions among neighbors while being independent of the specific identities of neighbors. Using a local mean-field approach, we prove rigorously that, under certain conditions on the network and initial node configuration, the evolution of ASD can be approximated, in the large-scale limit, by the solution of a system of nonlinear ODEs. Our framework is very general and applies to a large class of graph ensembles for which the typical random graph is locally tree-like. In particular, we focus on labeled configuration-model random graphs, a generalization of the traditional configuration model which allows different classes of nodes to be mixed together in the network, permitting us, for example, to incorporate a community structure in the system. Our analysis also applies to configuration-model graphs having a power-law degree distribution, an essential feature of many real systems. To demonstrate the power and flexibility of our framework, we consider several examples of dynamics belonging to our class of stochastic processes. Moreover, we illustrate by simulation the applicability of our analysis to realistic scenarios by running our example dynamics over a real social network graph.