In this paper, we study atomic dynamic routing games with multiple destinations. We first show that if the first-in–first-out (FIFO) principle is always fulfilled locally to regulate the congestion, then most probably we cannot guarantee the existence of any reasonable approximate Nash equilibrium. By partly discarding the FIFO principle and introducing destination priorities in the regulation rules, we propose a new atomic routing model. In each such game, we prove that a pure strategy Nash equilibrium always exists and can be computed in polynomial time. In addition, the multicommodity routing game can be iteratively decomposed into a series of well-behaved single-destination routing games, which will provide a good characterization of all NEs of the original game.
[1] Cao, Z., Chen, B., Chen, X., Wang, C.: Atomic dynamic flow games: adaptive versus nonadaptive agents. Oper. Res. 69(6), 1680-1695 (2021)
[2] Cominetti, R., Correa, J., Larré, O.: Dynamic equilibria in fluid queueing networks. Oper. Res. 63(1), 21-34 (2015)
[3] Correa, J., Cristi, A., Oosterwijk, T.: On the price of anarchy for flows over time. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC ’19, pp. 559-577. ACM (2019)
[4] Harks, T., Peis, B., Schmand, D., Tauer, B., Koch, L.V.: Competitive packet routing with priority lists. ACM Trans. Econ. Comput. 6(1), 4 (2018)
[5] Hoefer, M., Mirrokni, V.S., Röglin, H., Teng, S.-H.: Competitive routing over time. Theor. Comput. Sci. 412(39), 5420-5432 (2011)
[6] Koch, R., Skutella, M.: Nash equilibria and the price of anarchy for flows over time. Theory Comput. Syst. 49(1), 71-97 (2011)
[7] Scarsini, M., Schröder, M., Tomala, T.: Dynamic atomic congestion games with seasonal flows. Oper. Res. 66(2), 327-339 (2018)
[8] Sering, L., Koch, L.V.: Nash flows over time with spillback. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’19, pages 935—945, USA (2019)
[9] Sering, L., Skutella, M.: Multi-source multi-sink Nash flows over time. In: Borndörfer, R., Storandt, S. (eds), Proceedings of the 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, pp. 12:1-12:20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
[10] Werth, T.L., Holzhauser, M., Krumke, S.O.: Atomic routing in a deterministic queuing model. Oper. Res. Perspect. 1(1), 18-41 (2014)
[11] Vickrey, W.S.: Congestion theory and transport investment. Am. Econ. Rev. 59(2), 251-260 (1969)
[12] Horni, A., Nagel, K., Axhausen, K.W.: The Multi-Agent Transport Simulation MATSim. Ubiquity Press, London (2016)
[13] Ismaili, A.: Routing games over time with FIFO policy. In: International Conference on Web and Internet Economics, pp. 266-280. Springer (2017)
[14] Sering, L., Vargas Koch, L., Ziemke, T.: Convergence of a packet routing model to flows over time. In: Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 797-816, (2021)
[15] Scheffler, R., Strehler, M., Koch, L.V.: Routing games with edge priorities. ACM Trans. Econ. Comput. 10(1), 1-27 (2022)
[16] Hoefer, M., Mirrokni, V.S., Röglin, H., Teng, S.-H.: Competitive routing over time. In: International Workshop on Internet and Network Economics, pp. 18-29. Springer (2009)
[17] Kulkarni, J., Mirrokni, V.: Robust price of anarchy bounds via LP and fenchel duality. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1030-1049, Philadelphia, PA, USA (2015)
[18] Cominetti, R., Correa, J., Olver, N.: Long-term behavior of dynamic equilibria in fluid queuing networks. Oper. Res. 70(1), 516-526 (2022)
[19] Kaiser, M.: Computation of dynamic equilibria in series-parallel networks. Math. Oper. Res. 47(1), 50-71 (2022)
[20] Sering, L., Skutella, M.: Multi-source multi-sink Nash flows over time. In: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, arXiv:1807.01098 (2018)
