When drivers independently choose their fastest routes, the network settles into an equilibrium that can create more total travel time than coordinated routing. A theorem first published online in 2021 sharply constrains how this inefficiency changes with demand when travel costs are affine. We found a small, exactly checkable network where the natural common-degree quartic extension fails.
We've released the manuscript and exact supplement publicly. It is a limited, precise claim — one network, one natural extension ruled out by an exact counterexample — and the certificate's decisive inequalities can be replayed on a laptop.
Selfish routing in ninety seconds
In a road network, each driver choosing a fastest route produces a Wardrop equilibrium: no one can improve their travel time by switching paths. Equilibria are stable, but not necessarily efficient. The price of anarchy (PoA) measures the gap — the ratio of total travel time under selfish routing to the best achievable total. PoA of 1 means there is no efficiency loss; higher values mean a larger loss.
A natural question: as total demand grows — rush hour building — how does the price of anarchy change?
The shape question
Cominetti, Dose, and Scarsini proved a clean answer for affine costs (travel time growing linearly with load). They define the active network as the edges lying on equilibrium shortest paths. Between demand levels where this network changes, the PoA curve is remarkably tame: monotone, or falling to a single interior minimum. Crucially, no interior maximum while the active network stays fixed.
Traffic models often use nonlinear costs. A standard Bureau of Public Roads (BPR) specification adds a fourth-power load term, capturing congestion that rises steeply with traffic. The same paper gave a mixed-degree example where tameness fails, but it did not settle the direct extension: do common-degree quartic BPR costs still obey the affine-like shape?
Fig. 1 — Between active-network breakpoints, the affine-cost theorem allows monotone curves or a single interior minimum. The quartic counterexample has an interior maximum while its active network stays fixed.
What we found
No. The counterexample is a five-vertex, six-edge network with three routes from origin to destination — a Wheatstone (Braess-style) diamond behind one shared entry edge — with every cost of the form a + b·x⁴, all coefficients positive rationals.
Fig. 2 — The counterexample network. One shared entry edge feeds a Wheatstone diamond; exactly three routes connect origin to destination. Particle density approximates the certified demand-21 equilibrium shares (69.1% · 23.6% · 7.3%). Every edge cost has the form a + b·x⁴ with positive rational coefficients.
Exact interval certificates show that across the entire demand range [17, 24], all three routes carry positive traffic and remain shortest. The active network is therefore the full six-edge graph throughout the interval. A direct quartic extension of the affine theorem would predict the same tame shape. Yet
PoA(21) > PoA(17) and PoA(21) > PoA(24).
Fig. 3 — Numerical PoA curve on [17, 24]. The vertical axis shows PoA − 1 in millionths. Exact rational interval arithmetic certifies the comparisons at demands 17, 21, and 24; the curve and peak near 21.36 are numerical illustrations.
Both comparisons are strict, so by continuity the price of anarchy has an interior local maximum — the bump the affine shape forbids. At differentiability points, a serial-edge identity shows a mechanism: a quartic edge shared by every route can bend the PoA derivative without changing how traffic splits.
Why an exact certificate matters
The bump is numerically shallow. A floating-point plot could neither establish it nor rule it out — rounding error would swallow the inequality either way. So the proof uses exact rational arithmetic end to end: Krawczyk interval operators isolate Wardrop and social-optimum KKT solutions, short exact inequalities exclude the boundary cases, and rational interval costs certify both strict comparisons without relying on rounded decimals.
That makes the result independently checkable in a strong sense. The verifier rebuilds the certificate from the coefficients and compares the output byte-for-byte against the published one. Readers can inspect the checker and rerun every decisive sign test rather than trusting a plot.
Beyond, the research system operated by Nth Research Collective, assisted with literature retrieval, hypothesis generation, proof critique, code and experiment design, adversarial checking, and drafting. Beyond is not an author; Ian D'Ambrosio made the final scientific judgments and accepts full responsibility.
An external audit found manuscript defects but no fatal theorem error. We repaired them, and a fresh independent audit cleared the revised bundle.
What this does and doesn't establish
This is a public preprint awaiting arXiv submission, not peer-reviewed work. The claim is deliberately narrow: to our knowledge, this is the first exact counterexample to this direct common-degree quartic extension of the affine shape theorem. It is one network, not a general theory of quartic PoA; we make no claim that the topology is minimal, and the coefficients are constructed, not calibrated to real roads.
Read it, run it
Reproducibility archive (manuscript and exact certificate): doi.org/10.5281/zenodo.21864490
Verifier and certificate: github.com/Nth-Research-Collective/research — run python3 projects/quartic-bpr-routing/verification/verify.py from the repository root.
If you know of an earlier equivalent result, please send it to research@nthresearch.org.