Fairness and optimality in congestion games

Abstract

We study two problems, that of computing social optimum and that of finding fair allocations, in the congestion game model of Milchtaich[8] Although we show that the general problem is hard to approximate to any factor, we give simple algorithms for natural simplifications. We also consider these problems in the symmetric network congestion game model [11, 4], and show hardness results and approximate solutions.