The Effectiveness of Stackelberg Strategies and Tolls for Network Congestion Games
- Creators
- Swamy, Chaitanya
Abstract
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.
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.Additional details
- Eprint ID
- 35227
- DOI
- 10.1145/2344422.2344426
- Resolver ID
- CaltechAUTHORS:20121101-092524415
- 327620-09
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Ontario Early Researcher Award
- Created
-
2012-11-01Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field