Braess’s paradox in large random graphs. (English) Zbl 1207.05185
Summary: Braess’s Paradox is the counterintuitive fact that removing edges from a network with ”selfish routing” can decreasethe latency incurred by traffic in an equilibrium flow. We prove that Braess’s Paradox is likely to occur in a natural random network model: with high probability, 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.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
References:
| [1] | Altman, Avoiding paradoxes in multi-agent competitive routing, Comput Networks 43 pp 133– (2003) · Zbl 1069.68507 |
| [2] | Beckmann, Studies in the economics of transportation (1956) |
| [3] | Bertsekas, Parallel and distributed computation: Numerical methods (1989) · Zbl 0743.65107 |
| [4] | Bollobás, Random graphs (1985) |
| [5] | Braess, Über ein Paradoxon aus der Verkehrsplanung, Unternehmensforschung 12 pp 258– (1968) · Zbl 0167.48305 |
| [6] | Braess, On a paradox of traffic planning, Transport Sci 39 pp 446– (2005) |
| [7] | Dafermos, On some traffic equilibrium theory paradoxes, Transport Res B 18 pp 101– (1984) |
| [8] | Dafermos, The traffic assignment problem for a general network, J Res Nat Bur Stand, B 73 pp 91– (1969) · Zbl 0197.46003 · doi:10.6028/jres.073B.010 |
| [9] | R. El Azouzi E. Altman O. Pourtallier Properties of equilibria in competitive routing with several user types In Proceedings of the 41st IEEE Conference on Decision and Control 4 Las Vegas, NV 2002 3646 3651 |
| [10] | Erdös, On the evolution of random graphs, Publ Math Inst Hungar Acad Sci 5 pp 17– (1960) |
| [11] | Fisk, Empirical evidence for equilibrium paradoxes with implications for optimal planning strategies, Transport Res A 15 pp 245– (1981) |
| [12] | Frank, The Braess Paradox, Math Program 20 pp 283– (1981) · Zbl 0468.90078 |
| [13] | Frank, Cost-deceptive links on ladder networks, Meth Oper Res 45 pp 75– (1983) · Zbl 0524.90036 |
| [14] | Friedman, In Proceedings of the 43rd Annual IEEE Conference on Decision and Control pp 4667– (2004) |
| [15] | Hall, Properties of the equilibrium state in transportation networks, Transport Sci 12 pp 208– (1978) |
| [16] | Kameda, In Proceedings of the 21st INFOCOM Conference 1 pp 437– (2002) |
| [17] | G. Kolata What if they closed 42nd Street and nobody noticed? New York Times, December 25 1990 38 |
| [18] | Korilis, Capacity allocation under noncooperative routing, IEEE Trans Automat Contr 42 pp 309– (1997) · Zbl 0872.90035 |
| [19] | Korilis, Avoiding the Braess paradox in noncooperative networks, J Appl Probab 36 pp 211– (1999) · Zbl 0942.60091 |
| [20] | Libman, The designer’s perspective to atomic noncooperative networks, IEEE/ACM Trans Networking 7 pp 875– (1999) |
| [21] | Lin, In Proceedings of the 15th Annual Symposium on Discrete Algorithms pp 333– (2004) |
| [22] | Lin, In Proceedings of the 32nd Annual International Colloquium on Automata, Languages, and Programming (ICALP) 3580, in: Lecture Notes in Computer Science pp 497– (2005) |
| [23] | Motwani, Randomized algorithms (1995) · doi:10.1017/CBO9780511814075 |
| [24] | Murchland, Braess’s paradox of traffic flow, Transport Res 4 pp 391– (1970) |
| [25] | Pas, Braess’paradox: Some new insights, Transport Res B 31 pp 265– (1997) |
| [26] | Penchina, Braess paradox: Maximum penalty in a minimal critical network, Transport Res A 31 pp 379– (1997) |
| [27] | Roughgarden, Selfish routing and the price of anarchy (2005) · Zbl 1318.68065 |
| [28] | Roughgarden, On the severity of Braess’s Paradox: Designing networks for selfish users is hard, J Comput Syst Sci 72 pp 922– (2006) · Zbl 1094.68122 |
| [29] | T. Roughgarden É. Tardos How bad is selfish routing? J ACM 49 2002 236 259 · Zbl 1323.90011 |
| [30] | Steinberg, The prevalence of Braess’Paradox, Transport Sci 17 pp 301– (1983) |
| [31] | Taguchi, Braess’paradox in a two-terminal transportation network, J Oper Res Soc Japan 25 pp 376– (1982) · Zbl 0502.90025 |
| [32] | Wardrop, In Proceedings of the Institute of Civil Engineers, Part II 1 pp 325– (1952) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
