| Russian Mathematical Surveys |
|
|
|
|
|
Brief communications Dynamics of replicator equations on Wardrop optimal networks A. G. Bagdasaryana, A. Kalampakasa, M. Kh. Saburova a College of Engineering and Technology, American University of the Middle East, Kuwait
Bibliographic databases:
     In this paper we introduce and study Wardrop optimal networks, that is, networks that admit Wardrop optimal flows, which are the Wardrop equilibria as well as the system optima of the networks. It is worth mentioning that the Wardrop optimal networks are the only networks for which the price of anarchy is exactly equal to its least value, that is, to $1$. We provide a complete and comprehensive characterization (see Theorem 1) of Wardrop optimal networks, which completely solves for the very first time a problem stated by Dafermos in the case of parallel networks (see [1]–[3]): given a network, characterize the class of cost functions for which the Wardrop equilibrium coincides with the system optimum of the network. We also study the geometric structure of the set of all routing cost vector functions for which any flow fixed a priori determines a Wardrop optimal flow. This set is a closed convex cone which is closed under the operations of addition, multiplication, and composition with convex functions (see Theorem 2). It should be noted that Dafermos (see [1] and [2]) provided only one example of a cost vector function with monomials of equal degree that is a Wardrop optimal network. However, we construct a much wider class of cost vector functions, called Wardrop optimal networks (see Theorem 2, (ii)). Finally, we propose a novel dynamical approach to flow distribution on Wardrop optimal networks, for which the key idea is that the flow on a link whose effective cost is smaller (larger) than the average effective cost of the network will quantitatively increase (decrease, respectively). For this purpose we consider the replicator equation on a Wardrop optimal network, for which the Nash equilibrium, the Wardrop equilibrium, and the system optimum determine the same flow distribution on the network (see Theorem 3, which generalizes the main results of [4]). 1. We consider a problem of routing one unit of flow in a network of $m$ alternative parallel links $\mathbf{I}_m=\{1,\dots,m\}$ that connect two fixed nodes as a single origin-destination pair. 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 $\widetilde{\mathbf{L}}(\mathbf{x}):=\mathbf{L}(\mathbf{x})+\mathbf{c}$ denote an effective cost vector function of routing at a flow vector $\mathbf{x}$, where $\mathbf{L}(\mathbf{x})=\langle \ell_1(x_1),\dots,\ell_m(x_m)\rangle$ and $\ell_k\colon[0,\infty)\to [0,\infty)$, $k\in\mathbf{I}_m$, is a convex, strictly increasing, and continuously differentiable function, $\mathbf{c}=(c_1,\dots,c_m)$ is a price vector of a network, and $c_k$ is the price of routing on the link $k$. Suppose $\mathbf{R}=(R,\dots, R)$ is a reservation utility vector, where $R$ is a common reservation utility (capacity) of the link. A flow vector $\mathbf{q}=(q_1,\dots,q_m)$ is called a Wardrop optimal flow if it satisfies the relation
$$
\begin{equation*}
\begin{aligned} \, \mathbf{q}&\in\!\!\operatorname*{argmax}\limits_{\mathbf{y} \geqslant 0,\,\|\mathbf{y}\|_1\leqslant 1} \biggl\{\sum_{k=1}^m\bigl(R-\ell_k(q_k)-c_k\bigr)y_k \biggr\} \cap\! \operatorname*{argmax}\limits_{\mathbf{y} \geqslant 0,\,\|\mathbf{y}\|_1\leqslant 1} \biggl\{\sum_{k=1}^m\bigl(R-\ell_k(y_k)-c_k\bigr)y_k\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
Let $\mathbb{S}^{m-1}:=\{\mathbf{x}\in \mathbb{R}_{+}^{m}\colon \|\mathbf{x}\|_1=1\}$ be the standard simplex. Here we present a complete characterization of the notion of a Wardrop optimal flow $\mathbf{q}$ under the condition $\mathbf{q}\in\mathbb{S}^{m-1}$. Theorem 1. A flow vector $\mathbf{q}=(q_1,\dots,q_m)\in\mathbb{S}^{m-1}$ is a Wardrop optimal flow if and only if the following conditions are satisfied: (i) $\tilde{\ell}_i(q_i)=\tilde{\ell}_j(q_j)$ for all $i,j\in\mathbf{I}_m$, where $q_i>0$ and $q_j>0$; (ii) $q_i\tilde{\ell}'_i(q_i)=q_j\tilde{\ell}'_j(q_j)$ for all $i,j\in\mathbf{I}_m$, where $q_i>0$ and $q_j>0$; (iii) $\tilde{\ell}_i(0)\geqslant\tilde{\ell}_j(q_j)+q_j\tilde{\ell}'_j(q_j)$ for all $i,j\in\mathbf{I}_m$, where $q_i=0$ and $q_j>0$. Set ${\widetilde{\mathbf{q}}}/{\mathbf{q}}:= ({\widetilde{q}_1}/{q_1},\dots,{\widetilde{q}_m}/{q_m})$, ${0}/{0}:=1$ for $\operatorname{supp}(\widetilde{\mathbf{q}})=\operatorname{supp}(\mathbf{q})$. In particular, ${\mathbf{1}}/{\mathbf{q}}:=({1}/{q_1},\dots,{1}/{q_m})$, where $\mathbf{1}=(1,\dots,1)$ and $\operatorname{supp}(\mathbf{q})=\mathbf{I}_m$. Let $\operatorname{WOF}(\mathbf{q})$ denote the set of all effective cost vectors for $\mathbf{q}$ being their common Wardrop optimal flow. Let $\mathbf{L}((\mathbf{\widetilde{q}}/\mathbf{q}) \,\,\boldsymbol\cdot\,)= \langle\ell_1((\widetilde{q}_1/{q_1}) \,\,\boldsymbol\cdot\,),\dots,\ell_m((\widetilde{q}_m/{q_m}) \,\,\boldsymbol\cdot\,)\rangle$ and
$$
\begin{equation*}
\begin{gathered} \, f\biggl(\mathbf{L}\biggl(\frac{\mathbf{\widetilde{q}}}{\mathbf{q}} \,\,\boldsymbol\cdot\,\biggr)\biggr)=\biggl\langle f\biggl(\ell_1 \biggl(\frac{\widetilde{q}_1}{q_1}\,\boldsymbol\cdot\,\biggr)\biggr),\dots, f\biggl(\ell_m\biggl(\frac{\widetilde{q}_m}{q_m} \,\boldsymbol\cdot\,\biggr)\biggr)\biggr\rangle. \end{gathered}
\end{equation*}
\notag
$$
Theorem 2. Let $\varphi,f_i\colon[0,\infty)\to [0,\infty)$ be convex, strictly increasing, and continuously differentiable functions, and let $\mathbf{\Phi}(\mathbf{x}):=(\varphi(x_1),\dots,\varphi(x_m))$, $\mathbf{x}\in\mathbb{S}^{m-1}$. Suppose $\mathbf{L}^{(k)}(\,\boldsymbol\cdot\,) \in \operatorname{WOF}(\mathbf{q}^{(k)})$ for $\operatorname{supp}(\mathbf{q}^{(k)})=\operatorname{supp}(\mathbf{q})$, $k\in\mathbf{I}_n$. Then the following hold: (i) $\operatorname{WOF}(\mathbf{q})$ is a convex cone for any $\mathbf{q}\in\mathbb{S}^{m-1}$; (ii) $\mathbf{\Phi}(({\mathbf{1}}/{\mathbf{q}}) \,\,\boldsymbol\cdot\,)\in\operatorname{WOF}(\mathbf{q})$ for $\operatorname{supp}(\mathbf{q})= \mathbf{I}_m$; (iii) ${\sum}_{k=1}^n f_k\bigl(\mathbf{L}^{(k)} (({\mathbf{q}^{(k)}}/{\mathbf{q}})\,\boldsymbol\cdot\,)\bigr) \in\operatorname{WOF}(\mathbf{q})$; (iv) ${\prod}_{k=1}^n f_k\bigl(\mathbf{L}^{(k)} (({\mathbf{q}^{(k)}}/{\mathbf{q}})\,\boldsymbol\cdot\,)\bigr) \in \operatorname{WOF}(\mathbf{q})$. It should be emphasized that Wardrop optimal networks are also generated by different functions, for instance, $\widetilde{\mathbf{L}}(\mathbf{x})=\mathbf{L}(\mathbf{x})+\mathbf{c} \in \operatorname{WOF}(\mathbf{q})$, where
$$
\begin{equation*}
\mathbf{L}(\mathbf{x})= \biggl\langle \frac{x_1}{q_1}\,,\frac{a_{22}}{2} \biggl(\frac{x_2}{q_2}\biggr)^2+\frac{a_{21}}{1} \biggl(\frac{x_2}{q_2}\biggr),\dots,\frac{a_{mm}}{m} \biggl(\frac{x_m}{q_m}\biggr)^m+\cdots+\frac{a_{m1}}{1} \biggl(\frac{x_m}{q_m}\biggr)\biggr\rangle,
\end{equation*}
\notag
$$
$\mathbf{c}=\langle 0,a_{22}/2,\dots,(m-1)a_{mm}/{m}+ \cdots+{2}a_{m3}/{3}+a_{m2}/{2}\rangle$ for $\operatorname{supp}(\mathbf{q})=\mathbf{I}_m$, $\sum_{k=1}^{i} a_{ik}= 1$ and $a_{ik}>0$ for all $i\in\mathbf{I}_m$.
2. Now we present the replicator equation on a Wardrop optimal network for which the Nash equilibrium and the Wardrop optimal flow specify the same flow distribution. Let $\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
$$
\begin{equation*}
L_n((\mathbf{1}/\mathbf{q})\,\,\boldsymbol\cdot\,)=\langle\ell_n((1/q_1)\,\,\boldsymbol\cdot\,),\dots, \ell_n((1/q_m)\,\,\boldsymbol\cdot\,)\rangle\in\operatorname{WOF}(\mathbf{q}),
\end{equation*}
\notag
$$
and let $\ell_n\colon[0,\bar{q}]\to[0,1]$ be a sequence of continuously differentiable and uniformly strictly increasing functions with uniformly bounded Pigouvian taxes
$$
\begin{equation*}
\mu:=\sup\limits_{n\in\mathbb{N}}\,\max\limits_{x\in[0,\bar{q}]}\,\dfrac{d}{dx}(x\ell_n(x))<\infty,
\end{equation*}
\notag
$$
where $\bar{q}:={1}/{\min_{i\in\mathbf{I}_m}{q_i}}$ and $n\in\mathbb{N}$. Let
$$
\begin{equation*}
(\mathcal{R}_n(\mathbf{x}))_k=x_k\biggl[1+\varepsilon\biggl(\ell_n\biggl(\frac{x_k}{q_k}\biggr) -\sum_{i=1}^mx_i\ell_n\biggl(\frac{x_i}{q_i}\biggr)\biggr)\biggr],
\end{equation*}
\notag
$$
where $k\in\mathbf{I}_m$ and $\varepsilon\in(-1,0)$. A flow $\mathbf{x}\in\mathbb{S}^{m-1}$ is called a common Nash equilibrium of the replicator equation if $\langle\mathbf{x}|\varepsilon{L}_n(\mathbf{x}/ \mathbf{q})\rangle \geqslant\langle\mathbf{y}| \varepsilon{L}_n (\mathbf{x}/\mathbf{q})\rangle$ for all $\mathbf{y}\in\mathbb{S}^{m-1}$ and $n\in\mathbb{N}$, where $\langle\mathbf{x}| L_n (\mathbf{x}/\mathbf{q})\rangle:= \sum_{k=1}^m x_k\ell_n(x_k/q_k)$.
Theorem 3. Let $\varepsilon\in(-{1}/{\mu},0)\cap(-1,0)$. Then the following statements hold: (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}$. 
Citation in format AMSBIB
\Bibitem{BagKalSab24} |
|
||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|