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.

Mean-Field Game Multi-Population Opinion Dynamics Model

Tigran Bakaryan Institute of Mathematics NAS of RA, Center For Scientific Innovation and Education Armenia Co-Author(s):    Ishkanuhi Hakobyan, Yuliang Gu, Xianjin Yang, Naira Hovakimyan

Abstract: This work presents a scalable and accurate multi-population opinion dynamics model aimed at understanding how interactions within populations lead to consensus, polarization, or fragmentation. Scalability and accuracy are achieved by leveraging group affiliations to define agent similarities, integrating both individual- and group-level interactions. The dual nature of the proposed method enables the examination of micro-level (individual) interactions and macro-level (group) dynamics, providing insights into the reciprocal influence between individual behaviors and group dynamics. Moreover, a corresponding mean-field game (MFG) model is also considered, leading to the examination of a coupled system of MFG equations. We prove the existence of solutions to the MFG model and provide numerical experiments capturing complex social phenomena.

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.

The Price of Cognition in Neural Networks Through Wardrop`s Equilibria Approaches

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):    Mansoor Saburov and Armen Bagdasaryan

Abstract: In a broader context, the experimental investigation postulates that toxic neuropeptides/neurotransmitters are causing damage to the functionality of synapses during neurotransmission processes. In this paper, we are aiming to propose a novel mathematical model that studies the dynamics of synaptic damage in terms of concentrations of toxic neuropeptides/neurotransmitters during neurotransmission processes. Our primary objective is to employ Wardrop`s first and second principles within a neural network of the brain. In order to comprehensively incorporate Wardrop`s first and second principles into the neural network of the brain, we introduce two novel concepts: \textit{neuropeptide`s (neurotransmitter`s) equilibrium} and \textit{synapses optimum}. The \textit{neuropeptide/neurotransmitter equilibrium} refers to \textit{a distribution of toxic neuropeptides/neurotransmitters that leads to uniform damage across all synaptic links}. Meanwhile, \textit{synapses optimum} is \textit{the most desirable distribution of toxic neuropeptides/neurotransmitters that minimizes the cumulative damage experienced by all synapses}. In the context of a neural network within the brain, an analogue of the price of anarchy is \textit{the price of cognition} which is \textit{the most unfavorable ratio between the overall impairment caused by toxic neuropeptide`s (neurotransmitter`s) equilibrium in comparison to the optimal state of synapses (synapses optimum)}. To put it differently, \textit{the price of cognition} measures \textit{the loss of cognitive ability resulting from increased concentrations of toxic neuropeptides/neurotransmitters}. Additionally, a replicator equation is proposed within this framework that leads to the establishment of the synapses optimum during the neurotransmission process. It is important to note that our model serves as a high-level simplification and abstraction of the natural neurotransmission process involving interactions between two neurons. Nevertheless, we envision that this mathematically abstract model can serve as a source of motivation to instigate novel experimental, mathematical, and computational research avenues in the field of contemporary neuroscience.