🚦

Every commuter picks the route that looks fastest, and the roads fill up until no switch helps. That this ever settles, rather than churning forever, is not obvious. A hidden bookkeeping quantity, the potential, guarantees it.

Congestion and potential games

In a congestion game, each player picks resources and pays a cost that rises with how many others share them. These games always have a pure Nash equilibrium, and strict better-response dynamics reach one, because every improving move decreases a single potential function that cannot fall forever.

From earlier lessons

Two quick ones before we start.

A driver switches to a faster route. Whose travel time is certain to improve from that choice?

A best-response dynamic has each unhappy player switch to their...

Predict, then play

Four drivers choose road A, whose cost equals its number of users, or road B, a flat 3. Move drivers around and watch the potential fall to its minimum.

Why did that happen?

Take a guess, then reveal the reason

Each time a driver switches to a cheaper road, they lower their own cost, and it turns out that this also lowers a global quantity, the potential, by exactly the same amount. Since the potential is bounded below and drops with every improving move, the process cannot go on forever, and where it stops, no one can improve, which is a Nash equilibrium. The potential is a ledger that turns many selfish moves into a single decreasing number.

The math

Definition, congestion and potential games

In a congestion game, each resource has a cost that depends only on how many players use it, and a player’s cost is the sum over the resources it picks. Rosenthal showed every such game admits an exact potential $\Phi$ : whenever one player switches, the change in $\Phi$ equals the change in that player’s cost. Because $\Phi$ strictly decreases at every improving move and takes finitely many values, strict better-response dynamics converge to a pure Nash equilibrium. Monderer and Shapley showed congestion games and finite potential games are essentially the same class.

Here $\Phi(x) = \sum_{k=1}^{x} k + 3(4 - x) = \tfrac{x(x+1)}{2} + 3(4-x)$ when $x$ drivers use road A. Evaluating: $\Phi(0) = 12$ , $\Phi(1) = 10$ , $\Phi(2) = 9$ , $\Phi(3) = 9$ , $\Phi(4) = 10$ . The potential bottoms out at $x = 2$ and $x = 3$ , and both are pure Nash equilibria. Starting from everyone on B, best-response dynamics walk $\Phi$ downhill and stop at $x = 2$ : the move to $x = 3$ takes the switcher from $3$ on B to $3$ on A, no gain, and leaves $\Phi$ unchanged at $9$ . A tie is where improving moves run out.

Work it out

Follow the potential downhill

Start with everyone on road B: $x = 0$ , and $\Phi(0) = 0 + 3\cdot 4 = 12$ . Road A costs $1$ to the first mover versus $3$ on B, so a driver switches; now $x = 1$ , $\Phi(1) = 1 + 9 = 10$ , down by $2$ , exactly that driver’s saving ( $3 \to 1$ ).

Another driver finds A now costs $2$ if they join (two users), strictly better than B’s $3$ , and switches; $x = 2$ , $\Phi = 3 + 6 = 9$ , down by $1$ , again that driver’s saving ( $3 \to 2$ ). Now stop. A third driver moving to A would make it three users at a cost of $3$ , exactly what they already pay on B, so no improving move is left and $x = 2$ is a pure Nash equilibrium. The potential says the same thing: $\Phi(3) = 6 + 3 = 9 = \Phi(2)$ , no drop, no move. The dynamics halt, guaranteed by the ever-decreasing potential.

Key idea

Congestion games always have a pure Nash equilibrium and strict better-response dynamics always reach one, because an exact potential function decreases at every improving move and cannot fall forever.

Check yourself

Check yourselfapply

The split 3 drivers on A and 1 on B is the game's other equilibrium. Why does no one switch there?

Check yourselfanalyse

Why can strict better-response dynamics in a potential game never cycle?

Check yourselfbrings back: pure Nash

What do congestion games guarantee that general games do not?

Sources

Rosenthal, R. W. (1973). A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1), 65-67.
Monderer, D., and Shapley, L. S. (1996). Potential games. Games and Economic Behavior, 14(1), 124-143.