A. G. Bagdasaryan, “Optimal flows in transport networks, affine-nonlinear deformations of networks, and replicator dynamical systems generated by Schur functions”, Russian Math. Surveys, 80:3 (2025), 540

In [1] two principles of network flow distribution that describe the situation of Wardrop equilibrium and the system optimum were formulated. Subsequently, Dafermos [2] considered the problem of the characterization of cost functions for which the Wardrop equilibrium coincides with the system optimum of the network. This problem was completely solved for parallel networks in [3], where a wide class of Wardrop-optimal networks ($\operatorname{WOF}$-networks) was introduced, for which the price of anarchy, as a measure of network inefficiency, is equal to its least value, that is, to $1$.

In this paper we construct affine (see Theorem 1 (i)) and nonlinear (see Theorem 1 (ii)) deformations of networks that transform an arbitrary network into a Wardrop-optimal network for an arbitrary a priori given flow. We introduce a more general class of Wardrop-optimal networks based on Schur functions and the concept of similar-order preservation [4], [5]. Finally, we propose a replicator dynamical system on a Wardrop-optimal network generated by Schur functions, for which we study the problem of stability (see Theorem 2), and for which the Nash equilibrium, Wardrop equilibrium, and system optimum determine the same flow distribution on the network (see Theorem 3). Note that Theorem 3 generalizes the main results of [3] and [4].

1. We consider a network $\mathbf{I}_m=\{1,\dots,m\}$ of $m$ alternative parallel links, that connect two fixed nodes as a single origin-destination pair. Suppose $\mathbb{R}^m$ is equipped with the $l_1$-norm $\|\mathbf{x}\|_1:=\sum_{k=1}^m|x_k|$. Let $\mathbf{x}=(x_1,\dots,x_m)\in \mathbb{R}_{+}^{m}$ be a flow vector of the network, where $x_k$ is a flow on the link $k$ such that $\|\mathbf{x}\|_1\leqslant 1$. Let $\mathbf{L}(\mathbf{x})=\langle \ell_1(x_1),\dots,\ell_m(x_m)\rangle$ denote an effective cost vector function of routing (network) at a flow vector $\mathbf{x}$, where the $\ell_k\colon[0,\infty)\to [0,\infty)$, $k\in\mathbf{I}_m$, are convex, strictly increasing, and continuously differentiable functions. A flow vector $\mathbf{x}$ is called a Wardrop equilibrium if it satisfies the condition $\ell_k(x_k)=\min_{i\in\mathbf{I}_m}\{\ell_i(x_i)\}$ for each $k\in \mathbf{I}_m$, $x_k>0$, and it is called a system optimum if $\mathbf{x}$ minimizes the value of the sum $\sum_{i=1}^m x_i\ell_i(x_i)$. A network $\mathbf{L}(\,\boldsymbol\cdot\,)$ is referred to as a $\operatorname{WOF}$-network if it admits a Wardrop optimal flow, which is the Wardrop equilibrium, as well as the system optimum of the network. Here, for Wardrop optimal flows $\mathbf{q}$ we have $\|\mathbf{q}\|_1=1$ [3]. The set of all networks with common Wardrop optimal flow $\mathbf{q}$ is denoted by $\operatorname{WOF}(\mathbf{q})$. Let $\mathbb{S}^{m-1}:= \{\mathbf{x}\in\mathbb{R}_{+}^{m}\colon\|\mathbf{x}\|_1=1\}$ be the standard simplex, and let $\operatorname{int}\mathbb{S}^{m-1}:=\{\mathbf{x}\in\mathbb{S}^{m-1}\colon \operatorname{supp}(\mathbf{x})=\mathbf{I}_m\}$.

Theorem 1. Let $\mathbf{L}(\mathbf{x})= \langle\ell_1(x_1),\dots,\ell_m(x_m)\rangle$ be a convex differentiable network at a flow vector $\mathbf{x}\in \mathbb{S}^{m-1}$ and $\mathbf{q}\in\operatorname{int}\mathbb{S}^{m-1}$ be any positive flow. Then there exist networks

