Structure and complexity of extreme Nash equilibria

Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is NP-hard to approximate the worst social cost within a multiplicative factor better than 2-2/(m+1).