Abstract
We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community.
We present a novel characterization of Nash equilibria for flows over time. It turns out that Nash flows over time can be seen as a concatenation of special static flows. The underlying flow over time model is the so-called deterministic queuing model that is very popular in road traffic simulation and related fields. Based upon this, we prove the first known results on the price of anarchy for flows over time.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Akamatsu, T.: A dynamic traffic equilibrium assignment paradox. Transp. Res. B 34(6), 515–531 (2000)
Akamatsu, T.: An efficient algorithm for dynamic traffic equilibrium assignment with queues. Transp. Sci. 35(4), 389–404 (2001)
Akamatsu, T., Heydecker, B.: Detecting dynamic traffic assignment capacity paradoxes in saturated networks. Transp. Sci. 37(2), 123–138 (2003)
Anshelevich, E., Ukkusuri, S.: Equilibria in dynamic selfish routing. In: Mavronicolas, M. (ed.) Proceedings of the 2nd International Symposium on Algorithmic Game Theory. Lecture Notes in Computer Science, vol. 5814, pp. 171–182. Springer, Berlin (2009)
Aronson, J.E.: A survey of dynamic network flows. Ann. Oper. Res. 20(1–4), 1–66 (1989)
Balmer, M., Rieser, M., Meister, K., Charypar, D., Lefebvre, N., Nagel, K.: MATSim-T: Architecture and simulation times. In: Bazzan, A., Klügl, F. (eds.) Multi-Agent Systems for Traffic and Transportation Engineering. Information Science Reference, Hershey (2009)
Ben-Akiva, M.J., Bierlaire, M., Koutsopoulos, H.N., Mishalani, R.: Dynamit: a simulation-based system for traffic prediction and guidance generation. In: Proceedings of the 3rd Triennial Symposium on Transportation Systems (1998)
Braess, D.: Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12 12, 258–268 (1968). In German
Carey, M.: Link travel times I: Properties derived from traffic-flow models. Netw. Spat. Econ. 4(3), 257–268 (2004)
Carey, M.: Link travel times II: Properties derived from traffic-flow models. Netw. Spat. Econ. 4(4), 379–402 (2004)
Chen, H.-K.: Dynamic Travel Choice Models: A Variational Inequality Approach. Springer, Berlin (1999)
Chen, H.-K., Hsueh, C.-F.: A model and an algorithm for the dynamic user-optimal route choice problem. Transp. Res. B 32(3), 219–234 (1998)
Daganzo, C.F.: Queue spillovers in transportation networks with a route choice. Transp. Sci. 32(1), 3–11 (1998)
Fleischer, L.K., Tardos, É.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3–5), 71–80 (1998)
Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6(3), 419–433 (1958)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Friesz, T.L., Bernstein, D., Smith, T.E., Tobin, R.L., Wie, B.W.: A variational inequality formulation of the dynamic network user equilibrium problem. Oper. Res. 41(1), 179–191 (1993)
Friesz, T.L., Luque, J., Tobin, R.L., Wie, B.W.: Dynamic network traffic assignment considered as a continuous time optimal control problem. Oper. Res. 37(6), 893–901 (1989)
Hamacher, H.W., Tjandra, S.A.: Mathematical modelling of evacuation problems: a state of the art. In: Schreckenberg, M., Sharma, S.D. (eds.) Pedestrian and Evacuation Dynamics, pp. 227–266. Springer, Berlin (2002)
Han, S., Heydecker, B.G.: Consistent objectives and solution of dynamic user equilibrium models. Transp. Res. B 40(1), 16–34 (2006)
Hendrickson, C., Kocur, G.: Schedule delay and departure time decisions in a deterministic model. Transp. Sci. 15(1), 62–77 (1981)
Hoefer, M., Mirrokni, V., Röglin, H., Teng, S.-H.: Competitive routing over time. In: Leonardi, S. (ed.) Proceedings of the 5th International Workshop on Internet and Network Economics. Lecture Notes in Computer Science, vol. 5929, pp. 18–29. Springer, Berlin (2009)
Jarvis, J.J., Ratliff, H.D.: Some equivalent objectives for dynamic network flow problems. Manag. Sci. 28, 106–108 (1982)
Koch, R.: PhD thesis, TU Berlin. In preparation
Koch, R., Skutella, M.: Nash equilibria and the price of anarchy for flows over time. In: Mavronicolas, M. (ed.) Proceedings of the 2nd International Symposium on Algorithmic Game. Lecture Notes in Computer Science, vol. 5814, pp. 323–334. Springer, Berlin (2009)
Köhler, E., Skutella, M.: Flows over time with load-dependent transit times. SIAM J. Optim. 15, 1185–1202 (2005)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Springer, Berlin (2008)
Lin, W.H., Lo, H.K.: Are the objective and solutions of dynamic user-equilibrium models always consistent? Transp. Res. A 34(2), 137–144 (2000)
Mahmassani, H.S., Herman, R.: Dynamic user equilibrium departure time and route choice on idealized traffic arterials. Transp. Sci. 18(4), 362–384 (1984)
Mahmassani, H.S., Peeta, S.: System optimal dynamic assignment for electronic route guidance in a congested traffic network. In: Gartner, N.H., Improta, G. (eds.) Urban Traffic Networks. Dynamic Flow Modelling and Control, pp. 3–37. Springer, Berlin (1995)
Mahmassani, H.S., Sbayti, H.A., Zhou, X.: DYNASMART-P Version 1.0 User’s Guide. Maryland Transportation Initiative, College Park (2004)
Mounce, R.: Convergence in a continuous dynamic queueing model for traffic networks. Transp. Res. B 40(9), 779–791 (2006)
Mounce, R.: Convergence to equilibrium in dynamic traffic networks when route cost is decay monotone. Transp. Sci. 41(3), 409–414 (2007)
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
de Palma, A., Ben-Akiva, M., Lefèvre, C., Litinas, N.: Stochastic equilibrium model of peak period traffic congestion. Transp. Sci. 17(4), 430–453 (1983)
Peeta, S., Ziliaskopoulos, A.K.: Foundations of dynamic traffic assignment: the past, the present and the future. Netw. Spat. Econ. 1(3–4), 233–265 (2001)
Powell, W.B., Jaillet, P., Odoni, A.: Stochastic and dynamic networks and routing. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.) Network Routing. Handbooks in Operations Research and Management Science, vol. 8, pp. 141–295. North-Holland, Amsterdam (1995)
Ran, B., Boyce, D.E.: Modelling Dynamic Transportation Networks. Springer, Berlin (1996)
Ran, B., Boyce, D.E., Leblanc, L.J.: A new class of instantaneous dynamic user-optimal traffic assignment models. Oper. Res. 41(1), 192–202 (1993)
Ran, B., Hall, R.W., Boyce, D.E.: A link-based variational inequality model for dynamic departure time/route choice. Transp. Res. B 30(1), 31–46 (1996)
Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)
Roughgarden, T., Tardos, É.: How bad is selfish routing. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 93–102 (2000)
Skutella, M.: An introduction to network flows over time. In: Cook, W., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Berlin (2009)
Smith, M.J.: The existence of a time-dependent equilibrium distribution of arrivals at a single bottleneck. Transp. Sci. 18(4), 385–394 (1984)
Smith, M.J.: A new dynamic traffic model and the existence and calculation of dynamic user equilibria on congested capacity-constrained road networks. Transp. Res. B 27(1), 49–63 (1993)
Szeto, W.Y., Lo, Hong K.: A cell-based simultaneous route and departure time choice model with elastic demand. Transp. Res. B 38(7), 593–612 (2004)
Taylor, N.B.: The CONTRAM dynamic traffic assignment model. Netw. Spat. Econ. 3(3), 297–322 (2003)
Vickrey, W.S.: Congestion theory and transport investment. Am. Econ. Rev. 59(2), 251–260 (1969)
Wu, J.H., Chen, Y., Florian, M.: The continuous dynamic network loading problem: a mathematical formulation and solution method. Transp. Res. Part B, Methodol. 32(3), 173–187 (1998)
Xu, Y.W., Wu, J.H., Florian, M., Marcotte, P., Zhu, D.L.: Advances in the continuous dynamic network loading problem. Transp. Sci. 33(4), 341–353 (1999)
Yagar, S.: Dynamic traffic assignment by individual path minimization and queuing. Transp. Res. 5(3), 179–196 (1971)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by DFG Research Center Matheon “Mathematics for key technologies” in Berlin. An extended abstract of this work has been presented at the 2nd International Symposium on Algorithmic Game Theory, see [25].
Rights and permissions
About this article
Cite this article
Koch, R., Skutella, M. Nash Equilibria and the Price of Anarchy for Flows over Time. Theory Comput Syst 49, 71–97 (2011). https://doi.org/10.1007/s00224-010-9299-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-010-9299-y