Distributed Hessian–Riemannian flow for multi-population wardrop equilibrium

Tigran Bakaryan; Christoph Aoun; Ricardo de Lima Ribeiro; Naira Hovakimyan; Diogo Gomes; Tigran Bakaryan; Christoph Aoun; Ricardo de Lima Ribeiro; Naira Hovakimyan; Diogo Gomes

doi:10.3934/math.2026623

AIMS Mathematics

2026, Volume 11, Issue 5: 15143-15162. doi: 10.3934/math.2026623

Previous Article Next Article

Research article

Distributed Hessian–Riemannian flow for multi-population wardrop equilibrium

1.
Institute of Mathematics NAS RA, Center for Scientific Innovation and Education, Yerevan State University, Yerevan, Armenia
2.
Department of Aerospace Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
3.
Applied Mathematics and Computational Sciences, King Abdullah University of Science and Technology, 23955 Thuwal, Saudi Arabia
4.
Department of Mechanical Science and Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
5.
Mathematics and Computational Sciences, King Abdullah University of Science and Technology, 23955 Thuwal, Saudi Arabia

Received: 31 December 2025 Revised: 28 April 2026 Accepted: 08 May 2026 Published: 29 May 2026
MSC : 90B20, 90C33, 91A43

In this paper, we studied a multi-population Wardrop equilibrium on generalized directed graphs with heterogeneous costs. Using an edge-flow representation, we formulated the equilibrium as a variational inequality and provided sufficient conditions for existence and uniqueness under compactness, continuity, and monotonicity assumptions. We showed that the equilibrium problem is equivalent to a noncooperative game among the populations. Relying on this game formulation, we proposed a multi-population Hessian–Riemannian flow for computing the equilibrium. The flow exploited the geometry of the feasible flow space and preserved the Kirchhoff flow-conservation constraints. We proved convergence of the continuous-time dynamics under the stated assumptions and demonstrated the method on heterogeneous traffic examples through comparisons with benchmark methods, including projected gradient, Gauss–Seidel, and nonlinear programming, as well as through an emissions-related case study.
- Wardrop equilibrium,
- multi-population traffic,
- variational inequality,
- edge-flow formulation,
- Hessian–Riemannian flow,
- distributed computation
Citation: Tigran Bakaryan, Christoph Aoun, Ricardo de Lima Ribeiro, Naira Hovakimyan, Diogo Gomes. Distributed Hessian–Riemannian flow for multi-population wardrop equilibrium[J]. AIMS Mathematics, 2026, 11(5): 15143-15162. doi: 10.3934/math.2026623

Related Papers:

Abstract

In this paper, we studied a multi-population Wardrop equilibrium on generalized directed graphs with heterogeneous costs. Using an edge-flow representation, we formulated the equilibrium as a variational inequality and provided sufficient conditions for existence and uniqueness under compactness, continuity, and monotonicity assumptions. We showed that the equilibrium problem is equivalent to a noncooperative game among the populations. Relying on this game formulation, we proposed a multi-population Hessian–Riemannian flow for computing the equilibrium. The flow exploited the geometry of the feasible flow space and preserved the Kirchhoff flow-conservation constraints. We proved convergence of the continuous-time dynamics under the stated assumptions and demonstrated the method on heterogeneous traffic examples through comparisons with benchmark methods, including projected gradient, Gauss–Seidel, and nonlinear programming, as well as through an emissions-related case study.

References

