The road that makes everyone later

Four nodes. Two of them, S and T, are where an abstract quantity enters the graph and where it leaves; A and B sit between. Four links join them, and each link carries a stated rule for what it costs to traverse: two of them charge a fixed amount whatever the traffic, and two charge in proportion to how much traffic is on them. Six units of traffic must get from S to T, and each unit picks whichever route is cheapest given what the others are doing. Then a fifth link is added, from A to B, and it is free.

Every number in that picture is exact, every route was priced at both flows, and nothing about it is a claim about any road anywhere. What follows is why the second panel is stable, why it is worse, and what “worse” is worth as a number.

What the condition actually says #

A Nash equilibrium is a profile of choices in which no single participant can do better by changing their own choice while everybody else’s stays fixed. That is the whole of the definition, and the whole of the trouble is in the phrase while everybody else’s stays fixed.

The condition is checked one participant at a time. It asks each of them a question about a world in which they alone move, and it never asks the question that would matter if the participants could move together. So an equilibrium is not a state anybody chose, not a state anybody prefers, and not a state anybody agreed to. It is a state with no unilateral escape.

The smallest possible demonstration has two participants and four cells.

The row chooser’s best reply to X is B, and to Y is also B; the column chooser’s best reply to A is Y, and to B is also Y. Each has a dominant strategy — a choice better than the alternative whatever the other does — so the equilibrium is forced, and the arithmetic is not close. And the cell AX, which the equilibrium is not, pays both of them more.

Nothing has gone wrong there. Neither chooser is confused, neither is punished for a mistake, and neither is hiding anything: the whole matrix is on the page and both can read it. The equilibrium is worse for both than a cell they can both see, and the definition of equilibrium has no opinion about that, because it only ever asked about one mover at a time.

The rest of this essay is that same sentence with six units of traffic instead of two choosers, and a graph instead of a matrix. It is worth saying at the outset that the two are the same phenomenon and not an analogy: in both, the state everybody lands in fails a comparison the equilibrium condition never makes.

Six units, two routes, and a time of ten #

Take the graph before the new link. Traffic leaving S can go through A or through B. The link S→A costs $1$ for each unit on it; the link A→T costs $7$ whatever the traffic. Through B the two costs are the other way round: S→B costs $7$ flat, and B→T costs $1$ per unit.

The two routes are therefore mirror images, and the equilibrium follows without any search. Suppose more than half the traffic went through A. Then S→A would carry more than $3$ units and cost more than $3$, while S→B still costs $7$ and B→T carries less than $3$; the route through B would be strictly cheaper and a unit would move. The same argument runs the other way. The only flow with nothing to move is the even split.

At that split each congestible link carries $3$ units and costs $3$, each fixed link costs $7$, and both routes come to $3 + 7 = 10$. Every unit takes $10$, the total across the six units is $6 \times 10 = 60$, and the equal cost of the two routes is exactly what makes the state stable — a unit that switched would find the route it moved to had become the fuller one.

This is a graph in the sense the oldest problem about one uses: nodes, links, and no geometry at all. The positions of S, A, B and T on the page carry nothing; the cost rules carry everything.

Why every unit moves onto the new link #

Now add A→B at zero cost. A third route appears, S→A→B→T, and it uses both congestible links and neither of the flat ones.

Consider a unit sitting on S→A→T while everybody else is somewhere. Its route costs whatever S→A costs at the current flow, plus $7$. The new route costs whatever S→A costs at the current flow, plus $0$, plus whatever B→T costs. Since B→T can never charge more than $6$ — that is the entire traffic — the new route is cheaper than the old one for that unit whatever anybody else has done. The same holds for a unit on S→B→T, by the mirror argument. Every unit moves, and the movement is not a cascade or a fashion; it is the same one-participant comparison the definition makes, answered the same way six times.

So all six units end on S→A→B→T. Both congestible links then carry the whole traffic and cost $6$ each, and the free link costs nothing, so every unit takes $6 + 0 + 6 = 12$.

That flow is an equilibrium, and the figure establishes it by pricing every route at that flow rather than by argument. A unit deviating to S→A→T pays $6$ for the congestible link it is still on and $7$ for the flat one, which is $6 + 7 = 13$; deviating to S→B→T costs the same by symmetry. Both are strictly worse than $12$, so nobody moves.

And every unit is later than it was. Before the link existed each took $10$; after it exists each takes $12$, and $12 = 1.2 \times 10$. Not the average traveller, not most of them — every one of the six, by the same amount. The graph gained an option, kept everything it had, and made every participant strictly worse off. That is Braess’s paradox, and nothing more elaborate than the four comparisons above is required to produce it.

