skip to main content
10.5555/1283383.1283505acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

The effectiveness of Stackelberg strategies and tolls for network congestion games

Published: 07 January 2007 Publication History

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 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.

References

[1]
B. Awerbuch, Y. Azar, and A. Epstein. The price of routing unsplittable flow. Proc. 37th STOC, pages 57--66, 2005.
[2]
M. Beckman, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
[3]
I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Taxes for linear atomic congestion games. Proc. 14th ESA, pages 184--195, 2006.
[4]
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. Proc. 37th STOC, pages 67--73, 2005.
[5]
R. Cole, Y. Dodis, and T. Roughgarden. How much can taxes help selfish routing? Journal of Computer and System Sciences, 72:444--467, 2006.
[6]
R. Cole, Y. Dodis, and T. Roughgarden. Pricing network edges for heterogeneous selfish users. Proc. 35th STOC, pages 521--530, 2003.
[7]
R. Cominetti, J. R. Correa, and N. Stier-Moses. Network games with atomic players. Proc. 33rd ICALP, pages 525--536. Springer, 2006.
[8]
J. Correa and N. Stier-Moses. A note on Stackelberg routing. Unpublished manuscript, September 2006.
[9]
J. R. Correa, A. S. Schulz, and N. Stier-Moses. Fast, fair, and efficient flows in networks. Proc. 10th IPCO, pages 59--73. Springer, 2004.
[10]
R. B. Dial. Network-optimized road pricing: Part i: A parable and a model. Operations Research, 47(1):54--64, 1999.
[11]
L. Fleischer, K. Jain, and M. Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. Proc. 45th FOCS, pages 277--285, Rome, Italy, 2004.
[12]
Lisa Fleischer. Linear tolls suffice: New bounds and algorithms for tolls in single source networks. Theoretical Computer Science, 348:217--225, 2005.
[13]
Ara Hayrapetyan, É. Tardos, and T. Wexler. The effect of collusion in congestion games. Proc. 38th STOC, pages 89--98, 2006.
[14]
A. Kaporis and P. Spirakis. The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. Proc. 18th SPAA, pages 19--28, 2006.
[15]
G. Karakostas and S. Kolliopoulos. Edge pricing of multicommodity networks for heterogeneous users. Proc. 45th FOCS, pages 268--276, 2004.
[16]
G. Karakostas and S. Kolliopoulos. Stackelberg strategies for selfish routing in general multicommodity networks. Technical report, McMaster University, June 2006.
[17]
Y. A. Korilis, A. A. Lazar, and A. Orda. Achieving network optima using Stackelberg routing strategies. IEEE/ACM Transactions on Networking, 5(1):161--173, 1997.
[18]
Elias Koutsoupias and C. Papadimitriou. Worst-case equilibria. Proc. 16th STACS, pages 404--413, 1999.
[19]
V. S. A. Kumar and A. Marathe. Improved results for Stackelberg scheduling strategies. Proc. 29th ICALP, 2002.
[20]
A. Orda, R. Rom, and N. Shimkin. Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking, 1:510--521, 1993.
[21]
C. H. Papadimitriou. Algorithms, games, and the internet.
[22]
A. C. Pigou. The Economics of Welfare. Macmillan, 1920.
[23]
T. Roughgarden. Selfish Routing and the Price of Anarchy. MIT Press, 2005.
[24]
T. Roughgarden. Stackelberg scheduling strategies. SIAM J. Computing, 33(2):332--350, 2004.
[25]
T. Roughgarden. The price of anarchy is independent of the network topology. Journal of Computer and System Sciences, 67(2):341--364, 2003.
[26]
T. Roughgarden and É. Tardos. How bad is selfish routing? Journal of the ACM, 49:236--259, 2002.
[27]
Y. Sharma and D. P. Williamson. Stackelberg thresholds in network routing games or the value of altruism. Unpublished manuscript, August 2006.
[28]
J. G. Wardrop. Some theoretical aspects of road traffic research. In Proc. Institute of Civil Engineers, Pt. II, volume 1, pages 325--378. 1952.
[29]
H. Yang and H. J. Huang. The multi-class, multi-criteria traffic network equilibria and system optimum problem. Transportation Research B, 28:1--15, 2004.

Cited By

View all
  1. The effectiveness of Stackelberg strategies and tolls for network congestion games

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
    January 2007
    1322 pages
    ISBN:9780898716245
    • Conference Chair:
    • Harold Gabow

    Sponsors

    Publisher

    Society for Industrial and Applied Mathematics

    United States

    Publication History

    Published: 07 January 2007

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
    Overall Acceptance Rate 411 of 1,322 submissions, 31%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Oracles & followersProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618858(11213-11236)Online publication date: 23-Jul-2023
    • (2019)Leadership in congestion gamesProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367102(485-491)Online publication date: 10-Aug-2019
    • (2017)The Price of OptimumAlgorithmica10.1007/s00453-015-0108-577:3(836-866)Online publication date: 1-Mar-2017
    • (2015)Inducing Approximately Optimal Flow Using Truthful MediatorsProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764509(471-488)Online publication date: 15-Jun-2015
    • (2015)On the Relationships Between Sub Problems in the Hierarchical Optimization FrameworkProceedings of the 28th International Conference on Current Approaches in Applied Artificial Intelligence - Volume 910110.1007/978-3-319-19066-2_23(232-241)Online publication date: 10-Jun-2015
    • (2014)Altruism and Its Impact on the Price of AnarchyACM Transactions on Economics and Computation10.1145/25978932:4(1-45)Online publication date: 28-Oct-2014
    • (2012)The effectiveness of stackelberg strategies and tolls for network congestion gamesACM Transactions on Algorithms10.1145/2344422.23444268:4(1-19)Online publication date: 4-Oct-2012
    • (2011)A Stackelberg strategy for routing flow over timeProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133054(192-201)Online publication date: 23-Jan-2011
    • (2011)Efficiency of restricted tolls in non-atomic network routing gamesProceedings of the 4th international conference on Algorithmic game theory10.5555/2050805.2050841(302-313)Online publication date: 17-Oct-2011
    • (2011)The price of optimum in a matching gameProceedings of the 4th international conference on Algorithmic game theory10.5555/2050805.2050817(81-92)Online publication date: 17-Oct-2011
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media