Existence and Complexity of Approximate Equilibria in Weighted Congestion Games: Polynomial Games of Degree d With No α-PNE for Any α < α(d), Where α(d) ≥ √d/(2 ln d) for Large dResearch Paper
Weighted congestion games model players of different sizes sharing resources whose cost grows with load: traffic of different volumes on network links, jobs of different lengths on machines. Rosenthal (1973) showed that unweighted congestion games always have a pure Nash equilibrium, but weighted games may have none, already with polynomial costs. The…