Network reconstruction from asynchronously updated evolutionary game

Networks can be generally used for describing systems composed by interacting elements. Such systems usually generate big time-series data based on the underlying dynamics or mechanics. Uncovering the network structures from observations is crucial to understand the collective dynamics of the systems and has attracted great interest in different fields, ranging from biology system Schneidman et al. (2006); Nguyen et al. (2016); Roudi and Hertz (2011a); Zeng and Aurell (2020a) to social science Pincus and Kalman (2004); Bury (2013); Zeng et al. (2014).

Meanwhile, the Prisoner’s Dilemma (PD) game has long been studied for the emergence of cooperation among connected (links of the network) selfish individuals (nodes of the network). With the PD game, the criminals could take cooperation (confessing the crime to the judge) or defection (denying the crime) strategy. A large number of studies have focused on the collective behaviors with different network structures, e.g., small-world network Masuda and Aihara (2003), two-dimensional lattice Szabó and Töke (1998) and scale-free network Chen et al. (2007), etc.. Furthermore, the couplings between players are typically symmetric and binary (with / without interactions) between players in those studies. To quantify the strength of interactions between players, here we studied fully connected asymmetric Sherrington-Kirkpatrick (SK) Kirkpatrick and Sherrington (1978) models, with an asymmetric degree parameter could be varying between 0 and 1. Thus the couplings between players are Gaussians and not necessarily symmetric, which are more closer to the realities in natural social systems. We are more interested in the reconstruction of the couplings between players instead of the collective behaviours of the system.

For an evolutionary PD game, the players’ strategies follow a binary-state dynamics, which could be naturally mapped into binary state, i.e., $+1$ for cooperation and $-1$ for defection. Hence, it is straightforward to pose the coupling inference problem for an evolutionary game into the inverse Ising problem. There are many related algorithms to recovering the couplings for the inverse Ising problems, as reviewed in Nguyen et al. (2017) and references therein.

Generally, the couplings can be reconstructed by equilibrium Aurell and Ekeberg (2012); Cocco et al. (2009a); Weigt et al. (2009) or non-equilibrium Pillow et al. (2008); Roudi and Hertz (2011b); Zhang (2012); Zeng et al. (2011, 2013) model given the time-dependent/independent system data. However, in many applications, equilibrium Ising models are typically not the ideal choice for network inference and statistical modeling of the data. A mismatch between the real couplings and the inferred ones can be seen for large systems Roudi et al. (2009); Roudi and Hertz (2011a); Zeng and Aurell (2020b). This is mainly because these systems have the out-of-equilibrium nature and asymmetric couplings between elements. Thus, researchers have moved to the kinetic Ising models, developed exact and approximate methods for network reconstruction Cocco et al. (2009b); Roudi and Hertz (2011a); Zeng et al. (2011, 2013), which has wider generality.

With kinetic Ising models, spins could update synchronously or asynchronously. Similarly, with evolutionary games, synchronous means all players update their strategies simultaneously at every time step Nowak and May (1992). This can be mathematically described by a finite difference equation, but rarely exists in social or natural systems. The players, or organisms usually act at different and uncorrelated times with the coming information which may be delayed and imperfect Huberman and Glance (1993). For instance, a neuron will be in a refractory period after releasing a spike, it cannot respond to an input signal because it is still processing or recovering from the previous input signal Greil et al. (2007); Zeng et al. (2020). The dynamics of such asynchronous update is usually expressed by differential equations, whose solutions are not always the same with those of their finite-difference counterparts. Thus players will update their strategies asynchronously here, even though all of them get their corresponding rewards through the game with and from all neighbors. With asynchronous updates of strategies, only one player will be assigned to update the strategy in one game round. For finite number of players $N$ this is not exactly the asynchronous update described above, but we do not see any differences at least for kinetic Ising models Zeng et al. (2011, 2013).

For the network reconstruction with evolutionary game data, some inference methods Wang et al. (2016, 2011) have been developed based on compressive sensing technique Foucart and Rauhut (2017), which is a paradigm for sparse-signal reconstruction. However, the compressive sensing methodology works with assumptions that the interactions between individuals should be explicit and stationary and the system could be handled linearly in some way. For example, in the studies of Wang et al. (2011); Guo et al. (2016); Wu et al. (2016), the observations are the strategies and the total payoff of each player in the evolutionary game. Furthermore, all agents are assumed to play the same game with a given payoff matrix. One player’s total payoff is hence the sum of the payoff from all neighbors. In studies Steinke et al. (2007); Chang et al. (2014); Li et al. (2017), the dynamical functions are employed, but which can also be decomposed into a linear sum of scalar basis functions.

Be distinct from compressive sensing based inference methods, we present here an exact method which is intuitive and based on maximum-log-likelihood estimation (MLE). Another approximate reconstruction method is presented also which is based on naive mean-field (nMF) approximation. Both of the derived inference formula for evolutionary PD game data is enlighten by the asynchronously updated Glauber dynamics Glauber (1963), which could converge to a stationary state described by Gibbs-Boltzman distribution when the couplings are symmetric. However, this is not necessarily true for synchronous case. Hence, we are interested in using a kinetic Ising-like model to reconstruct an evolutionary game network dynamically.

With evolutionary PD game, the update times $\{\tau_{i}\}$, history of strategies $\{s_{i}(t)\}$ and rewards for each player $\{x_{i}(t)\}$ are the full model data generated during the game process. MLE needs all of these data while nMF does not need the update times, neither the rewards for each game round. nMF method relies on means, correlations and the temptation of defection parameter $b$ parameter in the payoff matrix. With massive numerical simulations, we find that the nMF performs very close to MLE method while avoid long-time iteration process. One equilibrium inference method also tested for the sake of completeness, which shows poor reconstruction for the couplings of our non-equilibrium processes.

The paper is organized as follows. In Sec. II we present the testing network structure as well as the dynamics for the PD evolutionary game. In Sec. III, we derive the MLE and nMF inference formulae from evolutionary game data. Sec. IV, presents how these two methods perform for the network reconstruction, while Sec. V summarizes and discusses the results.

The quenched aSK model is composed by $N$ vertices, which represents $N$ game player with two kinds of strategies ($s_{i}=1$ for cooperation while $s_{i}=-1$ for defection). This is a fully connected model, i.e., all players are connected to each other. The interactions $J_{ij}$ between each pair of players have the form of

with $k$ the asymmetric degree of these interactions, while $J_{ij}^{s}=J_{ji}^{s}$ and $J_{ij}^{as}=-J_{ji}^{as}$ are symmetric and asymmetric matrices, respectively. They are Gaussian random variables with means $0$ and variances

The players do not play game with themselves. This indicates $J_{ii}=0$ and the diagonal elements of $J_{ij}^{s}$ and $J_{ij}^{as}$ are $0$ as well.

We now describe the dynamics for evolutionary game on the above aSK network model. Within an evolutionary PD game, the judge knows the players are criminal but without evidences. Then a player has two possible strategies (S): cooperation (confess their crime to the judge) or defection (deny their offense to the judge). They will get different payoff when they take different strategies. The rewards are usually expressed by a payoff matrix ${X}$, for the prisoner dilemma (PD) game:

with $1\leq b\leq 2$. If both players choose cooperation, then each of them will get a reward of $1$; if one takes cooperation while the counterpart defects, then the cooperated one will get a reward of $0$ while the defected one gets $b$ (temptation of defection); if both players choose defection, then none of them will get any rewards.

During each time step $t$, all players play games simultaneously and get corresponding rewards according to the payoff matrix $X$ in matrix (3). Thus, for each player, the rewards come form the games played with as well as from the neighbours. Once they get the rewards from the game, one randomly chosen player $i$ will be assigned to update his strategy according to the following formula:

