程序代写案例-COMP326/559

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top
COMP326/559 Tutorial Sheet 1
Exercise 1:
For each of the following instances G of the load balancing game compute a pure Nash
equilibrium A using th
e LPT scheduling algorithm. Also find an optimum assignment.
(a) m = 3 identical machines, n = 7 tasks with weights: 5, 5, 4, 4, 3, 3, 3.
(b) m = 4 identical machines, n = 9 tasks with weights 7, 7, 6, 6, 5, 5, 4, 4, 4.
(Canvas Practice Quiz) Compute also the ratio cost(A)
opt(G)
for each instance.
Generalize the instances to prove that for all m there exist an instance G such that LPT
computes a pure Nash equilibrium A with cost(A) =
(
4
3
− 1
3m
) · opt(G).
Exercise 2 (Optional):
For the example (b) of the previous exercise, start with an arbitrary allocation, and study
the best response dynamics. Check the lexicographic improvement at every step.
Exercise 3 (Optional):
Consider the instance with m = 2 identical machines and n = 3 tasks with weights
w1 = 4, w2 = 6 and w3 = 10. By si = (p, (1− p)) we denote the mixed strategy of player
i where he chooses machine 1 with probability p and machine 2 with probability 1− p.
(a) Show that s1 = (1, 0), s2 = (1/6, 5/6) and s3 = (3/10, 7/10) is a mixed Nash
equilibrium.
(b) What is the expected makespan of the above allocation?
(c) Can you identify any other mixed or pure Nash equilibrium?
Note that we have shown that any instance of the load balancing game admits a pure
Nash equilibrium.
Exercise 4:
Prove that the price of anarchy for pure equilibria on instances of the load balancing
game with n = 2 tasks and m = 2 machines with possibly different speeds is equal to
the golden ratio φ = 1
2
(1 +

5). That is, show the following.
• (Lower bound) Show that there exists a game instance G admitting an equilib-
rium assignment A with cost(A) = φ · opt(G).
• (Upper bound) Show that for every game instance G and every equilibrium
assignment A for this instance, it holds cost(A) ≤ φ · opt(G).
1

欢迎咨询51作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468