# Dynamic Tolling for Inducing Socially Optimal Traffic Loads

Chinmay Maheshwari∗,1, Kshitij Kulkarni∗,1, Manxi Wu1, and S. Shankar Sastry1

(Date: October 2021)

###### Abstract.

How to design tolls that induce socially optimal traffic loads with
dynamically arriving travelers who make selfish routing decisions? We propose
a two-timescale discrete-time stochastic dynamics that adaptively adjusts the
toll prices on a parallel link network while accounting for the updates of
traffic loads induced by the incoming and outgoing travelers and their route
choices. The updates of loads and tolls in our dynamics have three key
features: (i) The total demand of incoming and outgoing travelers is
stochastically realized; (ii) Travelers are myopic and selfish in that they
choose routes according to a perturbed best response given the current latency
and tolls on parallel links; (iii) The update of tolls is at a slower
timescale as compared to the the update of loads. We show that the loads and
the tolls eventually concentrate in a neighborhood of the fixed point, which
corresponds to the socially optimal load and toll price. Moreover, the fixed
point load is also a stochastic user equilibrium with respect to the toll
price. Our results are useful for traffic authorities to efficiently manage
traffic loads in response to the arrival and departure of travelers.

* Equal contribution

1 The authors are with the Department of Electrical Engineering and Computer
Sciences, University of California Berkeley, USA. Research supported in part
by the U.S. Office of Naval Research MURI grant N00014-16-1-2710 and by the
NSF Partnership for International Research and Education Excellence (PIRE):
Science of Design for Societal Scale Cyber-Physical Systems, National Science
Foundation award number OISE-1743772.

##  1\. Introduction

Efficient traffic routing is an increasingly important problem as congestion
aggravates on urban transportation networks. Many cities around the world have
implemented congestion pricing (tolling) to regulate the demand of travelers
([20, 11]). Tolling, when properly set in response to real-time traffic
conditions, can effectively alleviate congestion and even induce socially
optimal loads [21, 15].

One challenge of setting tolls is that travelers continuously arrive at and
depart from the network, which creates a dynamic evolvement of traffic loads
in network. Additionally, travelers are selfish in that they prefer to choose
the routes with the minimum cost - travel time cost and the tolls combined. To
design tolling that induces efficient traffic load, we must account for the
dynamics of incoming and outgoing traffic demands and the selfish nature of
travelers’ route choices. In particular, the tolls must be updated in response
to the changing traffic conditions.

We propose a discrete-time stochastic dynamics to capture the joint evolution
of the loads and tolls in a parallel network. In each time step of the
dynamics, non-atomic travelers arrive at the origin of the network, and they
make routing decisions according to a perturbed best response based on the
travel time cost and toll of each link in that step. Additionally, a fraction
of load on each link leaves the network. Both the incoming and outgoing demand
are randomly realized, and are identically and independently distributed
across steps. Therefore, the discrete-time stochastic dynamics of loads forms
a Markov process, which is governed by the total arriving demand, the
stochastic user equilibrium, and the load discharge rate. Furthermore, at each
time step, a traffic authority adjusts the toll on each link by interpolating
between the current toll and a new increment dependent on the marginal cost of
travel time given the load at that step.

In our setting, the dynamics of the toll evolves at a slower time-scale
compared to that of the load dynamics. In practice, fast changing tolls are
undesirable ([8]). This property ensures that the tolls change very slowly,
and thus travelers can view the tolls as static when they make routing
decisions at the arrival.

We show that the loads and tolls in the discrete-time stochastic dynamics
asymptotically concentrate in a neighborhood of a unique fixed point with high
probability. The fixed point load is _socially optimal_ in that it minimizes
the total travel time costs when the incoming and outgoing traffic demands
reach a _steady state_ , and the fixed point toll on each link equals to the
marginal cost. That is, with high probability, our dynamic tolling eventually
induces the socially optimal loads that accounts for the incoming and outgoing
travelers and their selfish routing behavior. Furthermore, we emphasize that
our dynamic tolling is _distributed_ in that the traffic authority only uses
the information of the cost and load on each link to update its toll.

Our technical approach to proving the main result involves: _(i)_ Constructing
a continuous-time deterministic dynamical system associated with the two
timescale discrete-time stochastic dynamics; _(ii)_ Demonstrating that the
flow of the continuous-time dynamical system has a unique fixed point that
corresponds to the socially optimal load and tolls; _(iii)_ Proving that the
unique fixed point of the flow of the continuous time dynamical system is
globally stable. In particular, we apply the theory of two time-scale
stochastic approximation to show that the loads and tolls under the stochastic
dynamics concentrates with high probability in the neighborhood of the fixed
point of the flow of continuous time dynamics constructed in _(i)_ ([2]).
Additionally, our proof in _(ii)_ on the uniqueness and optimality of fixed
point of the flow of continuous time dynamics builds on a variational
inequality, and extends the analysis of stochastic user equilibrium in static
routing games to account for the steady state of the network given the
incoming and outgoing demand ([5]). Furthermore, we show that the continuous
time dynamical system is cooperative, and thus its flow must converge to its
fixed point ([10]).

Our model and results contribute to the rich literature on designing tolling
mechanisms for inducing socially optimal route loads. Classical literature on
static routing games has focused on measuring the inefficiency of selfish
routing by bounding the "price of anarchy", and designing marginal cost
tolling to induce socially optimal route loads ([4, 18, 17]). In static
routing games, optimal tolling does not account for the dynamic arrival and
departure of travelers. The computation of optimal tolls relies on knowledge
of the entire network structure and the equilibrium route flows, which are
challenging to compute.

Dynamic toll pricing has been studied in a variety of settings to account for
the continuous incoming and outgoing traffic demand. The paper [1] analyzed a
discrete-time stochastic dynamics of of non-atomic travelers, and discussed
the impact of tolling on routing strategies. We consider an adaptive
adjustment of tolls using marginal toll pricing. This allows us to analyze the
long-run outcomes of the joint evolution of the route loads and tolls, and
shows that the tolls eventually induce a socially optimal traffic load
associated with the steady state of the network. Additionally, we prove that
the monotonicity condition – the equilibrium routing strategy is monotonic in
tolls (which is an assumption in [1]) – holds for any equilibrium routing
strategy.

Moreover, [7] proposed a continuous-time dynamical system to study socially
optimal tolling when strategic travelers continuously arrive and make selfish
routing decisions. In their model, the incoming and outgoing traffic demands
are equal so that the aggregate load in the network is a constant. In our
setting, both the incoming and outgoing traffic demands are random variables.
Therefore, our fixed point analysis needs to account for the total load at the
steady state of the network. Moreover, [7] assumes that the tolls are adjusted
at a faster time scale than their traveler’s route preferences, while we
assume that the update of tolls is at a slower timescale compared to the
change of routing decisions.

Finally, this article is also related to the literature on learning in routing
games, and learning for tolling with unknown network condition. In particular,
a variety of algorithms have been proposed to study how travelers learn an
equilibrium by repeatedly adjusting their routing decisions based on the
observed travel time in the network (e.g. [6, 13, 12]). Additionally, papers
[8, 16, 14, 22] have analyzed how the traffic authority adaptively updates the
tolls while learning the unknown network condition using crowd-sourced data on
traffic load and time costs.

This article is organized as follows: we introduce the dynamic tolling model
and the discrete time stochastic dynamics in Sec. 2. We present the main
result in Sec. 3, and numerical examples in Sec. 4. We conclude our work in
Sec. 5. We present the key ideas of our prove techniques in the main text, and
include all proofs in the appendix.

### Notations

We denote the set of non-negative real numbers by $\mathbb{R}_{\geqslant 0}$.
For any natural number $R$, we succinctly write $[R]=\\{1,2,\dots,R\\}$. For
any vector $x\in\mathbb{R}^{n}$, we define
$\textsf{diag}(x)\in\mathbb{R}^{n\times n}$ to be a diagonal matrix with its
diagonals filled with entries of $x$.

##  2\. Model

Consider a parallel link network with $R$ links connecting a single source-
destination pair. At each time step $n=1,2,\dots$, a non-atomic traveler
population arrives at the source node, and is routed through links $R$ to the
destination node.

At time step $n$, the traffic load (i.e. amount of travellers) on link
$i\in[R]$ is $X_{i}(n)$. The latency function on any link $i\in[R]$ is a
function of load on the link: $\ell_{i}:\mathbb{R}_{\geqslant
0}\longrightarrow\mathbb{R}_{\geqslant 0}$. We assume that the latency
function is _strictly-increasing_ and _convex_ , which reflect the congestible
nature of links and the fact that the latency increases faster when the load
is higher.

A traffic authority sets toll prices on links, denoted as
$P(n)=\left(P_{i}(n)\right)_{i\in\mathbb{R}}$, where $P_{i}(n)$ is the toll on
link $i$ at step $n$. The _cost function_ on link $i\in[R]$ at step $n$,
denoted $c_{i}(X_{i}(n),P_{i}(n))$, is the sum of the latency function
$\ell_{i}(X_{i}(n))$ and the charged toll price (see Fig. 1):

(2.1) $\displaystyle
c_{i}(X_{i}(n),P_{i}(n)))\coloneqq\ell_{i}(X_{i}(n))+P_{i}(n)$

$\mathcal{S}$$\mathcal{D}$$c_{1}(X_{1}(n),P_{1}(n))$$c_{2}(X_{2}(n),P_{2}(n))$$\dots$$c_{R-1}(X_{R-1}(n),P_{R-1}(n))$$c_{R}(X_{R}(n),P_{R}(n))$
Figure 1. A $R-$link parallel network with source node $\mathcal{S}$,
destination node $\mathcal{D}$, and cost functions at step $n$.

