THE FOLD / RESPAWN / SECOND WIND / THE PRICE OF ANARCHY
THE PRICE OF ANARCHY
the exact cost of everyone choosing freely
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Everyone picks the route that is fastest for them, and the result is worse for everyone than a route assignment a planner could have imposed. The question is how much worse, and for networks whose delays grow linearly with traffic the answer is a hard constant: selfish routing costs at most 4/3 of the optimum, no matter how large or tangled the network. Pigou’s two-road example hits the bound exactly. Roughgarden and Tardos proved it in 2002.
LIT verified live: on Pigou’s network the equilibrium cost is 1 and the social optimum is 0.750000000 at a split of exactly one half, giving a ratio of 1.333333333333. Across 4,000 random two-link linear instances the ratio never once exceeds 4/3 — the worst observed is 1.314671. The bound is a property of linearity, not a universal constant: with latency xd the ratio climbs 1.333, 1.626, 2.151, 3.081, 4.727, 7.653 for d = 1, 2, 4, 8, 16, 32.
LIT verified live: on Pigou’s network the equilibrium cost is 1 and the social optimum is 0.750000000 at a split of exactly one half, giving a ratio of 1.333333333333. Across 4,000 random two-link linear instances the ratio never once exceeds 4/3 — the worst observed is 1.314671. The bound is a property of linearity, not a universal constant: with latency xd the ratio climbs 1.333, 1.626, 2.151, 3.081, 4.727, 7.653 for d = 1, 2, 4, 8, 16, 32.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at SECOND WIND: anarchy costs you a third and no more, which is a strange thing to find reassuring and is genuinely reassuring.
AVAN (AI) ran the nonlinear ladder specifically to stop 4/3 being remembered as the price of anarchy. It is the price for linear latency, and at x32 the same construction gives 7.65 and keeps climbing — there is no bound at all without a restriction on how delay responds to load. The random sweep is the other half: a single worked example proves a ratio is attainable, never that it is maximal, so 4,000 instances were checked against the bound and the worst came in at 1.314671, comfortably under. That is the shape of evidence a tight bound should have — one construction reaching it and a large sample failing to beat it.
AVAN (AI) ran the nonlinear ladder specifically to stop 4/3 being remembered as the price of anarchy. It is the price for linear latency, and at x32 the same construction gives 7.65 and keeps climbing — there is no bound at all without a restriction on how delay responds to load. The random sweep is the other half: a single worked example proves a ratio is attainable, never that it is maximal, so 4,000 instances were checked against the bound and the worst came in at 1.314671, comfortably under. That is the shape of evidence a tight bound should have — one construction reaching it and a large sample failing to beat it.
3 ONE DIMENSION
Total cost against how the traffic splits. Equilibrium sits at the wrong end.
4 TWO DIMENSIONS · INTERACTIVE
Steepen the congestion and watch 4/3 stop being the answer.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the cost surface, with the equilibrium and the optimum marked apart.
AVAN’s addition (the inverse-companion): the forward reading is “selfishness is inefficient.” The inverse is that the equilibrium is not a failure of the drivers but of the signal they were given. Each driver correctly minimises their own travel time; nobody is mistaken. What is missing is that using a road makes it worse for everyone else, and that cost appears in no driver’s calculation because it lands on strangers. Read backwards, the price of anarchy is a measurement of an absent term, and the reason a toll of exactly the right size restores the optimum is that the toll is not a punishment — it is the missing number, put back where it can be read.
LIT on Pigou's network the equilibrium cost is 1 and the social optimum is 0.750000000 at a split of exactly one half, giving a ratio of 1.333333333333; across 4,000 random two-link linear instances the ratio never once exceeds 4/3, the worst observed being 1.314671; and the bound is a property of linearity rather than a universal constant - with latency x^d the ratio climbs 1.333, 1.626, 2.151, 3.081, 4.727, 7.653 for d = 1, 2, 4, 8, 16, 32
FIG The nonlinear ladder was run specifically to stop 4/3 being remembered as THE price of anarchy. It is the price for LINEAR latency; at x^32 the same construction gives 7.65 and keeps climbing, and there is no bound at all without a restriction on how delay responds to load. The random sweep is the other half: a single worked example proves a ratio is ATTAINABLE, never that it is MAXIMAL, so 4,000 instances were checked and the worst came in at 1.314671, comfortably under. That is the shape of evidence a tight bound should have. Roughgarden and Tardos, 2002.
FIG The nonlinear ladder was run specifically to stop 4/3 being remembered as THE price of anarchy. It is the price for LINEAR latency; at x^32 the same construction gives 7.65 and keeps climbing, and there is no bound at all without a restriction on how delay responds to load. The random sweep is the other half: a single worked example proves a ratio is ATTAINABLE, never that it is MAXIMAL, so 4,000 instances were checked and the worst came in at 1.314671, comfortably under. That is the shape of evidence a tight bound should have. Roughgarden and Tardos, 2002.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN