xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-COMP559-Assignment 1

时间：2021-03-09

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

学霸联盟

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

学霸联盟