Furthermore, we define $\tilde{c}_{i}(X_{i}(n),P_{i}(n),\nu_{i}(n))\coloneqq
c_{i}(X_{i}(n),P_{i}(n))+\nu_{i}(n)$ to be the randomly realized travel cost
experienced by the travelers, where $\nu_{i}(n)$ is an identically and
independently distributed (i.i.d) random variable with zero mean.

The demand of traffic arriving at the source node at step $n+1$ is a random
variable $\zeta(n+1)$. We assume that $\\{\zeta(n)\\}_{n\in\mathbb{N}}$ are
i.i.d with bounded support $[\underline{$\lambda$},\bar{\lambda}]$ and the
mean $\lambda$ (i.e. $\mathbb{E}[\zeta(n)]=\lambda$ for all $n$). At step
$n+1$, travelers make routing decisions
$F^{\textsf{(in)}}(n+1)=\left(F^{\textsf{(in)}}_{i}(n+1)\right)_{i\in[R]}$
based on the latest cost vector at step $n$, where
$F^{\textsf{(in)}}_{i}(n+1)$ is the demand of travelers who choose link $i$ at
step $n+1$. We assume that $F^{\textsf{(in)}}(n+1)$ is a perturbed best
response defined as follows:

######  Definition 2.1.

(Perturbed Best Response Strategy) At any step $n+1$, the routing strategy
$F^{\textsf{(in)}}_{i}(n+1)$ is _perturbed best response_ if for all
$i\in[R]$,

(2.2) $\displaystyle F^{\textsf{(in)}}_{i}(n+1)\coloneqq\frac{\exp(-\beta
c_{i}(X_{i}(n),P_{i}(n)))}{\sum_{j\in[R]}\exp(-\beta
c_{j}(X_{j}(n),P_{j}(n)))}\zeta(n),$

where $\beta\in[0,\infty)$.

The perturbed best response strategy reflects the myopic nature of travelers
route choices. In particular, $\beta$ is a dispersion parameter that governs
the relative weight of link costs in making routing decisions. If
$\beta\uparrow\infty$, $F^{\textsf{(in)}}_{i}(n+1)$ is a best response
strategy in that travelers only take links with the minimum cost in
$F^{\textsf{(in)}}_{i}(n+1)$. On the other hand, if $\beta\downarrow 0$, then
$F^{\textsf{(in)}}_{i}(n+1)$ assigns the arrival demand uniformly across all
links.

Furthermore, the proportion of load discharged from link $i\in[R]$ at step
$n+1$ is given by the random variable $\xi_{i}(n+1)\in(0,1)$. We assume that
$\\{\xi_{i}(n)\\}_{i\in[R],n\in\mathbb{N}}$ are i.i.d. with bounded support
$[\underline{$\mu$},\bar{\mu}]$ and mean $\mu$ (i.e.
$\mathbb{E}[\xi_{i}(n)]=\mu$ for all $i\in[R]$). Thus the load discharged from
link $i\in[R]$ at step $n+1$ is given by

(2.3) $\displaystyle F^{\textsf{(out)}}_{i}(n+1)\coloneqq
X_{i}(n)\xi_{i}(n+1).$

In each step $n$, the load on each link is updated as follows:

(2.4) $\displaystyle X_{i}(n+1)$
$\displaystyle=X_{i}(n)+F^{\textsf{(in)}}_{i}(n+1)-F^{\textsf{(out)}}_{i}(n+1).$

We note that the stochasticity of the load update arises from the randomness
in the incoming load $F^{\textsf{(in)}}(n+1)$ and the outgoing load
$F^{\textsf{(out)}}(n+1)$. We define

(2.5) $\displaystyle
h_{i}(x_{i},p_{i})\coloneqq\frac{\lambda}{\mu}\frac{\exp(-\beta
c_{i}(x_{i},p_{i}))}{\sum_{j\in[R]}\exp(-\beta c_{j}(x_{j},p_{j}))}.$

where $x,p\in\mathbb{R}^{R}$, and $\lambda$ (resp. $\mu$) is the mean of
incoming (resp. outgoing) load respectively. Using (2.2), (2.3), and (2.5), we
can re-write (2.4) as follows:

(Update-$X$) $\displaystyle X_{i}(n+1)$ $\displaystyle=(1-\mu)X_{i}(n)+\mu
h_{i}(X_{i}(n),P_{i}(n))+\mu M_{i}(n+1),$

where

(2.6) $\displaystyle M_{i}(n+1)$ $\displaystyle\coloneqq
h_{i}(X_{i}(n),P_{i}(n))(\zeta(n+1)-\lambda)$ $\displaystyle\quad-
X_{i}(n)\left(\xi_{i}(n+1)-\mu\right).$

The central authority updates the toll vector $P(n)\in\mathbb{R}^{R}$ at each
step $n$ as follows:

(Update-$P$) $\displaystyle
P_{i}(n+1)=(1-a)P_{i}(n)+aX_{i}(n)\frac{d\ell_{i}(X_{i}(n))}{dx}$

where $i\in[R],n\in\mathbb{N}$ and $a\in[0,1]$ is the step size. That is, the
updated toll is an interpolation between the current toll and the _marginal
cost_ of the link given the current load. We note that the toll is updated in
a distributed manner in that $P_{i}(n+1)$ only depends on the load and cost on
link $i$.

The updates of $(X(n),P(n))$ are jointly governed by the stochastic updates in
(Update-$X$) and (Update-$P$). We assume that tolls are updated at a slower
timescale compared with the load. That is, $a\ll\mu$, where $a$ (resp. $\mu$)
is the step size in (Update-$P$) (resp. (Update-$X$)).

##  3\. Main Results

In Sec. 3.1, we present a continuous-time deterministic dynamical system that
is associated with the discrete-time updates (Update-$X$) and (Update-$P$). We
show that the flow of the continuous-time dynamical system has a unique fixed
point that corresponds to the perturbed socially optimal load (refer
Definition 3.2) and the socially optimal tolling. In Sec. 3.2, we apply the
two timescale stochastic approximation theory to show that
$\left(X(n),P(n)\right)$ in the discrete-time stochastic updates concentrate
on a neighborhood of the fixed point of the flow of the continuous-time
dynamical system. Therefore, our dynamical tolling eventually induces a
perturbed socially optimal load vector with high probability.

###  3.1. Continuous-time dynamical system

We first introduce a _deterministic_ continuous-time dynamical system that
corresponds to (Update-$X$) – (Update-$P$). The time evolution in continuous-
time dynamical system is denoted by $t$ and it is related with the discrete-
time step $n$ as $t=an$, where $a$ is the stepsize in (Update-$P$). We define
$x(t)\in\mathbb{R}^{R}$ as the load vector and $p(t)\in\mathbb{R}^{R}$ as the
toll vector at time $t\in[0,\infty)$ We also define
$\epsilon\coloneqq\frac{a}{\mu}$, where $\mu$ (resp. $a$) is the stepsize of
the discrete-time load update (resp. toll update). Since the toll update
occurs at a slower timescale compared to the load update (i.e. $a\ll\mu$), we
have $\epsilon\ll 1$.

The continuous-time dynamical system is as follows:

(3.1) $\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\frac{1}{\epsilon}\left(h_{i}(x(t),p(t))-x_{i}(t)\right),$
$\displaystyle\dot{p}_{i}(t)$
$\displaystyle=-p_{i}(t)+x_{i}(t)\frac{d\ell_{i}(x_{i}(t))}{dx},\quad\forall\
t\geqslant 0.$

We introduce the following two definitions:

######  Definition 3.1.

(Stochastic user equilibrium) For any fixed $p\in\mathbb{R}^{R}$, a load
vector $\bar{x}^{(\beta)}(p)$111We explictly state the dependence on $p,\beta$
in order relate the definition to later results. is the stochastic user
equilibrium corresponding to the toll vector $p$ and demand
$\frac{\lambda}{\mu}$ if for all $i\in[R]$:

(3.2)
$\displaystyle\bar{x}^{(\beta)}_{i}(p)=\frac{\lambda}{\mu}\frac{\exp(-\beta
c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))}{\sum_{j\in[R]}\exp(-\beta
c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))}.$

Given the stochastic user equilibrium in (3.2), all travelers with total
demand of $\lambda/\mu$ make routing decisions in the network according to a
perturbed best response given the latency functions on links and tolls $p$. We
note that demand $\lambda/\mu$ is the expected value of the total demand in
network at step $n$ when $n\uparrow\infty$. This is because in each step $n$,
the expected value of the total demand in network is
$\sum_{m=1}^{n}(1-\mu)^{n-m}\lambda$, where $(1-\mu)^{n-m}\lambda$ is the
expected incoming demand in step $m$ that remains in the network in step $n$.
Thus, as $n\uparrow\infty$, the expected value of the total demand is
$\lambda/\mu$.

######  Definition 3.2.

(Perturbed socially optimal load) A load vector $\bar{y}^{(\beta)}$ is a
perturbed socially optimal load if $\bar{y}^{(\beta)}$ minimizes the following
convex optimization problem:

(3.3) $\displaystyle\min_{y\in\mathbb{R}^{R}}$
$\displaystyle\quad\sum_{i\in[R]}y_{i}\ell_{i}(y_{i})+\frac{1}{\beta}\sum_{i\in[R]}y_{i}\log(y_{i})$
s.t $\displaystyle\quad\sum_{i\in[R]}y_{i}=\frac{\lambda}{\mu}.$

