Braess's paradox in large random graphs

ABSTRACT

Braess's Paradox is the counterintuitive but well-known fact that removing edges from a network with "selfish routing" can decrease the latency incurred by traffic in an equilibrium flow. Despite the large amount of research motivated by Braess's Paradox since its discovery in 1968, little is known about whether it is a common real-world phenomenon, or a mere theoretical curiosity.In this paper, we show that Braess's Paradox is likely to occur in a natural random network model. More precisely, with high probability, (as the number of vertices goes to infinity), there is a traffic rate and a set of edges whose removal improves the latency of traffic in an equilibrium flow by a constant factor. Our proof approach is robust and shows that the "global" behavior of an equilibrium flow in a large random network is similar to that in Braess's original four-node example.

REFERENCES

• 1: E. Altman, R. El Azouzi, and O. Pourtallier. Avoiding paradoxes in routing games. In Proceedings of the 17th International Teletraffic Conference, 2001.
• 2: M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956.
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 4: B. Bollobás. Random Graphs. Academic Press, 1985.
• 5: D. Braess. Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung, 12:258--268, 1968. English translation in {6}.
• 6: D. Braess. On a paradox of traffic planning. Transportation Science, 39(4):446--450, 2005.
• 7: S. C. Dafermos and A. Nagurney. On some traffic equilibrium theory paradoxes. Transportation Research, Series B, 18(2): 101--110, 1984.
• 8: S. C. Dafermos and F. T. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards, Series B, 73(2):91--118, 1969.
• 9: R. El Azouzi, E. Altman, and O. Pourtallier. Properties of equilibria in competitive routing with several user types. In Proceedings of the 41st IEEE Conference on Decision and Control, volume 4, pages 3646--3651, 2002.
• 10: P. Erdös and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci., 5:17--61, 1960.
• 11: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754 ]
• 12: C. Fisk and S. Pallottino. Empirical evidence for equilibrium paradoxes with implications for optimal planning strategies. Transportation Research, Part A, 15(3): 245--248, 1981.
• 13: M. Frank. The Braess Paradox. Mathematical Programming, 20(3):283--302, 1981.
• 14: M. Frank. Cost-deceptive links on ladder networks. Methods of Operations Research, 45:75--86, 1983.
• 15: E. J. Friedman. Genericity and congestion control in selfish routing. In Proceedings of the 43rd Annual IEEE Conference on Decision and Control (CDC), pages 4667--4672, 2004.
• 16: M. A. Hall. Properties of the equilibrium state in transportation networks. Transportation Science, 12(3):208--216, 1978.
• 17: H. Kameda. How harmful the paradox can be in the Braess/Cohen-Kelly-Jeffries networks. In Proceedings of the 21st INFOCOM Conference, volume 1, pages 437--445, 2002.
• 18: G. Kolata. What if they closed 42nd Street and nobody noticed? New York Times, page 38, December 25, 1990.
• 19: Y. A. Korilis, A. A. Lazar, and A. Orda. Capacity allocation under noncooperative routing. IEEE Transactions on Automatic Control, 42(3):309--325, 1997.
• 20: Y. A. Korilis, A. A. Lazar, and A. Orda. Avoiding the Braess paradox in noncooperative networks. Journal of Applied Probability, 36(1):211--222, 1999.
• 21: Lavy Libman , Ariel Orda, The designer's perspective to atomic noncooperative networks, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.875-884, Dec. 1999 [doi>10.1109/90.811452]
• 22: Henry Lin , Tim Roughgarden , Éva Tardos, A stronger bound on Braess's Paradox, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 23: H. Lin, T. Roughgarden, #201;. Tardos, and A. Walkover. Braess's Paradox, Fibonacci numbers, and exponential inapproximability. In Proceedings of the 32nd Annual International Colloquium on Automata, Languages, and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, pages 497--512, 2005.
• 24: J D. Murchland. Braess's paradox of traffic flow. Transportation Research, 4(4):391--394, 1970.
• 25: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1/2):166--196, 2001. Preliminary version in STOC '99.
• 26: E. I. Pas and S. L. Principio. Braess' paradox: Some new insights. Transportation Research, Series B, 31(3):265--276, 1997.
• 27: C. M. Penchina. Braess paradox: Maximum penalty in a minimal critical network. Transportation Research, Series A, 31(5):379--388, 1997.
• 28: 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
• 29: Tim Roughgarden, Selfish Routing and the Price of Anarchy, The MIT Press, 2005
• 30: 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]
• 31: R. Steinberg and W. I. Zangwill. The prevalence of Braess' Paradox. Transportation Science, 17(3):301--318, 1983.
• 32: A. Taguchi. Braess' paradox in a two-terminal transportation network. Journal of the Operations Research Society of Japan, 25(4):376--388, 1982.
• 33: 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:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Economics, Theory

Keywords:
Braess's paradox, random graphs, selfish routing