# On the effect of memory on the Prisoner’s Dilemma game in correlated
networks

Nastaran Lotfi and Francisco A. Rodrigues

###### Abstract

Game theory is fundamental to understanding cooperation between agents.
Mainly, the Prisoner’s Dilemma is a well-known model that has been extensively
studied in complex networks. However, although the emergence of cooperation
has been investigated before, the influence of memory in its evolution is not
well understood. This paper presents a detailed study of cooperation dynamics
in which agents have memory. We simulate the evolutionary Prisoner’s dilemma
game on random, scale-free and networks presenting degree-degree correlation.
Through extensive simulations, we show that assortativity can improve
cooperation when the temptation to defect increases. Moreover, we show that
the inclusion of memory decreases the network structure influence. Our results
contribute to understanding the role of the network structure and the player’s
memory of cooperation.

##  1 introduction

In the last decades, evolutionary theory on complex networks has attracted
significant attention from scientists in many areas, from economy to physics
[1, 2]. Prisoner’s dilemma (PD) is a game in which two players acting
selfishly will ultimately result in a suboptimal choice for both players. Two
players, separated and unable to communicate, must each choose between
cooperating with the other or not. Thus, in the game, we have two types of
players, i.e., a cooperator (denoted by $C$) and a defector (denoted by $D$)
[3]. Cooperators benefit other individuals at some cost, whereas defectors
attempt to exploit such shared resources.

Initially, the PD was studied on regular graphs [4], where subjects played a
single game with their neighbours, adopting the strategy of the most
successful neighbour for the next round. Next, the PD was adapted to small-
world networks, which are obtained through the rewiring of connections in a
regular graph [5, 6, 7] or by adding links to a grid structure [8, 9, 10].
Although these analyzes allow a generalization of the traditional PD to
graphs, grids, small-world networks, and random graphs do not reproduce most
of the properties of real-world networks. Most complex networks have scale-
free organization, presenting densely connected nodes called hubs.

Thus, further works adapted the PD to scale-free networks [11, 12, 13, 14]. It
has been verified that in these networks, cooperation is enhanced in
comparison to regular graphs and small-world networks. Indeed, some works
investigated the influence of the initial distributions of defectors on the
evolution of the game [15], showing that the initial configurations for
defectors can greatly influence the cooperation level and the evolution speed
of cooperation. Moreover, the cooperation can be enhanced with the increasing
clustering when the initial cooperators are the most connected nodes [16]. In
networks with community structure, Chen et al. [17] verified that reducing the
connections inside the community can promote cooperation as the total links
were considered unchanged. The influence of the initial fractions of
cooperators on random and scale-free was analyzed in [14].

All these previous works showed that the structure of the network plays a
fundamental role in the evolution of cooperation [1, 18]. However, the
player’s strategy also influences cooperation. Mainly, players analyze the
game and remember their last strategies and the actions of other players.
Therefore, players have memory, influencing their planning to maximize their
earnings. Although this is an essential ingredient to model cooperation, only
a recent paper addressed this issue [19]. In this case, a player applies the
memory rule to define her/his action based on her/his historical payoffs. The
neighbours’ historical optimal procedures are also taken into account to
define the player’s strategy [19]. The authors verified that historical
information promotes cooperation in three classical evolutionary social
dilemmas, including the prisoner’s dilemma and the snowdrift game. However,
only a regular lattice was considered in that study. Therefore, cooperation
with memory in heterogeneous networks has not been studied yet.

In this paper, we introduce two new models for capturing the influence of
memory in cooperation depending on the players’ payoff in complex networks. In
the first one, the strategy of player $i$ is defined according to its
neighbour’s historical payoffs. In the second case, besides the information
from the neighbours, he/she considers his/her performance in previous games
too. We consider the $m$ previous games in both cases, which define the
player’s memory. We assume that players are organized in a complex network
whose structure changes from random to scale-free. Degree-degree correlation
is also included in the network’s structure, enabling us to investigate how
the network topology influences the evolution of cooperation. In addition, we
modify the neighbour selection process in the traditional PD game. In the
standard PD games, neighbours are assumed to be selected randomly, while we
add the degree probability for neighbour selection. All models are analyzed
considering both methods of neighbour selections to check the influence of
neighbours in the evolution of the cooperation. Through extensive simulations,
we find that degree-degree correlation and player’s memory length are two
fundamental ingredients to improve the cooperation between players. However,
when we assume that nodes have memory, the influence of network structure is
decreased.

