We investigate the impact of Stackelberg routing in network routing games. In this setting, a constant fraction of the entire flow demand is first routed by a central authority, called the Stackelberg leader, while the remaining demand is then routed by selfish (nonatomic) players. The aim is to devise Stackelberg strategies, i.e., strategies to route the centrally controlled demand, so as to minimize the price of anarchy of the resulting flow.

Although several advances have been made recently in proving that Stackelberg routing may in fact significantly reduce the price of anarchy for certain network topologies, it is still an open question whether this holds true in general. We answer this question negatively. We prove that no Stackelberg strategy can in general achieve a constant price of anarchy, not even in single-commodity networks.

In light of this negative result, we consider bicriteria bounds. We develop an efficiently computable Stackelberg strategy giving a smooth trade-off curve that scales between the absence of centralized control (doubling the demands is sufficient) and completely centralized control (no scaling is necessary).

Finally, we analyze the effectiveness of a simple Stackelberg strategy for polynomial latency functions, obtaining upper bounds that improve all previously known ones.