Nash equilibria and the price of anarchy for flows over time. (English) Zbl 1278.91027
Summary: 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.
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.
MSC:
| 91A43 | Games involving graphs |
| 91A10 | Noncooperative games |
| 90B22 | Queues and service in operations research |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | Akamatsu, T.: A dynamic traffic equilibrium assignment paradox. Transp. Res. B 34(6), 515–531 (2000) · doi:10.1016/S0191-2615(99)00036-3 |
| [2] | Akamatsu, T.: An efficient algorithm for dynamic traffic equilibrium assignment with queues. Transp. Sci. 35(4), 389–404 (2001) · Zbl 1069.90513 · doi:10.1287/trsc.35.4.389.10435 |
| [3] | Akamatsu, T., Heydecker, B.: Detecting dynamic traffic assignment capacity paradoxes in saturated networks. Transp. Sci. 37(2), 123–138 (2003) · doi:10.1287/trsc.37.2.123.15245 |
| [4] | 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) · Zbl 1262.90024 |
| [5] | Aronson, J.E.: A survey of dynamic network flows. Ann. Oper. Res. 20(1–4), 1–66 (1989) · Zbl 0704.90028 · doi:10.1007/BF02216922 |
| [6] | 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) |
| [7] | 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) · Zbl 1048.90061 |
| [8] | Braess, D.: Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12 12, 258–268 (1968). In German · Zbl 0167.48305 |
| [9] | Carey, M.: Link travel times I: Properties derived from traffic-flow models. Netw. Spat. Econ. 4(3), 257–268 (2004) · Zbl 1069.90023 · doi:10.1023/B:NETS.0000039782.48154.ef |
| [10] | Carey, M.: Link travel times II: Properties derived from traffic-flow models. Netw. Spat. Econ. 4(4), 379–402 (2004) · Zbl 1093.90005 · doi:10.1023/B:NETS.0000047114.31259.3d |
| [11] | Chen, H.-K.: Dynamic Travel Choice Models: A Variational Inequality Approach. Springer, Berlin (1999) |
| [12] | 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) · doi:10.1016/S0191-2615(97)00026-X |
| [13] | Daganzo, C.F.: Queue spillovers in transportation networks with a route choice. Transp. Sci. 32(1), 3–11 (1998) · Zbl 0987.90508 · doi:10.1287/trsc.32.1.3 |
| [14] | Fleischer, L.K., Tardos, É.: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23(3–5), 71–80 (1998) · Zbl 0947.90016 · doi:10.1016/S0167-6377(98)00037-6 |
| [15] | Ford, L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6(3), 419–433 (1958) · Zbl 0995.90516 · doi:10.1287/opre.6.3.419 |
| [16] | Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962) · Zbl 0106.34802 |
| [17] | 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) · Zbl 0771.90037 · doi:10.1287/opre.41.1.179 |
| [18] | 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) · Zbl 0691.49029 · doi:10.1287/opre.37.6.893 |
| [19] | 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) · Zbl 1048.90041 |
| [20] | Han, S., Heydecker, B.G.: Consistent objectives and solution of dynamic user equilibrium models. Transp. Res. B 40(1), 16–34 (2006) · doi:10.1016/j.trb.2005.01.002 |
| [21] | Hendrickson, C., Kocur, G.: Schedule delay and departure time decisions in a deterministic model. Transp. Sci. 15(1), 62–77 (1981) · doi:10.1287/trsc.15.1.62 |
| [22] | 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) · Zbl 1237.91051 |
| [23] | Jarvis, J.J., Ratliff, H.D.: Some equivalent objectives for dynamic network flow problems. Manag. Sci. 28, 106–108 (1982) · Zbl 0486.90042 · doi:10.1287/mnsc.28.1.106 |
| [24] | Koch, R.: PhD thesis, TU Berlin. In preparation |
| [25] | 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) · Zbl 1262.90026 |
| [26] | Köhler, E., Skutella, M.: Flows over time with load-dependent transit times. SIAM J. Optim. 15, 1185–1202 (2005) · Zbl 1097.90009 · doi:10.1137/S1052623403432645 |
| [27] | Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 4th edn. Springer, Berlin (2008) · Zbl 1149.90126 |
| [28] | 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) |
| [29] | Mahmassani, H.S., Herman, R.: Dynamic user equilibrium departure time and route choice on idealized traffic arterials. Transp. Sci. 18(4), 362–384 (1984) · doi:10.1287/trsc.18.4.362 |
| [30] | 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) · Zbl 0839.90035 |
| [31] | Mahmassani, H.S., Sbayti, H.A., Zhou, X.: DYNASMART-P Version 1.0 User’s Guide. Maryland Transportation Initiative, College Park (2004) |
| [32] | Mounce, R.: Convergence in a continuous dynamic queueing model for traffic networks. Transp. Res. B 40(9), 779–791 (2006) · doi:10.1016/j.trb.2005.10.004 |
| [33] | Mounce, R.: Convergence to equilibrium in dynamic traffic networks when route cost is decay monotone. Transp. Sci. 41(3), 409–414 (2007) · doi:10.1287/trsc.1070.0202 |
| [34] | Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007) · Zbl 1130.91005 |
| [35] | 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) · doi:10.1287/trsc.17.4.430 |
| [36] | 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) · doi:10.1023/A:1012827724856 |
| [37] | 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) · Zbl 0870.90059 |
| [38] | Ran, B., Boyce, D.E.: Modelling Dynamic Transportation Networks. Springer, Berlin (1996) · Zbl 0898.90004 |
| [39] | 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) · Zbl 0771.90039 · doi:10.1287/opre.41.1.192 |
| [40] | 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) · doi:10.1016/0191-2615(95)00010-0 |
| [41] | Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005) · Zbl 1318.68065 |
| [42] | 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) · Zbl 1323.90011 |
| [43] | 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) · Zbl 1359.90020 |
| [44] | Smith, M.J.: The existence of a time-dependent equilibrium distribution of arrivals at a single bottleneck. Transp. Sci. 18(4), 385–394 (1984) · doi:10.1287/trsc.18.4.385 |
| [45] | 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) · doi:10.1016/0191-2615(93)90011-X |
| [46] | 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) · doi:10.1016/j.trb.2003.05.001 |
| [47] | Taylor, N.B.: The CONTRAM dynamic traffic assignment model. Netw. Spat. Econ. 3(3), 297–322 (2003) · doi:10.1023/A:1025394201651 |
| [48] | Vickrey, W.S.: Congestion theory and transport investment. Am. Econ. Rev. 59(2), 251–260 (1969) |
| [49] | 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) · doi:10.1016/S0191-2615(97)00023-4 |
| [50] | 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) · Zbl 0958.90005 · doi:10.1287/trsc.33.4.341 |
| [51] | Yagar, S.: Dynamic traffic assignment by individual path minimization and queuing. Transp. Res. 5(3), 179–196 (1971) · doi:10.1016/0041-1647(71)90020-7 |
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.