$$ \begin{equation*} \begin{aligned} \, \mathbf{\Lambda}_1(\mathbf{x}) &=\langle r_1x_1,\dots,r_mx_m\rangle, \\ \mathbf{\Lambda}_2(\mathbf{x}) &=\langle a_1x_1+b_1,\dots,a_mx_m+b_m\rangle, \\ \mathbf{\Lambda}_3(\mathbf{x}) &=\langle c_1x_1^n+d_1,\dots,c_mx_m^n+d_m\rangle, \qquad n\geqslant 2,\quad n\in\mathbb{N}, \end{aligned} \end{equation*} \notag $$

such that

$$ \begin{equation*} \begin{alignedat}{2} \textrm{(i)}&&\quad \widetilde{\mathbf{L}}(\mathbf{x})&= [(\mathbf{\Lambda}_1\circ\mathbf{L})+\mathbf{\Lambda}_2](\mathbf{x})= \mathbf{\Lambda}_1(\mathbf{L}(\mathbf{x}))+\mathbf{\Lambda}_2(\mathbf{x}) \\ &&&=\langle r_1\ell_1(x_1)+a_1x_1+b_1,\dots,r_m\ell_m(x_m)+a_mx_m+b_m\rangle,\\ \textrm{(ii)}&&\quad \widehat{\mathbf{L}}(\mathbf{x})&= (\mathbf{\Lambda}_3+\mathbf{L})(\mathbf{x})= \mathbf{\Lambda}_3(\mathbf{x})+\mathbf{L}(\mathbf{x}) \\ &&&=\langle\ell_1(x_1)+c_1x_1^n+d_1,\dots,\ell_m(x_m)+c_mx_m^n+d_m\rangle \end{alignedat} \end{equation*} \notag $$

are Wardrop optimal networks $\operatorname{WOF}(\mathbf{q})$ at any a priori given flow $\mathbf{q}$.

From Theorem 1 it follows that any network can be transformed into a Wardrop-optimal network by means of affine-nonlinear deformations.

2. We construct a generalization of the class of Wardrop-optimal networks, which is associated with Schur functions. Let $\varphi\colon\mathbb{R}_{+}^m\to\mathbb{R}_{+}$ be a continuously differentiable, strictly increasing and strictly Schur-convex function. It is known [6] that the gradient vector field $\nabla\varphi\colon\mathbb{R}_{+}^m\to\mathbb{R}_{+}^m$, where $\nabla\varphi(\mathbf{x}):= (\partial\varphi(\mathbf{x})/\partial x_1,\ldots, \partial\varphi(\mathbf{x})/\partial x_m)$, is similar-order preserving: $x_i\mathbin{\bigl(\gtreqqless\bigr)}x_j\Leftrightarrow \partial\varphi(\mathbf{x})/\partial x_i\mathbin{\bigl(\gtreqqless\bigr)} \partial\varphi(\mathbf{x})/\partial x_j$, $i,j\in\mathbf{I}_m$. We introduce the networks ${}_{\mathcal{S}}\mathbf{\Phi}(\mathbf{x})= \Bigl\langle\,\underbrace{\partial\varphi(\mathbf{x})/ \partial x_1}_{\ell_1(x_1,\dots,x_m)},\dots, \underbrace{\partial\varphi(\mathbf{x})/ \partial x_m}_{\ell_m(x_1,\dots,x_m)}\,\Bigr\rangle$, $\mathbf{x}\in\mathbb{S}^{m-1}$, where each function $\ell_k$ depends not only on the flow on the link $k$, but also on the flows on the links $j\in\mathbf{I}_m$, $j\ne k$, from which we obtain a more general class of networks, to be referred to as Wardrop-Schur optimal networks. These networks can be constructed by using, for example, complete symmetric functions, gamma functions, or symmetric gauge functions of unitary invariant norms.

