The landscape nobody is looking at

The road that makes everyone later computed an equilibrium of a congestion network and never asked how anybody would arrive at one. The obvious procedure is to let one participant at a time move to whatever is cheaper given what everybody else is currently doing, and repeat until nobody wants to move.

That procedure has no reason to stop. On a general game it cycles: three participants can chase each other round a loop of states forever, each move an improvement for its mover and the whole sequence returning to where it began. On a congestion game it always stops, and the reason is one number.

What the number is #

Each resource charges according to how many are using it: the first user pays one price, the second another, and so on. Write $c_e(k)$ for what the $k$-th user of resource $e$ pays.

Rosenthal’s potential of a state is

$$\Phi = \sum_{e}\ \sum_{k=1}^{n_e} c_e(k),$$

where $n_e$ is how many are using $e$. For each resource, add up the price the first user pays, plus the price the second pays, plus the price the third, up to the number actually present.

It is nobody’s cost and it is not the total cost. The total cost is $\sum_e n_e\,c_e(n_e)$ — everybody currently on $e$ pays the price at the current load. The potential adds the prices at every load up to the current one, which is a different sum and generally a smaller one. Nothing in the game refers to it, no participant is trying to change it, and it has no interpretation as anybody’s anything.

Its whole property is what happens when somebody moves.

The exact equality #

Suppose one participant leaves resource $e$, which had $n_e$ users, and joins resource $f$, which had $n_f$. Their own cost changes from $c_e(n_e)$ to $c_f(n_f + 1)$, so they save

$$c_e(n_e) - c_f(n_f + 1).$$

The potential loses the top term of $e$’s sum and gains a new top term for $f$’s: it changes by $-c_e(n_e) + c_f(n_f+1)$, which is exactly the negative of that saving.

$$\Delta\Phi = -\,(\text{what the mover saves}).$$

Not proportional to it, not bounded by it — equal to it. The generator asserts that equality at every improving move on every state, and asserts the corresponding statement for every non-improving one, so the claim is checked on all $24$ transitions rather than on the ones that happen to be drawn as arrows.

The reason the equality is exact is that the mover’s cost is the top term of the sum for whichever resource they are on. Everybody else’s cost is unchanged in the sense that matters — the loads on the other resources do not move — and the two loads that do move each change by one user, which changes each sum by exactly one term.

Three consequences, all immediate #

No cycle. Every improving move strictly decreases $\Phi$, so a sequence of improving moves visits a strictly decreasing sequence of numbers and can never return to a state it has left. That is a pigeonhole argument run in reverse: a walk on a finite set must revisit a state eventually unless something forbids it, and here something does. That is the whole termination argument, and it is the same shape as the argument that a tableau closes: find a quantity that goes down at every step and cannot go down forever.

An equilibrium exists. The states are finite, so $\Phi$ has a least value somewhere. At a state of least potential no improving move is available, since one would lower $\Phi$ further. A state with no improving move is exactly a state nobody can leave alone profitably, which is the definition of an equilibrium. Existence is proved by a minimum rather than by a fixed point, which is a considerably cheaper argument than the one Nash needed.

The process is a descent. Best-reply dynamics on a congestion game is a walk downhill on a landscape none of the walkers can see. Each participant is optimising their own cost and the effect is to minimise a quantity nobody has any interest in — which is the precise sense in which selfish behaviour has a direction here, and it is a much more modest statement than it sounds, since the potential’s minimum is not the social optimum.

The minimum is not the good outcome #

It is worth being blunt about this because the descent picture invites the opposite reading.

The potential’s minimum is an equilibrium. It is not the state of least total cost, and the two are different objects: the total is $\sum_e n_e c_e(n_e)$, the potential is $\sum_e \sum_{k \le n_e} c_e(k)$, and minimising the second says nothing about the first.

The whole of the previous rung is that gap. Adding a free link to a network moved the equilibrium and made everybody slower, and the equilibrium after the change is a minimum of the new potential — so the descent arrived precisely where it should have and the destination was worse. A convergence proof is not a quality guarantee, and the two are constantly confused because both are stated as “the process reaches an equilibrium”.

The difference has a clean expression here. The potential charges each user of a resource the price they faced on arrival; the total charges every user the price everybody now faces. So the potential undercounts by exactly the amount each user’s presence raises the cost for the others, and that amount is the externality the equilibrium ignores. Selfish behaviour minimises a quantity in which each participant’s effect on the others has been deleted, which is as exact a statement of what is wrong as this subject has.

Where the valleys are, and how many #

The potential is a function on a finite set and the only structure it has is which states are one move apart. Reading it as a landscape means asking how many local minima it has, and the answer is not always one.

A state with no improving move is a local minimum of $\Phi$ in the only sense available: no neighbour reachable by one move is lower. Several such states can exist, and when they do the descent’s destination depends on where it started and on the order participants moved in.

That is not a defect in the argument; it is the argument being honest about what it proves. The theorem says the descent stops, and it stops at some state with no improving move. Which one is a question the potential does not answer, and there is generally no reason to expect the deepest valley.

The gap between a local and the global minimum of $\Phi$ is a second quantity, distinct from the gap between the equilibrium and the social optimum, and the two are independent. A game can have a unique equilibrium that is far from optimal, or several equilibria all of which are near-optimal, and knowing that the descent converges tells nothing about either.

There is one situation where the ambiguity disappears. When the potential has a strictly unique minimum — no ties anywhere — every descent reaches it and the equilibrium is unique. Ties are exactly where the multiplicity comes from, and on a game whose costs are generic whole numbers they are rare; on a symmetric game, where several participants are interchangeable, they are unavoidable, since permuting identical participants gives states of equal potential.

How long the descent takes #

Termination and speed are different questions, and the potential answers the first completely and the second not at all.

The bound the argument gives is crude: each improving move lowers an integer-valued quantity by at least one, so the number of moves is at most the difference between the largest and smallest potential. On the game drawn that is a handful; on a network with $n$ participants and costs of size $C$ it is proportional to $nC$, which is exponential in the number of bits needed to write $C$ down.

That bound is not merely pessimistic. Finding a pure equilibrium of a general congestion game is a hard problem — it belongs to the complexity class built exactly for problems whose solutions are guaranteed by a potential argument — and instances are known on which best-reply dynamics takes exponentially many moves whatever order the participants move in.

The cost question belongs to another site in this fleet and is named here rather than answered — this collection holds a standing licence to name it and not to price it. What belongs here is the structural half: the potential proves the process stops and says almost nothing about when, and the distinction between an existence proof and an algorithm is exactly the distance between those two sentences.

The same argument at the previous rung’s scale #

The network of the previous rung had six units of traffic rather than three participants, and the traffic was divisible — a unit could in principle split. That is the continuous version of the same statement, and it is worth seeing that the potential survives the change.

With divisible traffic the sum over users becomes an integral over the flow: for a link whose cost at flow $x$ is $c(x)$, the potential contributes $\int_0^{x} c(t)\,dt$ rather than $\sum_{k \le n} c(k)$, and the equilibrium is the flow minimising the sum of those integrals. That formulation is Beckmann’s, from 1956, and it predates Rosenthal’s discrete one by seventeen years.

The two say the same thing and the integral makes the gap to the social optimum unmistakable. The social cost of a link is $x\,c(x)$; the potential’s contribution is $\int_0^x c$. Differentiating the first gives $c(x) + x\,c'(x)$ and the second gives $c(x)$, and the missing term $x\,c'(x)$ is precisely the amount by which one more user raises the cost for everybody already there. The equilibrium optimises a quantity from which that term has been deleted.

Written that way, the whole of the previous rung’s paradox is a missing derivative. A link whose cost does not rise with load has $c' = 0$ and contributes nothing to the discrepancy; the two congestible links have $c' = 1$ and contribute everything. Adding a free link changed which links carry the traffic, moved it onto the two whose $c'$ is not zero, and the gap widened accordingly.

Which games have one #

Rosenthal proved in 1973 that every congestion game has this potential. The converse, proved by Monderer and Shapley in 1996, is the more surprising half: every game with a potential is a congestion game in disguise.

