Consensus at Competitive Equilibrium: Dynamic Flow of
Autonomous Cars in Traffic Networks

arXiv:1711.08498v2 [cs.SY] 28 Nov 2017

Dragoslav D. Šiljak∗
November 30, 2017

Abstract
The objective of this paper is to initiate a qualitative analysis of dynamic flow in traffic
networks by using the competitive equilibrium model of multiple market systems. A network
is modeled as a dynamic graph where routes (edges) are viewed by drivers (agents) as gross
substitute commodities which they choose by considering the traffic densities as prices of the
individual routes. By borrowing from economic equilibrium models the notions of gross substitution and homogeneity of excess demand functions, we will be able to show that the chosen
decision rule of the drivers will lead to a consensus resulting in an even distribution of traffic
density over all routes of the network.

Keywords. Competitive dynamic graphs, consensus, autonomous cars, traffic networks.

1

Introduction

The concept of consensus was introduced in the 1950s by Arrow, Block and Hurwicz [1], who
showed that under standard conditions for stability of the competitive equilibrium a nonlinear
time-invariant model of multiple-market system can reach consensus, that is, a unity equilibrium
ray where all normalized prices are equal to each other. At the cost of a more elaborate analysis, it
has been shown [2] that a time-varying version of the stability conditions guarantees that consensus
will be reached in a time-varying model of competitive equilibrium. The main objective of this
paper is to initiate a qualitative study of traffic networks using the general competitive analysis of
economic systems [1]–[4]. The underlying idea is to show that the drivers in a traffic network (like
economic agents in a multiple market system), when choosing alternative routes based solely on the
density of traffic in the corresponding routes, can reach an even distribution (consensus) of traffic
density over the network. We represent traffic networks by dynamic graphs which were introduced
in [5] to consider graphs as dynamic systems. By imitating competitive market models, we then
consider edges of a dynamic graph as commodities (goods) and traffic densities on the edges as
their prices.
The two basic assumptions in dynamic graph models of traffic networks are borrowed from
the competitive economic analysis. First, we consider the edges of a graph as gross substitute
commodities, meaning that if two edges are substitutes (for each other) then an increase in the
∗ Professor Emeritus of Electrical Engineering, Santa Clara University, Santa Clara, CA 95053, USA. dsiljak@scu.edu

1

density of one edge results in an increase in the demand for the other edge. Second, we assume
that the choice of edges (routes) by the drivers depends on the normalized densities of the routes,
and not on the absolute densities of the individual routes. This fact implies that the excess demand
functions are homogeneous of degree zero. With a few additional technical assumptions we will be
able to show that the agents will bring about a desired state of equilibrium of the traffic flow.
There is a large body of work on flows in networks and, in particular, in traffic networks.
Informative recent surveys and discussions of models and control design methods for traffic flows
are provided in the papers [6]–[9]. In general, the models of traffic networks treat a stream of
vehicles very much like water in a water distribution network, or gas in a gas distribution network,
etc. Individual drivers of the vehicles do not have decision power, but follow the rules set by the
parameters of the model reflecting the physics of the flow, or are directed by external feedback
control. As distinct from this approach, we consider traffic networks as interconnected systems
with implicit assumption of dynamic coupling among traffic densities on all the routes. In our
model, the drivers behave as economic agents who choose in a decentralized way individual routes
solely on the basis of density of the traffic in any given route. The densities define a state of the
network which is represented by a nonlinear time-varying dynamic system. In the course of our
analysis we will establish existence of system motions and attraction of an unit equilibrium ray in
the state space of the network. By converging to the equilibrium ray the agents reach the consensus
resulting in an even distribution of traffic over the network.

2

Competitive Dynamic Graphs

We consider a weighted directed graph (or simply, graph) D = (V,E) which is an ordered pair, where
V = {v1 ,v2 , . . . ,vn } is a nonempty and finite set of vertices (points) and E = {e1 , e2 , . . . , em } is
a family of elements of the Cartesian product V × V, called edges (lines). Each edge (vj ,vi ) is
oriented from vj to vi , and is assigned a real number ek , the weight of the edge. Graph D is a
multigraph if there are two or more parallel edges that join the same pair of vertices. Parallel edges
are considered distinct and are labeled individually. A graph without parallel edges is a simple
graph, in which case E is a set.
Dynamic graphs were defined in [5] by setting up a linear graph space D and describing motions
of graphs by a one-parameter group D(t; t0 , D0 ) of transformations of the space D into itself. Since
dynamic graphs so defined are isomorphic to dynamic adjacency (interconnection) matrices, an mdimensional linear space E of adjacency matrices was defined, where the analysis of dynamic graphs
has been carried out as motions E(t; t0 , E0 ) of adjacency matrices E = (eij ) in terms of edge weight
vectors e ∈ E defined over the field F of real numbers. By choosing Rm for E, a dynamic adjacency
matrix E was described by differential equation
E : ė = g(t, e),

(1)

where function g : T × Rm → Rm was assumed to be sufficiently smooth, so that solutions e(t; t0 , e0 )
of E exist and are unique for all (t0 , e0 ) ∈ T × Rm and t ∈ T 0 , where T is the time interval (τ, +∞),
τ is a number or symbol −∞, and T0 is the semi-infinite time interval [t0 , +∞). How the model E
of minimal dimension m can be obtained from a given graph D via the fundamental interconnection
matrix Ē = (ēij ) has been explained in [5].
To introduce a competitive model of multi-agent traffic networks, we use the theory of competitive equilibrium of multiple market systems (e.g. [1], [3], and [4]). We recall that economic agents
2

