Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSYS5020: Interdependent Civil Systems – Assignment
Calculation Exercise
Q.1
Pagerank algorithm can be used as an effective centrality measure particularly for directed
networks.
i. Let us compute some ‘pagerank’ values for this network. Assume alpha = 0.8, and all
nodes have a value of (1/N) to begin with, where N is the size of the network. Prepare
an Excel spreadsheet, which dynamically updates the pagerank value of each node
based on the values of relevant nodes in the previous timestep. Based on your
spreadsheet, prepare a sorted list of pagerank values for all nodes after 100 iterations.
(15 marks)
You may assume that pagerank scores are governed by the expression:
Where Pit is the pagerank of node i at time t, A is the adjacency matrix of the network, and
is the damping factor.
ii. Verify that the pagerank values still add up to 1. (2 marks)
iii. How does the pagerank of Node 6 and Node 9 compare? Do you think this makes
sense? Please explain how. (2 marks)
iv. If all the edges are now considered bidirectional (except the ones between Node 6 and
Node 7, which together already make a bidirectional edge), how would it affect the
relative rank of Node 6? Predict and justify your answer without re-computing the
pagerank values of the whole network. (6 marks)
Q.2
Two competing Super Luxury bus services, Alpha Travels and BuzzMe, are operating a daily
service between the Indian cities of Chennai and Bangalore. Each service runs only once a
day, and starts from the same buss stand in each city at 6PM. Travellers do not pre-book
tickets, but come to the buss stand and simply get on board one or the other buss. Dinner is
served on board each bus for all passengers free of charge. The ticket prices are the same,
therefore the travellers will simply choose the bus based on the choice of meal available in
each luxury buss. Usually, each service has a market share of 50%.
Alpha travels has only two meal choices, A1 and A2, however on a given day, it can offer
only one to its customers. Similarly, BuzzMe has four choices of meals, but on a given day
will offer only one. Given the choice of meals on a particular day, a certain percentage of
customers will switch from one service to the other, as given in the following matrix.
B1 B2 B3 B4
A1 2 2 3 -1
A2 4 3 2 6
The numbers given are percentage gains, for Alpha Travels.
(a) What strategy must Alpha Travels choose, to minimise its maximum losses? (to minimise
the damage in their worst-case scenario?) (4 marks)
(b) What strategy BuzzMe must choose, to minimise its maximum losses? (to minimise the
damage in their worst-case scenario?) (4 marks)
(c) Is there a pure saddle point (a pure strategy Nash equilibrium)? If not, what does the
absence of such equilibrium signify? (4 marks)
Suppose that, on a given day, Alpha travel will choose meal A1 with probability x (and meal
A2, therefore, with probability 1-x).
(d) Calculate the expected payoff for Alpha Travels for each of BuzzMe’s pure strategies
(meal choices), in terms of x. Based on this, fill the following table. (8 marks)
B’s pure Strategy A’s expected payoff
B1
B2
B3
B4
(e) Given that x is a probability and ranges from 0 to 1.0, plot A’s expected pay-off against x
as a graph for each of B’s pure strategies, on the same plot. (8 marks)
(f) Using your plot, for each of the following values of x, identify what is the worst pay-off
for A, and which pure strategy of B it corresponds to. (7 marks)
x = 0, 0.2, 0.4, 0.5, 0.6, 0.8, 1.0
(g) Using the plot, identify what is the best (highest) value of the minimum payoff of A, and
what is the value of x this corresponds to. (5 marks)
(i) If A wants to optimise its outcome of the worst-case scenario, how often it should serve
meal A1 and how often it should serve meal A2? (4 marks)
(j) A similar approach can be used to prescribe a ‘mixed strategy’ for BuzzMe. Comment on
why this task is relatively more difficult. (6 marks)
Q.3
Consider an Iterated Stag Hunt (ISH) played in a networked system. The networked system
on which the game is played is given by Fig.2. The pay-off metric for stag-hunt is given by
Fig. 3. The nodes at each iteration play a round of SH with each of their nearest neighbours.
Thus, M games are played per iteration, where M is the number of edges. The nodes use the
simple strategies of coordination C or defection D. Your overall objective is to maximise the
system utility (total payoff for the system).
i. What is the pay-off for the system from a D-C link, a C-C link, and a D-D link,
respectively? Consequently, which types of links do you need to maximise to
increase system pay-off? Which is the second-best type of link? (7 marks)
ii. If there is a constraint that the number of players playing C must equal the number
of players playing D, come up with a scheme which ensures highest public utility per
iteration. In your answer, denote what pure strategy each node must play, and the
corresponding total pay-off per iteration. If the number of nodes is odd, you must
choose a configuration which gives you the highest utility where the difference
between the number of Coordinators and number of Defectors is exactly one. (10
marks)
iii. Now assume that each node plays tit-for-tat in an iterated game, and the pure
strategies that you have assigned are simply the initial pure strategies for iteration
one. Will the system pay-off change in the second iteration? By how much? Justify
the answer. Assume that a given node could play C against one neighbour and D
against another in the same iteration, if the tit-for-tat strategy prescribes that. (4
marks)
iv. If there is no constraint on how many nodes must play C or D, assign the strategy for
each node which will maximise the system pay-off. (4 marks)