А. Г. Багдасарян, А. Калампакас, М. Х. Сабуров, “Динамика уравнений репликатора в Вардроп-оптимальных сетях”, УМН, 79:1(475) (2024), 187–188; Russian Math. Surveys, 79:1 (2024), 176

В этой статье мы вводим и изучаем Вардроп-оптимальные сети, т. е. сети, в которых имеются Вардроп-оптимальные потоки, являющиеся как равновесием по Вардропу, так и системным оптимумом сети. Следует отметить, что Вардроп-оптимальные сети – это единственно возможные сети, для которых цена анархии в точности равна ее минимальному значению, т. е. единице. Мы приводим полную характеризацию (см. теорему 1) такого рода сетей, что впервые полностью решает проблему, поставленную С. Дафермос, для случая параллельных сетей (см. [1]–[3]): для заданной сети охарактеризовать функции стоимости, при которых равновесие по Вардропу совпадает с системным оптимумом сети. Мы также изучаем геометрическую структуру множества всех вектор-функций стоимости маршрутизации, для которых априори заданный поток является Вардроп-оптимальным потоком. Это множество представляет собой выпуклый замкнутый конус, который замкнут относительно операций сложения, умножения, а также суперпозиции с выпуклыми функциями (см. теорему 2). Заметим, что С. Дафермос (см. [1], [2]) приводит лишь один пример мономиальной вектор-функции стоимости, являющейся Вардроп-оптимальной сетью. Нами построен намного более широкий класс вектор-функций – Вардроп-оптимальных сетей (см. теорему 2, (ii)). И наконец, предложен динамический подход к распределению потока на Вардроп-оптимальной сети, основная идея которого заключается в том, что поток на дуге с актуальной стоимостью, меньшей (большей) чем средняя актуальная стоимость сети, будет увеличиваться (уменьшаться). С этой целью рассмотрено уравнение репликатора на Вардроп-оптимальной сети, для которого равновесие по Нэшу, равновесие по Вардропу и системный оптимум определяют одно и то же распределение потока в сети (см. теорему 3, обобщающую основные результаты статьи [4]).

1. Рассмотрим проблему маршрутизации потока в сети из $m$ параллельных дуг $\mathbf{I}_m=\{1,\dots,m\}$, соединяющих фиксированную пару вершин источник-сток. Пусть $\mathbf{x}=(x_1,\dots,x_m)\in \mathbb{R}_{+}^{m}$ – вектор-поток сети ($x_k$ – поток на дуге $k$) такой, что $\|\mathbf{x}\|_1\leqslant 1$. Обозначим $\widetilde{\mathbf{L}}(\mathbf{x}):=\mathbf{L}(\mathbf{x})+\mathbf{c}$ вектор-функцию актуальной стоимости маршрутизации на вектор-потоке $\mathbf{x}$, где $\mathbf{L}(\mathbf{x})=\langle \ell_1(x_1),\dots,\ell_m(x_m)\rangle$ и $\ell_k\colon[0,\infty)\to [0,\infty)$, $k\in\mathbf{I}_m$, является выпуклой, строго возрастающей и непрерывно дифференцируемой функцией, $\mathbf{c}=(c_1,\dots,c_m)$ – вектор-цена сети, $c_k$ – цена маршрутизации по дуге $k$. Пусть $\mathbf{R}=(R,\dots, R)$ – вектор полезности, где $R$ – общая полезность использования дуги.

Вектор-поток $\mathbf{q}=(q_1,\dots,q_m)$ назовем Вардроп-оптимальным потоком, если

$$ \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 $$

Пусть $\mathbb{S}^{m-1}:=\{\mathbf{x}\in \mathbb{R}_{+}^{m}\colon \|\mathbf{x}\|_1=1\}$ – симплекс. Здесь мы приводим характеризацию введенного нами понятия Вардроп-оптимального потока $\mathbf{q}$ при условии $\mathbf{q}\in\mathbb{S}^{m-1}$.

Теорема 1. Вектор-поток $\mathbf{q}=(q_1,\dots,q_m)\in\mathbb{S}^{m-1}$ является Вардроп-оптимальным потоком тогда и только тогда, когда выполнены условия: (i) $\tilde{\ell}_i(q_i)=\tilde{\ell}_j(q_j)$ для всех $i,j\in\mathbf{I}_m$, $q_i>0$ и $q_j>0$; (ii) $q_i\tilde{\ell}'_i(q_i)=q_j\tilde{\ell}'_j(q_j)$ для всех $i,j\in\mathbf{I}_m$, $q_i>0$ и $q_j>0$; (iii) $\tilde{\ell}_i(0)\geqslant \tilde{\ell}_j(q_j)+q_j\tilde{\ell}'_j(q_j)$ для всех $i,j\in\mathbf{I}_m$, $q_i=0$ и $q_j>0$.

Обозначим ${\widetilde{\mathbf{q}}}/{\mathbf{q}}:= ({\widetilde{q}_1}/{q_1},\dots,{\widetilde{q}_m}/{q_m})$, ${0}/{0}:=1$ при $\operatorname{supp}(\widetilde{\mathbf{q}})=\operatorname{supp}(\mathbf{q})$. В частности, ${\mathbf{1}}/{\mathbf{q}}:=({1}/{q_1},\dots,{1}/{q_m})$, где $\mathbf{1}=(1,\dots,1)$ и $\operatorname{supp}(\mathbf{q})=\mathbf{I}_m$. Обозначим $\operatorname{WOF}(\mathbf{q})$ множество всех актуальных вектор-стоимостей, для которых $\mathbf{q}$ есть общий Вардроп-оптимальный поток. Пусть $\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$ и

$$ \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 $$

Теорема 2. Пусть $\varphi,f_i\colon[0,\infty)\to [0,\infty)$ – выпуклые, строго возрастающие и непрерывно дифференцируемые функции, причем $\mathbf{\Phi}(\mathbf{x}):=(\varphi(x_1),\dots,\varphi(x_m))$, $\mathbf{x}\in\mathbb{S}^{m-1}$. Пусть $\mathbf{L}^{(k)}(\,\boldsymbol\cdot\,) \in \operatorname{WOF}(\mathbf{q}^{(k)})$ при $\operatorname{supp}(\mathbf{q}^{(k)})=\operatorname{supp}(\mathbf{q})$, $k\in\mathbf{I}_n$. Тогда: (i) $\operatorname{WOF}(\mathbf{q})$ есть выпуклый конус для любого $\mathbf{q}\in\mathbb{S}^{m-1}$; (ii) $\mathbf{\Phi}(({\mathbf{1}}/{\mathbf{q}}) \,\,\boldsymbol\cdot\,)\in\operatorname{WOF}(\mathbf{q})$ при $\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})$.

Следует особо подчеркнуть, что Вардроп-оптимальные сети порождаются также с помощью разных функций; например, $\widetilde{\mathbf{L}}(\mathbf{x})=\mathbf{L}(\mathbf{x})+\mathbf{c} \in \operatorname{WOF}(\mathbf{q})$, где

$$ \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 $$

2. Предложим уравнение репликатора на Вардроп-оптимальной сети, для которой равновесие по Нэшу и Вардроп-оптимальный поток задают одно и то же распределение потока. Пусть $\mathbf{q}>0$ и $\mathbf{x}/\mathbf{q}:= (x_1/q_1\,,\dots,x_m/q_m)$ для любого $\mathbf{x}\in\mathbb{S}^{m-1}$. Пусть ${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})$ и $\ell_n\colon[0,\bar{q}]\to[0,1]$ есть последовательность выпуклых, непрерывно дифференцируемых и равномерно строго возрастающих функций с равномерно ограниченными тарифами Пигу $\mu:=\sup\limits_{n\in\mathbb{N}}\, \max\limits_{x\in[0,\bar{q}]}\,\dfrac{d}{dx}(x\ell_n(x))<\infty$, где $\bar{q}:={1}/{\min_{i\in\mathbf{I}_m}{q_i}}$, $n\in\mathbb{N}$. Пусть $(\mathcal{R}_n(\mathbf{x}))_k= x_k\bigl[1+\varepsilon\bigl(\ell_n({x_k}/{q_k})- \sum_{i=1}^mx_i\ell_n({x_i}/{q_i})\bigr)\bigr]$, $k\in\mathbf{I}_m$, $\varepsilon\in(-1,0)$. Поток $\mathbf{x}\in\mathbb{S}^{m-1}$ назовем общим равновесием по Нэшу уравнения репликатора, если $\langle\mathbf{x}|\varepsilon{L}_n(\mathbf{x}/ \mathbf{q})\rangle \geqslant\langle\mathbf{y}| \varepsilon{L}_n (\mathbf{x}/\mathbf{q})\rangle$ $\forall\,\mathbf{y}\in\mathbb{S}^{m-1}$, $n\in\mathbb{N}$, где $\langle\mathbf{x}| L_n (\mathbf{x}/\mathbf{q})\rangle:= \sum_{k=1}^m x_k\ell_n(x_k/q_k)$.

Теорема 3. Пусть $\varepsilon\in(-{1}/{\mu},0)\cap(-1,0)$. Тогда: (i) единственное общее равновесие по Нэшу есть только лишь Вардроп-оптимальный поток $\mathbf{q}$; (ii) только лишь Вардроп-оптимальный поток $\mathbf{q}$ является единственной устойчивой общей неподвижной точкой; (iii) любая орбита, лежащая строго внутри симплекса, сходится к Вардроп-оптимальному потоку $\mathbf{q}$.

Образец цитирования: А. Г. Багдасарян, А. Калампакас, М. Х. Сабуров, “Динамика уравнений репликатора в Вардроп-оптимальных сетях”, УМН, 79:1(475) (2024), 187–188; Russian Math. Surveys, 79:1 (2024), 176–178

Цитирование в формате AMSBIB

\RBibitem{BagKalSab24}

\by А.~Г.~Багдасарян, А.~Калампакас, М.~Х.~Сабуров

\paper Динамика уравнений репликатора в~Вардроп-оптимальных сетях

\jour УМН

\yr 2024

\vol 79

\issue 1(475)

\pages 187--188

\mathnet{http://mi.mathnet.ru/rm10165}

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

\mathscinet{https://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}

\transl

\jour Russian Math. Surveys

\yr 2024

\vol 79

\issue 1

\pages 176--178

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

\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}

Список литературы