Problem -

Consider the following load balancing game: There are m machines F = {1, . . . , m} and n players. Each player i may choose a single machine on which to run his job: for all i, A_i = F. But now each player's job may take a different amount of time to run on each machine (the machines are not identical - one may have a faster CPU, one may have a faster graphics card, etc). For each machine j ∈ F and each player i, there is a corresponding weight w_i,j describing how long it takes to run player i's job on machine j. The cost of machine j is the sum of the weights of the jobs assigned to it: l_j(a) = ∑_{i:a_i = j} w_i,j. The cost of player i is the cost of the machine he selected: c_i(a) = l_{a_i} (a).

The load balancing game we considered in class was the special case when each player had the same weight on every machine: w_i,j =  w_i,j' ≡ w_i for all j, j'.

1. Fix an action profile a and suppose player i makes a best-response move (i.e. one that strictly decreasing his cost) from playing on machine a_i to playing on machine a'_i. Write a' = (a'_i, a_-i). Show that for all j ∉ {a_i, a'_i}, l_j(a)= l_j(a') and that:

max(l_{a_i}(a'), l_{a'_i}(a')) < max(l_{a_i} (a), l_{a'_i}(a))

2. Show that the load balancing games on unrelated machines has an ordinal potential function (equivalently, a total ordering on all action profiles a ∈ A such that best response moves only move to states later in the ordering), and conclude that such games always have pure strategy Nash equilibria.