# The Price of Stability of Weighted Congestion Games

arXiv: https://arxiv.org/abs/1802.09952 · HTML: https://mlsanity.com/paper/1802.09952/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

## Built on by (most cited first, 1 of 1)

- [Bilevel Coordinated Reflection: A Game-Theoretic Approach to Multi-Agent LLM Systems](https://mlsanity.com/paper/2609.02750/) (2026)

## Abstract (arXiv)

We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least varOmega(Phid)d+1, where Phid~ d/ln d is the unique positive root of equation xd+1=(x+1)d. This almost closes the huge gap between varTheta(d) and Phidd+1. Our bound extends also to network congestion games. We further show that the PoS remains exponential even for singleton games. More generally, we provide a lower bound of varOmega((1+1/α)d/d) on the PoS of α-approximate Nash equilibria for singleton games. All our lower bounds hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of α-approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter α. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter ranges from varTheta(1) to d+1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of α-approximate Nash equilibria is at most (d+1)/α.