A commonly used notion to quantify the social objective is the total latency
experienced on the network [17, 8]. Note that (3.3) is an _entropy_
regularized social objective function where the regularization weight depends
on $\beta$. As $\beta\uparrow\infty$, the perturbed socially optimal load
$\bar{y}^{(\beta)}$ becomes the socially optimal flow, which minimizes the
total latency.

The following theorem shows that the flow of the continuous-time dynamical
system has a unique fixed point, and this fixed point corresponds to the
perturbed socially optimal load.

######  Theorem 3.3.

The flow of the continuous-time dynamical system (3.1) has a _unique_ fixed
point $(\bar{x}^{(\beta)}(\bar{p}),\bar{p})$ such that
$\bar{x}^{(\beta)}(\bar{p})$ is a stochastic user equilibrium corresponding to
$\bar{p}$, and

(3.4)
$\displaystyle\bar{p}_{i}=\bar{x}^{(\beta)}_{i}(\bar{p})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}.$

Moreover, $\bar{x}^{(\beta)}(\bar{p})$ is the perturbed socially optimal load.

At $(\bar{x}^{(\beta)}_{i}(\bar{p}),\bar{p})$, the load on the network is a
stochastic user equilibrium given $\bar{p}$ and demand $\lambda/\mu$. This
implies that travelers’ routing strategy, when averaged over all time steps,
is a perturbed best response given $\bar{p}$ and $\lambda/\mu$. Moreover, the
unique price vector $\bar{p}$ is the marginal latency cost, which ensures that
the stochastic user equilibrium $\bar{x}^{(\beta)}(\bar{p})$ is also a
perturbed socially optimal load. As $\beta\to\infty$,
$\bar{x}^{(\beta)}(\bar{p})$ becomes a socially optimal load.

We prove Theorem 3.3 in three parts: Firstly, we show that for any toll vector
$p\in\mathbb{R}^{R}$, the stochastic user equilibrium $\bar{x}^{(\beta)}(p)$
exists and is unique, and can be solved as the optimal solution of a convex
optimization problem (Lemma 3.4). Secondly, we show that there exists a unique
toll vector $\bar{p}$ that satisfies (3.4) (Lemma 3.6). This requires us to
prove that the stochastic user equilibrium $\bar{x}^{(\beta)}(p)$ is monotonic
in $p$ (Lemma 3.5 ). Finally, we conclude the theorem by proving that at
$\bar{p}$ the stochastic user equilibrium $\bar{x}^{(\beta)}(\bar{p})$ is the
perturbed socially optimal load (Lemma 3.7).

We now present the lemmas that are referred in each of the parts above, and
provide the proof ideas of these results. We include the formal proofs in
Appendix B.

_Part 1:_ For any $p$, the load vector $\bar{x}^{(\beta)}(p)$ is the unique
stochastic user equilibrium.

######  Lemma 3.4.

For every $p\in\mathbb{R}^{R}$, $\bar{x}^{(\beta)}(p)$ is the unique optimal
solution to the following convex optimization problem:

(3.5) $\displaystyle\min_{y\in\mathbb{R}^{R}}$
$\displaystyle\quad\sum_{i\in[R]}\int_{0}^{y_{i}}c_{i}(s,p_{i})ds+\frac{1}{\beta}\sum_{i\in[R]}y_{i}\ln{y_{i}},$
s.t $\displaystyle\quad\sum_{i\in[R]}y_{i}=\frac{\lambda}{\mu}$

The proof of Lemma 3.4 follows by verifying that $\bar{x}^{(\beta)}(p)$ (refer
Definition 3.1) satisfies the Karush–Kuhn–Tucker (KKT) conditions
corresponding to (3.5), which is strictly convex problem and therefore has
unique solution. We note that as $\beta\to\infty$, the stochastic user
equilibrium $\bar{x}^{(\beta)}(p)$ becomes a Wardrop equilibrium, where
travelers only take routes with the minimum cost.

_Part 2:_ We first show that the stochastic user equilibrium
$\bar{x}^{(\beta)}(p)$ is monotonic in $p$. This allows us to prove the
existence and uniqueness of $\bar{p}$ given by (3.4).

######  Lemma 3.5.

(Monotonicity of $\bar{x}^{(\beta)}(p)$) For any
$p,p^{\prime}\in\mathbb{R}^{R}$ we have

$\left\langle\bar{x}^{(\beta)}(p)-\bar{x}^{(\beta)}(p^{\prime}),p-p^{\prime}\right\rangle<0.$

Furthermore, $\bar{x}^{(\beta)}(p)$ is a continuously differentiable function.
Consequently, $\frac{\partial\bar{x}^{(\beta)}_{i}(p)}{\partial p_{i}}<0$ for
all $i\in[R]$.

The proof of Lemma 3.5 is proved by using the variational inequalities of
stochastic user equilibrium, which are the first-order optimality condition
associated with (3.5). Moreover, the monotonicity property relies on the fact
that the latency on each link increases in the load.

######  Lemma 3.6.

(Existence and uniqueness of $\bar{p}$) The price vector $\bar{p}$, defined in
(3.4), exists and is unique.

In Lemma 3.6 the existence is proved by using the Brouwer’s fixed point
theorem. We prove uniqueness by contradiction. More formally, let
${p},{p}^{\prime}\in\mathbb{R}^{R}$ be two distinct toll vectors that satisfy
(3.4). Then, from (3.4), we know that for every $i\in[R]$:

$\displaystyle\bar{p}_{i}-\bar{p}_{i}^{\prime}$
$\displaystyle=\left(\bar{x}^{(\beta)}_{i}(p)-\bar{x}^{(\beta)}_{i}(p^{\prime})\right)\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}$
(3.6)
$\displaystyle\quad\quad+\bar{x}^{(\beta)}_{i}(p^{\prime})\left(\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}-\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p^{\prime}))}{dx}\right).$

By multiplying both sides of (3.6) by
$(\bar{x}^{(\beta)}_{i}(p)-\bar{x}^{(\beta)}_{i}(p^{\prime}))$,and summing
over all $i\in[R]$, we have

$\displaystyle\left\langle\bar{x}^{(\beta)}(p)-\bar{x}^{(\beta)}(p^{\prime}),p-p^{\prime}\right\rangle\geqslant
0,$

which contradicts the monotonicity condition proved in Lemma 3.5. Therefore,
the price $\bar{p}$ is unique.

_Part 3:_ Finally, we prove that given $\bar{p}$, $\bar{x}^{(\beta)}(\bar{p})$
is a perturbed socially optimal load.

######  Lemma 3.7.

The load vector $\bar{x}^{(\beta)}(\bar{p})$ is the perturbed socially optimal
load.

We prove Lemma 3.7 by showing that the variational inequality satisfied by the
stochastic user equilibrium at $\bar{p}$ is identical to that satisfied by the
perturbed socially optimal load.

Lemmas 3.4 – 3.7 conclude Theorem 3.3.

###  3.2. Convergence

In this section, we show that $(X_{i}(n),P_{i}(n))$ induced by the discrete-
time stochastic update converges to a neighborhood of
$(\bar{x}^{(\beta)}(\bar{p}),\bar{p})$. The size of the neighborhood depends
on the load update stepsize $\mu$ and the stepsize ratio between the two
dynamics $a/\mu$. That is, the tolls eventually induce a perturbed socially
optimal flow.

######  Theorem 3.8.

(3.7)
$\displaystyle\limsup_{n\longrightarrow+\infty}\mathbb{E}[\|X_{n}-\bar{x}^{(\beta)}(\bar{p})\|^{2}+\|P_{n}-\bar{p}\|^{2}]=\mathcal{O}\left(\mu+\frac{a}{\mu}\right).$

Moreover, for any $\delta>0$:

(3.8)
$\displaystyle\limsup_{n\longrightarrow+\infty}\Pr(\|X_{n}-\bar{x}^{(\beta)}(\bar{p})\|^{2}+\|P_{n}-\bar{p}\|^{2}\geqslant\delta)\leqslant\mathcal{O}\left(\frac{\mu}{\delta}+\frac{a}{\delta\mu}\right).$

In Theorem 3.8, (3.7) provides the neighborhood of the socially optimal load
and tolls, where the discrete-time stochastic updates converge to in
expectation. In particular, as the step size $\mu$ and the stepsize ratio
between the two updates $\epsilon=a/\mu$ decreases (i.e. the discrete-time
step for load update is small, and the toll update is much slower than the
load update), the expected value of the distance between $(X(n),P(n))$ and
$(\bar{x}^{(\beta)}(\bar{p}),\bar{p})$ decreases for $n\to\infty$. Moreover,
by applying the Markov’s inequality, (3.7) also implies that for any
neighborhood of $(\bar{x}^{(\beta)}(\bar{p}),\bar{p})$, $(X(n),P(n))$
converges to that neighborhood with high probability, and this probability
increases as $\mu$ and $\epsilon$ decreases.

To prove Theorem 3.8, we need to prove the following technical lemma:

######  Lemma 3.9.

  * (C1)

For all $i\in[R]$, $\\{M_{i}(n+1)\\}_{n}$ in (2.6) is a martingale difference
sequence with respect to the filtration
$\mathcal{F}_{n}=\sigma(\cup_{i\in[R]}\left(X_{i}(1),\zeta(1),\xi_{i}(1),\dots,X_{i}(n),\zeta(n),\xi_{i}(n)\right))$

  * (C2)

For all $i\in[R]$,
$X_{i}(n)\in\left(0,X_{i}(0)+\frac{\bar{\lambda}}{\underline{$\mu$}}\right)$.
Consequently, $\mathbb{E}[\|X(n)\|^{2}]<+\infty$,
$\mathbb{E}[\|P(n)\|^{2}]<+\infty$.

  * (C3)