The present paper is organized as follows. In section 2, we describe the
prisoner’s dilemma, network construction, and also the memory models. Section
3 is devoted to presenting and discussing our results. As follows, we conclude
our work.

##  2 Concepts and methods

###  2.1 Traditional prisoner’s dilemma

The simulation of cooperation follows the prisoner’s dilemma. Initially, each
player is defined as a cooperator ($C$) or a defector ($D$) with the same
probability and independently. In the traditional prisoner’s dilemma, in each
time step, players can only interact with their nearest neighbours with the
following rules: if the player is a cooperator, then it receives the payoff
$R$ ($S$) as the neighbour is $C$ ($D$). If the player is a defector, the
payoff value would be $T$ ($P$) as the neighbour is $C$ ($D$). Due to
different values of payoffs, when $T>R>P>S$, the game is named PD. In this
paper, values of PD payoffs have been set to $R=1$, $T=b>1$, $P=0$, i.e., no
benefit under defectors interactions, and $P-S=\epsilon$ [4, 11]. Small
positive values of $\epsilon\ll 1$ have no qualitative differences in the
results, where the limit $\epsilon\rightarrow 0^{+}$ was used in [4, 11, 20].
Here, we consider the same approach.

At each time step, every node $i$ plays with its nearest neighbours and
accumulates the payoffs $p_{i}$ according to its current state ($C$ or $D$).
Next, each player compares its payoff with the payoff of a neighbour chosen at
random. In our study, the random selection of the neighbours is made in two
ways: (i) at random or (ii) according to the node degree. In this way, the
neighbours with a higher degree get a higher chance of being selected. Player
$i$ will keep its strategy if $p_{i}>p_{j}$ or will copy $j$’s strategy with
probability

$P_{i\rightarrow j}=\frac{1}{max(k_{i},k_{j})*b}(p_{j}-p_{i})\quad\text{ if
}p_{i}<p_{j}.$

where $k$ is the node degree (number of connections). The state of the nodes
is defined by the vector $s_{i}(i=1,...,N)$, whose entries are equal to 1 if
node $i$ is a cooperator or 0 if it is a defector. As a result, an
instantaneous fraction of cooperators at time $t$ can be defined as
$C(t)=N^{-1}\sum_{i}s_{i}(t)$. After the transient time $t_{0}$ (which is
large enough to make the mean value of $C$ stationary), we get the average
number of cooperators ($\langle C\rangle$) for each parameter value $b$.

###  2.2 The prisoner’s dilemma with memory

The simulation of the PD with memory considers two classes of nodes,
cooperator ($C$) and defector ($D$). At the beginning of the process, each
node is classified in one of these two states. The initial fraction of
cooperators is a parameter of the simulation. Each node selects a neighbour
and changes its state to maximize its gains.

To verify how memory affects cooperation, we consider two different
possibilities. In the first one, at each game, a player can keep its last
strategy (C or D) or change it according to the neighbour’s actions. In this
case, a player analyzes the payoff obtained by its neighbours in previous
games. On the other hand, a player can consider its previous strategies to
decide to cooperate or defect along with the neighbors history. To simulate
these two different scenarios, we consider these two models:

  1. 1.

In model $A$, each node sets its last state according to its neighbour’s
memory. To do so, node $i$ will decide to changed its strategy if
$p_{i}<\overline{p}_{j}^{m}$ with probability:

$P_{i\rightarrow j}=\frac{1}{max(k_{i},k_{j})*b}(\overline{p}_{j}^{m}-p_{i}),$
(1)

