**Homework number 1**

1.
** Nash
Equilibrium:** Show a game where a player by reducing his
payoffs in some outcomes (money burning) improves his payoff at equilibrium.

*2.
*__Cornout__** Competition** Consider a
linear Cornout Competition where the price is

Show that this game has always a pure Nash
equilibrium, for any number of players.

3.
** Max
cut game:** Max cut game is composed from a graph G(V,E). The players are the nodes V. The actions of each
player is binary {0,1}. The utility of each player is
the number of edges connected to it which the other node has a different
action, i.e., the utility of v

a.
Show that every optimal solution is a strong Nash
Equilibrium.

b.
Show that the Price of Anarchy of Max Cut Game is exactly 2
(both upper and lower bound).

c.
BONUS: show that the strong price of anarchy is 3/2

4.
** Job Scheduling:** Show how to compute efficiently a Nash equilibrium for

(Hint:
consider the jobs in a sorted order.)

5. ** Selfish Routing:** For non-atomic routing answer:

a.
Show that if the delay function is *l _{e}
(x) =a_{e} x^{d}* , for

b.
Consider a quadratic delay function is *l _{e}
(x) = a_{e} x^{2} + b_{e} x
+1*, for some constants

__The
homework is due in two weeks__