Part III. Games on networks

# 1. Goal

Our goal here is to extend the model we have created in the previous chapter to study different types of networks.

# 2. Motivation. Assessing the significance of network structure

The model we will develop in this chapter will allow us to explore the importance of network structure on evolutionary game dynamics. Consider, for instance, the 2-player 2-strategy single-optimum coordination game of the previous chapter:

 Player 2 Player 2 chooses A Player 2 chooses B Player 1 Player 1 chooses A 1 , 1 0 , 0 Player 1 chooses B 0 , 0 2 , 2

In the previous chapter we saw that, in this game, under certain conditions:[1]

• an unstructured population of 100 agents (i.e., complete network) will most likely approach the inefficient state where all agents choose strategy A and spend most of the time around there (see fig. 1),[2] but,
• in stark contrast, if we embed that population on a G(n-of-players = 100, prob-link = 0.02) Erdős–Rényi random network, then agents will most likely approach the state where all agents choose strategy B and spend most of the time close to it (see fig. 2).

What is different in these two networks? For a start, note that the degree (i.e. number of link-neighbors) of players in the unstructured population model is 99 (i.e. complete network), while the expected degree of players in the G(100,0.02) random network is just 0.02 · 99 = 1.98 ≈ 2. Thus, an interesting question is: will agents approach the efficient state in any network where they have an average degree of about 2? or is there something special about the random network?

To explore this question, we should embed the population on other networks with average degree about 2, but with different structure. The following figure shows other types of networks where players have about two link-neighbors on average.

Figure 3. Different types of networks with average degree about 2. The average degree is exactly 2 for the ring and the small world networks, and it is (2 · 99 / 100) = 1.98 for the path, star and preferential attachment network.

For each of the networks shown above, do you think that we will get similar results as with the random network? The average degree is about the same in all of them, but the network structure is very different in each case.

Let us build a model to explore this question!

# 3. Description of the model

The only functionality we are going to add to the program implemented in the previous chapter is the possibility of using different network-generating algorithms to create the network. Thus, we refer to the previous chapter to read the basic description of the model. The only information we should add is the following:

Agents are embedded on a network which is created using a network model determined by parameter network-model. This parameter is implemented as a chooser, with 8 possible values:

• “Erdos-Renyi”.  The network is created following the G(n-of-players, prob-link) Erdős–Rényi random network model (Erdös and Rényi (1959)).
• “Watts-Strogatz-small-world”. The network is created using the Watts–Strogatz model (Watts and Strogatz (1998)). This model has two parameters:
• avg-degree-small-world, which determines the average degree of the network, and
• prob-rewiring, which determines the probability of rewiring.

Informally, the algorithm works as follows: initially, nodes are placed in a circle and each node is linked to its closest avg-degree-small-world spatial neighbors (considering both sides). This forms a regular[3] ring lattice, where every node is linked to exactly avg-degree-small-world other nodes. Then, starting at any one node, consider each of her original links that go clockwise and, with probability prob-rewiring, rewire its end at random. Then go to the next node clockwise, and repeat until all nodes have been considered. Self-links (i.e., loops) and duplicated links (i.e., more than one link between two nodes) are not allowed. See example with avg-degree-small-world = 2 and prob-rewiring = 0.1.

• “preferential-attachment”. The network is created following the Barabási–Albert model (Barabási and Albert (1999)). This model has one parameter, i.e. min-degree, which determines the minimum degree that a node can have. Informally, the network is created starting from a complete network of min-degree nodes, and then sequentially adding new nodes. Each new node comes with min-degree additional links to the network, which the new node will use to link to existing nodes with probability proportional to the existing nodes’ degree.  See example with min-degree = 1.
• “ring”.  The network created is a ring, i.e. a network where each node is linked with exactly two other nodes. (See example.)
• “star”. The network created is a star, i.e. a network where one node is linked with every other node, and there are no more links. (See example.)
• “wheel”. The network created is a wheel, i.e. a ring network with one extra node that is linked with every other node. (See example.)
• “grid-4-nbrs”. The network created is a square grid network. In this case, the program will compute the largest integer no greater than the square root of the number of players, and build a square grid network with that many players in each row and column. (See example.)
• “path”. The network created is a path, i.e. a ring network where one link has been removed. (See example.)

The network is created once at the beginning of the simulation and it is kept fixed for the whole simulation. Players can only interact with their link-neighbors in the network.

Figure 4. A wheel network and a square grid network, each with 100 nodes.

# CODE  4. Interface design

We depart from the model we developed in the previous chapter (so if you want to preserve it, now is a good time to duplicate it).

The new interface (see figure 5 above) includes one new chooser and three new sliders at the right side of the interface, where we are placing every parameter related to networks. To be precise, we have to add:

• One chooser for new parameter network-model (with possible values “Erdos-Renyi”, “Watts-Strogatz-small-world”, “preferential-attachment”, “ring”, “star”, “wheel”, “grid-4-nbrs” and “path”).
• Two sliders for the Watts-Strogatz small world networks: one for parameter avg-degree-small-world (with minimum = 0, maximum = 20, and increment = 2), and another one for parameter prob-rewiring (with minimum = 0, maximum = 1, and increment = 0.01).
• One slider for the preferential-attachment networks, for parameter min-degree (with minimum = 1, maximum = 5, and increment = 1).

You may want to add some notes above the sliders, as in figure 5, to let the user know the network model for which each parameter is relevant.

# CODE  5. Code

## 5.1. Skeleton of the code

Since we only have to modify how the network is created, and this is something that is conducted in procedure to setup-players, we will only have to modify that procedure. Nonetheless, to make our code modular and elegant, we will create a new procedure named to build-network where the network will be created, and some other procedures which will run the different network-generating algorithms (see fig. 6).

## 5.2. Procedures to create networks

In the same way that we programmed a procedure to build networks according to the Erdős–Rényi random network model (i.e., to build-Erdos-Renyi-network), we will have to create new procedures for the other network-generating algorithms. To do this, the nw extension will be invaluable.

All procedures we will program to generate networks will be very short (two lines long, at the most) so, in the following sections, rather than providing you with the code, we will just give you the name of the key command you will have to use. We advise you to read the documentation of the key command and try to implement the procedure by yourself. It is not going to be easy, but we know you are ready for the challenge and, if you try this, you will become an even better programmer.

Also, please, do test your code before looking at the solution, and try to fix it. Your first attempts at the code will most likely contain several errors. Being able to understand and fix errors is one of the most important skills we need to develop. Errors are great opportunities to learn. Embrace them as an integral part of the learning process, and enjoy fixing them!

### to build-Watts-Strogatz-small-world-network

Have a look at the documentation of command nw:generate-watts-strogatz and try to implement this procedure. Recall that you will have to use parameters avg-degree-small-world and prob-rewiring.

Implementation of procedure to build-Watts-Strogatz-small-world-network
to build-Watts-Strogatz-small-world-network
(avg-degree-small-world / 2) prob-rewiring
end


### to build-preferential-attachment-network

Have a look at the documentation of command nw:generate-preferential-attachment and try to implement this procedure. Recall that you will have to use parameter min-degree.

Implementation of procedure to build-preferential-attachment-network
to build-preferential-attachment-network
min-degree
end

### to build-ring-network

Have a look at the documentation of command nw:generate-ring and try to implement this procedure.

Implementation of procedure to build-ring-network
to build-ring-network
end


### to build-star-network

Have a look at the documentation of command nw:generate-star and try to implement this procedure.

Implementation of procedure to build-star-network
to build-star-network
end

### to build-grid-4-nbrs-network

Have a look at the documentation of command nw:generate-lattice-2d and try to implement this procedure. Recall that we want to compute the largest integer no greater than the square root of the number of players, and build a square grid network with that many players in each row and column.

Implementation of procedure to build-grid-4-nbrs-network
to build-grid-4-nbrs-network
let players-per-line (floor sqrt n-of-players)
players-per-line players-per-line false
end

### to build-wheel-network

Have a look at the documentation of command nw:generate-wheel and try to implement this procedure.

Implementation of procedure to build-wheel-network
to build-wheel-network
end

### to build-path-network

There is no command to create a path network in the nw extension, but you can easily create it departing from a ring network. Give it a try!

Implementation of procedure to build-path-network
to build-path-network
build-ring-network
end


## 5.3. Procedure to build-network

Our next challenge is to create procedure to build-network, which will run all the commands related to the creation of the network. Currently, some of these commands are in procedure to setup-players, so we should move them to the new procedure. In to build-network we should also run the network-generating algorithm selected by the user in chooser network-model. Taking all this into account, we could program the new procedure as follows:

to build-network
set-default-shape players "circle"
;; the line above comes from setup-players
;; and it should be included before we
;; create the network (which creates the players)

(ifelse
network-model = "Erdos-Renyi"
[build-Erdos-Renyi-network]
network-model = "Watts-Strogatz-small-world"
[build-Watts-Strogatz-small-world-network]
network-model = "preferential-attachment"
[build-preferential-attachment-network]
network-model = "ring"
[build-ring-network]
network-model = "star"
[build-star-network]
network-model = "grid-4-nbrs"
[build-grid-4-nbrs-network]
network-model = "wheel"
[build-wheel-network]
network-model = "path"
[build-path-network]
)

;; the line above comes from setup-players
;; and it should be included after we
;; have created the players
end

The ifelse  block of code above can be replaced by one simple line using command run (a primitive that can take a string containing the name of a command as an input, and it runs the command). Can you implement that line?

Implementation using run
to build-network
set-default-shape players "circle"
run (word "build-" network-model "-network")
end

## 5.4. Procedure to setup-players

Once we have implemented procedure to build-network, we should call it from procedure to setup-players and clean up a little bit. The new implementation of to setup-players could look as follows:

to setup-players
let initial-distribution

if length initial-distribution != length payoff-matrix [
user-message (word "The number of items in\n"
"n-of-players-for-each-strategy (i.e. "
length initial-distribution "):\n"
n-of-players-for-each-strategy
"\nshould be equal to the number of rows\n"
"in the payoff matrix (i.e. "
length payoff-matrix "):\n"
payoffs
)
]

set n-of-players sum initial-distribution

;; the tasks below take place in
;; to build-network now

;; set-default-shape players "circle"  <== deleted line
;; build-Erdos-Renyi-network           <== deleted line
;; ask players [fd 15]                 <== deleted line

build-network   ;; <== new line

let i 0
foreach initial-distribution [ j ->
ask n-of j players with [strategy = -1] [
set payoff 0
set strategy i
set strategy-after-revision strategy
]
set i (i + 1)
]

set n-of-players count players
update-players-color
end

## 5.5. Other procedures

Note that there is no need to modify the code of any other procedure.

## 5.6. Final fixes

The bulk of the code is done, but there are still a couple of minor issues we should deal with. We present them below as instructions that will throw an error. Your goal is to fix the problem.

Run the model with 3 agents embedded on a wheel network

If you try to do this, you will get an error because you need at least 4 agents to create a wheel. To fix this problem, you could modify procedure to setup-players to make sure that there are at least 3 agents, and issue a message if not:

to setup-players
let initial-distribution

if length initial-distribution != length payoff-matrix [
user-message (word "The number of items in\n"
"n-of-players-for-each-strategy (i.e. "
length initial-distribution "):\n"
n-of-players-for-each-strategy
"\nshould be equal to the number of rows\n"
"in the payoff matrix (i.e. "
length payoff-matrix "):\n"
payoffs
)
]

set n-of-players sum initial-distribution
ifelse n-of-players < 4                                  ;<==
[ user-message "There should be at least 4 players" ]  ;<==
[                                                      ;<==
build-network

let i 0
foreach initial-distribution [ j ->
ask up-to-n-of j players with [strategy = -1] [
set payoff 0
set strategy i
set strategy-after-revision strategy
]
set i (i + 1)
]

set n-of-players count players
update-players-color
]                                                      ;<==
end

Create a grid-4-nbrs with initial distribution [20 15]

If you try to do this, you will get the error “Requested 15 random agents from a set of only 5 agents”. This is because procedure to build-grid-4-nbrs-network creates a network of agents. Then, at the foreach loop in procedure to setup-players, initially, 20 random agents out of the 25 with strategy = -1 will be assigned strategy 0. In the second step of the foreach loop, the code asks 15 agents with strategy = -1 to set their strategy to 1, but there are only 5 agents with strategy -1. Thus the error. To fix it, you can use reporter up-to-n-of instead of n-of.

## 5.7. Complete code in the Code tab

extensions [nw]

globals [
payoff-matrix
n-of-strategies
n-of-players
]

breed [players player]

players-own [
strategy
strategy-after-revision
payoff
]

;;;;;;;;;;;;;
;;; SETUP ;;;
;;;;;;;;;;;;;

to setup
clear-all
setup-payoffs
setup-players
setup-graph
reset-ticks
update-graph
end

to setup-payoffs
set n-of-strategies length payoff-matrix
end

to setup-players
let initial-distribution

if length initial-distribution != length payoff-matrix [
user-message (word "The number of items in\n"
"n-of-players-for-each-strategy (i.e. "
length initial-distribution "):\n"
n-of-players-for-each-strategy
"\nshould be equal to the number of rows\n"
"in the payoff matrix (i.e. "
length payoff-matrix "):\n"
payoffs
)
]

set n-of-players sum initial-distribution
ifelse n-of-players < 4
[ user-message "There should be at least 4 players" ]
[
build-network

let i 0
foreach initial-distribution [ j ->
ask up-to-n-of j players with [strategy = -1] [
set payoff 0
set strategy i
set strategy-after-revision strategy
]
set i (i + 1)
]

set n-of-players count players
update-players-color
]
end

to setup-graph
set-current-plot "Strategy Distribution"
foreach (range n-of-strategies) [ i ->
create-temporary-plot-pen (word i)
set-plot-pen-mode 1
set-plot-pen-color 25 + 40 * i
]
end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; NETWORK CONSTRUCTION ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to build-network
set-default-shape players "circle"
run (word "build-" network-model "-network")
end

to build-Erdos-Renyi-network
end

to build-Watts-Strogatz-small-world-network
(avg-degree-small-world / 2) prob-rewiring
end

to build-preferential-attachment-network
min-degree
end

to build-ring-network
end

to build-star-network
end

to build-grid-4-nbrs-network
let players-per-line (floor sqrt n-of-players)
players-per-line players-per-line false
end

to build-wheel-network
end

to build-path-network
build-ring-network
end

;;;;;;;;;;
;;; GO ;;;
;;;;;;;;;;

to go
if (random-float 1 < prob-revision) [
update-strategy-after-revision
]
]

tick
update-graph
update-players-color
end

;;;;;;;;;;;;;;;;;;;;;;;;;
;;; UPDATE PROCEDURES ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;

to update-payoff
set payoff
item ([strategy] of mate) (item strategy payoff-matrix)
]
end

to update-strategy-after-revision
ifelse random-float 1 < noise
[ set strategy-after-revision (random n-of-strategies) ]
[
if ([payoff] of observed-player) > payoff [
set strategy-after-revision
([strategy] of observed-player)
]
]
]
end

to update-strategy
set strategy strategy-after-revision
end

to update-graph
let strategy-numbers (range n-of-strategies)
let strategy-frequencies map [ n ->
count players with [strategy = n] / n-of-players
] strategy-numbers

set-current-plot "Strategy Distribution"
let bar 1
foreach strategy-numbers [ n ->
set-current-plot-pen (word n)
plotxy ticks bar
set bar (bar - (item n strategy-frequencies))
]
set-plot-y-range 0 1
end

to update-players-color
ask players [set color 25 + 40 * strategy]
end

;;;;;;;;;;;;;;
;;; LAYOUT ;;;
;;;;;;;;;;;;;;

;; Procedures taken from Wilensky's (2005a) NetLogo Preferential
;; Attachment model
;; http://ccl.northwestern.edu/netlogo/models/PreferentialAttachment
;; and Wilensky's (2005b) Mouse Drag One Example
;; http://ccl.northwestern.edu/netlogo/models/MouseDragOneExample
to relax-network
;; the number 3 here is arbitrary; more repetitions slows down the
;; model, but too few gives poor layouts
repeat 3 [
;; the more players we have to fit into
;; the same amount of space, the smaller
;; the inputs to layout-spring we'll need to use
let factor sqrt count players
;; numbers here are arbitrarily chosen for pleasing appearance
(1 / factor) (7 / factor) (3 / factor)
display  ;; for smooth animation
]
;; don't bump the edges of the world
let x-offset max [xcor] of players + min [xcor] of players
let y-offset max [ycor] of players + min [ycor] of players
;; big jumps look funny, so only adjust a little each time
set x-offset limit-magnitude x-offset 0.1
set y-offset limit-magnitude y-offset 0.1
ask players [ setxy (xcor - x-offset / 2) (ycor - y-offset / 2) ]
end