where $\overline{p}_{j}^{m}$ is the neighbours’ average payoff over the
previous $m$ games. The neighbour $j$ is selected with a probability that
depends on its degree $k_{j}$ (preferential selection according to the number
of connections) or uniformly at random.

  2. 2.

In model B, we adopt the same configuration as in model A. However, we add the
memory influence of member $i$ too. In other words, we assume that the node
has some background from its previous games and also its neighbors history. As
a result, node $i$ will decide to changed its strategy if
$\overline{p}_{i}^{m}<\overline{p}_{j}^{m}$ with the probability:

$P_{i\rightarrow
j}=\frac{1.0}{max(k_{i},k_{j})*b}(\overline{p}_{j}^{m}-\overline{p}_{i}^{m}).$
(2)

In both models, the traditional PD rules are applied until reaching the memory
step $m$, and after that, the new defined models are operated. Studying
neighbour’s power in the decision making of the members, for each of the
models mentioned above, we examine two types of neighbour selection. At first,
we consider a regular random selection of neighbours in which there is no
priority for selection. In this way, neighbours have the same chance to be
selected. In the second method, we examine the influence of selecting
neighbours according to their degrees. In this case, higher degree nodes are
more likely to be selected.

###  2.3 Network construction

Many works have verified that most real-world networks are heterogeneous, such
that the probability distribution of the number of connections (degree)
follows a power law. These networks are called scale-free networks [21, 22].
Exponential graphs cannot describe these networks, that present a Poisson-like
degree distribution (e.g. random networks) [23, 24]. There are many models to
generate scale-free and random networks. For example, Gomez et al. [20]
proposed a new model to get a smooth transition from random to scale-free
networks. To construct the network, we start with fully connected $m_{0}$
nodes ($m_{0}=3$ in our case), and the rest of the nodes ($N-m_{0}$) are
disconnected. At each time step, a new node is added to the network. With
probability $\alpha$, this node is connected to any of the $N-1$ nodes in the
network. With probability $(1-\alpha)$, the node establishes a link according
to the preferential attachment strategy, i.e., a node’s probability of
receiving a new link is proportional to its degree. For each node, this
process is repeated $\overline{k}$ times, where $\overline{k}$ is the mean
degree of the network, and all nodes from a set of ($N-m_{0}$) are considered.
Notice that the transition from random to scale-free networks is controlled by
the parameter $\alpha$, where $\alpha=0$ for pure random networks and
$\alpha=1$ for a scale-free organization.

We also consider assortative networks, which are given by degree-degree
correlations. Assortativity is defined as the tendency of nodes with a similar
degree to be connected [25]. In other words, the assortativity coefficient is
measured as the Pearson correlation coefficient $(r)$ of the node degree at
the end of each edge. Positive values of $r$ indicate that nodes of similar
degrees are connected. On the other hand, negative values suggest that hubs
tend to connect to low-degree nodes. The assortativity is calculated by[26]:

$r=\frac{\sum_{i=1}^{N}\sum_{j=1}^{N}\left(A_{ij}-\frac{k_{i}k_{j}}{2M}\right)k_{i}k_{j}}{\sum_{i=1}^{N}\sum_{j=1}^{N}\left(ki\delta(i,j)-\frac{k_{i}k_{j}}{2M}\right)k_{i}k_{j}}.$
(3)

where $A_{ij}$ is equal to one if there is a connection between nodes $i$ and
$j$ or equal to zero, otherwise.

To change from random to assortative (disassortative) scale-free networks, we
modify the algorithm [27]. In this case, two random links are selected and
rewired if the network’s total assortativity (dissassortativity) increases
(decreases). Otherwise, the system keeps its first configuration. The node
degree is preserved during this process.

