A Caltech Library Service

The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games

Swamy, Chaitanya (2007) The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery , New York, pp. 1133-1142. ISBN 978-0-898716-24-5.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be unbounded even if the system consists of only two parallel links. This ratio is called the price of anarchy (PoA). In this paper, we investigate ways by which one can reduce the performance degradation due to selfish behavior. We investigate two primary methods (a) Stackelberg routing strategies, where a central authority, e.g., network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b) network tolls, where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced Nash equilibrium. We obtain results demonstrating the effectiveness of both Stackelberg strategies and tolls in controlling the price of anarchy. For Stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs. (i) In series-parallel graphs, we show that Stackelberg routing reduces the PoA to a constant (depending on the fraction of flow controlled). (ii) For general graphs, we obtain latency-class specific bounds on the PoA with Stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy. (iii) In parallel-link graphs, we show that for any given class L of latency functions, Stackelberg routing reduces the PoA to at most α + (1 − α) • ρ(L), where α is the fraction of flow controlled and ρ(L) is the PoA of class L (when α = 0). For network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of atomic splittable routing games. We show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a convex program. Furthermore, we give a complete characterization of flows that can be induced via tolls. These are the first results on the effectiveness of tolls for atomic splittable games.

Item Type:Book Section
Related URLs:
Additional Information:© 2007 ACM. Research supported partially by NSERC grant 32760-06. I thank Lisa Fleischer for several stimulating discussions, and useful comments on earlier drafts of this paper. In particular, the results in Section 3.1 were obtained in collaboration with her, and I thank her for allowing me to include these results.
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)32760-06
Record Number:CaltechAUTHORS:20121101-093309983
Persistent URL:
Official Citation:Swamy, C. (2007). The effectiveness of Stackelberg strategies and tolls for network congestion games. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. New Orleans, Louisiana, Society for Industrial and Applied Mathematics: 1133-1142.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:35228
Deposited By: Tony Diaz
Deposited On:09 Nov 2012 20:13
Last Modified:03 Oct 2019 04:26

Repository Staff Only: item control page