[1]	E. Altman, T. Basar, T. Jimenez, N. Shimkin, Competitive routing in networks with polynomial cost, Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, Israel: IEEE, 3 (2000), 1586–1593. https://doi.org/10.1109/infcom.2000.832557
[2]	F. Alvarez, J. Bolte, O. Brahic, Hessian riemannian gradient flows in convex programming, SIAM J. Control Optim., 43 (2004), 477–501. https://doi.org/10.1137/s0363012902419977 doi: 10.1137/s0363012902419977
[3]	M. J. Beckmann, C. B. McGuire, C. B. Winsten, Studies in the economics of transportation, Santa Monica, CA: RAND Corporation, 1955.
[4]	F. Al Saleh, T. Bakaryan, D. Gomes, R. de Lima Ribeiro, First-order mean-field games on networks and wardrop equilibrium, Port. Math., 81 (2024), 201–246. https://doi.org/10.4171/pm/2124 doi: 10.4171/pm/2124
[5]	U. Bhaskar, L. Fleischer, D. Hoy, C. C. Huang, Equilibria of atomic flow games are not unique, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2009,748–757. https://doi.org/10.1137/1.9781611973068.82
[6]	J. R. Correa, N. E. Stier-Moses, Wardrop equilibria, In: Wiley encyclopedia of operations research and management science, John Wiley & Sons, Ltd., 2011. https://doi.org/10.1002/9780470400531.eorms0962
[7]	F. Facchinei, C. Kanzow, Generalized nash equilibrium problems, Ann. Oper. Res., 175 (2010), 177–211. https://doi.org/10.1007/s10479-009-0653-x doi: 10.1007/s10479-009-0653-x
[8]	M. Gairing, M. Klimm, Congestion games with player-specific costs revisited, In: B. V"ocking, Algorithmic game theory, SAGT 2013, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, 2013, 98–109. https://doi.org/10.1007/978-3-642-41392-6_9
[9]	D. A. Gomes, X. Yang, The hessian riemannian flow and newton's method for effective hamiltonians and mather measures, ESAIM: Math. Model. Numer. Anal., 54 (2020), 1883–1915.
[10]	A. Haurie, P. Marcotte, On the relationship between nash–cournot and wardrop equilibria, Networks, 15 (1985), 295–308. https://doi.org/10.1002/net.3230150303 doi: 10.1002/net.3230150303
[11]	P. T. Harker, J. S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Program., 48 (1990), 161–220. https://doi.org/10.1007/bf01582255 doi: 10.1007/bf01582255
[12]	H. K. Khalil, Nonlinear systems, 3 Eds., Upper Saddle River, NJ: Prentice Hall, 2002.
[13]	Y. Li, W. Jia, L. Liu, Cooperative emergence induced by asymmetric punishment and strategy persistence mechanisms in multilayer networks, Commun. Nonlinear Sci. Numer. Simul., 152 (2026), 109187. https://doi.org/10.1016/j.cnsns.2025.109187 doi: 10.1016/j.cnsns.2025.109187
[14]	H. S. Mahmassani, K. C. Mouskos, Some numerical results on the diagonalization algorithm for network assignment with asymmetric interactions between cars and trucks, Transp. Res. Part B: Methodol., 22 (1988), 275–290. https://doi.org/10.1016/0191-2615(88)90004-5 doi: 10.1016/0191-2615(88)90004-5
[15]	F. Meunier, T. Pradeau, A lemke-like algorithm for the multiclass network equilibrium problem, In: Y. Chen, N. Immorlica, Web and internet economics, Berlin, Heidelberg: Springer, 2013,363–376. https://doi.org/10.1007/978-3-642-45046-4_30
[16]	F. Meunier, T. Pradeau, Computing solutions of the multiclass network equilibrium problem with affine cost functions, Ann. Oper. Res., 274 (2019), 447–469. https://doi.org/10.1007/s10479-018-2817-z doi: 10.1007/s10479-018-2817-z
[17]	A. Orda, R. Rom, N. Shimkin, Competitive routing in multi-user communication networks. Proceedings of IEEE INFOCOM '93: The Conference on Computer Communications, Vol. 3, San Francisco, CA, USA: IEEE, 1993,964–971. https://doi.org/10.1109/infcom.1993.253270
[18]	M. Patriksson, The traffic assignment problem: models and methods, Dover Publications, 2015.
[19]	D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, J. Lygeros, Nash and wardrop equilibria in aggregative games with coupling constraints, IEEE Trans. Automat. Control, 64 (2019), 1373–1388. https://doi.org/10.1109/tac.2018.2849946 doi: 10.1109/tac.2018.2849946
[20]	O. Richman, N. Shimkin, Topological uniqueness of the nash equilibrium for selfish routing with atomic users, Math. Oper. Res., 32 (2007), 215–232. https://doi.org/10.1287/moor.1060.0229 doi: 10.1287/moor.1060.0229
[21]	J. B. Rosen, Existence and uniqueness of equilibrium points for concave n-person games, Econometrica, 33 (1965), 520–534. https://doi.org/10.2307/1911749 doi: 10.2307/1911749
[22]	M. J. Smith, The existence, uniqueness and stability of traffic equilibria, Transp. Res. Part B: Methodol., 13 (1979), 295–304. https://doi.org/10.1016/0191-2615(79)90022-5 doi: 10.1016/0191-2615(79)90022-5
[23]	M. J. Smith, Junction interactions and monotonicity in traffic assignment, Transp. Res. Part B: Methodol., 16 (1982), 1–3. https://doi.org/10.1016/0191-2615(82)90036-4 doi: 10.1016/0191-2615(82)90036-4
[24]	T. T. Shang, W. S. Jia, The GUS-property of linear complementarity problems over tensor spaces, Optimization, 75 (2026), 1831–1854. https://doi.org/10.1080/02331934.2025.2517324 doi: 10.1080/02331934.2025.2517324
[25]	N. Shimkin, A survey of uniqueness results for selfish routing, In: T. Chahed, B. Tuffin, Network control and optimization, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, 2007, 33–42. https://doi.org/10.1007/978-3-540-72709-5_4
[26]	J. Tidswell, A. Raith, Modelling traffic assignment objectives with emission cost functions, Australasian Transport Research Forum (ATRF) 2017 Proceedings, Auckland, New Zealand, 2017.
[27]	J. G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the Institution of Civil Engineers, Part II, 1 (1952), 325–362. https://doi.org/10.1680/ipeds.1952.11259 doi: 10.1680/ipeds.1952.11259
[28]	K. Wang, W. Jia, A new intelligent algorithm for solving generalized nash equilibrium problem, Alex. Eng. J., 123 (2025), 17–28. https://doi.org/10.1016/j.aej.2025.03.044 doi: 10.1016/j.aej.2025.03.044

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)