Let $\mathbf{q}=(q_1,\dots,q_m)\in\mathbb{S}^{m-1}$, $\mathbf{q}>0$, and let $\mathbf{x}/\mathbf{q}:=(x_1/q_1,\dots,x_m/q_m)$ for any $\mathbf{x}\in\mathbb{S}^{m-1}$. Let ${}_\mathcal{S}\mathbf{\Phi}_n\biggl(\dfrac{\mathbf{1}}{\mathbf{q}} \,\boldsymbol\cdot\,\biggr):=\biggl\langle\dfrac{\partial\varphi^{(n)}} {\partial\,\bullet_1}\biggl(\dfrac{\mathbf{1}} {\mathbf{q}}\,\boldsymbol\cdot\,\biggr),\dots,\dfrac{\partial\varphi^{(n)}} {\partial\,\bullet_m}\biggl(\dfrac{\mathbf{1}} {\mathbf{q}}\,\boldsymbol\cdot\,\biggr)\biggr\rangle$, $n\in\mathbb{N}$, and $\{\varphi^{(n)}\}_{n\in\mathbb{N}}$, where $\varphi^{(n)}\colon[0,\bar{q}]^m \to [0,1]$, be a sequence of continuously differentiable and uniformly strictly increasing Schur functions with uniformly bounded Pigouvian taxes

$$ \begin{equation*} \mu:=\displaystyle\sup_{n\in\mathbb{N}} \biggl[\displaystyle\max_{x_i \in[0,\bar{q}],\, i\in\mathbf{I}_m} \dfrac{\partial}{\partial x_i}\biggl(x_i\dfrac{\partial\varphi^{(n)}} {\partial x_i}(\mathbf{x})\biggr)\biggr]<\infty, \quad \bar{q}=\dfrac{1}{\min_{i\in\mathbf{I}_m}{q_i}}. \end{equation*} \notag $$

$$ \begin{equation} \begin{gathered} \, \bigl({}_\mathcal{S}\mathcal{R}_n(\mathbf{x})\bigr)_k= x_k\biggl[1+\varepsilon\biggl\{\frac{\partial\varphi^{(n)}}{\partial x_k} \biggl(\frac{\mathbf{x}}{\mathbf{q}}\biggr)-\sum_{i=1}^m x_i\,\frac{\partial\varphi^{(n)}}{\partial x_i} \biggl(\frac{\mathbf{x}}{\mathbf{q}}\biggr)\bigg\}\biggr] \\ \forall\,k\in\mathbf{I}_m, \quad \varepsilon\in(-1,0), \quad n\in\mathbb{N}. \end{gathered} \end{equation} \tag{1} $$

Theorem 2. Let $\varepsilon\in(-1/\mu,0)\cap(-1,0)$. Then an orbit of the replicator dynamical system ${}_\mathcal{S}\mathcal{R}_n\colon\mathbb{S}^{m-1}\to\mathbb{S}^{m-1}$ starting from an arbitrary initial point $\mathbf{x}\in\mathbb{S}^{m-1}$ converges to the fixed point $\mathbf{q}_{\operatorname{supp}(\mathbf{x})}$ located in the interior of the face $\mathbb{S}^{|\operatorname{supp}(\mathbf{x})|-1}$.

A flow $\mathbf{x}\in\mathbb{S}^{m-1}$ is called a common Nash equilibrium for the replicator system (1) if $\varepsilon\langle\mathbf{x}\mid {{}_\mathcal{S}\mathbf{\Phi}}_n(\mathbf{x}/\mathbf{q})\rangle\geqslant \varepsilon\langle\mathbf{y} \mid {{}_\mathcal{S}\mathbf{\Phi}}_n(\mathbf{x}/\mathbf{q})\rangle$ for all $\mathbf{y}\in\mathbb{S}^{m-1}$, $n\in\mathbb{N}$.

Theorem 3. Let $\varepsilon\in(-1/\mu,0)\cap(-1,0)$. Then the following statements hold for system (1):

(i) the unique Wardrop optimal flow $\mathbf{q}$ is the only common Nash equilibrium;

(ii) the unique Wardrop optimal flow $\mathbf{q}$ is the only stable common fixed point;

(iii) each interior orbit converges to the unique Wardrop optimal flow $\mathbf{q}$.

The author is grateful to M. Kh. Saburov for posing the problem and fruitful discussions.

Citation in format AMSBIB

\Bibitem{Bag25}

\by A.~G.~Bagdasaryan

\paper Optimal flows in transport networks, affine-nonlinear deformations of networks, and replicator dynamical systems generated by Schur functions

\jour Russian Math. Surveys

\yr 2025

\vol 80

\issue 3

\pages 540--542

\mathnet{http://mi.mathnet.ru/eng/rm10226}

\crossref{https://doi.org/10.4213/rm10226e}

\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=4961292}

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2025RuMaS..80..540B}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001620411700007}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-105016148252}

Bibliography