Bottleneck links, variable demand, and the tragedy of the commons

ABSTRACT

The price of anarchy, a measure of the inefficiency of selfish behavior, has been successfully analyzed in a diverse array of models over the past five years. The overwhelming majority of this work has studied optimization problems that sought an optimal way to allocate a fixed demand to resources whose performance degrades with increasing congestion. While fundamental, such problems overlook a crucial feature of many applications: the intrinsic coupling of the quality or cost of a resource and the demand for that resource. This coupling motivates allowing demand to vary with congestion, which in turn can lead to "the tragedy of the commons"---severe inefficiency caused by the overconsumption of a shared resource.Allowing the demand for resources to vary with their congestion illuminates a second issue with existing studies of the price of anarchy: the standard additive method of aggregating the costs of different resources in a player's strategy is inappropriate for some important applications, including many of those with variable demand. For example, in networking applications a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. This disconnect motivates consideration of nonlinear cost aggregation functions, such as the lp norms.In this paper, we initiate the study of the price of anarchy with variable demand and with broad classes of nonlinear aggregation functions. We focus on selfish routing in single- and multicommodity networks, and on the lp norms for 1 ≤ p ≤ ∞; our main results are as follows.• For a natural "prize-collecting" objective function, the price of anarchy in multicommodity networks with variable demand is no larger than that in fixed-demand networks. Thus the inefficiency arising from the tragedy of the commons is no more severe than that from routing inefficiencies.• Using the lp norm with 1 < p < ∞ as a cost aggregation function can dramatically increase the price of anarchy in multicommodity networks (relative to additive aggregation), but causes no such additional inefficiency in single-commodity networks.• Using the l∞ norms as a cost aggregation function can dramatically increase the price of anarchy, even in single-commodity networks. If attention is restricted to equilibria with additional structure, however---structure that is ensured by distributed shortest-path routing protocols---then using the l∞ norm does not increase the price of anarchy relative to additive aggregation.

REFERENCES

• 1: A. Akella, S. Chawla, and S. Seshan. Realistic models for selfish routing in the Internet. Manuscript, 2003.
• 2: 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 (FOCS'04), p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 3: 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]
• 4: James Aspnes , Kevin Chang , Aleksandr Yampolskiy, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: A. Banerjee and J. Yoo. Minimizing maximum logical link congestion in packet switched optimal networks. In Proceedings of the 1997 IEEE International Conference on Communcations (ICC), volume 3, pages 1298--1302, 1997.
• 6: R. Banner and A. Orda. Bottleneck games in noncooperative networks. Technical Report CCIT-510, Technion University, 2004.
• 7: M. J. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 8: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 9: D. Braess. Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12:258--268, 1968.
• 10: J. H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proceedings of INFOCOM, pages 22--31, 2000.
• 11: C. K. Chau and K. M. Sim. The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Operations Research Letters, 31(5):327--334, 2003.
• 12: José R. Correa , Andreas S. Schulz , Nicolás E. Stier-Moses, Selfish Routing in Capacitated Networks, Mathematics of Operations Research, v.29 n.4, p.961-976, November 2004 [doi>10.1287/moor.1040.0098]
• 13: J. R. Correa, A. S. Schulz, and N. E. Stier Moses. On the inefficiency of equilibria in congestion games. In Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), 2005. To appear.
• 14: A. Czumaj. Selfish routing on the Internet. In J. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 42. CRC Press, 2004.
• 15: S. C. Dafermos. Traffic equilibrium and variational inequalities. Transportation Science, 14(1):42--54, 1980.
• 16: 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]
• 17: N. H. Gartner. Optimal traffic assignment with elastic demands: A review; Part I. Analysis framework. Transportation Science, 14(2):174--191, 1980.
• 18: Michel X. Goemans , David P. Williamson, The primal-dual method for approximation algorithms and its application to network design problems, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: Magnús M. Halldórsson , Joseph Y. Halpern , Li (Erran) Li , Vahab S. Mirrokni, On spectrum sharing games, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011783]
• 20: G. Hardin. The tragedy of the commons. Science, 162:1243--1248, December 13 1968.
• 21: R. Johari and J. N. Tsitsiklis. Routing and peering in a competitive Internet. Technical Report 2570, MIT LIDS, 2003.
• 22: Ramesh Johari , John N. Tsitsiklis, Efficiency Loss in a Network Resource Allocation Game, Mathematics of Operations Research, v.29 n.3, p.407-435, August 2004 [doi>10.1287/moor.1040.0091]
• 23: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 24: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1563 of Lecture Notes in Computer Science, pages 404--413, 1999.
• 25: A. Nagurney. Network Economics: A Variational Inequality Approach. Kluwer, 1993. Second Edition, 1999.
• 26: G. Perakis. The price of anarchy when costs are non-separable and asymmetric. In Proceedings of the 10th Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 3064 of Lecture Notes in Computer Science, pages 46--58, 2004.
• 27: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 28: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65--67, 1973.
• 29: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 30: Tim Roughgarden, The price of anarchy is independent of the network topology, Journal of Computer and System Sciences, v.67 n.2, p.341-364, September 2003 [doi>10.1016/S0022-0000(03)00044-8]
• 31: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 32: 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]
• 33: T. Roughgarden and É. Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 49(2):389--403, 2004.
• 34: D. Schmeidler. Equilibrium points of nonatomic games. Journal of Statistical Physics, 7(4):295--300, 1973.
• 35: M. J. Smith. The existence, uniqueness and stability of traffic equilibria. Transportation Research, Part B, 13(4):295--304, 1979.
• 36: É. Tardos. Course notes. Cornell CS684, 2004.
• 37: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 38: Y. Wang and Z. Wang. Explicit routing algorithms for Internet traffic engineering. In Proceedings of the 8th International Conference on Computer Communications and Networks (ICCN), pages 582--588, 1999.
• 39: J. G. Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Pt. II, volume 1, pages 325--378, 1952.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Theory