**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

(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,

**4. **__Selfish Routing:__

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

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

__The
homework is due in two weeks__