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.
- Aashtiani, H. Z., and Magnanti, T. L. 1981. Equilibria on a congested transportation network. SIAM J. Alg. Disc. Meth. 2, 3, 213--226.Google Scholar
- Bass, T. 1992. Road to ruin. Discover 13, 56--61.Google Scholar
- Beckmann, M., McGuire, C. B., and Winsten, C. B. 1956. Studies in the Economics of Transportation. Yale University Press.Google Scholar
- Bertsekas, D. P., and Gallager, R. 1992. Data Networks, 2nd ed. Prentice-Hall, Englewood Cliffs, N.J. Google Scholar
- Bott, R., and Duffin, R. J. 1953. On the algebra of networks. Trans. AMS 74, 99--109.Google Scholar
- Braess, D. 1968. Uber ein paradoxon der verkehrsplanung. Unternehmensforschung 12, 258--268.Google Scholar
- Cohen, J. E., and Horowitz, P. 1991. Paradoxical behavior of mechanical and electrical networks. Nature 352, 699--701.Google Scholar
- Cohen, J. E., and Kelly, F. P. 1990. A paradox of congestion in a queuing network. J. Appl. Prob. 27, 730--734.Google Scholar
- Cohn, R. M. 1950. The resistance of an electrical network. Proc. AMS 1, 316--324.Google Scholar
- Czumaj, A., and Vöcking, B. 2002. Tight bounds for worst-case equilibria. In Proceedings of the 13th Annual Symposium on Discrete Algorithms. SIAM, Philadelphia, Pa., pp. 413--420. Google Scholar
- Dafermos, S. 1980. Traffic equilibrium and variational inequalities. Transport. Sci. 14, 1, 42--54.Google Scholar
- Dafermos, S. C., and Nagurney, A. 1984. On some traffic equilibrium theory paradoxes. Transport. Res. Ser. B 18B, 101--110.Google Scholar
- 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.Google Scholar
- Dubey, P. 1986. Inefficiency of Nash equilibria. Math. Oper. Res. 11, 1, 1--8. Google Scholar
- Fisk, C. 1979. More paradoxes in the equilibrium assignment problem. Transport. Res. 13B, 305--309.Google Scholar
- Florian, M. 1986. Nonlinear cost network models in transportation analysis. Math. Prog. Study 26, 167--196.Google Scholar
- 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.Google Scholar
- Frank, M. 1981. The Braess Paradox. Math. Prog. 20, 283--302.Google Scholar
- Friedman, E. J. 2001. A generic analysis of selfish routing. Working paper.Google Scholar
- 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.Google Scholar
- Hall, M. A. 1978. Properties of the equilibrium state in transportation networks. Transport. Sci. 12, 3, 208--216.Google Scholar
- Haurie, A., and Marcotte, P. 1985. On the relationship between Nash--Cournot and Wardrop equilibria. Networks 15, 295--308.Google Scholar
- Kalyanasundaram, B., and Pruhs, K. 2000. Speed is as powerful as clairvoyance. Journal of the ACM 47, 4, 617--643. Preliminary version in FOCS '95. Google Scholar
- Knight, F. H. 1924. Some fallacies in the interpretation of social cost. Quart. J. Econ. 38, 582--606.Google Scholar
- Knödel, W. 1969. Graphentheoretische Methoden und ihre Anwendungen. Springer-Verlag, New York.Google Scholar
- Korilis, Y. A., Lazar, A. A., and Orda, A. 1997. Capacity allocation under noncooperative routing. IEEE Trans. Automat. Cont. 42, 3, 309--325.Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- Lazar, A. A., Orda, A., and Pendarakis, D. E. 1997. Virtual path bandwidth allocation in multiuser networks. IEEE/ACM Trans. Netw. 5, 861--871. Google Scholar
- Mavronicolas, M., and Spirakis, P. 2001. The price of selfish routing. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing. ACM, New York, pp. 510--519. Google Scholar
- Murchland, J. D. 1970. Braess's paradox of traffic flow. Transport. Res. 4, 391--394.Google Scholar
- Nagurney, A. 2000. Sustainable Transportation Networks. Edward Elgar, Cheltenham, England.Google Scholar
- Nesterov, Y. 1999. Stable flows in transportation networks. CORE Discussion Paper 9907.Google Scholar
- Nesterov, Y., and De. Palma, A. 2000. Stable dynamics in transportation systems. CORE Discussion Paper 00/27.Google Scholar
- Orda, A., Rom, R., and Shimkin, N. 1993. Competitive routing in multi-user communication networks. IEEE/ACM Trans. Netw. 1, 510--521. Google Scholar
- Owen, G. 1995. Game Theory. 3rd ed. Academic Press. Orlando, Fla.Google Scholar
- Papadimitriou, C. 2001. Algorithms, games, and the Internet. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing. ACM, New York, pp. 749--753. Google Scholar
- Peressini, A. L., Sullivan, F. E., and Uhl, J. J. 1988. The Mathematics of Nonlinear Programming. Springer-Verlag, New York. Google Scholar
- 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.Google Scholar
- Rosen, J. B. 1965. Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33, 3, 520--534.Google Scholar
- Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.Google Scholar
- Roughgarden, T. 2001a. Designing networks for selfish users is hard. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp 472--481. Google Scholar
- Roughgarden, T. 2001b. Stackelberg scheduling strategies. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing. ACM, New York, pp. 104--113. Google Scholar
- Roughgarden, T. 2002a. The price of anarchy is independent of the network topology. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, to appear. Google Scholar
- Roughgarden, T., and Tardos, &Eaccute; 2000. How bad is selfish routing? In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 93--102. Google Scholar
- Roughgarden, T., and Tardos, &Eaccute;. 2002. Bounding the inefficiency of Nash equilibria in nonatomic congestion games. In preparation.Google Scholar
- Sheffi, Y. 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
- Smith, M. J. 1978. In a road network, increasing delay locally can reduce delay globally. Transport. Res. 12, 419--422.Google Scholar
- Smith, M. J. 1979. The existence, uniqueness and stability of traffic equilibria. Transport. Res. 13B, 295--304.Google Scholar
- Steinberg, R., and Stone, R. E. 1988. The prevalence of paradoxes in transportation equilibrium problems. Transport. Sci. 22, 4, 231--241.Google Scholar
- Steinberg, R., and Zangwill, W. I. 1983. The prevalence of Braess' paradox. Transport. Sci. 17, 3, 301--318.Google Scholar
- 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.Google Scholar
Index Terms
- How bad is selfish routing?
Recommendations
How bad is selfish routing?
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceWe 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 ...
Pricing network edges for heterogeneous selfish users
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingWe study the negative consequences of selfish behavior in a congested network and economic means of influencing such behavior. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a ...
How much can taxes help selfish routing?
EC '03: Proceedings of the 4th ACM conference on Electronic commerceWe study economic incentives for influencing selfish behavior in networks. We consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are ...
Comments