When every travel cost is quartic, can selfish-routing inefficiency rise and then fall while the active network stays fixed?
Yes. We found a five-vertex, six-edge network where the price of anarchy develops an interior maximum even though every route stays active. That is the bump the affine-cost theorem forbids.
The bump is shallow enough that a floating-point plot cannot prove it. Exact rational certificates establish the decisive comparisons, and the verifier replays them on a laptop.
How selfish routing becomes a curve
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 between total travel time under selfish routing and the best achievable total. PoA of 1 means there is no efficiency loss; higher values mean a larger loss.
As total demand grows and rush hour builds, how does the price of anarchy change?
The shape theorem this network breaks
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?
The five-node counterexample
No. The counterexample is a five-vertex, six-edge network with three routes from origin to destination. A Wheatstone (Braess-style) diamond sits behind one shared entry edge. Every 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).
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 the bump needs exact arithmetic
The bump is numerically shallow. A floating-point plot could neither establish it nor rule it out because rounding error would swallow the inequality either way. The proof therefore 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. Research systems are not authors; the author 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 with DOI, awaiting arXiv submission. It is 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
Archived record (manuscript and certificates): 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.