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 the 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作业君