2.1 Prisoner’s Dilemma on Scale-Free Networks
We consider a population of agents on scale-free networks of contacts (SF NoCs)—a widely adopted heterogeneous population structure in population dynamics and evolutionary games. We focus our analysis on the efficiency of various interference mechanisms in spatial settings, adopting an agent-based model directly comparable with the setup of recent laboratory experiments on cooperation [
45].
One of the main targets of this work is therefore to measure the impact of network properties and structural heterogeneity in the evolutionary dynamics of interference behaviours. To measure these effects, we will make use of two types of scale-free networks [
6,
16,
34], generated through two growing network models: the
Barabási and Albert (BA) model [
6] and the
Dorogovtsev–Mendes–Samukhin (DMS) model [
17].
The Barabási and Albert (BA) model [
6] is one of the most famous models used in the study of highly heterogeneous, complex networks. The main features of the BA model are that it follows a
preferential attachment rule and has a small clustering coefficient and a typical
power-law degree distribution. In order to explain preferential attachment, let us describe the construction of a BA network. Starting from a small set of
\(m_0\) interconnected nodes, each new node selects and creates a link with
m older nodes according to a probability proportional to their degree. The procedure stops when the required network size of
N is reached. This will produce a network characterised by a power-law distribution,
$$\begin{aligned} p_k \sim k^{-\gamma }, \end{aligned}$$
(1)
where the exponent
\(\gamma \) is its
degree exponent [
5]. There is a high degree correlation between nodes, and the degree distribution is typically skewed with a long tail. There are few hubs in the network that attract an increasing number of new nodes which attach as the network grows (in a typical
“rich-get-richer” scenario). The power-law distribution exhibited by BA networks resembles the heterogeneity present in many real-world networks. However, they are also defined by low clustering coefficients, which means they cannot always be used to approximate realistic settings [
54].
To build heterogeneous networks with a large clustering coefficient, [
17] have proposed the eponymous DMS model. This model follows a similar method of construction as the BA model, is also exemplary of the preferential attachment rules and follows a power-law degree distribution. Crucially, each new node connects with the two extremities of
m (
\(m \ge 2\)) randomly chosen edges, instead, therefore forming characteristic triangular motifs whenever a new node is added to the network. Since the number of edges arriving to any node reflects its degree, the probability of attaching the new node to an old node is proportional to its degree and preferential attachment is recovered. The degree distribution is therefore the same as the one of a BA model, and the degree–degree correlations are also equal [
15]. However, the clustering coefficient is large, and more accurately mimics many realistic social networks [
7,
54]. Moreover, we select an initial number of nodes
\(m_0 = 2\), with two additional edges being created at every time step of network generation. This produces networks of average connectivity
\(z = 4\), serving as a direct comparison between this work and other studies performed on structured populations [
22].
Initially each agent in a population of size
N is designated as either a cooperator (C) or defector (D) with equal probability. Agents’ interaction is modelled using the one-shot prisoner’s dilemma game, where mutual cooperation (mutual defection) yields the reward
R (penalty
P) and unilateral cooperation gives the cooperator the sucker’s pay-off
S and the defector the temptation
T. As a popular interaction model of structured populations [
36], we adopt the following scaled pay-off matrix of the PD (for row player):
with
b (
\(1 < b \le 2\)) representing the temptation to defect. We adopt this weak version of the prisoner’s dilemma in spite of cooperation prevalence shown in previous works on scale-free networks [
48], so as to have a direct comparison with studies on the effects of rewarding mechanisms in different types of networks [
22].
At each time step or generation, each agent plays the PD with its immediate neighbours. The score for each agent is the sum of the pay-offs in these encounters. Before the start of the next generation, the conditions of interference are checked for each agent, and if they qualify, the external decision-maker increases their pay-off. Multiple mechanisms (i.e. multiple conditions) can be active at once, but the individual investment cannot be applied more than once; the schemes determine the eligibility for investment.
At the start of the next generation, each agent’s strategy is updated using one of two social learning paradigms—a
deterministic or a
stochastic rule. Using a deterministic update rule, each agent will choose to imitate the strategy of its highest scored neighbour [
36,
56]. In the stochastic case, instead of copying the highest scored neighbour, at the end of each generation an agent
A with score
\(f_A\) chooses to copy the strategy of a randomly selected neighbour agent
B with fitness
\(f_B\), using a pairwise comparison rule, with an imitation probability given by the Fermi–Dirac function [
57]:
$$\begin{aligned} (1+e^{(f_A - f_B)/K})^{-1}, \end{aligned}$$
where
K denotes the amplitude of noise in the imitation process [
56]. We set
\(K = 0.1\) in our simulations, a value usually adopted in previous works [
11,
41,
56]. Our analysis will be based on this standard evolutionary process in order to focus on understanding the cost efficiency of different interference mechanisms.
We simulate this evolutionary process until a stationary state or a cyclic pattern is reached. The simulations converge quickly in the case of deterministic update, with the exception of some cyclic patterns which never reach a stationary state. Because this work studies cost-effective intervention, these rarely occurring patterns which inherently invite very large total costs are escaped early by running simulations for 75 generations (deterministic update) and 500 generations (stochastic update), at which point the accumulated costs are excessive enough for this mechanism to not be of interest. The difference in the final number of generations accounts for the slower convergence time associated with stochastic dynamics. Moreover, the results are averaged for the last 25 generations of the simulations for a clear and fair comparison (e.g. due to cyclic patterns). In order to improve accuracy related to the randomness of network topology in scale-free networks, each set of parameter values is ran on 10 different pre-seeded graphs for both types of SF NOCs. Furthermore, the results for each combination of network and parameter values are obtained from averaging 30 independent realisations. It is important to note that the distribution of cooperators and defectors on the network is different for every realisation.
Note that we do not consider mutations or random explorations when employing a deterministic update rule. Thus, whenever the population reaches a homogeneous state (i.e. when the population consists of 100% of agents adopting the same strategy), it will remain in that state regardless of interference. Hence, whenever detecting such a state, no further interference will be made. Errors can sometimes occur under the presence of stochastic imitation; thus, we never pre-emptively pause these simulations. Given the difference in convergence time, network size and stopping conditions, we do not directly compare the total costs between these two paradigms.
2.2 Cost-Efficient Interference in Networks
We aim to study how one can efficiently interfere in spatially heterogeneous populations to achieve high levels of cooperation while minimising the cost of interference. An investment decision consists of a cost \(\theta > 0\) to the external decision-making agent/investor, and this value \(\theta \) is added as surplus to the pay-off of each suitable candidate. In order to determine cost efficiency, we vary \(\theta \) for each proposed interference strategy, measuring the total accumulated costs to the investor. Thus, the most efficient interference schemes will be the ones with the lowest relative total cost.
Moreover, in line with previous works on network interference [
10,
22,
26], we compare global interference strategies where investments are triggered based on network-wide information, local neighbourhood information and, lastly, node centrality information.
In the population-based (POP) approach, a decision to invest in desirable behaviours is based on the current composition of the population. We denote \(x_c\) the fraction of individuals in the population adopting cooperative behaviour. Namely, an investment is made if \(x_c\) is at most equal to a threshold \(p_c\) (i.e. when \(x_c \le p_c\)), for \(0 \le p_c \le 1\). They do not invest otherwise (i.e. \(x_c > p_c\)). The value \(p_c\) describes how rare the desirable behaviours should be to trigger external support.
In the neighbourhood-based (NEB) approach, committing an abuse of notation, a decision to invest is based on the fraction \(x_c\) of neighbours of a focal individual with the desirable behaviours, calculated at the local level. Investment happens if \(x_c\) is at most equal to a threshold \(n_c\) (i.e. when \(x_c \le n_c\)), for \(0 \le n_c \le 1\); otherwise, no investment is made.
Given the deliberate inequality between nodes, we need a measurement to distinguish important/influential nodes from less important ones. The degree centrality is the oldest measure of importance or influence ever used in network science [
9]. It denotes the number of neighbours of the node
i; namely, it measures the number of edges of node
i. By definition, degree centrality is normalised using the total number of nodes, or the maximal possible degree,
\(n-1\), to obtain a number between 0 and 1. Despite its simple definition, degree centrality is often a highly effective measure of the influence or importance of a node, since people with more connections tend to be more influential in a social network [
8,
35]. The reason why we define degree centrality by using the previous normalised definition, and not simply the degree, is that it allows us to compare two nodes that belong to different networks regardless of network size [
50]. We will refer to this examination as the
node influence-based (
NI) approach. Degree centrality, denoted by NI-deg or
\(x_{i}^{deg}\), is defined as follows:
$$\begin{aligned} x_{i}^{deg}=deg_{i}=\frac{k_i}{n-1}, \end{aligned}$$
(2)
where
\(k_{i}\) is the degree of the node
i and
\(n-1\) is the total number of nodes. The degree
\(k_i\) of a node
i is given by:
\(k_i = \sum _{j=1}^{n} A_{ij}\), where
A is the adjacency matrix of a finite graph, populated with pairs of vertices which are adjacent (i.e. connected). The decision-maker invests in a cooperator node
C when the value of its degree centrality is above a threshold of influence
\(c_I\), for
\(0 \le c_I \le 1\). Otherwise, i.e. when
\(0 \le x_i < c_I\), no investment is made. The value
\(c_I\) describes how influential a cooperator node should be to trigger an investment into its survival.
For the POP and NEB schemes, the threshold signifies an increase in the number of nodes that satisfy the requirements for investment. In other words, a threshold of 1 means always investing in all nodes which follow the desired strategy. Conversely, a lower threshold implies a more careful approach to investment, whereby the exogenous agent is stricter in their selection of suitable candidates. The opposite is true for NI, as a value of 1 implies only the most connected individual(s) is eligible for investment, whereas a value of 0 means investing in every cooperative agent.
Interestingly, we posit that these mechanisms require different levels of information, which may or may not be readily available in the given network. In some cases, such as social networks, the connectivity (i.e. the number of friends) of a node is virtually free information which requires no effort on the part of the external decision-maker to discern. On the other hand, neighbourhood-based approaches inherently require more information about the population and the level of cooperativeness in different parts of the network. Thus, POP is a broad mechanism which only requires knowledge about overall cooperativeness, but NEB invites complex information gathering, in order to determine the cooperativeness in each neighbourhood. Combining NI with NEB does not require any additional observation than NEB by itself. Our study of neighbourhood-based interference does not directly take into account the cost of gathering information, it is a comparison between perceived gains in cooperation and the associated per-individual cost of interference set out in the interference mechanisms. Our discussion will naturally present these subtle differences in the hierarchy of information gathering, as they signal hidden costs for some application domains.