to-report limit-magnitude [number limit]
if number > limit [ report limit ]
if number < (- limit) [ report (- limit) ]
report number
end

to drag-and-drop
if mouse-down? [
let candidate min-one-of players
[distancexy mouse-xcor mouse-ycor]
if [distancexy mouse-xcor mouse-ycor] of candidate < 1 [
;; The WATCH primitive puts a "halo" around the watched turtle.
watch candidate
while [mouse-down?] [
;; If we don't force the view to update, the user won't
;; be able to see the turtle moving around.
display
;; The SUBJECT primitive reports the turtle being watched.
ask subject [ setxy mouse-xcor mouse-ycor ]
]
;; Undoes the effects of WATCH.
reset-perspective
]
]
end

# 6. Sample runs

Now that we have the model, we can investigate the question we posed at the motivation section above. To obtain robust statistics, we can conduct an experiment where we run 1000 runs for different types of networks with average degree about 2, and for each type of network we gather the average percentage of players with strategy B at tick 5000 (across the 1000 runs).

The baseline settings will be the same as in the previous chapter (i.e.: noise = 0.03, prob-revision = 0.1, and initial strategy distribution [70 30]), and we will consider the following network-generating algorithms and parameter values:

• “Erdos-Renyi”, with prob-link = 0.02
• “Watts-Strogatz-small-world”, with avg-degree-small-world = 2 and five different values for prob-rewiring: {0, 0.25, 0.5, 0.75, 1}
• “preferential-attachment” with min-degree = 1
• “ring”
• “star”
• “path”

Try to set up this experiment by yourself. You can find our setup below.

Experiment setup

We have set up the following two experiments in BehaviorSpace:

1. One for all the runs that do not use the network model “Watts-Strogatz-small-world”:

The full setting of variables for this experiment is:

["network-model" "Erdos-Renyi" "preferential-attachment" "ring" "star" "path"]
["min-degree" 1]
["payoffs" "[[1 0]\n [0 2]]"]
["n-of-players-for-each-strategy" "[70 30]"]
["prob-revision" 0.1]
["noise" 0.03]
["avg-degree-small-world" 2]
["prob-rewiring" 0]

2. And a second experiment for all the runs that use the network model “Watts-Strogatz-small-world”:

The full setting of variables for this experiment is:

["network-model" "Watts-Strogatz-small-world"]
["avg-degree-small-world" 2]
["prob-rewiring" [0 0.25 1]]
["payoffs" "[[1 0]\n [0 2]]"]
["prob-revision" 0.1 ]
["noise" 0.03]
["n-of-players-for-each-strategy" "[70 30]"]
["min-degree" 1]


We obtained the data in table format and, with the help of a pivot table (within an Excel spreadsheet), we easily created the following table:

Network model Average percentage of
B-strategists
Std. error of the average[4]
Erdos-Renyi, with
87.18% 0.17%
Watts-Strogatz-small-world, with
avg-degree-small-world = 2 and
—> prob-rewiring = 0 95.56% 0.10%
—> prob-rewiring = 0.25 94.92% 0.12%
—> prob-rewiring = 0.50 94.73% 0.13%
—> prob-rewiring = 0.75 94.39% 0.16%
—> prob-rewiring = 1.00 94.31% 0.15%
preferential-attachment with min-degree = 1 93.95% 0.23%
ring 95.65% 0.09%
star 50.33% 1.50%
path 95.48% 0.10%

Looking at the table, we can see that under most network models, agents are able to coordinate on the efficient strategy regardless of the network structure, but there is one exception: the star network. See the following video:

Under this configuration, the population spends most of the time near one of the two monomorphic states (where all players are choosing the same strategy), with frequent switches between the two regimes. Thus, the 50.33% average does not denote that at tick 5000 we can expect to see half the population using strategy A and the other half strategy B. What we can observe is most agents choosing strategy A with probability ~50% and most agents choosing strategy B with probability ~50%. This bimodal distribution explains the high standard error of the average, compared with the other networks.