There is a resemblance here worth naming, to a field of this collection that has nothing to do with choosing. In where Newton’s method goes instead, every step is an improvement by the only test the step can apply, and the sequence of improvements arrives somewhere nobody wanted. The mechanism is identical in shape: a locally correct rule, iterated, with no term anywhere in it for the destination.

The link is not the villain #

The obvious reading of the two panels is that the new link was a mistake. That reading is wrong, and the arithmetic says so sharply.

Ask what the least total travel time on the enlarged graph is — over every way of dividing the six units among the three routes, not only the ones an equilibrium would produce. Write $t$ for the traffic on the new route and let the remaining $6 - t$ split evenly between the old two, which symmetry allows. Then each congestible link carries $(6+t)/2$ and each flat link carries $(6-t)/2$, and the total is

$$2 \cdot \left(\frac{6+t}{2}\right)^2 + 7 \cdot (6 - t).$$

That expression is quadratic in $t$ with a positive leading coefficient, so it is convex, and a convex function on an interval has one minimum. Differentiating and setting to zero gives $t = 1$: exactly one unit in six across the new link.

At that split the congestible links carry $7/2$ each and the flat links $5/2$ each, and the total comes to $119/2$, which is $59.5$ — an average of $119/12$, about $9.917$ per unit. That is better than anything the old graph could do, whose best was $60$ in total and $10$ apiece. The new link is a genuine improvement to the graph. It is the equilibrium that ruins it.

The figure does not take the closed form on trust. It computes the same total a second way, by pricing that flow link by link, and requires the two numbers to agree; and then it sweeps every split of the traffic on a lattice of sixths — 703 of them for six units — and asserts that none costs less. The convexity argument and the sweep are independent routes to one number, which is the house habit and is the only reason a closed form belongs in a figure at all.

The window the constant has to sit in #

Both halves of the story needed the flat cost to be $7$, and neither half survives an arbitrary choice. The generator refuses anything outside a window, and the window is worth reading because it is the whole condition for the paradox.

The flat cost $c$ must exceed the rate times the total traffic, here $1 \times 6 = 6$. Below that, the new route is not attractive enough: at the all-on-the-new-route flow, a deviator to a flat route would pay less than the $12$ everybody else is paying, so that flow is not an equilibrium and there is nothing to draw. The flat cost must also fall short of three halves of the same quantity, here $3 \times 1 \times 6 / 2 = 9$. At or above that, the old routes were already so dear that $12$ is an improvement, and the new link makes everybody faster.

Strictly between the two, Braess’s paradox happens. With whole numbers that leaves exactly two admissible flat costs at this size, and the other one is worth drawing.

One step in either direction and the construction stops being clean — at $6$ a unit that abandoned the new route would pay exactly what staying pays, so the flow is no longer something every unit strictly prefers; at $9$ the change is an improvement rather than a harm; and below $6$ the new route is not taken at all. That sensitivity is not a weakness of the example. It is the finding: whether adding a free option helps or harms depends on a comparison between two numbers that nothing in the graph’s description makes visible.

The number the gap has, and the number it does not #

The honest measure of the gap between an equilibrium and an optimum is a ratio: the total the equilibrium produces, divided by the least total achievable. It is called the price of anarchy, and here it is $72$ against $119/2$, which is $144/119$, or $1.210$ to three places.

The word “anarchy” is doing no moral work in that name, and this essay draws no conclusion from it. It names a quantity, and the quantity is a property of a graph and its cost rules, not of the participants — the participants in this graph are units of an abstract quantity and have no character to speak of.

The ratio is not a constant. It moves when the graph does.

Three graphs of the same shape, and the ratio climbs: $1.210$, then $1.254$, then $1.266$. A reader who had seen only the first would have concluded that the equilibrium wastes about a fifth, and would have been wrong about the second and the third. The smallest instance of a family is the one most likely to be drawn and the least entitled to speak for the family, which is a habit this collection has met before — the four stable matchings of an instance with four on a side say nothing about the three of a hundred and twenty at five.

What the climbing sequence does not establish is where it climbs to. There is a theorem, due to Roughgarden and Tardos in 2002, that for cost rules of this shape — constant plus a term proportional to flow — the price of anarchy is never more than $4/3$, over every graph of every size with every such rule. Every ratio above is below $4/3$, which is consistent with the theorem and is not evidence for it. Three graphs cannot establish a bound quantified over all of them.

When no cell survives the test #

Return to the two-chooser picture, because the equilibrium condition has a second failure mode and it is the one that made the subject need probability.

Whatever cell is proposed, somebody has a reason to move, and moving takes the pair to a cell where somebody else has a reason to move. Chase it and the four cells cycle. An existence claim about equilibria is therefore false as stated, and the repair is to let a chooser name a probability rather than a choice: a mixed strategy, which is a weighting over the available options, evaluated by expected payoff.

