COMP559 Assignment 1 (15% of the final grade)
Due: 17:00 on Wednesday 9 March 2022
Please submit your solutions electronically (only in PDF format) in CANVAS. Please do
not use red colour in your solutions and include your name and student number.
Failure in the assessment may be compensated for by higher marks in other components of the
module. Marking of subquestions will be based on the marking descriptors of the University’s
Code of Practice on Assessment.
Standard UoL penalty applies for late submission in accordance with the University’s Code of
Practice on Assessment. The strict deadline even for late submission is 14:00 on Tuesday 15
March 2022, because a feedback will be given afterwards.
Please be aware of the University guidelines on plagiarism and collusion.
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 (first case)). 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.23.
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 4.2 (Theorem 19.13 of [1]).
Use that
∑k
i=1 i
2 = k(k+1)(2k+1)6 and find an upper and lower bound of this expression
that are of the form a · k3 and b · k3, respectively, for some constants a and b.
3. Global Connection Game: (30 marks) The following lower bound construction illus-
trated 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. What is
optimum solution and what is the Price of Stability in this case?
• 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

欢迎咨询51作业君