Special Session 120: Congestion Games on Networks and the Price of Anarchy: Theory and Applications

Traditional selfish routing models in network flow

Ovidiu O Bagdasar University of Derby England Co-Author(s):

Abstract: Traditional selfish routing models in network flow typically focus on a single objective, such as travel time or distance, and are guided by the principle of user equilibrium (UE). However, real-world scenarios demand the consideration of multiple objectives, such as distance, travel time, and pollution. This paper addresses a bi-criteria problem where individual road users aim to minimize their travel time, conflicting with the collective objective of minimizing total fuel consumption. By adjusting `free` parameters, specifically speed limits, we explore how user behavior can be influenced to align better with the fuel consumption objective. Inspired by the Price of Anarchy (PoA) concept, which measures the suboptimality of equilibrium based on minimum total travel time, we classify equilibrium solutions using a weighted model that balances travel time and fuel consumption. Our results indicate that modest parameter adjustments can yield Pareto-improving solutions, demonstrating that while our equilibrium suboptimality measure reveals network inefficiencies, it may not fully capture solution quality when comparing different network configurations.

Discrete-time replicator equations on Wardrop optimal transport networks

Armen Bagdasaryan American University of the Middle East Kuwait Co-Author(s):    Mansur Saburov

Abstract: In this talk, we consider a novel field of application of replicator dynamics by proposing the discrete-time replicator equations for studying optimal transport networks with congestion. We first introduce the concept of a Wardrop optimal network that admits Wardrop optimal flows that are both Nash equilibrium and system optimum, and are the only networks with the price of anarchy exactly equal to its least value of 1. Then we present a novel dynamical model of optimal flow distribution on Wardrop optimal networks, using the ideas of evolutionary game theory, which unlike the classical game theory, focuses on the dynamics of strategy change. Our dynamical model is based on discrete-time mean-field replicator equations defined over probability simplices, generated by nonlinear order-preserving mappings. In particular, we study replicator dynamics induced by convex differentiable functions and Schur-convex potential functions. As examples, we employ complete symmetric functions, gamma functions, and symmetric gauge functions in generating replicator dynamics. We analyze the dynamic behavior of these systems, focusing on convergence and stability properties. Using techniques from dynamical systems theory, including Lyapunov functions, we examine Nash equilibria, convergence to fixed points, and conditions for asymptotic stability. For the replicator equations under consideration, the Nash equilibrium, the Wardrop equilibrium, and the system optimum coincide, thus representing the same point in the state space. Certain affine and nonlinear deformations of networks that preserve the property of Wardrop optimality and stochastic method of the construction of Wardrop optimal networks will be presented.

Tigran Bakaryan Institute of Mathematics NAS of RA, Center For Scientific Innovation and Education Armenia Co-Author(s):

Abstract:

Exact Solutions to Stationary Mean-Field Games on Networks

Ricardo L Ribeiro KAUST Saudi Arabia Co-Author(s):    Fatimah Al Saleh, Tigran Bakaryan, Diogo A. Gomes

Abstract: In this talk, I will present a recursive algorithm developed to solve stationary critical congestion mean-field games (MFGs) on networks. These games model scenarios where a large number of agents move through a network -- such as transportation systems -- seeking to minimize costs based on their actions and the congestion created by others. The MFG formulation leads to an algebraic system consisting of linear equations, inequalities, and complementarity conditions. The algorithm I will discuss handles the complexity of the problem. We implement preprocessing steps that reduce the system`s size and complexity, along with a custom approach for managing the combinatorial challenges at key network nodes. However, the recursive nature of the algorithm introduces some limitations, particularly with regard to scalability. I will illustrate the algorithm`s performance using several case studies, including road merges and forks, and a real-world scenario inspired by the Jamarat bridge during the Hajj pilgrimage. Finally, if time permits, I will discuss the challenges posed by non-critical congestion cases and explore future directions for improving the algorithm`s efficiency and applicability.

Mansur Saburov Department of Mathematics and Natural Science, College of Arts and Sciences (CAS), Center for Applied Mathematics and Bioinformatics (CAMB), Gulf University for Science and Technology (GUST) Kuwait Co-Author(s):

Abstract: