FIT3139: Assignment 2
(Due by 11:59pm, Friday, 25 Oct 2018)
[Weight: 15 = 12 + 3 marks.]
This assignment has two parts. The objective of the first part is to use Markov Chain Theory to formulate
and analyse a simple model of social segregation; this part is worth 12 of 15 marks. The second part of the
assignment is a simple problem of strategic interactions, where a game theoretical analysis is useful. This
part is worth 3 marks.
Follow these procedures to submit this assignment
The assignment must be submitted online via Moodle, and should follow the following procedure:
• Accept the Electronic Plagiarism Statement for this Assignment. All your scripts/program will be
scanned using MOSS (a plagiarism detection software). Read Monash Student Academic Integrity
policy for consequences of plagiarism.
• All your scripts and reports MUST contain your name and student ID.
– You are free to program the assignment in either MATLAB or Python.
– Your submitted archive must extract to a directory named as your student ID.
– This directory should contain a subdirectory for each of the two questions in the assignment,
named as q1/, and q2/.
– Within each of those subdirectories the contents include MATLAB/Python A PDF report with
references to the scripts you used (in Python or MATLAB). You should include the scripts as
well.
– When submitting scripts and reports, choose file names that identify the subquestion. (Eg.
q1a script.py, or q1b report.pdf, or q2 script driver.m, or q2 output.txt)
• Submit your zipped file electronically via Moodle.
1
Part 1: A simplified Schelling model
Background
The Schelling model was proposed by Thomas Schelling to explain segregation. We discussed the ba-
sic elements of the model in the first lecture of the unit. Because the model has a very large num-
ber of possible states it is hard to compute the quantities of interest exactly, mostly having to rely on
Montecarlo simulations. A simple implementation of this simulation model can be found here: http:
//www.natureincode.com/code/various/schelling.html.
To make this model tractable, using Markov chains we propose a simplified version of the model. In
the simplified Schelling model agents live on a cycle of finite size n. Agents can be of two types, say 0 and
1. There are no empty positions, thus, a cycle of size n also implies n agents.∗ In this simplified version
there are no thresholds. Instead, an agent is “happy” if at least one of her neighbours is of the same type.
Time is discrete, so t = 1, 2, 3, . . . The dynamics go as follows: At each time-step, two individuals
(residing in different slots) are matched to potentially trade places. This matching procedure is randomly
uniform. Each encounter may result in the agents trading places or retaining their position. Agents will
agree to trade places if at least one of the two benefits and none of the two is worse off after the swap.
It is easy to see that this process gives rise to an absorbing Markov Chain.
Figure 1: Example: A cycle of size 7. According to the rules above, all agents are “happy” except agent 5
Questions Part 1
(a) An absorbing Markov Chain:
• Specify explicitly the transition Matrix of the MC for n = 4. Explain how the transition proba-
bilities are computed and how the states are labeled.
• Show the canonical form of the Markov chain for n = 4. Make sure to specify clearly how states
are re-labeled or re-ordered if necessary.
• Using Montecarlo simulations show how the absorption time varies with n = 4, 5, . . . 10 †.
• Numerically approximate the absorption times for n = 4 and n = 5 and show that they agree
with the Montecarlo simulations.‡
What should you submit for this question?
Your submission must include a report for part 1A, answering the questions and referencing any scripts
used to perform the calculations/simulations. The scripts should also be included as part of your
∗This is a big difference with the standard Schelling model in which vacant spots are a fundamental feature.
†Assume you have n/2 type 0’s and n/2 type 1’s for even n; or (bn/2c+1) type 1’s for odd n. Note that for this larger n
you do not necessarily need to formulate the whole transition matrix of the Markov chain. You can simply simulate the events
that transform one state into another
‡For the numerical calculations in the case of n=5, it may not be necessary to specify a full transition matrix.
2
submission. Alternatively, if using Python, you can submit a Jupyter notebook containing text and
code.
(b) We now turn to a model in which agent may swap places “by mistake”. This means with a probability
they will fail to swap places when they intend to, or will fail to stay put when they should. This small
change results in a new chain that is ergodic.§
• Specify the full transition matrix for n = 4, compute the stationary distribution numerically and
show that it is in agreement with Montecarlo simulations. What can you conclude from this
model?
• Repeat this analysis in the case where agents do not live on a cycle, but on a simple linear
structure; i.e., the agents on both ends only have one neighbour.
• Discuss reasonable extensions of this model that would allow for richer, and perhaps more realistic
dynamics, while keeping tractability at hand. What can you conclude from this exercise?
What should you submit for this question?
Your submission must include a report for part 1B, answering the questions and referencing any scripts
used to perform the calculations/simulations. The scripts should also be included as part of your
submission. Alternatively, if using Python, you can submit a Jupyter notebook containing text and
code.
Part 2
This part of the assignment is about a routing game.
Background:
50 agents are tasked with routing one packet each through a network from vertex S to vertex T . There is
no central control, so each agent is autonomous and strives to minimize total latency for each packet sent
through. The structure of the network is presented in Figure one. The edges S − A, and B − T have a
latency equal to the number of packets going through the edges. Edges S −B and A− T have constant
latency. For example, a single packet going through a route S − A − T has latency 51. If 20 agents are
using that very same route, each will experience a latency of 70, and so on.
S T
A
B
x 50
x50
Figure 2: A network
Questions Part 2
(a) Use a game theoretical argument to predict what each agent should do. Compute the average latency
experienced by each agent for your prediction.
§For numerical and simulation results assume a small
3
(b) A new high-sped technology is introduced that allows for very low-latency traffic. This technology is
expensive, so an edge is afforded and the network is modified as specified in Figure 3. How does your
prediction change, and what is the gain experienced by each agent in this new configuration?
S T
A
B
x 50
x50
0
Figure 3: Network after new technology is introduced
What should you submit for this question?
Your submission must include a report for part 2, answering the questions and (if necessary) referencing any
scripts used to perform calculations. Any scripts used should also be included as part of your submission.
Alternatively, if using Python, you can submit a Jupyter notebook containing text and code.
4