That the two numbers coincide is the minimax theorem, which is the previous rung of this anchor and which is linear-programming duality in different clothes — the same equality that closes the gap in two numbers that have to meet. Once mixed strategies are allowed, an equilibrium always exists, and the proof is the surprising part: it is not a construction and not a search, but an appeal to the fact that a continuous map of a suitable region into itself must leave something exactly where it was. Nash’s 1950 argument is a fixed-point theorem from topology, applied to the map that sends every profile of mixtures to the best replies to it. A theorem about a rubber sheet is the reason a game has a solution.

Existence, however, is all it gives. Nothing in the fixed-point argument says the fixed point is good for anybody, and the network above is the demonstration that it need not be.

The strategies that can be struck, in any order #

One thing in this subject is robust, and it deserves its place beside so much that is not.

A strategy is strictly dominated when another belonging to the same chooser pays strictly more against every reply still in play — the mirror of the dominant strategy in the first matrix, where one option beat the other against everything the opponent had. A dominant strategy makes the choice for its owner in one step; a dominated one is removed and the removal changes what the other chooser faces. So striking one can expose another that was safe a moment earlier, the process has an order, and the claim that the order does not matter is exactly the kind a brute-force check settles and an argument does not. Here the choices branch: two independent two-step chains, six distinct orders, and the figure runs all six rather than the one that reads best.

That the survivor is also the boxed cell is not a coincidence: nothing strictly dominated can be part of an equilibrium, since a strategy beaten against every reply is a best reply to none. The figure asserts the agreement rather than remarking on it.

What the drawings settle #

The figures on this page decide four different kinds of thing, and they are not equally strong.

Settled completely. That these particular flows are equilibria, and that the travel times are $10$ and $12$, $11$ and $12$, $16$ and $20$, $19$ and $24$. Every route was priced at every flow drawn and the comparisons are between exact rationals with no tolerance anywhere. The same goes for the cells boxed in each matrix: every cell was put to two independent tests and the verdicts were required to agree.

Settled, with a stated qualification. That $119/2$ is the least total on the first enlarged graph. The closed form comes from a convexity argument, and it is confirmed against a lattice of sixths — 703 splits, every one priced in full. A lattice is not the set of all real-valued splits, and the confirmation is therefore a check on the closed form rather than a substitute for it. The convexity argument is what carries the claim; the 703 splits are what would have caught an error in it.

Not settled at all. That the price of anarchy for cost rules of this shape never exceeds $4/3$. That is a statement about every graph of every size, and no finite collection of drawings touches it; it is quoted above and attributed, and nothing here proves it. Likewise the existence of an equilibrium in mixed strategies for every finite game: the fixed-point argument proves it, the figures illustrate one instance of it, and the two should not be confused, in the way a finite check of finitely many cases is a proof of exactly what it enumerated and of nothing beyond.

Outside this page’s subject entirely. How much work it takes to find an equilibrium in a large graph, and how that grows. That is a question about cost, another site in this fleet owns it, and no sentence here divides one number by another to answer it.

Where the name comes from #

The construction is named for a paper of 1968 by Dietrich Braess, and the fact that it has a name is the whole of the history that belongs here: no real network, no real instance and no measurement appears on this page or is needed for any of it. The finding is a consequence of a stated cost rule and would be exactly as true if nothing in the world resembled it.

That is worth insisting on, because reaching for an instance would weaken the claim rather than support it. What has been established above is that this graph, with these rules, has an equilibrium worse than its optimum by a factor of $144/119$; an instance would be evidence about the world, and the arithmetic is a proof about the rule. The two-chooser matrix is older and carries the same lesson — a condition stated one participant at a time cannot see a comparison that needs two.

Where the field ends #

The rules for choosing gathered here all promise something, and every one of them turned out to cost something the person who wrote it down did not expect. Pairwise majority preference promises a winner and delivers a cycle with no top. A rule that is fair on four reasonable conditions turns out not to exist, and any rule that does exist can be lied to profitably. Rounding a share of seats to whole numbers promises proportionality and gives up monotonicity, so that a seat vanishes when the house grows. Cutting and choosing promises fairness and delivers only proportionality, never freedom from envy, and with indivisible items not even that. A stable matching always exists, and the side that proposes takes the best of them while the other side takes the worst.

Every one of those is the same shape as the one on this page. A condition is stated exactly, it is satisfied, and satisfying it is not what anybody thought they were asking for. The condition is never at fault and there is no better condition waiting behind it; what the exhaustive searches keep finding is that the gap between a rule and its purpose is a real object with a size, and that the size can be computed. For an equilibrium the size has a name, the price of anarchy, and on the first graph above it is $144/119$.