The price of anarchy in bertrand games

ABSTRACT

The Internet is composed of multiple economically-independent service providers that sell bandwidth in their networks so as to maximize their own revenue. Users, on the other hand, route their traffic selfishly to maximize their own utility. How does this selfishness impact the efficiency of operation of the network? To answer this question we consider a two-stage network pricing game where service providers first select prices to charge on their links, and users pick paths to route their traffic. We give tight bounds on the price of anarchy of the game with respect to social value--the total value obtained by all the traffic routed. Unlike recent work on network pricing, in our pricing game users do not face congestion costs; instead service providers must ensure that capacity constraints on their links are satisfied. Our model extends the classic Bertrand game in economics to network settings.

REFERENCES

• 1: Daron Acemoglu , Asuman Ozdaglar, Competition and Efficiency in Congested Markets, Mathematics of Operations Research, v.32 n.1, p.1-31, February 2007 [doi>10.1287/moor.1060.0231]
• 2: D. Acemoglu and A. Ozdaglar. Competition in parallel-serial networks. IEEE Journal on Selected Areas in Communications, special issue on Non-cooperative Behavior in Networking, 25(6):1180--1192, 2007.
• 3: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 4: Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780617]
• 5: Mark Bagnoli and Ted Bergstrom. Log-concave probability and its applications. Economic Theory, 26(2):445--469, 08 2005.
• 6: Michael R. Baye and John Morgan. A folk theorem for one-shot bertrand games. Economics Letters, 65(1):59--65, 1999.
• 7: Shuchi Chawla , Tim Roughgarden, Bertrand Competition in Networks, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_8]
• 8: Richard Cole , Yevgeniy Dodis , Tim Roughgarden, Pricing network edges for heterogeneous selfish users, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780618]
• 9: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 10: Lisa Fleischer , Kamal Jain , Mohammad Mahdian, Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.277-285, October 17-19, 2004 [doi>10.1109/FOCS.2004.69]
• 11: Joseph Jr. Harrington. A re-evaluation of perfect competition as the solution to the bertrand price game. Mathematical Social Sciences, 17(3):315--328, 1989.
• 12: Jason Hartline , Vahab Mirrokni , Mukund Sundararajan, Optimal marketing strategies over social networks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367524]
• 13: Ara Hayrapetyan , Éva Tardos , Tom Wexler, A network pricing game for selfish traffic, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073869]
• 14: A. Mas-Colell, M.D. Whinston, and J.R. Green. Microeconomic Theory. Oxford, 1995.
• 15: J. Musacchio and S. Wu. The price of anarchy in a network pricing game. In 45th Annual Allerton Conference on Communication and Control, 2007.
• 16: A. Ozdaglar and R. Srikant. Incentives and pricing in communication networks. In Algorithmic Game Theory. Cambridge Press, 2007.
• 17: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 18: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Economics, Theory

Keywords:
bandwidth pricing, bertrand competition, price of anarchy, two-sided markets