Problem 1) Maximum-Weight Best Response Dynamics

Consider the load balancing game on identical machines that we studied. We proved that hest response dynamic converges for this game.  In this problem, we prove that a modification of best response dynamics converges quickly.

Maximum-Weight Best Response Dynamics

Let a = (a₁, . . . , a_n) be an arbitrary action profiles.

while a is not a pure strategy Nash equilibrium do

Among all players i who are not playing best responses in a, let i be the index of the player with largest weight w_i, and let a'_i be a best response to a_-i.

Update the action profile to (a'_i, a_-i).

end while

Output a.

1. Prove that min_j l_j(a), the minimum load among all the machines, is non-decreasing as Maximum-Weight Best Response Dynamics is run.

2. Call a player i "active" if she is currently not playing a best response, and inactive otherwise. Show that a player never goes from being "inactive" to being "active" unless another player moves onto her machine.

3. Let i denote the active player of maximum weight at some intermediate step of Maximum-Weight Best Response Dynamics. Show that in the round after i makes a best response move, any other players i' who become active must have w' < w_i. Conclude that no player ever makes a best response move more than once, and hence that Maximum-Weight Best Reponse Dynamics converages after at most n steps, where n is the number of players.

Problem 2) Bandwidth Sharing Game

As you saw on the last homework, even games with infinite action sets can have pure strategy. Nash equilibria; here you will show another example of such a game using the potential function method.

In this game, each player wants to send flow along a shared channel of maximum capacity 1. On the one hand, each player wants to send as much flow as possible along the channel. On the other hand, the channel becomes less useful the closer it gets to its maximum capacity. Each player can choose to send an amount of flow x_i ∈ [0, 1] along the channel. (That is, the action set for each player i is A_i = [0, 1], and hence is not finite.) For a profile of actions x ∈ A, payer i has utility u_i(x_i, x_-i) =  x_i (1- _j=1∑ⁿx_j).

1. Show that this game is an exact potential game, and conclude that it has a pure strategy Nash equilibrium. (Hint: First write down how much player i's utility changes, fixing the actions of all of the other when i unilaterally deviates. Then try and find a potential function Φ that changes by exactly this amount.)

2. Find a Nash equilibrium of this game. What is the social welfare at this equilibrium? (i.e. the sum of utilities of all the players.)

3. What is the optimal social welfare? (i.e. what the social welfare at the profile of actions that maximizes it, regardless of whether or not this profile is an equilibrium.)