That is a genuine classification rather than a family resemblance. A game is called a potential game when some function on states falls by exactly the mover’s gain at every unilateral move; the theorem says any such game can be rewritten as participants choosing subsets of resources, with costs depending on load, so that the potential is Rosenthal’s. The two definitions — one about a function, one about a construction — describe the same objects.

And plenty of games have none. A game with a best-reply cycle cannot have a potential, since a cycle would require a number to decrease around a loop and return to itself, so the existence of a cycle is a proof that no potential exists — an impossibility established by exhibiting one loop, in the way an invariant establishes one by exhibiting one quantity.

Which puts the two rungs of this anchor in their relationship. A game with a potential has a pure equilibrium and a process that finds it. A game without one may have no pure equilibrium at all, and then existence needs mixtures and a fixed-point argument, and there is no descent anywhere.

Where the argument needs its hypotheses #

The costs must not fall as the load rises. Nothing above used that, and it is not needed for the potential to exist — the equality holds for any cost functions whatever. What it is needed for is the interpretation: with costs that fall as more join, the game is one of shared benefit rather than congestion, the potential still works, and the equilibrium reached is typically the one where everybody piles onto the same resource.

The participants must be identical in what they face. In the game drawn, any participant on resource $e$ pays $c_e(n_e)$; the potential argument breaks if two participants on the same resource pay differently. Weighted congestion games, where participants have different sizes, generally have no potential and can cycle — which was proved by exhibiting a cycle rather than by any general obstruction.

Moves must be one at a time. Two participants swapping resources simultaneously can raise the potential, because the equality was derived for a single change of load. The descent is a statement about a sequential process and says nothing about a simultaneous one.

And the resource set must be finite. The minimum argument needs a finite set of states. With a continuum of participants — the setting the previous rung’s traffic actually used — the corresponding statement is that the equilibrium minimises an integral, which is Beckmann’s formulation from 1956, and it predates Rosenthal’s by seventeen years.

What the pictures cannot show #

The figures rank eight states and draw twenty-four transitions, which is the whole of a game with three participants and two resources. Everything interesting about these games happens at sizes where the state count is astronomical — a hundred participants over five resources has $5^{100}$ states — and no picture of the landscape exists at any size worth studying.

The arrows show which moves improve and not which move is taken. The process is one participant at a time in some order, and the order is not drawn because the theorem does not depend on it: every order terminates, at possibly different equilibria. A figure showing one path would be showing a choice the argument was made not to require.

And the potential is drawn as a column of numbers rather than as a surface. It is a function on a finite set with no geometry — the states are not near or far from each other except through the moves — so the word landscape in this essay’s title is a metaphor the picture cannot support, and the honest object is a directed graph with no arrow going up.

The ladder from here #

Rungs above: two equilibria and no way to choose, which is what the descent leaves open when the landscape has more than one valley. Weighted and player-specific congestion games, where the potential fails and cycles reappear. The complexity class of problems whose solution is guaranteed by a potential argument, and the proof that finding a pure equilibrium is complete for it. Beckmann’s continuous formulation, where the equilibrium minimises an integral and the social optimum minimises a different one, so the price of anarchy is a ratio between two variational problems. And no-regret learning, whose long-run average is a coarse correlated equilibrium on every game rather than a pure one on some.

A quantity nobody is optimising #

The habit is worth stating on its own, because it is one of the most reliable ways to prove a process terminates and it looks like a trick every time.

The participants are minimising their own costs. The proof works with a completely different function, which nobody is minimising, which has no interpretation, and whose only property is an accounting identity relating its changes to theirs. The right quantity to find is not the one anybody wants, but the one the moves control.

The same manoeuvre is how a tableau is shown to terminate — the decreasing quantity is the total size of the undecomposed formulas, which nobody is trying to reduce — and how Euclid’s algorithm is, where it is the remainder — the same descent that produces a fraction’s continued form as a side effect. In every case the process is doing one thing and the proof watches another, and the whole art is finding the second one.

There is a caution to go with it. A decreasing quantity proves the process stops and says nothing about where. The potential’s minimum is an equilibrium and not a good outcome; the tableau terminates and may be enormous; Euclid’s algorithm halts in a number of steps nobody bounded well for two thousand years. Termination is the cheapest of the questions and the only one this kind of argument answers.