meet at the market place to exchange goods making their independent decisions solely on the basis
of the prices which they cannot control and take them as given. This is a characteristic of a perfectly competitive environment, where actions of economic agents can be all mutually compatible
and carried out simultaneously. In a graph representing a traffic network, we consider edges (vj ,vi )
as goods and weights eij , which represent the densities of traffic flows through the corresponding
edges, as prices of these goods. Then, the agents utilizing the network select edges on the basis of
their weights and under certain conditions can reach a traffic equilibrium.
To define a competitive graph D, we recall the gross substitute case of multiple market systems
[5] in which all goods are substitutes. We further recall that the gross substitute case is defined in
terms of the excess demand function g(t, e) as follows:
Assumption (A1 ). Function g(t, e) belongs to the class of gross substitute functions
Ḡ: gi (t, e0 ) ≤ gi (t, e00 ), ∀(t, e0 ), (t, e00 ) ∈ T × Rm
+ , ∀i ∈ M
e0i = e00i , e0j ≤ e00j , ∀j ∈ M, i 6= j,

(2)

m
where Rm
: ei ≥ 0, i ∈ M} denotes the nonnegative orthant in Rm , and M =
+ = {e ∈ R
{1, 2, . . . , n}.
Since we are interested in compatibility of the decisions of economic agents we are necessarily
concerned with the difference of demand and supply of the individual goods on the market. The
value of the function g(t, e) tells us what the excess demand would be if all economic agents carried
out their prefered actions at price e. Furthermore, if price of one good goes up while all other prices
stay constant, there will be excess demand for all goods whose prices has remained constant.
To shed more light on the modeling problem we recall [5] the notion of an equilibrium graph De
defined by D(t; t0 , De ) = De . A constant weight vector ee , which corresponds to De , defines the
equilibrium adjacency matrix E e by the equivalent condition

e(t; t0 , ee ) = ee ,

∀t ∈ T .

(3)

In the context of multiple market systems, ee is a price vector at which all agents achieve what they
want, and there is no action to cause a change in e. At ee decisions of all agents are compatible
and they can be carried out simultaneously. A change in price vector e from the equilibrium price
ee indicates incompatibility in the decisions of the agents; this is the familiar notion of the ”law of
supply and demand.”
To illustrate our modeling proposition, let us consider the linear constant model of multiple
market systems [10]. Then, a competitive dynamic graph D is described via adjacency matrix as
EL : ė = Ae + b

(4)

where e = (e1 , e2 , . . . , em )T ∈ Rm
+ is the edge vector standing for the price vector, A = (aij ) is a
constant m × m matrix with sign-pattern
aij

< 0, i = j
≥ 0, i =
6 j

(5)

and b = (b1 , b2 , . . . , bm )T ∈ Rm
+ is a nonnegative constant vector (bi ≥ 0, i ∈ M). The fact that
the off-diagonal elements of matrix A are nonnegative makes the matrix A a Metzler matrix [11],
implying further that Ae + b ∈ Ḡ defined in assumption (A1 ). In economic terms, we have a gross
substitute case where all edges are substitutes; the dynamic system EL is a linear constant model
of competitive equilibrium ee = −A−1 b [4].
3

e1

v1

v2

e2

Figure 1: A multigraph with two parallel routes.

Let us now illustrate the idea of a competitive dynamic graph in modeling of traffic networks
by a simple example involving a dynamic multigraph with two vertices and two parallel edges as
shown in Fig. 1. I[h] The graph represents a traffic network where drivers can get from vertex
v1 to vertex v2 by either of the two edges, where the weights e1 and e2 represent the density of
traffic in the respective edges. The instantaneous values of the density of flows e1 (t) and e2 (t) are
determined by the differential equations
EL : ė1 = a11 e1 + a12 e2 + b1
ė2 = a21 e1 + a22 e2 + b2

(6)

Now, if the density e1 (t) rises above the equilibrium value ee1 , the drivers would switch to road
e2 , which is a substitute to e1 . The switch would decrease the density e1 (t) while, at the same
time, cause the density e2 (t) to rise due to positivity of the coefficient a12 (the matrix A of EL is a
Metzler matrix). Then, the drivers entering the vertex v1 would begin to prefer the road e1 over
e2 , and so on. The fact that this type of price adjustment process converges to the competitive
equilibrium of a multiple market system with unfailing regularity is the most visible part of the
Adam Smith “invisible hand.” What we want to do in this paper is to capitalize on this remarkable
feature of competitive economic systems and propose a similar model for traffic flow networks.
The adjustment process, which was described in the example, goes on throughout the traffic
network. The drivers constitute completely decentralized controllers ([4], [27]), which are continuously choosing the less traveled roads resulting in a balanced traffic density in all routes of the
network; the drivers collectively constitute a “swarm” over the network. For the adjustment process
to succeed, it is essential that the drivers obtain the information about density distribution over
the routes of the network. At present, this information is provided either by GPS Maps situated
on the dashboard of the cars, or by smart phones.
The class Ḡ of functions g(t, e) was introduced by Müler [12] to serve as a basis for the comparison
principle in the theory of differential inequalities (Kamke [13]; Waževski [14]; Lakshmikantham and
Leela [15]; and Ladde [16]). The fact that the same class Ḡ represents excess demand functions
of gross substitute goods in the competitive equilibrium models of market systems in mathematical
econoimics (e. g., Arrow and Hahn [3]), was first recognized in (Šiljak [18]). This recognition
has been exploited in obtaining new results in stability analysis of models in as diverse fields as
population biology (Šiljak [4], [17]; Ladde [16]; Ikeda and Šiljak [19]), arms race (Šiljak [18], [20]),
chemical systems (Ladde [16], Ladde [22], Maeda et al. [23]), compartmental models (Ladde [16];
Jacquez [24]), and large-scale systems (Šiljak [4]; Michel and Miller [25]; Lakshmikantham et al.
[26]; Šiljak [27]; Martynyuk [28], [29]).

4

3

Positivity

For either physical or conceptual reasons, variables of dynamic systems are required to be nonnegative or strictly positive. Positive dynamic systems have been introduced in economics as mathematical models of multiple market systems where prices start and stay positive evolving within
the positive orthant for all time. Similarly, in traffic networks, the densities of traffic on routes of
the network are necessarily nonnegative variables. Within the context of dynamic graphs (Šiljak
[5]), this restriction means that if a graph (network) trajectory starts with nonnegative weights
representing the traffic densities, it stays with nonnegative weights for all future time. A positive
dynamic graph D and the corresponding dynamic matrix E belong to a broad and extensively
studied class of positive dynamic systems (e.g., Arrow and Hahn [3]; Šiljak [4], [5], [18]; Ladde
[16]; Krasnosel’skii [30]). Recently, breaking with tradition, these type of systems were termed
nonnegative systems (Haddad et al. [31], [32]). We note that variables of competitive systems are
nonnegative, and competitive systems are positive dynamic systems (see Remark 1 below), but they
are only a (large) subclass of such systems. To show this fact, we start with
Definition 1. Adjacency matrix E is a positive dynamic system if e0 ∈ Rm
+ implies e(t; t0 , e0 ) ⊂
m
is
an
invariant
set
of
E.
To
establish
positivity
of dynamic graphs
R+ for all t ∈ T0 , that is, Rm
+
we need the following:
Assumption (A2 ). Function g(t, e) belongs to the class
N : gi (t, e1 , . . . , ei−1 , 0, ei+1 , . . . , em ) ≥ 0, ∀(t, e) ∈ R × Rm
+ , ∀i ∈ M
ej ≥ 0, ∀j = 1, . . . , i − 1, i + 1, . . . , m.

(7)

Now, we prove the following:
Theorem 1. Under assumption (A2 ) the adjacency matrix E is a positive dynamic system.
Proof. We follow [30] and associate with dynamic matrix E the auxiliary system
Eε : ė1 = g1 (t, e1 , . . . , em ) + ε
ė2 = g2 (t, e1 , . . . , em ) + ε
···························
ėm = gm (t, e1 , . . . , em ) + ε

(8)

where ε > 0. Set Rm
+ is invariant with respect to the auxiliary system Eε since at every point of
intersection of a solution of Eε with the boundary of Rm
+ , the components of the solution (which
are zero) are increasing. When we let ε → 0, the solutions of the auxiliary system Eε become
solutions of the original system E. Since Rm
+ is a closed set, the theorem follows.
Remark 1. We note that (A2 ) implies (A1 ) provided g(t, 0) = 0 for all t ∈ T (Ladde, 1976),
which further implies that gross substitute assumption (A1 ), with the origin as an equilibrium point
of E, implies that dynamic adjacency matrix E is a positive dynamic system. This fact, in turn,
implies that competitive dynamic systems discussed in the last paragraph of Section 2, are positive
systems, while the opposite implication is not true in general.

4

Existence and Attraction

As it is standard in competitive equilibrium analysis [3], we assume that the economic agents
choose goods depending on their relative prices and not on the prices given in terms of a medium

5

of exchange (e.g., money). If we have a multiple market system described by the equation
Ē : _
e = g(t, e),

(9)

where e = (e0 , e1 , ..., em ) is the price vector of m + 1 goods, and g : T × Rm+1 → Rm+1 is the
excess demand function, we can arbitrarily set one of the prices to 1, say e0 = 1, and treat other
prices as ”normalized prices.” A good having the price e0 need not be money, but instead any
good that serves as numéraire, a measuring stick, with prices of all other goods being expressed in
terms of its price. Since e0 = 1, we write ei = ei /e0 and from the system Ē expressed in terms
of non-normalized prices e0 , e1 , ..., em we obtain the original system E in terms of the normalized
prices e1 , e2 , ..., em . Then, the components of excess demand functions are defined as
gi (t, e0 , e1 , ..., em ) = gi (t, 1, e1 , e2 , ..., em )

(10)

implying that the excess demand functions in terms of normalized prices are given as
gi (t, e1 , e2 , ..., em ) = gi (t, 1, e1 , e2 , ..., em )

(11)

In the context of traffic networks, we take the density in one of the routes as a numéraire, which
will serve as a reference for all other route densities taken as prices of the edges (goods). We hasten
to add that the density of the numéraire need not be constant, but may be varying in time. We
need the following [2]:
Assumption A3 . Function g(t, e) belongs to the class of positive homogeneous functions of
degree zero
H: g(t, λe) = g(t, e),
∀λ > 0.
(12)
To consider existence of solutions e(t; t0 , e0 ) of E we need a stronger version of assumption (A1 ):
0
Assumption (A1 ). Function g(t, e) belongs to the class of strong gross substitute functions
G: gi (t, e0 ) < gi (t, e00 ), ∀(t, e0 ), (t, e00 ) ∈ T × C, ∀i ∈ M
e0i = e00i , e0j < e00j , i ∈ M, j ∈ M − J,

(13)

C = {e ∈ Rm
+ : ei > 0, ∀i ∈ M}

(14)

where
is an open cone in Rn+ , and J is a nonvoid subset of M.
We also need the following :
Assumption (A4 ). There exists an equilibrium ee ∈ C as a solution of the equation g(t, e) = 0.
In terms of normalized densities, we obtain the following theorem concerning the equilibrium:
Theorem 2. Under the assumptions:
(A01 ) g(t, e) ∈ G
(A3 ) g(t, λe) = g(t, e), ∀λ > 0
(A4 ) ∃ee ∈ C: g(t, ee ) = 0, ∀t ∈ T

(15)

there exists a unique equilibrium ray
E = {ee ∈ C : ee = λe}
of E, where e = {1, 1, ..., 1} ∈ Rm
+ and λ is a positive number.
6

(16)

Remark 2. Theorem 2 is interesting because it says that given sufficiently long time, the
densities on all routes of the network will all be equal to each other. This result was first obtained
for a nonlinear time-varying version (Šiljak [2]) of the Richardson’s model of the arms race. This
phenomenon was termed ”consensus” in recent studies of multi-agent systems (e.g., Ren and Beard
[33]), where the differences (system L in Section 5 below) instead of ratios (system E) of state
variables were considered.
Using Theorem 2, we establish the existence result regarding the motion of densities over time
(Šiljak [2], Ladde and Šiljak [16]):
Theorem 3. If function g(t, e) satisfies the assumptions (A01 ) , (A3 ) and (A4 ) of Theorem 2,
then there exists a solution e(t; t0 , e0 ) of E for any (t0 , e0 ) ∈ T × C and all t ∈ T0 .
Both Theorems 2 and 3 are proved in the Appendix under weaker conditions. From the proof
of Theorem 2, it is clear that the assumptions further imply that all solutions are bounded on T0
for all (t0 , e0 ) ∈ T × C. Moreover, the solutions are positive and the open cone C is an invariant
set. That is, the solutions have the following property:
Property (P1 ). (t0 , e0 ) ∈ T × C ⇒ e(t; t0 , e0 ) ⊂ C, ∀t ∈ T0 .
The same set of assumptions of Theorem 2 imply, not only that the cone C is invariant, but that
it is also a region of attraction of the equilibrium ray E. Formally, we define the following
Property (P2 ). (t0 , e0 ) ∈ T × C ⇒ limt→+∞ d[e(t; t0 , e0 ), E] = 0, where
d(e, E) = inf
{k e − ee kM },
e
e ∈E

(17)

and k e kM = supi∈M {k ei k}.
In the Appendix, we prove a slightly stronger result than the following:
Theorem 4. If the function g(t, e) satisfies the assumptions (A01 ) , (A3 ) and (A4 ) of Theorem
2, then the solutions e(t; t0 , e0 ) of E have the property (P2 ).

5

Vertex Dynamics

So far, we have considered graphs with dynamic edges, leaving the edges static (constant in time).
The reversed situations, where the dynamics is restricted to the vertices of a graph while the
edges were state and/or time-dependent, have been extensively studied in the context of connective
stability of interconnected systems (Šiljak [4], [17]; Lakshmikantham et al. [26]; Martynyuk [28],
[29]). A graph with vertex dynamics can be considered as a vertex system
V : v̇ = f (t, v)

(18)

where v ∈ RN is the state of V and function f : T × Rn → Rn can be required to satisfy the same
conditions as function g(t, e) of E. The system V can be used to represent a nonlinear time varying
interaction in a team of n agents (e.g., unmanned vehicles in the air, water, and on the ground) that
share information to reach consensus via often unreliable communication channels with uncertain
topology (see the papers by Lin et al. [34], [37]; Fax and Murray [35]; Olfati-Saber and Murray
[36]; Li and Jiang[38]; and a recent book by Ren and Beard [33]). The most popular consensus
algorithm is
n
X
L : v̇ = −
eij [vi (t) − vj (t)], i ∈ N,
(19)
j6=i

7

where eij ’s are the constant elements of the n×n adjacency matrix E = (eij ), and N = {1, 2, . . . , n}.
The purpose of the algorithm is to achieve the consensus by driving the information state of each
individual agents toward the state of its neighbors, that is, to have kvi − vj k → 0, as t → ∞, for
all i ∈ N. Let us propose that the consensus algorithm be described by a nonlinear time varying
system V. Then, the desired consensus result is obtained from Theorem 4 as
Theorem 5. If the function f (t, v) satisfies the assumptions (A01 ) , (A3 ) and (A4 ), then the
agents reach consensus defined by the property
(P2 ) : (t0 , v0 ) ∈ T × C

⇒

lim d[v(t; t0 , e0 ), E] = 0,

t→+∞

(20)

where E = {v e ∈ C : v e = λe} and v e is the equilibrium state of V.
The essential difference between the consensus defined for the system L and our consensus
guaranteed by Theorem 5 is that we derived the consensus via scaling of the information state by a
numéraire, which, for example, can be taken as the information state of the team leader. A possible
advantage of the scaled consensus over the difference one should be explored in future research by
a more refined analysis followed by simulation and practical implementation.
Communication exchange among the individual pairs of agents may be disrupted due to unreliable communication topology (Ren and Beard [33]) resulting in a loss of consistency, accuracy,
and completeness of of information necessary to achieve consensus. A natural way to capture these
type of structural perturbations is to allow the adjacency matrix E to be time-varying and state
dependent (E : T × Rn → Rn×n ) within the concept of connective stability (Šiljak [4]) and derive
conditions under which we are guaranteed consensus despite arbitrary disconnections and connections of communication links between the agents. In the case of algorithm (system ) L we need
only replace each constant elements eij by a function eij : T × Rn → R+ . When we deal with the
nonlinear time-varying model V, we need to specify the structure of components fi of the function
f (t, v) as
fi (t, v, e) = fi (t, vi , ei1 v1 , ei2 v2 , . . . , ein vn ), i ∈ N.
(21)
There is a large number of results which exploit this structural form within the concept of connective
stability involving stochastic elements, time-delays, discontinuous nonlinearities, and parametric
uncertainties (Šiljak [4]; Lakshmikantham et al. [26]; Malikov and Matrosov [39]; Stipanović and
Šiljak [40], [41]; Ladde [42]; Chandra and Ladde [43]). The results can be carried over to multi-agent
systems in a natural way (Šiljak [5]).
Recently, dynamic graphs have been introduced which involve both the vertex and edge dynamics
(Šiljak [5]) in an composite system configuration
V:
E:

v̇ = f (t, v, e)
,
ė = g(t, e, v).

(22)

which was studied within the new concept of dynamic connective stability. A multi-agent system
has been considered as an add-on adaptive control device based on the dynamic adjacency matrix E
to drive the interconnections of a composite system V&E to a preassigned state which is required
to be its stable equilibrium. This opened up a new approach to control of complex systems,
which elevated the role of interconnections (edges) to the same level as subsystems (vertices) in
shaping the performance of interconnected systems. In future research, we plan to explore how
the unified vertex and edge dynamics can be used to describe and analyze more refined models of
traffic networks.

8

6

Conclusion

Our main objective in this paper was to model a traffic network as a multiple market system in
the context of competitive equilibrium analysis. Individual routes were considered as commodities
and their traffic densities as prices. Now, drivers become economic agents who choose alternative
routes based solely on their prices and can reach a traffic consensus (unity vector) where normalized
densities obtain the same value. Traffic network was modeled as a dynamic graph and Lyapunov’s
theory was used to establish stability of its consensus. In the proposed setting, a great deal can be
done to improve the competitive model of traffic networks and come up with new and interesting
results.

Appendix
To prove the existence result of Theorem 2, we start with the following lemma ( Šiljak [2], Ladde
and Šiljak [16]):
Lemma 1. If the function g(t, e) satisfies the assumptions (A01 ) , (A3 ) and (A4 ), then for any
two positive vectors u > 0, v > 0, u 6= v, there exist indicies k, l ∈ M, k 6= l, such that
gk (t, u) < gk (t, v),

gl (t, u) > gl (t, v)

(23)

for each fixed t ∈ T and all u, v ∈ Rm
+.
Proof. Define ξk = maxi∈M {ui /vi }, ηl = mini∈M {ui /vi } for any pair of vectors u, v > 0. With
each pair (u, v), we associate the pair (u∗ , u∗ ) given as u∗ = ξk−1 u, u∗ = ηl−1 u, so that u∗ ≤ v and
u∗ ≥ v. That is, u∗i ≤ vi , i 6= k, u∗k = vk and, likewise, u∗i ≥ vi , i 6= l, u∗l = vi . Furthermore, since
u 6= v, at least for some i we have u∗i < vi , u∗i > vi , i 6= k, i 6= l. Now, from (A01 ) and (A3 ), we have
gl (t, u) = gl (t, u∗ ) > gl (t, v)

gk (t, u) = gk (t, u∗ ) < gk (t, v),

(24)

for all t ∈ T , which proves the lemma.
Proof of Theorem 2. Uniqueness of E means that for any pair of equilibrium values e0 , e00 ∈ C,
0
e 6= e00 ,
g(t, e00 ) = g(t, e0 ) = 0 ⇒ e00 = λe0
(25)
for all t ∈ T and some λ > 0. Define µ = mini∈M {e0i /e00i }, where e0i , e00i are the i-th components of the
0
000
0
two equilibria e0i , e00i , and e000 = µe00 . Then, we have e000 ≤ e0 , that is, e000
i ≤ ei , i 6= l, el = el , and at
000
0
00
0
least for some i 6= l, ei < ei . Assume that the statement (20) is false. That is, e 6= λe for all λ > 0.
By (A01 ) , (A3 ) , (A4 ) , and g(t, e00 ) = g(t, e0 ) = 0, we have 0 = gl (t, e00 ) = gl (t, e000 ) < gl (t, e0 ) = 0,
which is absurd. This proves the theorem.
Remark 2. If we take any pair of vectors ee , e ∈ C such that ee ∈ E, e ∈
/ E, and use Theorem
2 and inequalities (18), we conclude that gk (t, e) < 0 and gl (t, e) > 0 for all t ∈ T and some indicies
k, l ∈ M.
To establish the existence result of Theorem 3 we can replace the assumptions (A01 ) , (A3 ) and
(A4 ) by the following weaker assumption:
Assumption A5 . g(t, ee ) = 0 ⇔ ee ∈ E, and for any e ∈ C, e ∈
/ E, and any ee ∈ E, there exists
a pair of indicies k, l ∈ M, k 6= l, such that
ek = max {ei } ⇒ gk (t, e) < 0,

el = min {ei } ⇒ gl (t, e) > 0

i∈M

i∈M

9

(26)

for all t ∈ T .
Remark 3. In view of Remark 2, the assumptions (A01 ), (A3 ) , (A4 ) taken together imply (A5 )
but not vice versa.
Now we can prove a slightly stronger result than Theorem 3 as the following:
Theorem 5. If the function g(t, e) satisfies the assumption (A5 ) , then there exists a solution
e(t) = e(t; t0 , e0 ) of E for all (t0 , e0 ) ∈ T × C and t ∈ T0 .
Proof. Consider e0 ∈
/ E, and α = ek0 = maxi∈M {ei0 }, β = el0 = mini∈M {ei0 },and α > β > 0.
Define
B p = {e ∈ Rn+ : β ≤ ei ≤ α, ∀i ∈ M}
(27)
B pp = {e ∈ Rn+ : 21 β ≤ ei ≤ α + 21 β, ∀i ∈ M}
and note B p ⊂ B pp . For any τ > 0, we define the time interval T 1 = [t0 , t0 + τ ] and the rectangle
T 1 × B pp . By continuity of g(t, e) we can find a number µ1 > 0 such that |gi (t, e)| ≤ µ1 for all
(t, e) ∈ T 1 × B pp and all i ∈ M. By Peano’s existence theorem (e.g., Hale [44]), there exists at least
one solution e(t) for all t ∈ [t0 , t0 + ε1 ], where ε1 = min {τ, α/µ1 }. Now, either e(t1 ) ∈ E for some
t1 ∈ (t0 , t0 + ε1 ], or e(t) ∈
/ E for all t ∈ [t0 , t0 + ε1 ]. In the first case, the solution e(t) exists for all
t ∈ T0 . When the second case takes place, then we extend successively the solution e(t) beyond the
time interval (t0 , t0 + ε1 ].
Note that for all (t0 , t0 + ε1 ], e(t) ∈ B pp . In fact, we can show that the same statement holds for
B p . Since e0 ∈
/ E, from (A5 ) we have (21) with e = e0 , which for t = t0 implies
gk (t0 , e0 ) < 0,

gl (t0 , e0 ) > 0.

(28)

By continuity of g(t, e) and e(t), we can find a δ1 > 0 such that
gk [t, e(t)] < 0,

gl [t, e(t)] > 0,

∀t ∈ [t0 , t0 + δ1 ]

(29)

which by integration yields
ek (t) ≤ ek0 ,

el (t) ≥ el0 ,

∀t ∈ [t0 , t0 + δ1 ]

(30)

and, in turn, implies that e(t) ∈ B p for all t ∈ [t0 , t0 +δ1 ]. Since e(t0 +δ1 ) ∈ B pp and also e(t0 +δ1 ) ∈
/ E,
by using again (A5 ), we get
gk [t0 + δ1 , e(t0 + δ1 )] < 0,

gl [t0 + δ1 , e(t0 + δ1 )] > 0,

(31)

and conclude that there exists a δ2 > 0 such that
gk [t, e(t)] < 0,

gl [t, e(t)] > 0,

∀t ∈ [t0 + δ1 , t0 + δ1 + δ2 ]

(32)

and
ek (t) ≤ ek (t0 + δ1 ),

el (t) ≥ el (t0 + δ1 ),

∀t ∈ [t0 + δ1 , t0 + δ1 + δ2 ].

(33)

Therefore, (24) and (28) imply that e(t) ∈ B for all t ∈ [t0 + δ1 , t0 + δ1 + δ2 ]. By continuing this
process, we conclude in finite number of steps that e(t) ∈ B p for all t ∈ [t0 , t0 + ε1 ]. Since e(t)
remains in B p for the entire interval [t0 , t0 + ε1 ], by using the above arguments we can show that
the solution e(t) can be extended over the interval [t0 + ε1 , t0 + 2ε1 ] and, therefore, over the interval
T 1 = [t0 , t0 + τ ]. Furthermore, e(t) ∈ B p for all t ∈ T 1 .
Because the solution e(t) ∈ B p during the entire time interval T 1 = [t0 , t0 + τ ], it can be
extended over the interval T 2 = [t0 + τ, t0 + 2τ ] by choosing subintervals of T 2 determined by
p

10

ε2 = min{τ, α/µ2 }, where µ2 is defined by the condition |gi (t, e)| ≤ µ2 , for all (t, e) ∈ T 2 × B pp and
i ∈ M. Moreover, we can show as before that e(t) ∈ B p for all t ∈ T 2 . Therefore, e(t) ∈ B p for all
t ∈ T 1 ∪ T 2 . Continuing in this way, we can find a solution staying inside B p for all t ∈ T 0 . This
proves the theorem.
Now, we can establish our main result concerning the attraction of the equilibrium ray E as
Theorem 6. If the function g(t, e) satisfies the assumption (A5 ) , then solutions e(t; t0 , e0 ) of
E have the property (P2 ).
Proof. [2] We prove this theorem by using a Liapunov-like function V : C → R+ , defined as
V (e) = d(e, E),

(34)

and V (e) ∈ C 0 (C). Function V (e) is Lipschitzian having the derivative D+ V (e)E with respect to
E, computed as
D+ V (e)E ≤ − min{|gi (t, e)|},
∀(t, e) ∈ T × C − E,
(35)
i∈L

where L is a non void subset of M, which is the set of all i ∈ M such that |gi (t, e)| > 0. To show
the last inequality, we note that for each (t, e) ∈ T × C − E there is λ0 > 0 such that V (e) can be
rewritten as
V (e) = max{|ei − λ0 |}.
(36)
i∈M

To see this, we note that the distance between a point e and the ray E is equal to the distance between
the point e and the foot e0 ∈ E of the normal drawn from the point e to the ray E. Furthermore,
there exists an index set L such that V (e) = |ei − λ0 | for all i ∈ L. Now, by assumption (A5 ) we
have either gi (t, e) > 0,or gi (t, e) < 0,and, therefore, |gi (t, e)| > 0, i ∈ L. By continuity of g(t, e)
and for ∆t > 0 sufficiently small, we conclude that the index set L remains invariant.
We now compute D+ V (e)E as follows:
V [e + ∆tg(t, e)] − V (e) = |ei + ∆tgi (t, e) − λ0 | − |ei − λ0 | ,

∀i ∈ L.

(37)

There are two cases to be considered: xi − λ0 > 0 and xi − λ0 < 0,for i ∈ L. When xi − λ0 > 0,
then gi (t, e) < 0, and when xi − λ0 < 0, then gi (t, e) > 0. In either case, the last equation can be
rewritten as
V [e + ∆tg(t, e)] − V (e) = ∆t |gi (t, e)| , ∀i ∈ L.
(38)
When xi − λ0 > 0, then gi (t, e) < 0, and when xi − λ0 < 0, then gi (t, e) > 0. Hence, from (33) we
get
V [e + ∆tg(t, e)] − V (e) = −∆t |gi (t, e)| , ∀i ∈ L,
(39)
and finally (39) establishes (35).
The second part of the proof consists in proving that the Liapunov-like function V (e) = d(e, E)
with inequality (35) implies property (P2 ). Let e(t) = e(t; t0 , e0 ) be any solution of the system E
for (t0 , e0 ) ∈ T × C. Then, e(t) ∈ B p fot all t ∈ T 0 . Set
ρ(t) = V [e(t)].

(40)

For sufficiently small ∆t > 0, we have
ρ(t + ∆t) − ρ(t)

= V [e(t + ∆t)] − V [e(t)]
= V [e(t + ∆t)] − V (e(t) + ∆tg[t, e(t)])
+ V (e(t) + ∆tg[t, e(t)]) − V [e(t)].
11

(41)

By using the fact that function V (e) is Lipschitzian, we immediately obtain
D+ ρ(t)E ≤ min{|gi (t, e)|},
i∈L

∀t ∈ T 0 .

(42)

We now proceed to establish property (P2 ) by contradiction. For some ε > 0, (t0 , e0 ) ∈ T × C,
there exists t1 > t0 and a sequence {tk }, tk > t1 , tk → +∞, k → +∞, such that d[e(tk ), E] = ε and
d[e(t), E] > ε for t ∈ (tk , tk+1 ). Let us introduce
B ppp = {e ∈ B p : d(e, E] ≥ ε},

(43)

which is a compact set. For any t ∈ T , and any fixed ẽ ∈ B ppp , there is an index subset L ⊂ M,
such that the function
θ(t, ẽ) = min{|gi (t, ẽ)|} > 0.
(44)
i∈L

By continuity of θ(t, ẽ), there exists a neighborhood N (ẽ) of ẽ ∈ B ppp such that θ(t, e) > 0, for all
e ∈ N (ẽ). Let U = {N (ẽ) : ẽ ∈ B ppp } be an open cover of B ppp . Since B ppp is compact, by Heine-Borel
Theorem (Royden [45]), we can extract a finite subcover {N (ẽ1 ), N (ẽ2 ),. . . , N (ẽm )}, where to
each N (ẽj ) there corresponds an index subset Lj and function
θj (t, e) = min{|gi (t, e)|}.
i∈Lj

(45)

We define ψ(t, e) = minj {θ1 (t, e), θ2 (t, e),. . . , θm (t, e)}, and note that ψ(t, e) ∈ C (0,0) (T × B ppp ), and
ψ(t, e) > 0, for all (t, e) ∈ T × B ppp . Therefore, we can take inf e∈Bppp´ ψ(t, e) = ϕ(t), and ϕ(t) ∈ C 0 (T )
since B ppp is compact.
Now, from inequality (42), we can obtain
D+ ρ(t)E ≤ −ϕ(t),

(46)

where e(t) ∈ B ppp , t ∈ [tk , tk+1 ]. Integrating this inequality from tk to tk+1 , and using the definitions
of V (e) and ρ(t), we get
tZk+1
0 = ρ(tk+1 ) − ρ(tk ) ≤ −
ϕ(τ )dτ < 0,
(47)
tk

which is absurd. Therefore, the proof of the theorem is complete.

Acknowledgment
My first thanks go to my longtime colleague, co-author and friend Professor Gangaram S. Ladde,
Department of Mathematics and Statistics, University of South Florida, for his generous help in
writing the first phase of this paper. I am also exceedingly grateful to my colleague Professor
Mohammad A. Ayoubi, Mechanical Engineering Department, Santa Clara University, for his help
in completing the paper.

12

References
[1] K. J. Arrow, H. D. Block, and L. Hurwicz, “On the Stability of the competitive equilibrium
II,” Econometrica, 27 (1959) 82–109. See also K. J. Arrow and L. Hurwicz(Eds.), Studies in
Resource Allocation Processes, Cambridge University Press, Cambridge, England, 1977.
[2] D. D. Šiljak, “Competitive analysis of the arms race,” Annals of Economic and Social Measurement, 5/3 (1976) 283–295.
[3] K. J. Arrow and F. H. Hahn, General Competitive Analysis, Holden-Day, San Francisco, CA,
1971.
[4] D. D. Šiljak, Large-Scale Dynamic Systems: Stability and Structure, North-Holland, Amsterdam, The Netherlands, 1978. (reprinted by Dover, 2007).
[5] D. Šiljak, “Dynamic Graphs, Nonlinear Analysis: Hybrid Systems,” 2 (2008) 544–567.
[6] S. Darbha and K. R. Rajagopal, “Intelligent cruise control systems and traffic flow stability,”
Transportation Research, Part C, 7 (1999) 329–352.
[7] P. Ioannou, Y. Wang, and H. Chang, “Modeling, simulation, and control of transportation
systems,” in Modeling and Control of Complex Systems, P. Ioannou and A. Pitsillides (Eds.),
CRC Press, Boca Raton, FL, 2007 407–437.
[8] E. B. Kosmatopoulos, M. Papageorgiou, A. Vakouli, and A. Kouvelas, “Adaptive fine-tuning
of nonlinear control systems with application to the urban traffic control strategy TUC,”
IEEE Transactions on Control Systems Technology, 15 (2007), 991-1002. W. Sandberg, “On
mathematical theory of interactions in social groups,” IEEE Transactions on Systems, Man,
and Cybernetics, SMC-4 (1974) 432–445.
[9] V. Tyagi, S. Darbha, and K. R. Rajagopal, “A dynamical systems approach based on averaging
to model the macroscopic flow of freeway traffic,” Nonlinear Analysis: Hybrid Systems, 2
(2008), 590-612.M. A. Krasnosel’skii, Shift Operator on Trajectories of Differential Equations
(in Russian), Nauka, Moscow, 1966.
[10] K. J. Arrow, “Price-quality adjustments in multiple markets with rising demands,” in Mathematical Methods in Social Sciences, K. J. Arrow, S. Karlin, P. Suppes, Stanford University
Press, Stanford, CA, 1966, pp. 3–15.
[11] K. J. Arrow, “The genesis of dynamic systems governed by Metzler matrices,” Collected Papers
of Keneth J. Arrow,General Equilibrium, Belknap Press, Cambridge, MA, 1983, pp. 245–264.I.
D.
[12] M. Müler, “Über das Fundamentaltheorem in der Theorie der gewönlichen Differentialgleihungen,” Mathematische Zeitschrift, 26 (1926) 619–645.
[13] E. Kamke, “Zur Theorie der Systeme gewönlicher Differentialgleihungen,” II, Acta matematica,
58 (1932) 57–85.
[14] T. Wažewski, “Systèmes des équations et des inegalites différentielles ordinaires aux dèuxiemes
membres monotones etleursapplicationes,” Annales de la Societé Polonaise de mathematiques,
23 (1950) 112–166.
13

[15] V. Lakshmikantham, and S. Leela, Differential and Integral Inequalities, Vols. I and II, Academic, New York, 1969.
[16] G. S. Ladde, “Competitive Processes and comparison differentgial systems,” Transactions of
the American Mathematical Society, 221 (1976) 391–402.
[17] D. D. Šiljak, “Connective stability of complex ecosystems,” Nature, 249 (1975) 280.
[18] D. D. Šiljak, “Competitive economic systems: Stability, decomposition, and aggregation,”
IEEE Transactions on Automatic Control, AC-21 (1976) 149–160.
[19] M. Ikeda and D. D. Šiljak, “Lotka-Volterra equations: Decomposition, stability, and structure,
Part I: Equilibrium analysis,” Journal of Mathematical Biology, 9 (1980) 56–83.
[20] D. D. Šiljak, “On stability of the arms race,” in: J. V. Gillespie and D. A. Zinnes (Eds.),
Mathematical Systems in International Relations Research, Praeger, New York, 1977, pp. 264–
296.
[21] G. S. Ladde, “Cellular Systems I: Stability of chemical system,” Mathematical Biosciences, 29
(1976) 309–330.
[22] G. S. Ladde, “Cellular Systems II: Stability of compartmental systems,” Mathematical Biosciences, 30 (1976) 1-21.H.
[23] Maeda, S. Kodama, and Y. Ohta, “Qualitative analysis of a class of nonlinear compartmental
systems: Nonoscillation and stability,” IEEE Transactions on Circuits and Systems CAS,25
(1978) 372–378.
[24] J. A. Jacquez and C. P. Simon, “Qualitative theory of compartmental systems,” SIAM Review,
35 (1993) 43–79.
[25] A. N. Michel and R. K. Miller, Qualitative Analysis of Large Scale Dynamical Systems,Academic Press, New York, 1977.
[26] Lakshmikantham, V. M. Matrosov, and S. Sivasundaram, Vector Lyapunov Functions and Stability Analysis of Nonlinrear Systems, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1991.
[27] D. D. Šiljak, Decentralized Control of Complex Systems, Academic Press, Boston, MA, 1991.
[28] A. A. Martynyuk, Qualitative Methods in Nonlinear Dynamics: Novel Approaches to Liapunov’s Matrix Functions, Marcel Dekker, New York, 2002.
[29] A. A. Martynyuk, Stability of Motion: The Role of Multicomponent Liapunov’s Functions,
Cambridge Scientific Publishers, Cambridge, UK, 2007.
[30] M. A. Krasnosel’skii, Shift Operator on Trajectories of Differential Equations (in Russian),
Nauka, Moscow, 1966.
[31] W. M. Haddad, V. Chellaboina, and S. G. Nersesov, “Thermodynamics and large-scale nonlinear dynamical systems: A vector dissipativity systems approach, Dynamics of Continuous,
Discrete & Impulsive Systems, Part B: Applications & Algorithms,” 11 (2004) 609–649.
14

[32] W. M. Haddad and V. Chellaboina, V. , “Stability and dissipativity theory for nonnegative
dynamical systems: A unified analysis framework for biological and physiological systems,”
Nonlinear Analysis, RWA 6 (2005) 35–65.
[33] W. Ren and W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control, Springer,
London, UK, 2008.
[34] Z. Lin, M. Broucke, and B. Francis, “Local control strategies for groups of mobile autonomous
agents,” IEEE Transactions on Automatic Control, 49 (2004) 622–629.
[35] J. A. Fax and R. M. Murray, “Information flow and cooperative control of vehicle formations,”
IEEE Transactions on Automatic Control, 49 (2004), 1465–1476.
[36] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching
topology and time-delays.” IEEE Transactions on Automatic Control, 49 (2004), 1520–1533.
[37] Z. Lin, B. Francis, and M. Maggiore, “State agreement for continuous-time coupled nonlinear
systems,” SIAM Journal of Control and Optimization, 46 (2007) 288–307.
[38] Q. Li and Z.-P. Jiang, “Two decentralized leading consensus algorithms for nonlinear multiagent systems,”Asian Journal of Control, 10 (2008) 187–200.
[39] A. I. Malikov and V. M. Matrosov, “Lyapunov vector functions in the analysis of dynamical
properties of systems with structural changes,” Journal of Computers and Systems Sciences
International, 37 (1998), 207–214.
[40] D. M. Stipanović and D. D. Šiljak, “Stability of polytopic systems via convex M -matrices and
parameter-dependent Liapunov functions,” Nonlinear Analysis 40 (2000), 589–609.
[41] D. M. Stipanović and D. D. Šiljak, “Connective stability of discontinuous dynamic systems,”
Journal of Optimization Theory and applications, 115 (2004), 711–726.
[42] G. S. Ladde, “Hybrid systems: Convergence and stability analysis of large-scale approximation
schemes,” International Journal of Hybrid Systems, 2 (2002) 235–260.
[43] J. Chandra and G. S. Ladde, “Stability analysis of stochastic hybrid systems,” International
Journal of Hybrid Systems, 4 (2004) 179–198.
[44] J. K. Hale, Ordinary Differential Equations, Wiley-Interscience, New York, 1969.
[45] H. L. Royden, Real Analysis, Second Edition, Macmillan, New York, 1968.

15

