Skip to main content
SpringerLink
Log in

Stackelberg Strategies for Selfish Routing in General Multicommodity Networks

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

A natural generalization of the selfish routing setting arises when some of the users obey a central coordinating authority, while the rest act selfishly. Such behavior can be modeled by dividing the users into an α fraction that are routed according to the central coordinator’s routing strategy (Stackelberg strategy), and the remaining 1−α that determine their strategy selfishly, given the routing of the coordinated users. One seeks to quantify the resulting price of anarchy, i.e., the ratio of the cost of the worst traffic equilibrium to the system optimum, as a function of α. It is well-known that for α=0 and linear latency functions the price of anarchy is at most 4/3 (J. ACM 49, 236–259, 2002). If α tends to 1, the price of anarchy should also tend to 1 for any reasonable algorithm used by the coordinator.

We analyze two such algorithms for Stackelberg routing, LLF and SCALE. For general topology networks, multicommodity users, and linear latency functions, we show a price of anarchy bound for SCALE which decreases from 4/3 to 1 as α increases from 0 to 1, and depends only on α. Up to this work, such a tradeoff was known only for the case of two nodes connected with parallel links (SIAM J. Comput. 33, 332–350, 2004), while for general networks it was not clear whether such a result could be achieved, even in the single-commodity case. We show a weaker bound for LLF and also some extensions to general latency functions.

The existence of a central coordinator is a rather strong requirement for a network. We show that we can do away with such a coordinator, as long as we are allowed to impose taxes (tolls) on the edges in order to steer the selfish users towards an improved system cost. As long as there is at least a fraction α of users that pay their taxes, we show the existence of taxes that lead to the simulation of SCALE by the tax-payers. The extension of the results mentioned above quantifies the improvement on the system cost as the number of tax-evaders decreases.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aashtiani, H.Z., Magnanti, T.L.: Equilibria on a congested transportation network. SIAM J. Algebr. Discret. Methods 2, 213–226 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  2. Başar, T., Olsder, G.J.: Dynamic Noncooperative Game Theory. SIAM, Philadelphia (1999)

    MATH  Google Scholar 

  3. Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press (1956)

  4. Cole, R., Dodis, Y., Roughgarden, T.: Pricing network edges for heterogeneous selfish users. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 521–530 (2003)

  5. Correa, J.R., Stier Moses, N.E.: Personal communication (2006)

  6. Correa, J.R., Schulz, A.S., Stier Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29, 961–976 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  7. Dafermos, S.C.: Traffic equilibrium and variational inequalities. Transp. Sci. 14(1), 42–54 (1980)

    Article  MathSciNet  Google Scholar 

  8. Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 277–285 (2004)

  9. Kaporis, A.C., Spirakis, P.G.: The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. In: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 19–28 (2006)

  10. Karakostas, G., Kolliopoulos, S.G.: Edge pricing of multicommodity networks for heterogeneous selfish users. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 268–276 (2004)

  11. Karakostas, G., Kolliopoulos, S.G.: Stackelberg strategies for selfish routing in general multicommodity networks. Technical Report AdvOL2006/08, McMaster University (June 2006)

  12. Korilis, Y.A., Lazar, A.A., Orda, A.: Achieving network optima using Stackelberg routing strategies. IEEE/ACM Trans. Netw. 5, 161–173 (1997)

    Article  Google Scholar 

  13. Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pp. 404–413 (1999)

  14. Perakis, G.: The price of anarchy when costs are non-separable and asymmetric. In: Proceedings of the 10th Conference on Integer Programming and Combinatorial Optimization, pp. 46–58 (2004)

  15. Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33, 332–350 (2004). Conference version in STOC 2001

    Article  MATH  MathSciNet  Google Scholar 

  16. Roughgarden, T.: Selfish routing. Ph.D. thesis, Cornell University (2002)

  17. Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 341–364 (2003). Special issue on STOC 2002

    Article  MATH  MathSciNet  Google Scholar 

  18. Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)

    Google Scholar 

  19. Roughgarden, T.: Selfish routing and the price of anarchy. Optima (2006)

  20. Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM 49, 236–259 (2002)

    Article  MathSciNet  Google Scholar 

  21. Sharma, Y., Williamson, D.P.: Stackelberg thresholds in network routing games or the value of altruism. In: Proc. ACM Conference on Electronic Commerce, pp. 93–102 (2007)

  22. Sun, J.: A convergence analysis for a convex version of Dikin’s algorithm. Ann. Oper. Res. 62, 357–374 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  23. Swamy, C.: The effectiveness of Stackelberg strategies and tolls for network congestion games. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (2007)

  24. Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. Part II 1, 325–378 (1952)

    Google Scholar 

  25. Yang, H., Huang, H.-J.: The multi-class, multi-criteria traffic network equilibrium and systems optimum problem. Transp. Res. B 38, 1–15 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computing and Software, McMaster University, 1280 Main st. W., Hamilton, ON, L8S 4K1, Canada

    George Karakostas

  2. Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Panepistimiopolis Ilissia, Athens, 157 84, Greece

    Stavros G. Kolliopoulos

Authors
  1. George Karakostas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stavros G. Kolliopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to George Karakostas.

Additional information

Research of G. Karakostas supported by an NSERC Discovery Grant and MITACS.

Research of S. Kolliopoulos partially supported by the University of Athens under the project Kapodistrias.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Karakostas, G., Kolliopoulos, S.G. Stackelberg Strategies for Selfish Routing in General Multicommodity Networks. Algorithmica 53, 132–153 (2009). https://doi.org/10.1007/s00453-007-9018-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9018-5

Keywords

Search

Navigation