Computational Game Theory


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 xvxw}

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