Thus, in this particular case,[5] it seems that, for most networks with average degree about 2, we can expect most agents to coordinate on efficient strategy B, but there is at least one network (e.g. the star network) for which this statement is not true.

# 7. Exercises

Exercise 1. In this chapter we have seen that if players are embedded on a star network, simulations with nxn-imitate-if-better-networks.nlogo with low (but strictly positive) noise will spend most of the time near one of the two monomorphic states (where all players are choosing the same strategy), with frequent switches between the two regimes. Furthermore, the long-run fraction of agents that use strategy B seems to be 50% Can you explain why this is the case?

Hint: When does the central player change strategy? When do the players at the periphery change strategy?

Exercise 2. In this chapter we have implemented several network-generating algorithms. Some of these can generate a greater number of different networks than others. Can you fill in the following table assuming there are N distinguishable nodes? (i.e., a path network 1-2-3 is different from a path network 1-3-2). Assume N > 4.

Network model Number of different networks that can appear Expected degree Do all generated networks have the same average degree? Do all nodes of all generated networks have the same degree?
Erdős–Rényi, with
ring
star
wheel
path

To fill in the last three columns, consider the following notes:

Expected degree () is the expected degree of a node before the specific network is created. Expected degree is a property of the network model.

Average degree () of a specific (already created) network is the average of every node’s degree. In general, a network model may produce different networks, with potentially different average degrees. However, in some network models, all specific networks that are generated with that model have the same average degree; naturally, in those cases, the average degree is the same as the expected degree, but it is useful to think about whether every network generated by a certain network model has the same average degree or not.

Finally, in some network models, all nodes of all specific networks that are generated with that model have the same degree (). It is also useful to think about whether this is the case for each of the network models. Naturally, in those cases, the degree of every node is the same as the average degree of the specific network and the same as the expected degree of the network model.

Exercise 3. Try to answer the following questions:

1. It is possible that the Erdős–Rényi network model produces a ring network?
2. It is possible that the Erdős–Rényi network model produces a star network?
3. It is possible that the Erdős–Rényi network model produces a wheel network?
4. It is possible that the Erdős–Rényi network model produces a path network?
5. It is possible that the Watts-Strogatz network model produces a ring network?
6. It is possible that the Watts-Strogatz network model produces a star network?
7. It is possible that the Watts-Strogatz network model produces a wheel network?
8. It is possible that the Watts-Strogatz network model produces a path network?
9. Assume the number of nodes is N. Is the Erdős–Rényi network model with prob-link = 2/(N-1) the same as the Watts-Strogatz network model with avg-degree-small-world = 2 and prob-rewiring = 1?

CODE  Exercise 4. Can you implement procedure to build-star-network without using the nw extension?

Hint to implement procedure to build-star-network without using the nw extension

You will have to use primitive create-links-with.

CODE  Exercise 5. Can you implement procedure to build-ring-network without using the nw extension?

Hint to implement procedure to build-ring-network without using the nw extension

You may want to build a list with all the players using sort and then use primitive foreach over two lists. The following sketch may be of help:

1 ~ 2 ~ 3 ~ 4 ~ ... ~ (n-1) ~  n
|   |   |   |           |      |
n ~ 1 ~ 2 ~ 3 ~ ... ~ (n-2) ~ (n-1)

You can create the second list from the first one using fput, last and but-last.

CODE  Exercise 6. Can you implement procedure to build-wheel-network without using the nw extension?

Hint to implement procedure to build-wheel-network without using the nw extension

You may want to start building a ring network.

1. Conditions were that agents use the imitate if better rule with noise = 0.03, prob-revision = 0.1, and initial strategy distribution is 70 A-strategists and 30 B-strategists.
2. This statement refers to finite-time horizons, i.e., what Binmore et al. (1995, p. 10) call the long run.
3. A regular network is a network where every node has the same degree.
4. The standard error of the average equals the standard deviation of the sample divided by the square root of the sample size (1000 in our case).
5. We are assuming that agents use the imitate if better rule with noise = 0.03, prob-revision = 0.1, and initial strategy distribution is 70 A-strategists and 30 B-strategists.