Abstract
Braess’s paradox, in its original context, is the counter-intuitive observation that, without lessening demand, closing roads can improve traffic flow. With the explosion of distributed (selfish) routing situations understanding this paradox has become an important concern in a broad range of network design situations. However, the previous theoretical work on Braess’s paradox has focused on “designer” graphs or dense graphs, which are unrealistic in practical situations. In this work, we exploit the expansion properties of Erdős-Rényi random graphs to show that Braess’s paradox occurs when np ≥ c log(n) for some c > 1.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the economics of transportation. Yale University Press, London (1956)
Fisk, C., Pallottino, S.: Empirical evidence for equilibrium paradoxes with implications for optimal planning strategies. Transportation Research Part A: General 15(3), 245–248 (1981)
Frank, M.: The Braess paradox. Math. Programming 20(3), 283–302 (1981)
Hall, M.A.: Properties of the equilibrium state in transportation networks. Transportation Science 12(3), 208–216 (1978)
Kameda, H.: How harmful the paradox can be in the braess/cohen-kelly-jeffries networks. In: Proceedings of IEEE Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2002, vol. 1, pp. 437–445 (2002)
Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif. (1969); dedicated to the memory of Theodore S. Motzkin), pp. 159–175. Academic Press, New York (1972)
Kolata, G.: What if they closed 42d street and nobody noticed? The New York Times (December 25, 1990)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Lin, H., Roughgarden, T., Tardos, É.: A stronger bound on Braess’s paradox. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (electronic), pp. 340–341. ACM, New York (2004)
Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (electronic), pp. 749–753. ACM, New York (2001)
Pas, E.I., Principio, S.L.: Braess’ paradox: Some new insights. Transportation Research Part B: Methodological 31(3), 265–276 (1997)
Penchina, C.M.: Braess paradox: Maximum penalty in a minimal critical network. Transportation Research Part A: Policy and Practice 31(5), 379–388 (1997)
Roughgarden, T.: On the severity of Braess’s Paradox: designing networks for selfish users is hard. J. Comput. System Sci. 72(5), 922–953 (2006)
Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM (electronic) 49(2), 236–259 (2002)
Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM (electronic) 51(3), 385–463 (2004)
Valiant, G., Roughgarden, T.: Braess’s paradox in large random graphs. Random Structures Algorithms (to appear)
Wardrop, J.: Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, Part II 1(36), 352–362 (1952)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chung, F., Young, S.J. (2010). Braess’s Paradox in Large Sparse Graphs. In: Saberi, A. (eds) Internet and Network Economics. WINE 2010. Lecture Notes in Computer Science, vol 6484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17572-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-17572-5_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17571-8
Online ISBN: 978-3-642-17572-5
eBook Packages: Computer ScienceComputer Science (R0)