Properties of interaction networks underlying the minority game

The minority game is a well-known agent-based model with no explicit interaction among its agents. However, it is known that they interact through the global magnitudes of the model and through their strategies. In this work we have attempted to formalize the implicit interactions among minority game agents as if they were links on a complex network. We have defined the link between two agents by quantifying the similarity between them. This link definition is based on the information of the instance of the game (the set of strategies assigned to each agent at the beginning) without any dynamic information on the game and brings about a static, unweighed and undirected network. We have analyzed the structure of the resulting network for different parameters, such as the number of agents $\left(N\right)$ and the agent's capacity to process information $\left(m\right)$, always taking into account games with two strategies per agent. In the region of crowd effects of the model, the resulting networks structure is a small-world network, whereas in the region where the behavior of the minority game is the same as in a game of random decisions, networks become a random network of Erdos-Renyi. The transition between these two types of networks is slow, without any peculiar feature of the network in the region of the coordination among agents. Finally, we have studied the resulting static networks for the full strategy minority game model, a maximal instance of the minority game in which all possible agents take part in the game. We have explicitly calculated the degree distribution of the full strategy minority game network and, on the basis of this analytical result, we have estimated the degree distribution of the minority game network, which is in accordance with computational results.

Figure 1

Reduced variance $\left({\sigma }^2/N\right)$ as a function of the control parameter $\left(\alpha =\mathcal{H}/N=2^m/N\right)$ for the MG for different values of $m$ (from 2 to 14) and $N$ agents (plus symbols denote the 1001 case, triangle denotes 501 case, and $X$ denotes the 101 case). For each value of $N$ and $m$, 100 runs have been performed, with each of $T=100000$ time steps discarding the first $50000$ steps. The dashed line corresponds to the case of random decisions. Regions of crowd effects, coordination, and random decisions are highlighted.

Figure 2

Probability of finding links on the MG networks, $\langle k\rangle /(N-1)$, vs $m$ for different values of $N$ (circle symbols for $N=5001$ case, plus for 1001, triangle for 501 and $X$ for 101 case). Each point correspond to an average value over 100 instances. The inset of the figure shows the standard deviations for the values of the probability of finding a link by using the same symbols as in the main figure. The case of $N=5001$ presents an error bar which is lower than the symbol size of main figure.

Figure 3

In gray, degree distribution of MG networks for (a) $m=3$, (b) $m=5$, (c) $m=8$, and (d) $m=11$ for $N=1001$, averaged over 100 different instances. The continuous black curves correspond to the degree distributions for equivalent Erdos-Renyi networks, where we approximate the Poisson distribution with a normal distribution $N(\mu ,\sigma )$ with the parameters $\mu ={\langle k\rangle }_I$ and $\sigma =\sqrt{{\langle k\rangle }_I}$, where ${\langle k\rangle }_I$ is the value obtained by averaging the mean degree of the $G^{\mathrm{MG}}$ over 100 instances. We performed a Pearson's ${\chi }^2$ statistical test in order to check the following null hypothesis H0: “data observed of degree distribution of $G^{\mathrm{MG}}$ are distributed like in random networks, i.e. a normal distribution with equal mean and variance.” We computed the statistical value $X^2$ as the weighed sum of the squared deviations from the number of events observed and expected in each class of the histogram, i.e., $X^2={\sum }_{i=1}^l{(n_i-n{p}_{0i})}^2/n{p}_{oi}$, where $n_i$ is the number of observed events in class $i$ and $n{p}_{0i}$ is the predicted number of events in the class $i$, with $n$ being the total number of events and $p_{0i}$ the predicted probability of class $i$ for the underlying distribution. In our case, we are testing that this is a normal distribution with equal mean and variance $\mu$ which has been estimated from the same set of data. When H0 is true, $X^2$ is approximately a ${\chi }_{l-2}^2$ distribution with $l-2$ degrees of freedom (because of the constrait of the normalization condition of $p_{0i}$ and the parameter $\mu$ estimated from data) [34]. We can reject H0 for $m=8$ case with a significance level smaller than $0.1\%$, in which case the normalized statistics [$X_n^2=X^2/(l-2)$ which is expected value 1] is $X_n^2=2.43$ and $l=67$. For $m=9,\cdots ,14$ we cannot reject the hypothesis H0 because the values obtained for the normalized statistics are $X_n^2=0.38$ and $l=63$ for $m=9,X_n^2=0.15$ and $l=61$ for $m=10,X_n^2=0.135$ and $l=61$ for $m=11,X_n^2=0.127$ and $l=64$ for $m=12,X_n^2=0.132$ and $l=63$ for $m=13$, and, finally, $X_n^2=0.128$ and $l=62$ for the $m=14$ case.

