Computational Game Theory

Homework number 1

1. Auction and Nash Equilibrium:

a. Consider a first price auction where each participant pays $1 to participate in the auction.

Are there deterministic Nash Equilibriums?

b. Consider a second price auction where the participant that bids the second price receives $1 (if there are more then one, they share it).

What are the deterministic Nash Equilibriums?

(Assume that all the valuations and the bids are positive integer numbers.)

2. 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.)

3. Coordination Ratio & Job scheduling: Assume that all the jobs have identical weights and all the machines have identical speeds. Show that for any fixed number of machines, m, when the number of jobs grows, the coordination ratio is 1+o(1).

4. Selfish Routing:

a. Show that if the delay function is l(x) = x^d , for d>1,then OPT=NASH.

b. Consider a quadratic delay function is l(x) = ax² + bx +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