Abstract
We study the properties of Braess’s paradox in the context of the model of congestion games with flow over time introduced by Koch and Skutella. We compare them to the well known properties of Braess’s paradox for Wardrop’s model of games with static flows. We show that there are networks which do not admit Braess’s paradox in Wardrop’s model, but which admit it in the model with flow over time. Moreover, there is a topology that admits a much more severe Braess’s ratio for this model. Further, despite its symmetry for games with static flow, we show that Braess’s paradox is not symmetric for flows over time. We illustrate that there are network topologies which exhibit Braess’s paradox, but for which the transpose does not. Finally, we conjecture a necessary and sufficient condition of existence of Braess’s paradox in a network, and prove the condition of existence of the paradox either in the network or in its transpose.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Akamatsu, T., Heydecker, B.: Detecting dynamic traffic assignment capacity paradoxes in saturated networks. Transportation Science 37(2), 123–138 (2003)
Braess, D.: Uber ein paradoxon aus der verkehrsplanung. Unternehmensforschung 12, 258–268 (1968); English translation in [3]
Braess, D., Nagurney, A., Wakolbinger, T.: On a paradox of traffic planning. Transportation Science 39(4), 446–450 (2005)
Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Applications 10, 303–318 (1965)
Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Operations Research 6(3), 419–433 (1958)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Haurie, A.B., Marcotte, P.: On the relationship between nash-cournot and wardrop equilibria. Networks 15, 295–308 (1985)
Kameda, H.: How harmful the paradox can be in the Braess/Cohen-Kelly-Jeffries networks. In: IEEE INFOCOM, vol. 1, pp. 437–445 (2002)
Koch, R., Skutella, M.: Nash equilibria and the price of anarchy for flows over time. In: Algorithmic Game Theory, pp. 323–334 (2009)
Lin, H., Roughgarden, T., Tardos, É.: A stronger bound on braess’s paradox. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 340–341. Society for Industrial and Applied Mathematics, Philadelphia (2004)
Macko, M.: The Price of Anarchy in Network Congestion Games. PhD thesis, Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava, Slovakia (2010)
Milchtaich, I.: Network topology and the efficiency of equilibrium. Games and Economic Behavior 57(2), 321–346 (2006)
Peeta, S., Ziliaskopoulos, A.K.: Foundations of dynamic traffic assignment: The past, the present and the future. Networks and Spatial Economics 1(3-4), 233–265 (2001)
Roughgarden, T.: On the severity of braess’s paradox: designing networks for selfish users is hard. Journal Computer System Sciences 72(5), 922–953 (2006)
Roughgarden, T.: Selfish routing and the price of anarchy. Optima Mathematical Programming Society Newsletter 74, 1–14 (2006)
Roughgarden, T., Tardos, É.: How bad is selfish routing? Journal of the ACM 49(2), 236–259 (2002)
Vickrey, W.S.: Congestion theory and transport investment. The American Economic Review 59(2), 251–260 (1969)
Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952)
Yagar, S.: Dynamic traffic assignment by individual path minimization and queuing. Transportation Research 5(3), 179–196 (1971)
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
Macko, M., Larson, K., Steskal, Ľ. (2010). Braess’s Paradox for Flows over Time. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds) Algorithmic Game Theory. SAGT 2010. Lecture Notes in Computer Science, vol 6386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16170-4_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-16170-4_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16169-8
Online ISBN: 978-3-642-16170-4
eBook Packages: Computer ScienceComputer Science (R0)