Figure 4

Degree correlation coefficient of $G^{\mathrm{MG}}$ as a function of $m$ for different values of $N$ (circles denote the $N=5001$ case, plus signs denote the 1001 case, triangles denote the 501 case, and $X$ denotes the 101 case). Each point corresponds to an average value over 100 instances. The inset shows the values of standard deviation of the degree correlation in a log scale by using the same symbols.

Figure 5

Black symbols are the clustering coefficient as a function of $m$ for games with a different number of agents $N$ (circles denotes the $N=5001$ case, plus signs denote the 1001 case, triangles denote the 501 case, and $X$ denotes the 101 case). In all cases, the results shown are averages over 100 different instances. Gray symbols are the link probability reported in Fig. 2. The inset of the figure shows values of clustering coefficient for the case of $m=6$ for different values of $m$; error bars are the standard deviation obtained over the 100 instances. Error bars corresponding to the $N=5001$ case are smaller than the size of the symbols. A ${\chi }^2$ statistical test cannot reject the null hypothesis H0: “the values obtained from $N=101,501,1001$, and 5001 are mutually consistent (i.e., correspond to variables with the same mean value)” for any value of $m$. The figure inset reports the values corresponding to $m=6$ with error bars for different values of $N$. For each value of $m$ we performed a ${\chi }^2$ statistical test on means in order to check the null hypothesis H0: “the four values are mutually consistent within these error bars, i.e., the obtained values of clustering coefficient for $N=101,N=501,N=1001$, and $N=5001$ correspond to measurements of variables with the same mean value, and normal distribution” [34]. We computed the statistical value $S$ as the weighed sum of the squared deviations from the weighed average value of the four measurements $\left(\overline{x}\right)$, i.e., $S={\sum }_{i=1}^4{(x_i-\overline{x})}^2/\Delta x_i^2$, where $x_i$ and $\Delta x_i$ are the variable and error corresponding to the $i$ case (i.e., each one of the obtained clustering coefficients for $G^{\mathrm{MG}}$ with $N=101,N=501,N=1001$, and with $N=5001$ agents) and $\overline{x}$ is the maximum likelihood estimator of the mean of the four values. When H0 is true, $S$ is approximately a ${\chi }_3^2$ distribution with 3 degrees of freedom (because the parameter $\overline{x}$ is estimated from data) [34]. For $m=2$, we obtained $S=0.0013$; for $m=3,S=0.0009$; for $m=4,S=0.0009$; for $m=5,S=0.0006$; for $m=6,S=0.000008$, for $m=7,S=0.0007$; for $m=8,S=0.0002$; for $m=9,S=0.00003$; for $m=10,S=0.0006$; for $m=11,S=0.00005$; for $m=12,S=0.00002$; for $m=13,S=0.0004$; and for $m=14,S=0.0006$. For this reason H0 cannot be rejected for any value of $m$.

Figure 6

Big symbols: minimum mean path as a function of $m$ for MG networks with different number of agents. In each case of MG network, data show the mean value of 100 instances (each instance consists in a different assignment of strategies to the agents). Small symbols: minimum mean path for Erdos-Renyi networks $\left(G^{\mathrm{ER}}\right)$ with the same value of $N$ and $\langle k\rangle$ as $G^{\mathrm{MG}}$; we used the igraph of the r project package to calculate the minimum mean path [35, 36].

Figure 7

In gray, degree distribution for MG networks for $N=1001$ and $m=3$. Histogram is an average over 100 different instances. The continuous black line shows $P^{\mathrm{MG}}\left(\tilde{k}\right)$, the degree distribution estimated using the degree distribution of FSMG, $P^{\mathrm{FSMG}}\left(k\right)$. The inset shows $P^{\mathrm{FSMG}}\left(k\right)$ for $m=3$: $P(k=4370)=0.0078$; $P(k=1710)=0.14$; $P(k=740)=0.49$ (actually, there are two values of degree which were joined: 740 for the case of $h=3/8$ and 741 for the case of $h=1/2$); $P(k=210)=0.33$ and $P(k=0)=0.035$.