A network pricing game for selfish traffic | Distributed Computing Skip to main content
Springer Nature Link
Log in

A network pricing game for selfish traffic

  • Special Issue PODC 05
  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disparate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Acemoglu, D., Ozdaglar, A.: Price competition with elastic traffic and multiple user classes. In: Allerton Conference on Communication, Control and Computing (2005)

  2. Acemoglu, D., Ozdaglar, A.: Competition and efficiency in congested markets (Unpublished Manuscript, 2004)

  3. Acemoglu, D., Ozdaglar, A.: Flow control, routing, and performance from service provider viewpoint (Unpublished Manuscript, 2004)

  4. Afèche, P.: Incentive-compatible revenue management in queuing systems: optimal strategic idleness and other delaying tactics (Unpublished Manuscript, 2004)

  5. Allon, G., Federgruen, A.: Competition in service industries (Unpublished Manuscript, 2004)

  6. Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: IEEE Symposium on Foundations of Computer Science, pp. 295–304 (2004)

  7. Anshelevich, E., Dasgupta, A., Tardos, É., Wexler, T.: Near-optimal network design with selfish agents. In: ACM Symposium on theory of computing, pp. 511–520 (2003)

  8. Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the economics of transportation. Yale University Press, New Haven, Connecticut (1956)

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

  10. Cole, R., Dodis, Y., Roughgarden, T.: How much can taxes help selfish routing. In: ACM Conference on Electronic Commerce, pp. 98–107 (2003)

  11. Correa JR., Schulz A.S. and Stier-Moses N.E. (2004). Selfish routing in capacitated networks. Math. Oper. Res. 29(4): 961–976

    Article  MATH  MathSciNet  Google Scholar 

  12. Czumaj, A., Krysta, P., Vöcking, B.: Selfish traffic allocation for server farms. In: ACM Symposium on Theory of Computing, pp. 287–296 (2002)

  13. Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 413–420 (2002)

  14. Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: ACM SIGACT-SIGOPT Symposium on Principles of Distributed Computing, pp. 247–251 (2003)

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

  16. Karakostas, G., Kolliopoulos, S.G.: Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. In: IEEE Symposium on Foundations of Computer Science, pp. 268–276 (2004)

  17. Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: International Symposium on Theoretical Aspects of Computer Science, pp. 404–413 (1999)

  18. Lee I.H. and Mason R. (2001). Market structure in congestible markets. In: Eur. Econ. Rev. 45(4–6): 809–818

    Article  Google Scholar 

  19. Pigou, A.C.: The economics of welfare. In: Macmillan, New York (1920)

  20. Roughgarden, T.: The price of anarchy is independent of the network topology. In: ACM Symposium on Theory of Computing, pp. 428–437 (2002)

  21. Roughgarden, T.: Stackelberg scheduling strategies. In: ACM Symposium on Theory of Computing, pp.104–113 (2001)

  22. Roughgarden, T., Tardos, É.: How bad is selfish routing? In: IEEE Symposium on Foundations of Computer Science, pp. 93–102 (2000)

  23. Suri, S., Toth, C.D., Zhou, Y.: Selfish load balancing and atomic congestion games. In: ACM Symposium on Parallel Algorithms and Architectures, pp. 188–195 (2004)

  24. Vetta, A.: Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: IEEE Symposium on Foundations of Computer Science, pp. 416–425 (2002)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Cornell University, 4126 Upson Hall, Ithaca, NY, 14853, USA

    Ara Hayrapetyan, Éva Tardos & Tom Wexler

Authors
  1. Ara Hayrapetyan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Éva Tardos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tom Wexler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ara Hayrapetyan.

Additional information

A preliminary version of this paper appeared in the proceedings of 24th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, July 17–20, 2005, Las Vegas, Nevada, USA.

The work of Ara Hayrapetyan was supported in part by NSF ITR grant CCR-0325453. The work of Éva Tardos was supported in part by NSF grant CCR-0311333, ITR grant CCR-0325453, and ONR grant N00014-98-1-0589. The work of Tom Wexler was supported in part by NSF ITR grant CCR-0325453.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hayrapetyan, A., Tardos, É. & Wexler, T. A network pricing game for selfish traffic. Distrib. Comput. 19, 255–266 (2007). https://doi.org/10.1007/s00446-006-0020-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-006-0020-y

Keywords

Search

Navigation