We study the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, a constant fraction of the entire demand is routed centrally according to a predefined Stackelberg strategy and the remaining demand is routed selfishly by nonatomic players. We exhibit a family of single-commodity networks for which every Stackelberg strategy has price of anarchy at least proportional to the size of the network, and we exhibit a Stackelberg strategy with price of anarchy bounded by a function of the size of the network. We also give improved bounds on the price of anarchy induced by specific Stackelberg strategies in other cases, such as when the latency functions are polynomials of bounded degree.
This is joint work with Tobias Harks and Guido Schäfer.