A Caltech Library Service

The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games

Swamy, Chaitanya (2012) The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games. ACM Transactions on Algorithms, 8 (4). Art. No. 36. ISSN 1549-6325. doi:10.1145/2344422.2344426.

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 article, 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, for example, 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.

Item Type:Article
Related URLs:
Additional Information:© 2012 ACM. Received March 2010; revised September 2010 and March 2011; accepted 2011. A preliminary version appeared in the Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms [Swamy 2007]. This research was partially supported by NSERC grant 327620-09 and an Ontario Early Researcher Award, and carried out while the author was a postdoctoral scholar at Caltech. 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. I also thank the anonymous referees for their careful reading of the manuscript and their useful suggestions.
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)327620-09
Ontario Early Researcher AwardUNSPECIFIED
Subject Keywords:Algorithms; Theory; Algorithmic game theory; routing and congestion games; price of anarchy; convex optimization
Issue or Number:4
Record Number:CaltechAUTHORS:20121101-092524415
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:35227
Deposited By: Tony Diaz
Deposited On:01 Nov 2012 21:47
Last Modified:09 Nov 2021 23:13

Repository Staff Only: item control page