The Impact of Stackelberg Routing in General Networks

Vincenzo Bonifaci, Tobias Harks, and Guido Schäfer

not available

game theory, selfish routing, Stackelberg game

We investigate the impact of Stackelberg routing in network routing games. In this setting, a fraction alpha of the entire 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 the price of anarchy achievable via Stackelberg routing can be unbounded even for single-commodity networks. In light of this negative result, we consider bicriteria bounds. We develop an efficiently computable Stackelberg strategy that induces a flow whose cost is at most the cost of an optimal flow with respect to demands scaled by a factor of 1 + (1-alpha)^1/2. Thus, we obtain 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, called SCALE, for polynomial latency functions. Our analysis is based on a general technique which is simple, yet powerful enough to obtain (almost) tight bounds for SCALE in general networks. For linear latency functions, we derive an upper bound that matches the current best one and show that this bound is tight. For general polynomial latency functions, we obtain upper bounds that improve all previously known ones.

Download as [PDF] [ps.gz]