Russian Mathematical Surveys
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Russian Mathematical Surveys, 2024, Volume 79, Issue 1, Pages 176–178
DOI: https://doi.org/10.4213/rm10165e
(Mi rm10165)
 

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
References:
Received: 30.11.2023
Bibliographic databases:
Document Type: Article
MSC: 90B10, 90C33
Language: English
Original paper language: Russian

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}$.


Bibliography

1. S. C. Dafermos, Traffic assignment and resource allocation in transportation networks, Ph.D. thesis, Johns Hopkins Univ., 1968, 280 pp.
2. S. C. Dafermos and F. T. Sparrow, J. Res. Nat. Bur. Standards Sect. B, 73B:2 (1969), 91–118  crossref  mathscinet  zmath
3. A. Krylatov, V. Zakharov, and T. Tuovinen, Optimization models and methods for equilibrium traffic assignment, Springer Tracts Transp. Traffic, 15, Springer, Cham, 2020, xi+228 pp.  crossref  mathscinet
4. M. Saburov, Russian Math. Surveys, 78:2 (2023), 387–389  mathnet  crossref  mathscinet  zmath

Citation: A. G. Bagdasaryan, A. Kalampakas, M. Kh. Saburov, “Dynamics of replicator equations on Wardrop optimal networks”, Russian Math. Surveys, 79:1 (2024), 176–178
Citation in format AMSBIB
\Bibitem{BagKalSab24}
\by A.~G.~Bagdasaryan, A.~Kalampakas, M.~Kh.~Saburov
\paper Dynamics of replicator equations on Wardrop optimal networks
\jour Russian Math. Surveys
\yr 2024
\vol 79
\issue 1
\pages 176--178
\mathnet{http://mi.mathnet.ru//eng/rm10165}
\crossref{https://doi.org/10.4213/rm10165e}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4774057}
\zmath{https://zbmath.org/?q=an:1544.90046}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2024RuMaS..79..176B}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001292806100005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85206001948}
Linking options:
  • https://www.mathnet.ru/eng/rm10165
  • https://doi.org/10.4213/rm10165e
  • https://www.mathnet.ru/eng/rm/v79/i1/p187
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
    Statistics & downloads:
    Abstract page:343
    Russian version PDF:5
    English version PDF:35
    Russian version HTML:22
    English version HTML:107
    References:25
    First page:24
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024