where

is the normalization factor (local partition function), which sums over both cooperation and defection states of player $i$.

We denote the cooperative and defective strategy of player $i$ at time $t$ as $\alpha_{i}(t)$ and $\beta_{i}(t)$ respectively

Then the partition function can be rewritten as

Define

and substitute $Z_{i}(t)$ in (4) with Eq. (6), then we have

During each time step, all players join the prisoners’ dilemma game and obtain corresponding payoff according to the payoff matrix (3) from each counterpart. The averaged gain during this time step for player $i$ is derived in Eq. (25). However, only one of the players is going to update his strategy, which is not necessarily change his current choice. This is why we refer this dynamics as asynchronous PD game.

We infer the evolutionary game network by MLE (10) and nMF (22) formula respectively. In Fig. 1, the scatter plots for reconstructed structure against the true ones are presented for both methods. Fig. 1(a) is for the data length $L=N\times 10^{5}$ and Fig. 1(b) for $L=N\times 10^{7}$. It shows that both nMF and MLE perform better with larger data length $L$. Furthermore, MLE works slightly better than nMF in both cases. The nMF method over estimates the couplings especially for $L=N\times 10^{7}$, as shown in Fig. 1(b).

We introduce the mean square error (MSE) to measure the distance between the reconstructed and the true tested network structure.

where $J_{ij}^{True}$ are the tested network couplings and $J_{ij}^{Rec.}$ for the inferred ones.

With the reconstruction error MSE defined by (23), we compared the performance of MLE and nMF method for fully connected SK model (1). We study both methods for different data length $L$, the asymmetric degree $k$, the temptation of defection parameter $b$ in the payoff matrix (3) as well as the coupling strength $g$. The inverse of $g$ corresponds to the temperature in spin glass system, which can be explained as the noise (say, fake information or rumors etcetera) in the evolutionary PD game.

Figure 2 shows the performance of both methods. Similar to the results for asynchronous Ising case Zeng et al. (2013), the MSE for MLE is $\propto 1/L$ here. However, with the data length $L$ we tested here, nMF does not approach to a saturated value as happened for asynchronous Ising case. Instead, the reconstruction error MSE for nMF is about twice of that for MLE, see Fig. 2(a). This could be an indication for game network, nMF inference formula can be obtained also by taken the average of update times in MLE formula (10), which has been proved so in Zeng et al. (2013) for asynchronous Ising models. Figure 2(b) shows the MSE for both methods is not sensitive to the asymmetric degree $k$, no matter the network is symmetric ($k=0$) or fully asymmetric ($k=1$). Here, the data length $L=N\times 10^{6}$ with $N=20$ and $g=0.3$. The difference between two methods is effected mainly by the data length $L$. The MSE for MLE is about half of that for nMF approach, which agrees well with that shown in Fig. 2(a). Figure 2(c) shows the performance of MLE and nMF algorithm for different reward parameter $b$ in the payoff matrix (3), which is a specific parameter for game networks. Both algorithms recover the network better with larger reward $b$. However, the proportion of MSE between nMF and MLE increases slightly for larger $b$. Finally, the effects of inverse $g$ over network inference is illustrated in Fig. 2(d). For strong couplings, nMF works much worse than MLE. However, for $g\leq 1$, their performances are not effected by $g$ anymore. MLE still has its advantage of the factor 2 (conferred by the information of update times) compared with nMF.

To illustrate how the equilibrium inference method works for the non-equilibrium process, we use the naive mean-filed equilibrium inference Kappen and Spanjers (2000) algorithm which depends on the equal time correlations only:

We refer this as equilibrium inference to avoid the confusion with the nMF method for asynchronous case we derived here. Then, we present the inferred networks through scatter-plots in Fig. 3 with both equilibrium and non-equilibrium method for evolutionary data generated by PD games.

