Consider a load balancing game with six jobs and two machines: both machines have speed 1...

 

Transcribed Image Text:

Consider a load balancing game with six jobs and two machines: both machines have speed 1 and the weights of the six jobs are 1, 2, 3, 3, 4 and 5, respectively. (a) [5 marks] Find a best pure Nash equilibrium in this game, that is a pure Nash equilibrium with the smallest possible makespan. (b) [10 marks] Suppose that each job selects uniformly at random and independently the machine to be executed. What is the expected makespan in this case? You need to justify your answer. Consider a load balancing game with six jobs and two machines: one machine has speed 1 and the other one has speed 2 and the weights of the six jobs are 1,2,3,3,4 and 5, respectively. (c) [10 marks] Prove or disprove the following statement: Suppose that each job selects uniformly at random and independently the machine to be executed. Then, this is a Nash equilibrium. Now consider a general load-balancing game with n jobs and m identical machines. (d) [10 marks] For this game, prove or disprove that if there is an allocation of the jobs to the machines that achieves the smallest possible makespan, then this allocation is a pure Nash equilibrium. Consider a load balancing game with six jobs and two machines: both machines have speed 1 and the weights of the six jobs are 1, 2, 3, 3, 4 and 5, respectively. (a) [5 marks] Find a best pure Nash equilibrium in this game, that is a pure Nash equilibrium with the smallest possible makespan. (b) [10 marks] Suppose that each job selects uniformly at random and independently the machine to be executed. What is the expected makespan in this case? You need to justify your answer. Consider a load balancing game with six jobs and two machines: one machine has speed 1 and the other one has speed 2 and the weights of the six jobs are 1,2,3,3,4 and 5, respectively. (c) [10 marks] Prove or disprove the following statement: Suppose that each job selects uniformly at random and independently the machine to be executed. Then, this is a Nash equilibrium. Now consider a general load-balancing game with n jobs and m identical machines. (d) [10 marks] For this game, prove or disprove that if there is an allocation of the jobs to the machines that achieves the smallest possible makespan, then this allocation is a pure Nash equilibrium.