With the rules mentioned above, constructed networks will be connected as each
node will have at least one connection. For the rest of the paper, the size of
the undirected networks and the mean degree of the nodes is considered as
$N=2000$ and $\overline{k}=4$, respectively. Three values for $\alpha$ are
considered here: (i) $\alpha=1$ for random networks, (ii) $\alpha=0.5$ for
networks between random and scale-free structures, and (iii) $\alpha=0.3$ for
scale-free networks. We verify that as $\alpha$ is close to zero, the obtained
results are noisier, although the behaviour trend is the same.

##  3 Results

Initially, we consider the traditional prisoner’s dilemma model without
memory. Each player defines its strategy by randomly selecting a neighbour to
compare its payoff. This neighbour selection can be made at random or
according to the neighbour’s degree. In figures 1 (a) and (d) ($\alpha=1$), we
show the results for random networks. As we can see, the level of
assortativity does not influence the fraction of cooperators. Moreover, the
way we select the neighbours to interact with does not affect the level of
cooperation. This lack of cooperation influence is an expected result because
random networks are homogeneous, and hubs are absent.

When we increase $\alpha$ to 0.5 (figures 1 (b) and (e)), we can see that
assortativity starts to play an essential role in cooperation dynamics. Indeed
for higher values of $\alpha$, when the networks turn to become scale-free
networks (figures 1 (c) and (f)), for small values of $b$, the level of
cooperation is higher for non-assortative and assortative networks. On the
other hand, when $b$ is increased, the cooperation is enhanced in
disassortative networks. Moreover, selecting the neighbours according to the
degree improves the cooperation in disassortative networks. For assortative
networks, the cooperation decreases faster as the value of the parameter $b$
is increased. Therefore, assortativity plays an essential role in cooperation,
but its influence is not trivial. It depends on the defection temptation,
which can improve cooperation if it is more prominent in disassortative
networks.

We repeated the same analysis by including the player’s memory to verify how
the information about previous games influences the evolution of cooperation.
In figure 2, we show the results for the traditional prisoner’s dilemma game
with memory. We consider model A, in which each player follows the information
about the previous games of their neighbours to define their current strategy.
The plots show that increasing the memory length implies the growth of
cooperation, independently of the value of $\alpha$, i.e., for random and
scale-free networks. Also, the neighbour selection according to the degree
tends to increase the level of cooperation, as shown in figure 2(d-f).

For the case of model B, in which each player adds its historical game
recordings to define its strategy, the results are shown in figure 3. The
memory helps improve the cooperation only for larger values of $T=b$. Indeed,
for scale-free networks ($\alpha=0.3$), we can see that the cooperation is
enhanced only for $b>1.5$. Again, the neighbour selection by considering the
node degree raises the level of cooperation, as shown in figure 3(d-f).

To verify the effect of memory and assortativity altogether, we simulate the
prisoner’s dilemma in degree-degree correlated networks. The results for model
A, which considers the information about the neighbour’s payoff, are shown in
figure 4. We consider three memory lengths ($m=1$, $5$ and $20$) with
different assortativity values for three types of networks ($\alpha=1.0,0.5$
and $0.3$). Neighbours are selected according to their degree. In all cases,
increasing the memory length increases the level of cooperation. However, non-
correlated scale-free networks present the highest fraction of cooperators
(see figure 4(c)). For model B, results are in figure 5. Again, uncorrelated
networks with the highest memory length present the highest level of
cooperation.

Compared with the previous results, we can see that memory length decreases
the influence of degree-degree correlation on the level of cooperation.
Moreover, the player strategy (models A or B) does not impact the final
fraction of cooperators significantly. Even so, scale-free networks are the
topology that most improves cooperation.

Figure 1: Fraction of cooperations according to the payoff $T=b$ (the
temptation to defect) for random ($\alpha=1$), half-random ($\alpha=0.5$) and
scale-free ($\alpha=0.3$) networks. Results for the uniform neighbour
selection are shown in (a)-(c), whereas the neighbour sampling in terms of the
node degree is depicted in (d)-(f). Figure 2: Memory influence in PD in
complex networks by assuming the model $A$ with $r=0$. Results for the uniform
neighbour selection are shown in (a)-(c), whereas the neighbour sampling in
terms of the node degree is depicted in (d)-(f).  Figure 3: Memory influence
in PD in complex networks by assuming the model $B$ with $r=0$. Results for
the uniform neighbour selection are shown in (a)-(c), whereas the neighbour
sampling in terms of the node degree is depicted in (d)-(f). Figure 4: Level
of cooperation in degree-degree correlated networks for model A. We consider
three memory lengths (m=1, 5, and 20) and networks topologies (random
($\alpha=1$), half-random ($\alpha=0.5$) and scale-free ($\alpha=0.3$)).Colors
represents the fraction of cooperators $\langle C\rangle$. Figure 5: Level of
cooperation in degree-degree correlated networks for model B. We consider
three memory lengths (m=1, 5, and 20) and networks topologies (random
($\alpha=1$), half-random ($\alpha=0.5$) and scale-free ($\alpha=0.3$)).Colors
represents the fraction of cooperators $\langle C\rangle$.

##  4 Conclusion

This paper has studied the prisoner’s dilemma in correlated networks. We have
verified that assortativity plays a vital role in defining cooperation. For
small values of the temptation payoff, assortativity impairs cooperation in
scale-free networks. On the other hand, cooperation is more considerable when
this payoff increases than in non-correlated or disassortative networks. The
network structure’s effect is weak when we include the player’s memory, who
can consider her/his last games or the last neighbours’ games. Cooperation
impairs when we consider small memory lengths, whereas cooperation improves
for longer memory lengths. Also, scale-free networks promote the highest level
of cooperation when the effect of memory is present.

Therefore, we have verified that non-trivial patterns of connections and the
player’s strategy are two ingredients to be considered to improve the
cooperation between agents. These results can be continued considering other
patterns of connections, like community structure and the presence of cycles
in the network. Moreover, the extension for multilayer networks [28, 29], made
of connected networks, is also a promising analysis since these networks
represent social interactions with more details than traditional single-layer
networks.

##  5 acknowledgement

N. Lotfi is thankful to the FAPESP (grant with number 2020/08359-1) for the
support given to this research.

