We present a deterministic polynomial-time algorithm for computing @math -approximate (pure) Nash equilibria in weighted congestion games with polynomial cost functions of degree at most @math . This is an exponential improvement of the approximation factor with respect to the previously best algorithm. An appealing additional feature of our algorithm is that it uses only best-improvement steps in the actual game, as opposed to earlier approaches that first had to transform the game itself. Our algorithm is an adaptation of the seminal algorithm by [FOCS'11, TEAC 2015], but we utilize an approximate potential function directly on the original game instead of an exact one on a modified game. A critical component of our analysis, which is of independent interest, is the derivation of a novel bound of @math for the Price of Anarchy (PoA) of @math -approximate equilibria in weighted congestion games, where @math is the Lambert-W function. More specifically, we show that this PoA is exactly equal to @math , where @math is the unique positive solution of the equation @math . Our upper bound is derived via a smoothness-like argument, and thus holds even for mixed Nash and correlated equilibria, while our lower bound is simple enough to apply even to singleton congestion games.
We consider the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. For asymmetric games, the price of anarchy of maximum social cost is Θ(√N), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5 2. We extend the results to latency functions that are polynomials of bounded degree. We also extend some of the results to mixed Nash equilibria.