How bad is selfish routing?

ABSTRACT

We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge given its congestion; the objective is to route traffic such that the sum of all travel times---the total latency---is minimized.In many settings, it may be expensive or impossible to regulate network traffic so as to implement an optimal assignment of routes. In the absence of regulation by some central authority, we assume that each network user routes its traffic on the minimum-latency path available to it, given the network congestion caused by the other users. In general such a "selfishly motivated" assignment of traffic to paths will not minimize the total latency; hence, this lack of regulation carries the cost of decreased network performance.In this article, we quantify the degradation in network performance due to unregulated traffic. We prove that if the latency of each edge is a linear function of its congestion, then the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency (subject to the condition that all traffic must be routed). We also consider the more general setting in which edge latency functions are assumed only to be continuous and nondecreasing in the edge congestion. Here, the total latency of the routes chosen by unregulated selfish network users may be arbitrarily larger than the minimum possible total latency; however, we prove that it is no more than the total latency incurred by optimally routing twice as much traffic.

REFERENCES

• 1: Aashtiani, H. Z., and Magnanti, T. L. 1981. Equilibria on a congested transportation network. SIAM J. Alg. Disc. Meth. 2, 3, 213--226.
• 2: Bass, T. 1992. Road to ruin. Discover 13, 56--61.
• 3: Beckmann, M., McGuire, C. B., and Winsten, C. B. 1956. Studies in the Economics of Transportation. Yale University Press.
• 4: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 5: Bott, R., and Duffin, R. J. 1953. On the algebra of networks. Trans. AMS 74, 99--109.
• 6: Braess, D. 1968. Uber ein paradoxon der verkehrsplanung. Unternehmensforschung 12, 258--268.
• 7: Cohen, J. E., and Horowitz, P. 1991. Paradoxical behavior of mechanical and electrical networks. Nature 352, 699--701.
• 8: Cohen, J. E., and Kelly, F. P. 1990. A paradox of congestion in a queuing network. J. Appl. Prob. 27, 730--734.
• 9: Cohn, R. M. 1950. The resistance of an electrical network. Proc. AMS 1, 316--324.
• 10: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 11: Dafermos, S. 1980. Traffic equilibrium and variational inequalities. Transport. Sci. 14, 1, 42--54.
• 12: Dafermos, S. C., and Nagurney, A. 1984. On some traffic equilibrium theory paradoxes. Transport. Res. Ser. B 18B, 101--110.
• 13: Dafermos, S. C., and Sparrow, F. T. 1969. The traffic assignment problem for a general network. J. Res. NBS. Ser. B 73B, 2, 91--118.
• 14: Pradeep Dubey, Inefficiency of Nash equilibria, Mathematics of Operations Research, v.11 n.1, p.1-8, Feb. 1986 [doi>10.1287/moor.11.1.1]
• 15: Fisk, C. 1979. More paradoxes in the equilibrium assignment problem. Transport. Res. 13B, 305--309.
• 16: Florian, M. 1986. Nonlinear cost network models in transportation analysis. Math. Prog. Study 26, 167--196.
• 17: Florian, M., and Hearn, D. 1995. Network equilibrium models and algorithms. In Network Routing. M. O. Ball, T. Magnanti, C. Monma, and G. Nemhauser, Eds. Elsevier Science, Amsterdam, The Netherlands, Chapter 6, pp. 485--550.
• 18: Frank, M. 1981. The Braess Paradox. Math. Prog. 20, 283--302.
• 19: Friedman, E. J. 2001. A generic analysis of selfish routing. Working paper.
• 20: Hagstrom, J. N., and Abrams, R. A. 2001. Characterizing Braess's paradox for traffic networks. In Proceedings of the IEEE Conference on Intelligent Transportation Systems. IEEE Computer Society Press, Los Alamitos, Calif., pp. 837--842.
• 21: Hall, M. A. 1978. Properties of the equilibrium state in transportation networks. Transport. Sci. 12, 3, 208--216.
• 22: Haurie, A., and Marcotte, P. 1985. On the relationship between Nash--Cournot and Wardrop equilibria. Networks 15, 295--308.
• 23: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 24: Knight, F. H. 1924. Some fallacies in the interpretation of social cost. Quart. J. Econ. 38, 582--606.
• 25: Knödel, W. 1969. Graphentheoretische Methoden und ihre Anwendungen. Springer-Verlag, New York.
• 26: Korilis, Y. A., Lazar, A. A., and Orda, A. 1997. Capacity allocation under noncooperative routing. IEEE Trans. Automat. Cont. 42, 3, 309--325.
• 27: Korilis, Y. A., Lazar, A. A., and Orda, A. 1999. Avoiding the Braess paradox in noncooperative networks. Journal of Applied Probability 36, 1, 211--222.
• 28: Koutsoupias, E., and Papadimitriou, C. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. pp. 404--413.
• 29: Aurel A. Lazar , Ariel Orda , Dimitrios E. Pendarakis, Virtual path bandwidth allocation in multiuser networks, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.861-871, Dec. 1997 [doi>10.1109/90.650145]
• 30: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 31: Murchland, J. D. 1970. Braess's paradox of traffic flow. Transport. Res. 4, 391--394.
• 32: Nagurney, A. 2000. Sustainable Transportation Networks. Edward Elgar, Cheltenham, England.
• 33: Nesterov, Y. 1999. Stable flows in transportation networks. CORE Discussion Paper 9907.
• 34: Nesterov, Y., and De. Palma, A. 2000. Stable dynamics in transportation systems. CORE Discussion Paper 00/27.
• 35: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 36: Owen, G. 1995. Game Theory. 3rd ed. Academic Press. Orlando, Fla.
• 37: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 38: A. L. Peressini , Francis E. Sullivan , J. J. Uhl, Jr., The mathematics of nonlinear programming, Springer-Verlag New York, Inc., New York, NY, 1988
• 39: Phillips, C. A., Stein, C., Torng, E., and Wein, J. 2002. Optimal time-critical scheduling via resource augmentation. Algorithmica 32, 2, 163--200. Preliminary version in STOC '97.
• 40: Rosen, J. B. 1965. Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33, 3, 520--534.
• 41: Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.
• 42: 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
• 43: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 44: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 45: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 46: Roughgarden, T., and Tardos, &Eaccute;. 2002. Bounding the inefficiency of Nash equilibria in nonatomic congestion games. In preparation.
• 47: Sheffi, Y. 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Englewood Cliffs, N.J.
• 48: Smith, M. J. 1978. In a road network, increasing delay locally can reduce delay globally. Transport. Res. 12, 419--422.
• 49: Smith, M. J. 1979. The existence, uniqueness and stability of traffic equilibria. Transport. Res. 13B, 295--304.
• 50: Steinberg, R., and Stone, R. E. 1988. The prevalence of paradoxes in transportation equilibrium problems. Transport. Sci. 22, 4, 231--241.
• 51: Steinberg, R., and Zangwill, W. I. 1983. The prevalence of Braess' paradox. Transport. Sci. 17, 3, 301--318.
• 52: Wardrop, J. G. 1952. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Pt. II. Vol. 1. pp. 325--378.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Economics, Theory

Keywords:
Braess's Paradox, Nash equilibria, network flow, selfish routing