## References

  * [1] G. Szabó and G. Fath, “Evolutionary games on graphs,” Phys. Rep., vol. 446, no. 4-6, pp. 97–216, 2007.
  * [2] C. P. Roca, J. A. Cuesta, and A. Sánchez, “Evolutionary game theory: Temporal and spatial effects beyond replicator dynamics,” Phys. Life Rev, vol. 6, no. 4, pp. 208–249, 2009.
  * [3] A. Robert et al., “The evolution of cooperation,” 1984.
  * [4] M. A. Nowak and R. M. May, “Evolutionary games and spatial chaos,” Nature, vol. 359, no. 6398, pp. 826–829, 1992.
  * [5] G. Abramson and M. Kuperman, “Social games in a social network,” Phys. Rev. E, vol. 63, no. 3, p. 030901, 2001.
  * [6] N. Masuda and K. Aihara, “Spatial prisoner’s dilemma optimally played in small-world networks,” Phys. Lett. A, vol. 313, no. 1-2, pp. 55–61, 2003\.
  * [7] F. C. Santos, J. F. Rodrigues, and J. M. Pacheco, “Epidemic spreading and cooperation dynamics on homogeneous small-world networks,” Phys. Rev. E, vol. 72, no. 5, p. 056128, 2005.
  * [8] B. J. Kim, A. Trusina, P. Holme, P. Minnhagen, J. S. Chung, and M. Choi, “Dynamic instabilities induced by asymmetric influence: prisoners’ dilemma game in small-world networks,” Phys. Rev. E, vol. 66, no. 2, p. 021907, 2002.
  * [9] Z.-X. Wu, X.-J. Xu, Y. Chen, and Y.-H. Wang, “Spatial prisoner’s dilemma game with volunteering in newman-watts small-world networks,” Phys. Rev. E, vol. 71, no. 3, p. 037103, 2005.
  * [10] J. Ren, W.-X. Wang, and F. Qi, “Randomness enhances cooperation: A resonance-type phenomenon in evolutionary games,” Phys. Rev. E, vol. 75, no. 4, p. 045101, 2007.
  * [11] F. C. Santos and J. M. Pacheco, “Scale-free networks provide a unifying framework for the emergence of cooperation,” Phys. Rev. Lett, vol. 95, no. 9, p. 098104, 2005.
  * [12] F. C. Santos, J. M. Pacheco, and T. Lenaerts, “Evolutionary dynamics of social dilemmas in structured heterogeneous populations,” Proc. Natl. Acad. Sci., vol. 103, no. 9, pp. 3490–3494, 2006.
  * [13] J. Gómez-Gardenes, M. Campillo, L. M. Floría, and Y. Moreno, “Dynamical organization of cooperation in complex topologies,” Phys. Rev. Lett, vol. 98, no. 10, p. 108103, 2007.
  * [14] J. Poncela, J. Gómez-Gardenes, L. M. Floría, and Y. Moreno, “Robustness of cooperation in the evolutionary prisoner’s dilemma on complex networks,” New J. Phys, vol. 9, no. 6, p. 184, 2007.
  * [15] X. Chen, F. Fu, and L. Wang, “Influence of different initial distributions on robust cooperation in scale-free networks: A comparative study,” Phys. Lett. A, vol. 372, no. 8, pp. 1161–1167, 2008.
  * [16] L. Chuang, J. Jian-Yuan, C. Xiao-Jie, C. Rui, and W. Long, “Prisoner’s dilemma game on clustered scale-free networks under different initial distributions,” Chin. Phys. Lett, vol. 26, no. 8, p. 080202, 2009.
  * [17] X. Chen, F. Fu, and L. Wang, “Prisoner’s dilemma on community networks,” Physica A, vol. 378, no. 2, pp. 512–518, 2007.
  * [18] M. Perc, J. J. Jordan, D. G. Rand, Z. Wang, S. Boccaletti, and A. Szolnoki, “Statistical physics of human cooperation,” Phys. Rep., vol. 687, pp. 1–51, 2017.
  * [19] F. Shu, Y. Liu, X. Liu, and X. Zhou, “Memory-based conformity enhances cooperation in social dilemmas,” Appl. Math. Comput, vol. 346, pp. 480–490, 2019.
  * [20] J. Gómez-Gardeñes and Y. Moreno, “From scale-free to erdos-rényi networks,” Phys. Rev. E, vol. 73, no. 5, p. 056124, 2006.
  * [21] M. E. Newman, “The structure and function of complex networks,” SIAM Review, vol. 45, no. 2, pp. 167–256, 2003.
  * [22] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, “Complex networks: Structure and dynamics,” Phys. Rep., vol. 424, no. 4-5, pp. 175–308, 2006.
  * [23] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.
  * [24] A.-L. Barabási, R. Albert, and H. Jeong, “Mean-field theory for scale-free random networks,” Physica A, vol. 272, no. 1-2, pp. 173–187, 1999.
  * [25] M. E. Newman, “Assortative mixing in networks,” Phys. Rev. Lett, vol. 89, no. 20, p. 208701, 2002.
  * [26] M. E. J. Newman, Networks: an introduction.  Oxford University Press, 2018.
  * [27] J. D. Noh, “Percolation transition in networks with degree-degree correlation,” Phys. Rev. E, vol. 76, no. 2, p. 026116, 2007.
  * [28] M. Kivelä, A. Arenas, M. Barthelemy, J. P. Gleeson, Y. Moreno, and M. A. Porter, “Multilayer networks,” J. Complex Networks, vol. 2, no. 3, pp. 203–271, 2014.
  * [29] S. Boccaletti, G. Bianconi, R. Criado, C. I. Del Genio, J. Gómez-Gardenes, M. Romance, I. Sendina-Nadal, Z. Wang, and M. Zanin, “The structure and dynamics of multilayer networks,” Phys. Rep., vol. 544, no. 1, pp. 1–122, 2014.