COMP559编程代写、代写Java，Python程序

日期：2022-02-24 11:15

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)

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),

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