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:

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.

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:

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.

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.

to build-Watts-Strogatz-small-world-network
  nw:generate-watts-strogatz players links n-of-players 
     (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.

to build-preferential-attachment-network
  nw:generate-preferential-attachment players links n-of-players    
     min-degree
end

to build-ring-network

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

to build-ring-network
  nw:generate-ring players links n-of-players    
end

to build-star-network

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

to build-star-network
  nw:generate-star players links n-of-players    
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.

to build-grid-4-nbrs-network
  let players-per-line (floor sqrt n-of-players)
  nw:generate-lattice-2d players links 
     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.

to build-wheel-network
  nw:generate-wheel players links n-of-players    
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!

to build-path-network
  build-ring-network
  ask one-of links [die]
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]
   )

  ask players [fd 15]
  ;; 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?

to build-network
  set-default-shape players "circle"
  run (word "build-" network-model "-network")
  ask players [fd 15]
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
      read-from-string n-of-players-for-each-strategy

  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  

  ask players [set strategy -1]
  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.

to setup-players
  let initial-distribution
      read-from-string n-of-players-for-each-strategy

  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
      
      ask players [set strategy -1]
      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

5.7. Complete code in the Code tab

The Code tab is ready!

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 payoff-matrix read-from-string payoffs
  set n-of-strategies length payoff-matrix
end

to setup-players
  let initial-distribution
      read-from-string n-of-players-for-each-strategy

  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

      ask players [set strategy -1]
      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")
  ask players [fd 15]
end

to build-Erdos-Renyi-network
  nw:generate-random players links n-of-players 
     prob-link
end

to build-Watts-Strogatz-small-world-network
 nw:generate-watts-strogatz players links n-of-players 
    (avg-degree-small-world / 2) prob-rewiring
end

to build-preferential-attachment-network
  nw:generate-preferential-attachment players links n-of-players 
     min-degree
end

to build-ring-network
  nw:generate-ring players links n-of-players
end

to build-star-network
  nw:generate-star players links n-of-players
end

to build-grid-4-nbrs-network
  let players-per-line (floor sqrt n-of-players)
  nw:generate-lattice-2d players links 
     players-per-line players-per-line false
end

to build-wheel-network
  nw:generate-wheel players links n-of-players
end

to build-path-network
  build-ring-network
  ask one-of links [die]
end

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

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

  tick
  update-graph
  update-players-color
end

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

to update-payoff
  if any? link-neighbors [
    let mate one-of link-neighbors
    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 any? link-neighbors [
        let observed-player one-of link-neighbors
        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
    layout-spring players links 
                  (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"]
["prob-link" 0.02]
["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]"]
["prob-link" 0.02]
["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:

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 (strategy 0 in the program) and the other half strategy B (strategy 1 in the program). What we can observe is most agents choosing strategy A with probability close to 50% and most agents choosing strategy B with probability close to 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

You can use the following link to download the complete NetLogo model: nxn-imitate-if-better-networks.nlogo.

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 prob-link =
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?

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

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

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

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