Congestion Games

Games where each player's payoff depends on the load each facility carries.

Ask the Game theory assistant 1 min read · Updated September 9, 2026

Definition

Players choose subsets of facilities $E$ ; payoff $u_i(s)=-\sum_{e\in s_i}c_e(f_e(s))$ where $f_e(s)$ is the number of players using $e$ .

Nonatomic (continuous flow) and atomic (discrete) variants yield Wardrop and Nash equilibria respectively.

Every facility's cost depends only on its total usage, not on who uses it.

Always a potential game, so pure equilibria always exist.

Selfish routing on Pigou's network shows the Price of Anarchy $=4/3$ for linear latencies (Roughgarden-Tardos).

Job scheduling on identical machines is a congestion game.

Rosenthal (1973): every congestion game has the exact potential $\Phi(s)=\sum_e\sum_{k=1}^{f_e(s)}c_e(k)$ , hence a pure Nash equilibrium.

Beckmann-McGuire-Winsten variational formulation gives Wardrop equilibrium as a convex program.

Internet routing (BGP), transportation planning, load balancing in data centers, and cloud resource allocation.

Core in algorithmic game theory.

Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.