The price of anarchy of finite congestion games

TLDR

The authors investigate the price of anarchy of pure Nash equilibria in congestion games, extending their analysis to polynomial latency functions and mixed Nash equilibria. They analyze congestion games with linear latency functions, then generalize the results to bounded‑degree polynomial latency functions and to mixed Nash equilibria. They find that for asymmetric games the maximum‑social‑cost price of anarchy grows as Θ(√N), while in all other symmetric or asymmetric cases and for both maximum and average social cost it equals 5/2.

Abstract

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.