There exists $K>0$ such that for any $i\in[R]$ and any $n$,
$\mathbb{E}[|M_{i}(n+1)|^{2}|\mathcal{F}_{n}]\leqslant
K\left(1+\|X_{i}(n)\|^{2}\right)<+\infty.$

  * (C4)

For any $p$, any $\tilde{x}(t):\mathbb{R}_{\geqslant 0}\to\mathbb{R}^{R}$
induced by following continuous-time dynamical system

(3.9) $\displaystyle\dot{\tilde{x}}_{i}(t)$
$\displaystyle=h_{i}(\tilde{x}(t),p)-\tilde{x}_{i}(t),\quad\quad\forall
i\in[R],\forall\ t\geqslant 0,$

satisfies $\lim_{t\to\infty}\tilde{x}(t)=\bar{x}^{(\beta)}(p)$. Futhermore,
$\bar{x}^{(\beta)}(p)$ is Lipschitz.

  * (C5)

Any $\tilde{p}(t):\mathbb{R}_{\geqslant 0}\to\mathbb{R}^{R}$ induced by
following continuous-time dynamical system

(3.10)
$\displaystyle\dot{\tilde{p}}_{i}(t)=-\tilde{p}_{i}(t)+\bar{x}^{(\beta)}_{i}(\tilde{p}(t))\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\tilde{p}(t)))}{dx},\quad
t\geqslant 0,$

satisfies $\lim_{t\to\infty}\tilde{p}(t)=\bar{p}$.

In Lemma 3.9, condition (C1) relies on the fact that both the incoming and
outgoing loads are i.i.d.. Condition (C2) ensures the boundedness of the loads
and the tolls in the discrete-time stochastic updates, and it relies on the
boundedness of $\zeta_{n}$ and $\xi_{n}$. Condition (C3) ensures the
boundedness of the martingale sequence $\\{M_{i}(n+1)\\}_{n}$, and it is built
on condition (C1) and (C2).

In conditions (C4), the continuous-time dynamical system (3.9) is associated
with the discrete-time load update (Update-$X$) when the toll is set as a
constant $p$. That is, due to the fact that toll update is at a slower
timescale compared with the load update ($\epsilon\ll 1$), the continuous-time
dynamical system of load evolves as if the toll is a constant $p$. We prove
condition (C4) by showing that (3.9) is cooperative (see Theorem A.1 in the
appendix). Condition (C4) ensures that the load of the continuous-time
dynamical system converges to the stochastic user equilibrium (Definition 3.1)
with respect to $p$. Recall from Lemma 3.4, the stochastic user equilibrium is
unique.

On the other hand, in condition (C5), (3.10) is associated with (Update-$P$)
when the load – which is updated at a faster timescale – has already converged
to the stochastic user equilibrium with respect to $p(t)$. Similar to
condition (C4), we show that (3.10) is a cooperative dynamical system. The
proof of this condition is built on the monotonicity of stochastic user
equilibrium with respect to the toll (Lemma 3.5) and the uniqueness of
$\bar{p}$ (Lemma 3.6). The proofs of (C1) – (C5) are in Appendix B.

Based on Lemma 3.9, we can apply the theory of two timescale stochastic
approximation with constant stepsizes:

######  Lemma 3.10 ([2]).

Given $\epsilon\ll 1$, (3.7) is satisfied under (C1) – (C5).

Lemmas 3.9 and 3.10 proves (3.7). Additionally, (3.8) can be directly derived
from (3.7) using the Markov’s inequality. Thus, we can conclude Theorem 3.8.

##  4\. Numerical Experiments

In this section we present numerical experiments for the results presented in
§3. We observe that loads and tolls concentrate on a neighborhood of the
socially optimal loads and tolls, and the continuous-time dynamical system
(3.1) closely approximates the discrete-time stochastic updates (Update-$X$) –
(Update-$P$). Our numerical results are consistent with Theorems 3.3 and 3.8.

Consider a network with six parallel links (i.e. $R=6$) with the following
link latency functions:

(4.1) $\displaystyle\ell_{i}(x)=ix^{2}+i,\quad\quad\forall\ i\in[R].$

We set the total time steps of discrete-time stochastic update as $N=2000$,
and the dispersion parameter $\beta=100$. We conduct the four sets of
experiments with the following parameters:

(S1) $\lambda=0.1$, $\mu=0.05$ and $a=0.0015$;

(S2) $\lambda=0.2$, $\mu=0.05$ and $a=0.0015$;

(S3) $\lambda=0.1$, $\mu=0.05$ and $a=0$;

(S4) $\lambda=0.2$, $\mu=0.05$ and $a=0$.

We note that tolls are updated with positive stepsizes in (S1) – (S2), but
remain zero in (S3) – (S4). Also, the mean incoming load of travelers in each
step $\lambda$ is high in (S1) and (S3), and low in (S2) – (S4). In Fig. 2, we
demonstrate the loads and tolls obtained in the discrete-time stochastic
updates (Update-$X$) – (Update-$P$) (represented by dots), and those induced
by the continuous-time dynamical system (3.1) (represented by solid lines) in
(S1) and (S2), respectively. In Fig. 3, we demonstrate the loads in the
discrete-time updates and the socially optimal load for (S3) and (S4). We omit
the figures for tolls since tolls are not updated with step size $a=0$.

We now present the main observations from the numerical study. Firstly, we
observe that in Fig. 2, the trajectories of continuous-time dynamical system
(3.1) closely track the discrete-time stochastic load update. Moreover, we
observe that it takes more time steps for the tolls (refer Fig.2b, Fig.2d) to
converge compared to the loads. This is because tolls are updated at a slower
timescale (i.e. $a\ll\mu$).

Secondly, we show that the repeatedly updated tolls eventually induce the
perturbed socially optimal load in Fig. 2a and 2c. On the other hand, when
tolls are zero (i.e. inactive) in all steps, loads converge to a stochastic
user equilibrium (Fig. 3a and 3b), which is different from the socially
optimal load. This means that links are inefficiently utilized when tolls are
inactive. We observe that the low cost links (links 1, 2, and 3) are
disproportionately over-utilized while the remaining links are underused
especially in the setting with high incoming load $\lambda$ (Fig.3b).

Thirdly, we note that both the perturbed socially optimal load and the
stochastic user equilibrium change with the average incoming load $\lambda$.
In particular, more links are utilized at fixed point with high $\lambda$
(Fig. 2c for (S2) and Fig. 3b for (S4)) compared to that with low $\lambda$
(Fig. 2a for (S2) and Fig. 3a for (S4)).

a Loads in (S1)

b Tolls in (S1)

c Loads in (S2)

d Tolls in (S2)

Figure 2. Loads and Tolls in discrete-time stochastic update (Update-$X$) –
(Update-$P$) (dots) and continuous-time dynamical system (3.1) (solid lines)
in (S1) and (S2).

a Loads in (S3)

b Loads in (S4)

Figure 3. Comparison between loads induced by the discrete-time stochastic
update (Update-$X$)(solid lines) when $P_{n}=0$ and the socially optimal load
(dashed lines) in (S3) and (S4).

##  5\. Conclusions and Future Work

We propose a two timescale discrete-time stochastic dynamics that captures the
joint evolution of loads in parallel network and adaptive adjustment of tolls.
We analyze the properties of fixed points and the convergence of loads and
tolls in this dynamics. We find that under our dynamics, the tolls eventually
induce a socially optimal load with high probability. Our results allow a
central authority to set tolls in networks adaptively and _optimally_ in
response to the dynamic arrival of travelers who myopically make routing
decisions.

One future direction of interest is to extend our results on parallel networks
to general networks. The challenge of setting tolls on general networks is to
account for the fact that travelers may change their route choices at
intermediate nodes of the network due to the change of loads on links during
their trips. Therefore, the toll updates need to account for the myopic route
choice of incoming travelers as well as the change of routing decisions for
travelers in the network.

Another extension of this work is to design toll pricing that only set tolls
on a subset of links instead of the entire network. This extension is of
practical importance since setting high tolls on many links is difficult in
implementation, and is not socially desirable.

##  Appendix A Convergence for cooperative dynamical systems

In this section we review a result from [10] which provides an easily
verifiable requirement on the vector field which ensures convergence to
equilibrium.

A dynamical system

(A.1) $\displaystyle\dot{x}(t)=f(x(t))$

with a $C^{1}-$ function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ is
_cooperative_ if:

  1. (P-i)

for any $i\neq j\in[n]$ and $x\in\mathbb{R}^{n}$ we have $\frac{\partial
f_{i}(x)}{\partial x_{j}}\geqslant 0$;

  2. (P-ii)

the Jacobian matrix $\nabla f(x)$ is irreducible;222A matrix
$A=[A_{ij}]\in\mathbb{R}^{n\times n}$ is irreducible if whenever the set
$\\{1,\dots,n\\}$ is expressed as the union of two disjoint proper subsets
$S,S^{\prime}$, then for every $i\in S$ there exist $j,k\in S^{\prime}$ such
that $A_{ij}\neq 0$ and $A_{ki}\neq 0$.

  3. (P-iii)

for every $i\in[n]$, $f_{i}(0)\geqslant 0$;

  4. (P-iv)

for any $x\in\mathbb{R}_{\geqslant 0}^{n}$ there exists $y>x$ with
$f_{i}(y)<0$ for all $i\in[n]$

######  Theorem A.1 ([10, Theorem 5.1]).

If the dynamical system (A.1) is cooperative (i.e. satisfies the assumptions
(P-i)-(P-iv)), trajectories starting almost everywhere in
$\mathbb{R}_{\geqslant 0}^{n}$ converge to the set $\\{x:f(x)=0\\}$.

##  Appendix B Proofs

###  B.1. Proof of Lemma 3.4

In the subsequent proof we shall show that the following claims hold:

  1. (C-I)

For any $p\in\mathbb{R}^{R}$, the optimizer of (3.5) is unique; call it
$y^{\star}(p)$;

  2. (C-II)

$y^{\star}(p)$ is an optimal solution if and only if it satisfies
$h(y^{\star}(p),p)=y^{\star}$

Note that the above two claims ensure that
$\bar{x}^{(\beta)}(p)=y^{\star}(p)$. The subsequent exposition establishes the
validity of these claims.

To see that (C-I) is true, we note that the feasible set of (3.5) is a compact
convex set. Moreover, from the convexity of $\ell$ it follows that
$\sum_{i\in[R]}\int_{0}^{y_{i}}c_{i}(s,p_{i})ds+\frac{1}{\beta}\sum_{i\in[R]}y_{i}\ln{y_{i}}$
is a strictly convex function in $y$. Strict convexity ensures the uniqueness
of solution of a convex optimization problem on a convex compact set [3].

For (C-II), we now employ KKT conditions of optimality: let
$\delta\in\mathbb{R}$ be the Lagrange multiplier corresponding to the equality
constraint. Define the Lagrangian as follows:

$L(y,\delta,p)\coloneqq\sum_{i\in[R]}\int_{0}^{y_{i}}c_{i}(s,p_{i})ds+\frac{1}{\beta}\sum_{i\in
R}y_{i}\ln{y_{i}}+\delta\left(\sum_{i\in[R]}y_{i}-\frac{\lambda}{\mu}\right)$

The optimal solution $y^{\star}(p)$ and Lagrange multiplier $\delta^{\star}$
satisfy:

  1. (1)

$\nabla_{y}L(y^{\star}(p),\delta^{\star},p)=0$. This gives us
$c_{i}(y_{i}^{\star}(p),p_{i})+\frac{1}{\beta}\left(1+\ln(y_{i}^{\star}(p))\right)+\delta^{\star}=0$,
which can be also written as follows

(B.1) $\displaystyle y_{i}^{\star}(p)=\exp(-\beta\delta^{\star}-1)\exp(-\beta
c_{i}(y_{i}^{\star}(p),p_{i})),\quad\forall\ i\in[R].$

  2. (2)

$\nabla_{\delta}L(y^{\star}(p),\delta^{\star},p)=0$. That is, $\sum_{i\in
R}y_{i}^{\star}(p)=\frac{\lambda}{\mu}.$

From (B.1), summing over $i\in[R]$ on both the sides, we obtain

$\frac{\lambda}{\mu}=\exp(-\beta\delta^{\star}-1){\sum_{i\in[R]}\exp(-\beta
c_{i}(y_{i}^{\star}(p),p_{i}))}$

The above conditions give us that $y^{\star}(p)$ is an optimal solution of
(3.5) if and only if it satisfies

$y_{i}^{\star}(p)=\frac{\lambda}{\mu}\frac{\exp(-\beta
c_{i}(y_{i}^{\star}(p),p_{i}))}{\sum_{i\in[R]}\exp(-\beta
c_{i}(y_{i}^{\star}(p),p_{i}))}=h_{i}(y^{\star}(p),p),\quad\forall\ i\in[R].$

###  B.2. Proof of Lemma 3.5

Before proving Lemma 3.5, we will first state the following result that will
be useful later.

Define
$\textbf{C}(x)\coloneqq\textsf{diag}\left(\left(\frac{d\ell_{i}(x)}{dx}\right)_{i=1}^{R}\right)$
and
$\textbf{M}(x)\coloneqq\textsf{diag}\left(\left(x_{i}\frac{d\ell_{i}(x)}{dx}\right)_{i=1}^{R}\right)$.

######  Lemma B.1.

The function $h(x,p)$ presented in (2.5) is Lipschitz in $x$ and $p$ and
satisfies:

(B.2)
$\displaystyle\nabla_{x}h(\bar{x}^{(\beta)}(p),p)=\frac{\lambda}{\mu}\beta\bar{x}^{(\beta)}(p)\bar{x}^{(\beta)}(p)^{\top}\textbf{C}(\bar{x}^{(\beta)}(p))-\beta\textbf{M}\left(\bar{x}^{(\beta)}(p)\right)$

###### Proof of Lemma B.1.

To show that the function is Lipschitz, it is sufficient to show that the norm
of the gradient of this function is bounded. This is due to the first order
Taylor expansion of the function.

Therefore, for every $i\in[R]$ we first compute $\nabla_{x}h_{i}(x,p)$
entrywise as follows:

(B.3) $\displaystyle\frac{\partial h_{i}(x,p)}{\partial
x_{j}}=\begin{cases}\frac{\lambda}{\mu}\frac{-\beta\frac{d\ell_{i}(x_{i})}{dx}\sum_{k\in[R]}\exp(-\beta
c_{k}(x_{k},p_{k}))\exp(-\beta
c_{i}(x_{i},p_{i}))+\beta\frac{d\ell_{i}(x_{i})}{dx}\left(\exp(-\beta
c_{i}(x_{i},p_{i}))\right)^{2}}{\left(\sum_{k\in[R]}\exp(-\beta
c_{k}(x_{k},p_{k}))\right)^{2}}&\text{if}\ \ i=j;\\\
\frac{\lambda}{\mu}\beta\frac{d\ell_{j}(x_{j})}{dx}\exp(-\beta
c_{i}(x_{i},p_{i}))\frac{\exp(-\beta
c_{j}(x_{j},p_{j}))}{\left(\sum_{k\in[R]}\exp(-\beta
c_{k}(x_{k},p_{k}))\right)^{2}}&\text{otherwise}\end{cases}$

Evaluating the above derivative at $\bar{x}^{(\beta)}(p)$

(B.4) $\displaystyle\frac{\partial h_{i}(\bar{x}^{(\beta)}(p),p)}{\partial
x_{j}}=\begin{cases}\beta\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}\left(-\bar{x}^{(\beta)}_{i}(p)+\frac{\mu}{\lambda}\left(\bar{x}^{(\beta)}_{i}(p)\right)^{2}\right)&\text{if}\
\ i=j;\\\
\frac{\mu}{\lambda}\beta\frac{d\ell_{j}(\bar{x}^{(\beta)}_{j}(p))}{dx}\bar{x}^{(\beta)}_{i}(p)\bar{x}^{(\beta)}_{j}(p)&\text{otherwise}\end{cases}$

To state it concisely:

(B.5)
$\displaystyle\nabla_{x}h(\bar{x}^{(\beta)}(p),p)=\frac{\lambda}{\mu}\beta\bar{x}^{(\beta)}(p)\bar{x}^{(\beta)}(p)^{\top}\textbf{C}(\bar{x}^{(\beta)}(p))-\beta\textbf{M}\left(\bar{x}^{(\beta)}(p)\right)$

Similarly,

(B.6) $\displaystyle\frac{\partial h_{i}(x,p)}{\partial
p_{j}}=\begin{cases}\frac{\lambda}{\mu}\frac{-\beta\sum_{k\in[R]}\exp(-\beta
c_{k}(x_{k},p_{k}))\exp(-\beta c_{i}(x_{i},p_{i}))+\beta\left(\exp(-\beta
c_{i}(x_{i},p_{i}))\right)^{2}}{\left(\sum_{k\in[R]}\exp(-\beta
c_{k}(x_{k},p_{k}))\right)^{2}}&\text{if}\ \ i=j;\\\
\frac{\lambda}{\mu}\beta\exp(-\beta c_{i}(x_{i},p_{i}))\frac{\exp(-\beta
c_{j}(x_{j},p_{j}))}{\left(\sum_{k\in[R]}\exp(-\beta
c_{k}(x_{k},p_{k}))\right)^{2}}&\text{otherwise}\end{cases}$

To conclude the proof we observe that on a bounded domain the derivative in
(B.3) and (B.6) are bounded. ∎

####  B.2.1. Proof of Lemma 3.5

Recall from the proof of Lemma 3.4 ((C-II) to be precise) that for any
$p\in\mathbb{R}^{R}$, $\bar{x}^{(\beta)}(p)$ is a solution to the optimization
problem (3.5). Let the feasible set in the optimization problem (3.5) be
denoted by $F$. Using first order conditions for constrained optimization we
obtain the variational inequality:

(B.7)
$\displaystyle\sum_{i\in[R]}\left(c_{i}\left(\bar{x}^{(\beta)}_{i}(p),p\right)+\frac{1}{\beta}\left(\ln\left(\bar{x}^{(\beta)}_{i}(p)\right)+1\right)\right)\left(x_{i}-\bar{x}^{(\beta)}_{i}(p)\right)\geqslant
0\quad\forall x\in F.$

Similarly writing the above condition for $p^{\prime}$, we obtain

(B.8)
$\displaystyle\sum_{i\in[R]}\left(c_{i}\left(\bar{x}^{(\beta)}_{i}(p^{\prime}),p^{\prime}\right)+\frac{1}{\beta}\left(\ln\left(\bar{x}^{(\beta)}_{i}(p^{\prime})\right)+1\right)\right)\left(y_{i}-\bar{x}^{(\beta)}_{i}(p^{\prime})\right)\geqslant
0\quad\forall y\in F.$

Choosing $x=\bar{x}^{(\beta)}(p^{\prime})$ in (B.7) and
$y=\bar{x}^{(\beta)}(p)$ in (B.8) and adding the two equations we obtain

$\displaystyle\sum_{i\in[R]}\left(c_{i}(\bar{x}^{(\beta)}_{i}(p),p)-c_{i}(\bar{x}^{(\beta)}_{i}(p^{\prime}),p^{\prime})\right)\left(\bar{x}^{(\beta)}_{i}(p^{\prime})-\bar{x}^{(\beta)}_{i}(p)\right)$
$\displaystyle\quad\quad+\sum_{i\in[R]}\left(\frac{1}{\beta}\ln(\bar{x}^{(\beta)}_{i}(p))-\ln(\bar{x}^{(\beta)}_{i}(p^{\prime}))\right)\left(\bar{x}^{(\beta)}_{i}(p^{\prime})-\bar{x}^{(\beta)}_{i}(p)\right)\geqslant
0.$

From the fact that prices enter additively, we have

$\displaystyle\sum_{i\in[R]}\left(\ell_{i}(\bar{x}^{(\beta)}_{i}(p))-\ell_{i}(\bar{x}^{(\beta)}_{i}(p^{\prime}))\right)\left(\bar{x}^{(\beta)}_{i}(p^{\prime})-\bar{x}^{(\beta)}_{i}(p)\right)$
$\displaystyle\quad\quad+\sum_{i\in[R]}\left(p_{i}-p_{i}^{\prime}+\frac{1}{\beta}\ln(\bar{x}^{(\beta)}_{i}(p))-\ln(\bar{x}^{(\beta)}_{i}(p^{\prime}))\right)\left(\bar{x}^{(\beta)}_{i}(p^{\prime})-\bar{x}^{(\beta)}_{i}(p)\right)\geqslant
0.$

This gives

$\displaystyle\left\langle\bar{x}^{(\beta)}(p)-\bar{x}^{(\beta)}(p^{\prime}),p-p^{\prime}\right\rangle$
$\displaystyle\leqslant\left\langle\ell(\bar{x}^{(\beta)}(p))-\ell(\bar{x}^{(\beta)}(p^{\prime})),\bar{x}^{(\beta)}(p^{\prime})-\bar{x}^{(\beta)}(p)\right\rangle$
$\displaystyle\quad+\frac{1}{\beta}\left\langle\ln(\bar{x}^{(\beta)}(p))-\ln(\bar{x}^{(\beta)}(p^{\prime})),\bar{x}^{(\beta)}(p^{\prime})-\bar{x}^{(\beta)}(p)\right\rangle$
$\displaystyle<0,$

where the last inequality follows due to the monotonicity of the cost function
and natural logarithm.

Next, we show that $\bar{x}^{(\beta)}(p)$ is a differentiable function of $p$.
Recall the notation
$\textbf{C}(x)\coloneqq\textsf{diag}\left(\left(\frac{d\ell_{i}(x)}{dx}\right)_{i=1}^{R}\right)$
and
$\textbf{M}(x)\coloneqq\textsf{diag}\left(\left(x_{i}\frac{d\ell_{i}(x)}{dx}\right)_{i=1}^{R}\right)$.

To show the differentiability of $\bar{x}^{(\beta)}(p)$ with respect to $p$,
we invoke the implicit function theorem for the map $g(x,p)=x-h(x,p)$. Note
that for any fixed $p$, $\bar{x}^{(\beta)}(p)$ is the zero of $g(\cdot,p)$. To
satisfy the hypothesis for the implicit function theorem, for any $p$ we
compute the Jacobian of the function $g(x,p)$ with respect to $x$ and evaluate
it at $\bar{x}^{(\beta)}(p)$. Using Lemma B.1 the Jacobian is given by:

$\displaystyle\nabla_{x}g(\bar{x}^{(\beta)}(p),p)$
$\displaystyle=I-\nabla_{x}h(\bar{x}^{(\beta)}(p),p)$
$\displaystyle=I-\frac{\mu}{\lambda}\beta\bar{x}^{(\beta)}(p)\bar{x}^{(\beta)}(p)^{\top}\textbf{C}(\bar{x}^{(\beta)}(p))+\beta\textbf{M}\left(\bar{x}^{(\beta)}(p)\right)$
$\displaystyle=\left(\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)-\beta v\mathbbm{1}^{\top}\right)\textbf{M}(\bar{x}^{(\beta)}(p))$

where $v\coloneqq\frac{\mu}{\lambda}\bar{x}^{(\beta)}(p)$. Note that from
(3.2) we have $\mathbbm{1}^{\top}v=1$. We claim that
$\det(\nabla_{x}g(\bar{x}^{(\beta)}(p),p))\neq 0$. Indeed,

$\displaystyle\det(\nabla_{x}g(\bar{x}^{(\beta)}(p),p))$
$\displaystyle=\det\left(\textbf{M}(\bar{x}^{(\beta)}(p)\right)\det\left(\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)-\beta v\mathbbm{1}^{\top}\right)$
$\displaystyle=\det\left(\textbf{M}(\bar{x}^{(\beta)}(p)\right)\cdot\det\left(I-\beta
v\mathbbm{1}^{\top}\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)^{-1}\right)$
$\displaystyle\quad\quad\cdot\det\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)^{-1}$

It is sufficient to show that $\det\left(I-\beta
v\mathbbm{1}^{\top}\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)^{-1}\right)\neq 0$. Using the Sherman-Morrison formula [9] it is
necessary and sufficient to show that
$\beta\mathbbm{1}^{\top}\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)^{-1}v\neq 1$.

We show it by contradiction. Suppose
$\beta\mathbbm{1}^{\top}\left(\textbf{M}^{-1}(\bar{x}^{(\beta)}(p))+\beta
I\right)^{-1}v=1$. Then

$\displaystyle\implies\quad\sum_{i=1}^{R}v_{i}\frac{\beta}{\frac{1}{m_{i}}+\beta}=1$
$\displaystyle\implies\quad\sum_{i=1}^{R}v_{i}\frac{\beta}{\frac{1}{m_{i}}+\beta}=\sum_{i=1}^{R}v_{i}$
$\displaystyle\implies\sum_{i=1}^{R}v_{i}\frac{\frac{1}{m_{i}}}{\beta+\frac{1}{m_{i}}}=0$

This is not possible as the terms on the left hand side are all positive.

The claim that $\frac{\partial\bar{x}^{(\beta)}_{i}(p)}{\partial p_{i}}<0$
also follows from the monotonicity of $\bar{x}^{(\beta)}(p)$. Indeed, if we
choose two price profiles that differ only at one index then the monotonicity
property of $\bar{x}^{(\beta)}(p)$ ensures
$\frac{\partial\bar{x}^{(\beta)}_{i}(p)}{\partial p_{i}}<0$. This completes
the proof.

###  B.3. Proof of Lemma 3.6

We shall first show the existence and then prove the uniqueness of $\bar{p}$.

For any $p\in\mathbb{R}^{R},i\in[R]$, define
$z_{i}(p)=\bar{x}^{(\beta)}(p)\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}$.
The equilibrium price $\bar{p}$ is then solution to the fixed point equation
$p=z(p)$ where $z(p)=[z_{i}(p)]_{i\in[R]}$. Define a set
$K=\\{y\in\mathbb{R}^{R}:y\geqslant
0,\|y\|_{1}\leqslant\frac{\lambda}{\mu}\max_{i\in[R]}\frac{dc_{i}\left(\frac{\lambda}{\mu}\right)}{dx}\\}$.
Observe that $z(\cdot)$ maps the convex compact set $K$ to itself. Therefore,
Brouwer’s fixed point theorem [19] guarantees the existence of fixed point
$\bar{p}$.

Now, we prove the uniqueness of the fixed point $\bar{p}$ satisfying (3.4). We
shall prove this via a contradiction argument. Assume that there are two
distinct price profiles $\bar{p},\bar{p}^{\prime}\in\mathbb{R}^{R}$ that both
satisfy the fixed point equation (3.4), therefore for every $i\in[R]$:

$\displaystyle\bar{p}_{i}$
$\displaystyle=\bar{x}^{(\beta)}_{i}(\bar{p})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}$
$\displaystyle\bar{p}_{i}^{\prime}$
$\displaystyle=\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))}{dx}$

Taking the difference we get

$\displaystyle\bar{p}_{i}-\bar{p}_{i}^{\prime}$
$\displaystyle=\bar{x}^{(\beta)}_{i}(\bar{p})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))}{dx},$
$\displaystyle=\bar{x}^{(\beta)}_{i}(\bar{p})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}$
$\displaystyle\quad\quad\quad+\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))}{dx},$
$\displaystyle=\left(\bar{x}^{(\beta)}_{i}(\bar{p})-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\right)\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}$
$\displaystyle\quad\quad\quad+\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\left(\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}-\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))}{dx}\right),$

for every $i\in[R]$. Multiplying
$(\bar{x}^{(\beta)}_{i}(\bar{p})-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))$ in
the preceding equation we obtain

(B.9)
$\displaystyle(\bar{x}^{(\beta)}_{i}(\bar{p})-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))(\bar{p}_{i}-\bar{p}_{i}^{\prime})=\left(\bar{x}^{(\beta)}_{i}(\bar{p})-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\right)^{2}\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}$
$\displaystyle\quad\quad\quad+\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})\left(\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}-\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}))}{dx}\right)(\bar{x}^{(\beta)}_{i}(\bar{p})-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime})),$

for every $i\in[R]$. Convexity of the edge cost function ensures that right
hand side of (LABEL:eq:_pUniquenessContradiction) is always non-negative for
every $i\in[R]$. Summing over $i\in[R]$ and using Lemma 3.5 we obtain:

$\displaystyle
0>\left\langle\bar{x}^{(\beta)}_{i}(\bar{p})-\bar{x}^{(\beta)}_{i}(\bar{p}^{\prime}),\bar{p}-\bar{p}^{\prime}\right\rangle\geqslant
0.$

which contradicts our original hypothesis that there are two distinct price
profiles satisfying (3.4).

###  B.4. Proof of Lemma 3.7

Note that for any $i\in[R]$

(B.10)
$\displaystyle\bar{p}_{i}=\bar{x}^{(\beta)}_{i}(\bar{p})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))}{dx}$

Let

$\displaystyle x^{\star}=\operatorname*{arg\,min}_{y\in
F}\left(\sum_{i\in[R]}y_{i}\ell_{i}(y_{i})+\frac{1}{\beta}\sum_{i\in[R]}y_{i}\log(y_{i})\right),$

where $F=\\{y:\sum_{i\in[R]}y_{i}=\frac{\lambda}{\mu}\\}$ is the feasible set.
We claim that $x^{\star}=\bar{x}^{(\beta)}(\bar{p})$.

To show this claim, we first note that the above problem is a strictly convex
optimization problem. The necessary and sufficient conditions for constrained
optimality ensures that for any $y\in F$:

(B.11)
$\displaystyle\sum_{i\in[R]}\left(\ell_{i}(x^{\star}_{i})+x_{i}^{\star}\frac{d\ell_{i}(x_{i}^{\star})}{dx}+\frac{1}{\beta}\left(1+\log(x_{i}^{\star})\right)\right)\left(y_{i}-x_{i}^{\star}\right)\geqslant
0.$

Now recall that $\bar{x}^{(\beta)}(\bar{p})$ satisfies

$\displaystyle\bar{x}^{(\beta)}(\bar{p})=\operatorname*{arg\,min}_{y\in
F}\sum_{i\in[R]}\int_{0}^{y_{i}}\left(\ell_{i}(z)+\bar{p}_{i}\right)\textsf{d}z+\frac{1}{\beta}\sum_{i\in[R]}y_{i}\log(y_{i}).$

Note that we have already noted in proof of Lemma 3.4 that the above
optimization problem is strictly convex. The constrained optimality conditions
ensure that for any $y\in F$:

(B.12)
$\displaystyle\sum_{i\in[R]}\left(\ell_{i}(\bar{x}^{(\beta)}_{i}(\bar{p}))+\bar{p}_{i}+\frac{1}{\beta}\left(1+\log(\bar{x}^{(\beta)}_{i}(\bar{p}))\right)\right)\left(y_{i}-\bar{x}^{(\beta)}_{i}(\bar{p})\right)\geqslant
0.$

Note that using (B.10) in (B.12) we obtain that for any $y\in F$:

(B.13)
$\displaystyle\sum_{i\in[R]}\left(\ell_{i}(\bar{x})+\bar{x}_{i}\frac{d\ell_{i}(\bar{x}_{i})}{dx}+\frac{1}{\beta}\left(1+\log(\bar{x}_{i})\right)\right)\left(y_{i}-\bar{x}_{i}\right)\geqslant
0,$

where we have used $\bar{x}=\bar{x}^{(\beta)}(\bar{p})$ to simplify the
expression. Comparing expression (B.11) and (B.13) we conclude that
$x^{\star}=\bar{x}^{(\beta)}(\bar{p})$. This concludes the proof.

###  B.5. Proof of Lemma 3.9

We prove the claims in the lemma sequentially.

Proof of (C1): Using the independence of sequence $\zeta(n),\xi_{i}(n)$ we see
that the conditional expection of $M_{i}(n+1)$ conditioned on the filtration
$\mathcal{F}_{n}$ is zero. That is,

$\displaystyle\mathbb{E}[M_{i}(n+1)|\mathcal{F}_{n}]=h_{i}(X_{i}(n),P_{i}(n))\left(\mathbb{E}[\zeta(n+1)]-\lambda\right)-X_{i}(n)\left(\mathbb{E}[\xi_{i}(n+1)-\mu]\right)=0.$

Proof of (C2): Recall that we assume that the incoming loads and outgoing
fraction have finite support. That is, for every $i\in[R]$ and $n$ we have
$\zeta(n)\in[\underline{$\lambda$},\bar{\lambda}]\subset(0,\infty)$ and
$\xi_{i}(n)\in[\underline{$\mu$},\bar{\mu}]\subset(0,1)$. Note that
$X_{i}(0)\geqslant 0$ for all $i\in[R]$ as it is impractical to have negative
load on the network; therefore our update reflects the physical constraints of
the network. Under this assumption, the discrete-time stochastic update (2.4)
can be written as

$\displaystyle X_{i}(n+1)$
$\displaystyle=(1-\xi(n+1))X_{i}(n)+\frac{\exp(-\beta
c_{i}(X_{i}(n),P_{i}(n)))}{\sum_{j\in[R]}\exp(-\beta
c_{j}(X_{j}(n),P_{j}(n)))}\zeta(n),$
$\displaystyle\leqslant(1-\underline{$\mu$})X_{i}(n)+\zeta(n),$
$\displaystyle\leqslant(1-\underline{$\mu$})X_{i}(n)+\bar{\lambda},$
$\displaystyle\leqslant(1-\underline{$\mu$})^{n}X_{i}(0)+\frac{\bar{\lambda}}{\underline{$\mu$}}.$

The preceding inequalities establish that
$\mathbb{E}[\|X_{i}(n)\|^{2}]<+\infty$. Consequently, it also ensure that
$\mathbb{E}\left[X_{i}(n)\frac{d\ell_{i}(n)}{dx}\right]<+\infty$ and is
independent of $n$, which in turn, from (Update-$P$) leads to
$\mathbb{E}[\|P_{i}(n)\|^{2}]<+\infty$.

Proof of (C3): We see that:

$\displaystyle\mathbb{E}[|M_{i}(n+1)|^{2}|\mathcal{F}_{n}]$
$\displaystyle=\mathbb{E}[|h_{i}(X_{i}(n),P_{i}(n))(\zeta(n+1)-\lambda)-X_{i}(n)\left(\xi_{i}(n+1)-\mu\right)|^{2}|\mathcal{F}_{n}]$
$\displaystyle\leqslant\mathbb{E}[2|h_{i}(X_{i}(n),P_{i}(n))(\zeta(n+1)-\lambda)|^{2}+2|X_{i}(n)\left(\xi_{i}(n+1)-\mu\right)|^{2}|\mathcal{F}_{n}]$
$\displaystyle\leqslant\mathbb{E}[2\frac{\lambda}{\mu}|(\zeta(n+1)-\lambda)|^{2}+2|X_{i}(n)\left(\xi_{i}(n+1)-\mu\right)|^{2}|\mathcal{F}_{n}]$
$\displaystyle\leqslant K_{1}+K_{2}\|X_{i}(n)\|^{2}$ $\displaystyle\leqslant
K\left(1+|X_{i}(n)|^{2}\right)<+\infty$

where $K_{1}=\frac{2\lambda}{\mu}|\bar{\lambda}-\underline{$\lambda$}|^{2}$,
$K_{2}=2|\bar{\mu}-\underline{$\mu$}|^{2}$ and $K=\max(K_{1},K_{2})$. To
obtain the preceding bound we used
$h_{i}(X_{i}(n),P_{i}(n))\leqslant\frac{\lambda}{\mu}$.

Proof of (C4): To prove this result we shall use Theorem A.1. For that purpose
we need to check conditions Theorem A.1(P-i)-(P-iv).

The condition (P-i) is satisfied if we show that $\frac{\partial
h_{i}(x,p)}{\partial x_{j}}\geqslant 0$. Indeed, by definition

$\displaystyle\frac{\partial h_{i}(x,p)}{\partial
x_{j}}=\frac{\lambda}{\mu}\exp(-\beta
c_{i}(x_{i},p_{i}))\frac{\beta\exp(-\beta c_{j}(x_{j},p_{j}))\frac{\partial
c_{j}(x_{j},p_{j})}{\partial x_{j}}}{\left(\sum_{j\in[R]}\exp\left(-\beta
c_{j}(x_{j},p_{j})\right)\right)^{2}}>0.$

Furthermore, note that condition (P-ii) is also satisfied because the Jacobian
matrix has all the off-diagonal terms positive and is therefore irreducible.
Moreover, it follows from (2.5) that for any $x,p\in\mathbb{R}^{R}$ ,
$h_{i}(x,p)\in\left(0,\frac{\lambda}{\mu}\right)$ and therefore (P-iii)-(P-iv)
are also satisfied. This completes the proof.

Proof of (C5): We shall now show that (3.10) satisfies conditions (P-i)-(P-iv)
in Theorem A.1. This ensures global convergence to the equilibrium set which
is guaranteed to be singleton by Lemma 3.6. For better presentation, for any
$i,j\in[R]$, we denote the derivative of $\bar{x}^{(\beta)}_{i}(p)$ with
respect to $p_{j}$ by $\nabla_{j}\bar{x}^{(\beta)}(p)$333 Note that in Lemma
3.5, we established that $\bar{x}^{(\beta)}(p)$ is continuously
differentiable. Using (3.2) for any $i\neq j$ we have

(B.14) $\displaystyle\exp(-\beta
c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))\bar{x}^{(\beta)}_{i}(p)=\exp(-\beta
c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))\bar{x}^{(\beta)}_{j}(p)$

Taking derivative of the above equation with respect to $p_{k}$ for $k\neq
i\neq j$:

$\displaystyle\exp(-\beta
c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))\nabla_{k}\bar{x}^{(\beta)}_{i}(p)$
$\displaystyle\quad+\bar{x}^{(\beta)}_{i}(p)\exp(-\beta
c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))(-\beta\nabla_{x}c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j})\nabla_{k}\bar{x}^{(\beta)}_{j}(p))$
$\displaystyle=\exp(-\beta
c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))\nabla_{k}\bar{x}^{(\beta)}_{j}(p)$
$\displaystyle\quad+\bar{x}^{(\beta)}_{j}(p)\exp(-\beta
c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))(-\beta\nabla_{x}c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i})\nabla_{k}\bar{x}^{(\beta)}_{i}(p)).$

Collecting similar terms together we get

$\displaystyle\nabla_{k}\bar{x}^{(\beta)}_{i}(p)\left(\exp(-\beta
c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))\right)$
$\displaystyle\quad+\nabla_{k}\bar{x}^{(\beta)}_{i}(p)\left(\bar{x}^{(\beta)}_{j}(p)\exp(-\beta
c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))(\beta\nabla_{x}c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))\right)$
$\displaystyle=\nabla_{k}\bar{x}^{(\beta)}_{j}(p)\left(\exp(-\beta
c_{i}(\bar{x}^{(\beta)}_{i}(p),p_{i}))\right)$
$\displaystyle\quad+\nabla_{k}\bar{x}^{(\beta)}_{j}(p)\left(\bar{x}^{(\beta)}_{i}(p)\exp(-\beta
c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))(\beta\nabla_{x}c_{j}(\bar{x}^{(\beta)}_{j}(p),p_{j}))\right).$

This implies for $i\neq j\neq k$ and for any $p\in\mathbb{R}^{R}$ we have

(B.15)
$\displaystyle\nabla_{k}\bar{x}^{(\beta)}_{i}(p)\cdot\nabla_{k}\bar{x}^{(\beta)}_{j}(p)>0.$

Moreover, by definition of fixed point in (3.2) we have the constraint that

$\sum_{l\in[R]}\bar{x}^{(\beta)}_{l}(p)=\frac{\lambda}{\mu}.$

Taking derivative with respect to $p_{k}$ of the above equation we obtain

(B.16) $\displaystyle\sum_{l\neq
k}\nabla_{k}\bar{x}^{(\beta)}_{l}(p)=-\nabla_{k}\bar{x}^{(\beta)}_{k}(p)>0,$

where the last inequality follows from Lemma 3.5. Equation (B.16) in
conjunction with (B.15) implies that $\nabla_{k}\bar{x}^{(\beta)}_{i}(p)>0$
forall $i\neq k$. This ensures satisfaction of (P-i)-(P-ii). The requirement
(P-iii)-(P-iv) is also satisfied as for any $p\in\mathbb{R}^{R}$,
$\bar{x}^{(\beta)}(p)\in\left(0,\frac{\lambda}{\mu}\right)$. This completes
the proof.

###  B.6. Proof of Lemma 3.10

Note that to invoke the results from two timescale stochastic approximation
theory [2], in addition to Lemma 3.9 we also need to ensure the following

  1. (i)

the function $\bar{x}^{(\beta)}(p)$ is Lipschitz;

  2. (ii)

the function $g(x,p)\coloneqq h(x,p)-x$, which is the vector field in (3.9),
is Lipschitz;

  3. (iii)

the function
$r_{i}(p)\coloneqq\bar{x}^{(\beta)}_{i}(p)\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}-p_{i}$,
which is the vector field in (3.10), is Lipschitz for all $i\in[R]$.

If the above conditions hold, then [2, Chapter 9] ensures that Theorem 3.3
hold.

Note that (i) holds due the fact that $\bar{x}^{(\beta)}(p)\in(0,\lambda/\mu)$
and Lemma 3.5 where we established that it is continuously differentiable.
Moreover, (ii) holds due to Lemma B.1. At last, to show (iii) we note that for
any $p,p^{\prime}\in\mathbb{R}^{R}$ and $i\in[R]$:

$\displaystyle\|r_{i}(p)-r_{i}(p^{\prime})\|=\big{\|}\bar{x}^{(\beta)}_{i}(p)\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}-\bar{x}^{(\beta)}_{i}(p^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p^{\prime}))}{dx}\big{\|}$
$\displaystyle\leqslant\big{\|}\bar{x}^{(\beta)}_{i}(p)\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}-\bar{x}^{(\beta)}_{i}(p^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}\big{\|}+\big{\|}\bar{x}^{(\beta)}_{i}(p^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}-\bar{x}^{(\beta)}_{i}(p^{\prime})\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p^{\prime}))}{dx}\big{\|}$
$\displaystyle\leqslant\big{|}\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}\big{|}\|\bar{x}^{(\beta)}_{i}(p)-\bar{x}^{(\beta)}_{i}(p^{\prime})\|+|\bar{x}^{(\beta)}_{i}(p^{\prime})|\big{\|}\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p))}{dx}-\frac{d\ell_{i}(\bar{x}^{(\beta)}_{i}(p^{\prime}))}{dx}\big{\|}$
$\displaystyle\leqslant
K_{1}\bar{L}\|p-p^{\prime}\|+K_{2}\tilde{L}\|p-p^{\prime}\|,$

where
$K_{1}=\max_{i\in[R],x\in[0,\lambda/\mu]}\big{|}\frac{d\ell_{i}(x)}{dx}\big{|}$,
$\bar{L}$ is the Lipschitz constant for $\bar{x}^{(\beta)}(\cdot)$,
$K_{2}=\lambda/\mu\bar{L}$ and $\tilde{L}$ is the Lipschitz constant for
$\frac{d\ell_{i}(x)}{dx}$ when $x\in[0,\lambda/\mu]$.

## References

  * [1] Vivek S Borkar.  Cooperative dynamics and wardrop equilibria.  Systems & control letters, 58(2):91–93, 2009.
  * [2] Vivek S Borkar.  Stochastic approximation: a dynamical systems viewpoint, volume 48.  Springer, 2009.
  * [3] Stephen P Boyd and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [4] George Christodoulou and Elias Koutsoupias.  The price of anarchy of finite congestion games.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 67–73, 2005.
  * [5] Roberto Cominetti, Francisco Facchinei, and Jean B Lasserre.  Modern Optimization Modelling Techniques.  Springer Science & Business Media, 2012.
  * [6] Roberto Cominetti, Emerson Melo, and Sylvain Sorin.  A payoff-based learning procedure and its application to traffic games.  Games and Economic Behavior, 70(1):71–83, 2010.
  * [7] Giacomo Como and Rosario Maggistro.  Distributed dynamic pricing of multiscale transportation networks.  IEEE Transactions on Automatic Control, 2021.
  * [8] Farhad Farokhi and Karl H Johansson.  A piecewise-constant congestion taxing policy for repeated routing games.  Transportation Research Part B: Methodological, 78:123–143, 2015\.
  * [9] J. E. Gentle.  Matrix Algebra, volume 10.  Springer, 2007.
  * [10] Morris W Hirsch.  Systems of differential equations that are competitive or cooperative ii: Convergence almost everywhere.  SIAM Journal on Mathematical Analysis, 16(3):423–439, 1985.
  * [11] Soumya Karlamangla.  Why evening rush hour feels so much worse now.  New York Times, 2021.  Published on August 11, 2021. Available at https://www.nytimes.com/2021/08/11/us/ca-rush-hour-traffic.html.
  * [12] Robert Kleinberg, Georgios Piliouras, and Éva Tardos.  Multiplicative updates outperform generic no-regret learning in congestion games.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 533–542, 2009.
  * [13] Walid Krichene, Benjamin Drighes, and Alexandre Bayen.  On the convergence of no-regret learning in selfish routing.  In International Conference on Machine Learning, pages 163–171. PMLR, 2014.
  * [14] Emily Meigs, Francesca Parise, and Asuman Ozdaglar.  Learning dynamics in stochastic routing games.  In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 259–266. IEEE, 2017.
  * [15] Dario Paccagnan, Rahul Chandan, Bryce L Ferguson, and Jason R Marden.  Incentivizing efficient use of shared infrastructure: Optimal tolls in congestion games.  arXiv preprint arXiv:1911.09806, 2019.
  * [16] Jorge I Poveda, Philip N Brown, Jason R Marden, and Andrew R Teel.  A class of distributed adaptive pricing mechanisms for societal systems with limited information.  In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 1490–1495. IEEE, 2017.
  * [17] Tim Roughgarden.  Algorithmic game theory.  Communications of the ACM, 53(7):78–86, 2010.
  * [18] Tim Roughgarden and Éva Tardos.  How bad is selfish routing?  Journal of the ACM (JACM), 49(2):236–259, 2002.
  * [19] Shankar Sastry.  Nonlinear systems: analysis, stability, and control, volume 10.  Springer Science & Business Media, 2013.
  * [20] Rachel Schnalzer.  Traffic is terrible again. here’s how to get it closer to spring 2020 levels.  LA Times, 2021.  Published on July 22, 2021. Available at https://www.latimes.com/business/story/2021-07-22/los-angeles-traffic-congestion-commute-pandemic.
  * [21] Guni Sharon, Josiah P Hanna, Tarun Rambha, Michael W Levin, Michael Albert, Stephen D Boyles, and Peter Stone.  Real-time adaptive tolling scheme for optimized social welfare in traffic networks.  In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2017), 2017.
  * [22] Manxi Wu, Saurabh Amin, and Asuman Ozdaglar.  Bayesian learning with adaptive load allocation strategies.  In Learning for Dynamics and Control, pages 561–570. PMLR, 2020\.