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 p(s)=1-s, and s= ∑xi and the cost
of producing for player i is costi(xi) = ai xi. Namely, the utility of
player i is ui(x)=p(s)xi-aixi.
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 is Uv(x)
= { w: (v,w) in E and xv ≠xw}
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 n jobs and m (different
speed) machines.
(Hint:
consider the jobs in a sorted order.)
5. Selfish Routing: For non-atomic routing answer:
a.
Show that if the delay function is le
(x) =ae xd , for d>1
and a>0, then OPT=NASH.
b.
Consider a quadratic delay function is le
(x) = ae x2 + be x
+1, for some constants a and b.
Derive an example that NASH differs from OPT (as much as you can).
The
homework is due in two weeks