COMP559 Assignment 1 (15% of the final grade)
Due: 12:00 on Thursday 18 March 2021
Please submit your solutions electronically (in PDF format) at the electronic submission system
of the Computer Science Department which you can find at the following url.
https://sam.csc.liv.ac.uk/COMP/Submissions.pl.
Marking of subquestions will be based on the marking descriptors for level ’M’ modules pub-
lished in Section D.2.5 in the Postgraduate Student Handbook. Please be aware of the University
guidelines on plagiarism and collusion. The marks for late submissions will be affected in ac-
cordance with the University’s Code of Practice on Assessment published in Section 2.2 of the
Postgraduate Student Handbook.
Total: 100 marks
1. Load Balancing Games: (20 marks)
a. (10 marks) Let G be any instance of the load balancing game with n = 3 tasks that
should be placed on m = 2 identical machines. Show that any pure Nash equilibrium
A for G is optimal, i.e., cost(A) = opt(G).
b. (10 marks) (Lower bound Theorem 2.7(a)). Show that, for every m, there exists an
instance G of the load balancing game with m identical machines and n = 2m tasks
that has a Nash equilibrium assignment A : [n] 7→ [m] with
cost(A) =
(
2− 2
m + 1
)
· opt(G)
Hint: Generalize the example with two machines given on slide 2.10.
2. Congestion Games: (50 marks)
a. Wardrop Model: (15 marks) Suppose that we modify Pigou’s example, so that the
costs of the two parallel edges to be 1 and xd (instead of 1 and x) for some d ≥ 1, as
given in the following graph.
What is the price of anarchy of the resulting selfish routing network as a function of d?
1
b. Atomic Weighted Congestions games: (15 marks) Prove Theorem 3.8: Show
that for weighted congestion games with linear latency functions (ce(x) = ae · x + be
for all e ∈ E), the function
Φ˜(s) =
∑
i∈[k]
wi ·
∑
e∈si
(ce(xe(s)) + ce(wi))
=
∑
e∈E
xe(s) · ce(xe(s)) +
∑
i∈[k]
wi ·
∑
e∈si
ce(wi)
is a potential function. More precisely, show that if s = (s1, . . . , sk) and s
′ = (s′j , s−j)
for some j ∈ [k] and s′j ∈ Sj , then
Φ˜(s)− Φ˜(s′) = 2 · (Cj(s)− Cj(s′)).
c. Atomic Unweighted Congestions games: (20 marks) Show that the Price of
Stability of unweighted congestion game with latencies of the form ce(x) = x
2 is at
most 3.
Hint: Use the Potential Function Method, which is Theorem 19.13 of [1]. By appro-
priately defining the parameters of this theorem, you will need to show that cost of the
potential minimizer is at most three times the optimal cost.
3. Global Connection Game: (30 marks) The lower bound construction illustrated in
figure 19.3 (b), page 495 of [1] shows that the price of stability is at least Hk for directed
networks, in the Global Connection Game of section 19.3.1.
• Explain why this example does not give a Hk lower bound for the price of stability
of undirected (where each edge can be used in both directions) networks.
• Provide a lower bound of 4/3, for the price of stability of undirected networks with
only two players.
Hint: To show a lower bound for the Price of Stability it is a good idea to construct
a game which has a unique Nash equilibrium with as high cost as possible.
References
[1] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam-
bridge University Press, 2007.
2











































































学霸联盟