Abstract
Braess’s paradox states that removing a part of a network may improve the players’ latency at equilibrium. In this work, we study the approximability of the best subnetwork problem for the class of random \(\mathcal{G}_{n,p}\) instances proven prone to Braess’s paradox by (Roughgarden and Valiant, RSA 2010) and (Chung and Young, WINE 2010). Our main contribution is a polynomial-time approximation-preserving reduction of the best subnetwork problem for such instances to the corresponding problem in a simplified network where all neighbors of s and t are directly connected by 0 latency edges. Building on this, we obtain an approximation scheme that for any constant ε > 0 and with high probability, computes a subnetwork and an ε-Nash flow with maximum latency at most (1 + ε)L ∗ + ε, where L ∗ is the equilibrium latency of the best subnetwork. Our approximation scheme runs in polynomial time if the random network has average degree O(poly(ln n)) and the traffic rate is O(poly(ln ln n)), and in quasipolynomial time for average degrees up to o(n) and traffic rates of O(poly(ln n)).
This research was supported by the project Algorithmic Game Theory, co-financed by the European Union (European Social Fund - ESF) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES, investing in knowledge society through the European Social Fund, by the ERC project RIMACO, and by the EU FP7/2007-13 (DG INFSO G4-ICT for Transport) under Grant Agreement no. 288094 (Project eCompass).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Althöfer, I.: On Sparse Approximations to Randomized Strategies and Convex Combinations. Linear Algebra and Applications 99, 339–355 (1994)
Bollobás, B.: Random Graphs, 2nd edn. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge University Press (2001)
Braess, D.: Über ein paradox aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)
Chung, F., Young, S.J.: Braess’s paradox in large sparse graphs. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 194–208. Springer, Heidelberg (2010)
Chung, F., Young, S.J., Zhao, W.: Braess’s paradox in expanders. Random Structures and Algorithms 41(4), 451–468 (2012)
Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient methods for selfish network design. Theoretical Computer Science 448, 9–20 (2012)
Kelly, F.: The mathematics of traffic in networks. In: Gowers, T., Green, J., Leader, I. (eds.) The Princeton Companion to Mathematics. Princeton University Press (2008)
Lin, H.C., Roughgarden, T., Tardos, É., Walkover, A.: Stronger bounds on Braess’s paradox and the maximum latency of selfish routing. SIAM Journal on Discrete Mathematics 25(4), 1667–1686 (2011)
Lipton, R.J., Markakis, E., Mehta, A.: Playing Large Games Using Simple Strategies. In: Proc. of the 4th ACM Conference on Electronic Commerce (EC 2003), pp. 36–41 (2003)
Lipton, R.J., Young, N.E.: Simple Strategies for Large Zero-Sum Games with Applications to Complexity Theory. In: Proc. of the 26th ACM Symposium on Theory of Computing (STOC 1994), pp. 734–740 (1994)
Milchtaich, I.: Network Topology and the Efficiency of Equilibrium. Games and Economic Behavior 57, 321–346 (2006)
Nagurney, A., Boyce, D.: Preface to “On a Paradox of Traffic Planning”. Transportation Science 39(4), 443–445 (2005)
Pas, E.I., Principio, S.L.: Braess’s paradox: Some new insights. Transportation Research Part B 31(3), 265–276 (1997)
Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press (2005)
Roughgarden, T.: On the Severity of Braess’s Paradox: Designing Networks for Selfish Users is Hard. Journal of Computer and System Sciences 72(5), 922–953 (2006)
Steinberg, R., Zangwill, W.I.: The prevalence of Braess’ paradox. Transportation Science 17(3), 301–318 (1983)
Valiant, G., Roughgarden, T.: Braess’s paradox in large random graphs. Random Structures and Algorithms 37(4), 495–515 (2010)
Végh, L.A.: Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. In: Proc. of the 44th ACM Symposium on Theory of Computing (STOC 2012), pp. 27–40 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotakis, D., Kaporis, A.C., Lianeas, T., Spirakis, P.G. (2013). Resolving Braess’s Paradox in Random Networks. In: Chen, Y., Immorlica, N. (eds) Web and Internet Economics. WINE 2013. Lecture Notes in Computer Science, vol 8289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45046-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-45046-4_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45045-7
Online ISBN: 978-3-642-45046-4
eBook Packages: Computer ScienceComputer Science (R0)