Fig. 3(a) and (b) presents the reconstructed couplings for symmetric ($k=0$) and fully asymmetric ($k=1$) SK model respectively. Our asynchronous nMF (blue open dots) and MLE (red upper triangle) methods recover the couplings nicely while the equilibrium nMF (24) (open black squares) works much worse, even for $k=0$, the symmetric case. It is not surprising as equilibrium nMF (24) we tested here does not take into account the game process at all. For the original asynchronous Ising model without game process, the equilibrium nMF should work as good as the non-equilibrium methods Zeng and Aurell (2020b) since they are for the same dynamics.

We studied the network reconstruction problem with asynchronous updated evolutionary game data. The gamblers play the PD game with their counterparts simultaneously but update their strategies asynchronously. Two methods (exact and iterative MLE and approximate nMF) are introduced to infer the fully connected and Gaussian distributed couplings between players.

Comparing with the original asynchronous Ising model Zeng et al. (2011, 2013), we combine the PD games with Glauber dynamics, where the rewards during the game for each player is considered. The MLE and nMF reconstruction formulae for asynchronous Ising models in Zeng et al. (2011, 2013) hence have to be generalized for the asynchronous evolutionary game case here. MLE is derived from the log-likelihood of the system while nMF from the derivative of the equations of motion of means and correlations. However, they are not independent with each other. MLE utilizes the full model histories, $\{s_{i}(t)\}$, $\{x_{i}(t)\}$ and $\{\tau_{i}\}$. The update histories in Eq. (10) could be averaged and yields the nMF inference formula (22) by taking the linear term of the averaged $\tanh$ function.

With the derived MLE and nMF methods for asynchronously updates PD game, our numerical results show that the inference performance of nMF is comparable with that of MLE. Both methods are not sensitive to the asymmetric degree $k$, but proportional to the inverse of data length. For fixed data length, the reconstruction error (MSE) of MLE is half (benefit from update times) of that by nMF method. Furthermore, nMF prefers small/weak coupling strength ($g$) while MLE holds for much wider range of $g$. Both methods recover better for large payoff parameter $b$. This is reasonable as when the rewards of each players equal to $2$, then the external field Eq. (7) in the dynamics degenerates to the original asynchronous Ising model. With $b$ increases, the rewards of each players will also close to $2$ which show better performance of network reconstruction.

However, comparing with the data that MLE method used for inference, nMF needs only the $b$ parameter and the moments of strategy history $\{s_{i}(t)\}$. Furthermore, nMF infers much fast than MLE as no iterative procedure included for network inference. The scatter-plots in Fig. 1 and Fig. 3 show that the $J_{ij}^{nMF}$s are obviously comparable with $J_{ij}^{MLE}$s, even though the MSE for nMF is roughly twice of that for MLE. Thus, we expect that for the network inference with data from asynchronous PD game, nMF works well enough. The higher orders of tanh function (say, TAP) are not necessary.

Besides, we have tested a widely used equilibrium inference method (24) blindly for our dynamic data generated from evolutionary PD games, which recover much worse than that by non-equilibrium inference methods, even for symmetric interactions between players, as illustrated in Fig. 3(a). This bring us a message that if we have time series data generated from some certain dynamics, we should try non-equilibrium methods first. Furthermore, we start from the detailed balance condition to derive the asynchronous nMF formula for the network inference, but as shown by the numerical results, the inference formula holds for asymmetric $k=1$ case also where the system is not in the equilibrium realm any more.

This work focuses on a simple and idealized prisoner’s game with fully connected and Gaussian distributed interactions, which could be extended to certain type of structures or different distributions (say, random power-law, where strong couplings between few players while weak ones between most of them) for the couplings. Besides, we use a constant value of defection temptation $b$ which could be different for each players. Meanwhile, non-zero abut small $r$ in the payoff matrix (3) could also be tested. These will be studied by further work.