EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 4, 2024, 2448-2466 ISSN 1307-5543 – ejpam.com Published by New York Business Global Wardrop Optimal Networks Antonios Kalampakas College of Engineering and Technology, American University of the Middle East, Egaila, 54200, Kuwait Abstract. Optimal flow allocation in directed networks is often analyzed through two types of equilibria. The first, called user equilibrium, occurs when the travel times on all utilized routes are the same and shorter than every unused route. The second, called system optimum, minimizes the average travel time across all routes. These two concepts represent the optimality for individual users and for the network as a whole, respectively, and generally do not coincide. Our main objective in this paper is to introduce and examine the properties of networks where the user equilibrium and the system optimum are identical, termed Wardrop optimal networks. We achieve this by providing a set of necessary and sufficient conditions for Wardrop optimal flows and using this characterization we investigate the main properties of Wardrop optimal networks. Moreover, we illustrate that these flows remain consistent under several important transformations as well as under uniform changes in their latency functions. 2020 Mathematics Subject Classifications: 05C20,05C21,49Q22 Key Words and Phrases: Optimal flow allocation, Resource management, Wardrop equilibrium, user and system optimum 1. Introduction The efficient distribution of flow in directed networks is often examined through two different key concepts, known as Wardrop’s Principles: user equilibrium and system opti- mum [30]. Wardrop’s principles are fundamental concepts in transportation and network theory, providing a basis for understanding traffic flow and congestion management. Ac- cording to Wardrop’s first principle, user equilibrium is reached when travel times on all routes in use are the same, and no traveler can reduce their travel time by switching routes; this state is also referred to as a Wardrop equilibrium [7, 19]. The second principle asserts that the network flow configuration minimizes the total travel time for all users, representing an optimal state from the perspective of the network as a whole. In practice, user equilibrium and system optimum typically differ, leading to inefficien- cies in network usage. Achieving the system optimum typically requires a form of central DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.5384 Email address: antonios.kalampakas@aum.edu.kw (A. Kalampakas) https://www.ejpam.com 2448 Copyright: © 2024 The Author(s). (CC BY-NC 4.0) A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2449 control or coordination because individual users acting in their self-interest do not natu- rally lead to system optimal flows. To achieve the system optimum, traffic may need to be redistributed by encouraging or forcing users to follow less congested routes, even if their travel time increases. This redistribution reduces the overall congestion and minimizes the total travel time or cost for all users combined. At user equilibrium, the total travel time is generally higher than at system optimum because individuals are not incentivized to consider the overall system performance. In many networks, user equilibrium represents a ”selfish” solution, whereas the system optimum represents a ”cooperative” solution. The ratio of the total travel time at user equilibrium to that at system optimum is known as the price of anarchy. A flow that is both system optimum and user equilibrium is called Wardrop optimal flow and networks that admit such flows are termed Wardrop optimal networks [4, 13] (see also [2, 3, 5] where Wardrop optimal networks with dynamic flow assignment are examined and [14] presenting, without proofs, some of the main properties of Wardrop optimal networks we establish in this paper). By construction, the price of anarchy of such networks is optimal, i.e., equal to 1, a desirable property in network theory with applications in fields such as economics [26, 28], transportation [6, 23, 25, 29, 30], and communications [18, 20, 21, 24], and can be also applied to areas like multiprocessor task scheduling [8] and media flow with double diffusion [12]. For a comprehensive review of the literature in approaches bridging user equilibrium and system optimum see [22]. This paper focuses on analyzing these flows and their corresponding networks. A flow travelling from initial to target node is allocated across multiple links, causing congestion, which in turn increases travel times, captured by link-specific latency functions that are strictly increasing. We establish a connection between the user equilibrium and system optimum through the associated Pigovian network and derive conditions for the existence and uniqueness of optimal flows in convex networks. The paper is organized in the following way. In Section 2 we outline the basic defini- tions we use throughout the paper. Section 3 examines in detail the user equilibrium and introduces the discrete user equilibrium. Section 4 explores the system optimum, present- ing necessary and sufficient conditions for its characterization. In Section 5 we introduce Wardrop optimal networks and provide a characterization for differentiable convex net- works which demonstrates that these flows are maintained under specific transformations. 2. Preliminaries The networks we will examine have n links In = {1, 2, . . . , n} connecting the origin with the destination node [1]. Let ϕi ≥ 0 denote the flow via link i, for every i ∈ In. The total flow is distributed among the links such that n∑ i=1 ϕi = 1. The support of a flow ϕ is denoted by supp(ϕ) = {k ∈ In | ϕk ̸= 0}. Additionally, we A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2450 set Sn−1 = {ϕ ∈ Rn + : n∑ i=1 ϕi = 1} and Int(Sn−1) = {ϕ ∈ Sn−1 : supp(ϕ) = In}. On each link, the flow induces congestion, increasing the traversal delay [30]. This delay is captured by continuous and strictly increasing latency functions li(x) : [0, 1] → R, i ∈ In. Such a network of can thus be characterized by the vector of latency functions Nn = (l1(x), . . . , ln(x)). If all latency functions li(x) are differentiable, the network is called a differentiable network ; if they are convex, it is termed a convex network. A user equilibrium or Wardrop equilibrium of a network Nn = (l1(x), . . . , ln(x)) is a flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 such that lk(ϕk) = min i∈In {li(ϕi)}, ∀k ∈ In with ϕk > 0, i.e., the delay is equal among all used links and less than that of any unused link [6]. The overall delay of a network Nn = (l1(x), . . . , ln(x)) for ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is given by n∑ i=1 ϕili(ϕi). A system optimum of a network Nn = (l1(x), . . . , ln(x)) is a flow (ϕ1, . . . , ϕn) ∈ Sn−1 that minimizes this average delay [6]. 3. User Equilibrium In what follows, we explore several properties that will be essential throughout. The next lemma demonstrates that user equilibrium remains unchanged under mappings which are strictly increasing. This is because the minimum value in a set is preserved when a strictly increasing function is applied. Lemma 1. Consider a network Nn = (l1(x), . . . , ln(x)) and a strictly increasing and continuous function f(x) : R → R, if a flow (ϕ1, . . . , ϕn) ∈ Sn−1 is user equilibrium of Nn then it is also user equilibrium of f(Nn) = (f(l1(x)), . . . , f(ln(x))). On the other hand, the above property doesn’t hold for system optimums as it is illustrated in the following example. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2451 l1(x) = x2/3 l2(x) = 2x/3 Figure 1: A network N with two parallel links Example 1. We examine the network N = {x2 3 , 2x 3 } presented in Fig. 1 which was utilized in [1] to highlight the inefficiency due to congestion externalities. The system optimum that minimizes the average delay of the network is ϕSO = (23 , 1 3) and the user equilibrium that equates delay on the two links is ϕWE ≈ (0.73, 0.27). The network obtained by taking the image of N via the continuous and strictly increas- ing function f(x) = x2 is f(N) = {x4 9 , 4x2 9 }. It is straightforward to see that the user equilibrium of f(N) is the same but the new system optimum is ϕSO′ ≈ {0.69, 0.31}. The example demonstrates that, the system optimum unlike the user equilibrium is not generally maintained by the type of latency function we consider i.e., continuous, convex and strictly increasing. This raises the following question: do Wardrop optimal flows remain consistent under such transformations? We will address this question in Section 5. The below property will be very useful in our subsequent constructions. It can be easily proved by a simple geometric inspection of the curves of the strictly increasing latency functions on the same coordinate system. Below we provide a more detailed algebraic proof (similar constructions exist in the literature for the user equilibrium, see e.g. [27]). Proposition 1. There exists a unique user equilibrium for any network Nn. Proof. Let Nn = (l1(x), · · · , ln(x)). For each i ∈ In, we set ai = li(0), bi = li(1) and consider the inverse (again continuous, strictly increasing) function l−1 i : [ai, bi] → [0, 1] of each latency function li : [0, 1] → [ai, bi]. We define a continuous and increasing function l−1 i : R → [0, 1] by l−1 i (y) :=  0, if y < ai l−1 i (y), if ai ≤ y ≤ bi 1, if y > bi as well as a function L−1 : R → [0, n] by L−1(y) := ∑ i∈In l−1 i (y). A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2452 Then L−1 : R → [0, n] is also a continuous and increasing function such that L−1(y) = 0 for any 0 ≤ y ≤ min i∈In {ai} and L−1(y) = n for any y ≥ max i∈In {bi}. Since l−1 j : [aj , bj ] → [0, 1] is the strictly increasing function on the interval [aj , bj ] where aj = min i∈In {ai}, therefore the function L−1 : [aj , bj ] → [0, n] is also strictly increasing on the same interval [aj , bj ] where aj = min i∈In {ai}. It can be easily seen that L−1(aj) = 0 and L−1(bj) ≥ l−1 j (bj) = 1. Let L−1(bj) = 1. Then the unique user equilibrium is ϕ = (0, 0 · · · , 0, 1︸︷︷︸ j , 0, · · · 0) with supp(ϕ) = {j}. Indeed, since L−1(bj) = ∑ i∈In l−1 i (bj) = 1, it is easy to see that l−1 j (bj) = l−1 j (bj) = 1 or equivalently lj(1) = bj and meanwhile l−1 i (bj) = 0 for every i ∈ In with i ̸= j or equivalently bj ≤ ai for every i ∈ In with i ̸= j. The last inequality means that li(0) = ai ≥ bj = lj(1) for every i ∈ In with i ̸= j. Let L−1(bj) > 1. Since L−1([0, aj ]) = 0, the function L−1 is strictly increasing on the interval [aj , bj ], and L−1(bj) > 1. Then there always exists a unique c ∈ (aj , bj) such that L−1(c) = 1. Let us define the following sets α := {k ∈ In : c ∈ (ak, bk)} and β := {s ∈ In : c ̸∈ (as, bs)}. Obviously, due to the construction, we have that j ∈ α ̸= ∅, α ∪ β = In, and α ∩ β = ∅. Let us define ϕk := l−1 k (c) for every k ∈ α. It is obvious that 0 = l−1 k (ak) < ϕk = l−1 k (c) < l−1 k (bk) = 1, ∀ k ∈ α. We then obtain that 1 = L−1(c) = ∑ i∈In l−1 i (c) = ∑ k∈α l−1 k (c) + ∑ s∈β l−1 s (c) = ∑ k∈α l−1 k (c)︸ ︷︷ ︸ positive term + ∑ s∈β l−1 s (c) > ∑ s∈β l−1 s (c). (1) A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2453 Consequently, we derive that l−1 s (c) < 1 for any s ∈ β. Since c ̸∈ (as, bs) for any s ∈ β and l−1 s (c) < 1, due to the definition of the function l−1 s (y), we must have that l−1 s (c) = 0 for any s ∈ β. Equivalently, this means that lk(ϕk) = c ≤ as = ls(0), ∀ k ∈ α and ∀ s ∈ β. Moreover, since ∑ s∈β l−1 s (c) = 0, it follows from (1) that L−1(c) = ∑ i∈In l−1 i (c) = ∑ k∈α l−1 k (c) + ∑ s∈β l−1 s (c)︸ ︷︷ ︸ zero terms = ∑ k∈α l−1 k (c) = ∑ k∈α ϕk = 1. Hence, the flow ϕ = (ϕ1, ϕ2, · · · , ϕn) which is defined as follows ϕk := l−1 k (c) for every k ∈ α and ϕk := 0 for every k ∈ β = In \ α is user equilibrium and it is unique due to the uniqueness of the point c. This completes the proof. 3.1. Discrete User Equilibrium The definition of user equilibrium, as it was introduced [6, 7, 30] and studied in the literature since then, assumes that the traffic flow can be represented as a positive real number. The advantage of this representation is that it can be infinitely divided into smaller flows and thus we can always obtain the exact value of flow distribution that creates the user optimum. On the other hand this is just an approximation of the situation in real life scenarios, where for transportation networks individual vehicles can not be split and more over they can have varying sizes. The same can be said for information networks and parallel processing in relation respectively to the packages and the processes that run in parallel. To address these situations, in what follows, we will introduce a notion of user equilib- rium for Discrete Multi-type flow. An additional advantage of this representation is that the resulting discrete structures could be algebraically recognized in a manner similar to [10] for crisp graphs and [17], [16] for fuzzy structures. We will consider again a network with n parallel links, In = {1, 2, . . . , n}, where constants c1, . . . , cn, represent the cost of using the link i, for i = 1, . . . , n, for a transportation network this can be for example, the transit time of a unit traffic through the link i. The flow is given by a flow-vector ϕ = (ϕ1, ϕ2, . . . , ϕN ), ϕi > 0, N ≥ n, where ϕi is the size of the packet or vehicle i. We assume that all flow is distributed among all n links and denote the total flow size by X = N∑ i=1 ϕi. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2454 The elementary flow of each type is unsplittable in the sense that a vehicle or a packet ϕk is routed in whole along one and only one link i = 1, 2, . . . , n. Hence it holds n∑ k=1 N∑ i=1 δikϕ (k) i = X , where δik = { 1, if ϕi is routed along the link k 0, otherwise. In order to introduce the user equilibrium from the discrete case we will consider the particular case of two links, I2 = {1, 2}. Let X = {ϕ1, ϕ2, . . . , ϕN} be a flow-set, ϕi ∈ R+. Let PX 2 be a partition of X into two subsets X ′ and X ′′, where X ′ ̸= ∅, X ′′ ̸= ∅, X ′ ∪X ′′ = X, X ′ ∩X ′′ = ∅, and X ′′ = X \X ′. To further simplify, we assume that the latency functions lk(x) : [0, T ] → R, k ∈ In, T = ∑N i=1 ϕi of the two links, are given by lk(x) = cix, k = 1, 2. Hence, according to this setup, the user equilibrium can be described as the partition PX 2 that minimizes the difference between the time needed for each of the two flow subsets X ′ and X ′′ to travel across the two links. In other words, to find the user equilibrium one must solve the optimization problem min PX 2  ∣∣∣∣∣ck ∑ ϕi∈X′ δikϕi − ck ∑ ϕi∈X′′ δikϕi ∣∣∣∣∣  , k = 1, 2 with ϕi > 0. Consequently, the discrete user equilibrium does not equalize the link delays as in the continuous case, rather than minimize the absolute difference between them. This can be further generalized for more than two parallel links by minimizing the sum of absolute differences between all pairs of links delays. Moreover, the link latency function can be further enhanced by adding a maximum capacity and a constant toll price. Hence, if we denote by Ri, i ∈ In, the capacity of the link i, it can be assumed that the flow on the link i cannot exceed Ri, that is N∑ i=1 δikϕ (k) i ≤ Ri, k = 1, 2, . . . , n. If we additionally assume that the price of sending the flow through a link i = 1, 2, . . . , n is increased by a constant toll price pi, i = 1, 2, . . . , n. Then the delay on each link is given by ck N∑ i=1 δikϕi + pk, k = 1, 2, . . . , n. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2455 4. System Optimum Our next step is to investigate the properties of the system optimum. The networks we will examine from now on are assumed to be differentiable. We start with the following important result. Proposition 2. Consider a network Nn = (l1(x), . . . , ln(x)), then for every i, j ∈ In we have li(ϕi) + ϕil ′ i(ϕi) = lj(ϕj) + ϕjl ′ j(ϕj). provided that ϕ = (ϕ1, . . . , ϕn) ∈ Int(Sn−1) is system optimum of the network. Proof. Let (ϕ1, · · · , ϕi, · · · , ϕj , · · ·ϕn) ∈ intSn−1. The total delay of the network at this flow is T = ϕ1l1(ϕ1) + · · ·+ ϕili(ϕi) + · · ·+ ϕjlj(ϕj) + ϕnln(ϕn). For 0 < ϵ < 1, the total delay of the network at the flow x+ϵ,−ϵ {i,j} = (ϕ1, · · · , ϕi + ϵ, · · · , ϕj − ϵ, · · ·ϕn) ∈ intSn−1 is T+ϵ = ϕ1l1(ϕ1) + · · ·+ (ϕi + ϵ)li(ϕi + ϵ) + · · ·+ (ϕj − ϵ)lj(ϕj − ϵ) + · · ·+ ϕnln(ϕn). The delay T+ϵ is less than the delay T if the difference T+ϵ − T = (ϕi + ϵ)li(ϕi + ϵ)− ϕili(ϕi) + (ϕj − ϵ)lj(ϕj − ϵ)− ϕjlj(ϕj) = (ϕi + ϵ)li(ϕi + ϵ)− (ϕi + ϵ)li(ϕi) + ϵli(ϕi) + (ϕj − ϵ)lj(ϕj − ϵ)− (ϕj − ϵ)lj(ϕj)− ϵlj(ϕj) = (ϕi + ϵ)[li(ϕi + ϵ)− li(ϕi)] + ϵli(ϕi) − (ϕj − ϵ) [lj(ϕj)− lj(ϕj − ϵ)]− ϵlj(ϕj) is negative. By dividing with ϵ and taking the limit with ϵ → 0, the above quantity becomes li(ϕi) + ϕil ′ i(ϕi)− lj(ϕj)− ϕjl ′ j(ϕj). If this is negative, the marginal difference T+ϵ−T is negative, and therefore we will obtain a better total latency by removing flow from ϕj and adding it to ϕi. Hence, at any given flow as above, if we reduce the flow ϕj by ϵ while at the same time increase the flow ϕi by the same amount we will obtain a better total delay if li(ϕi) + ϕil ′ i(ϕi) < lj(ϕj) + ϕjl ′ j(ϕj). (2) Similarly we can consider the total delay of the flow x−ϵ = (ϕi − ϵ, ϕj + ϵ) ∈ S1 A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2456 as follows T−ϵ = (ϕi − ϵ)li(ϕi − ϵ) + (ϕj + ϵ)lj(ϕj + ϵ). In this case for the new delay T−ϵ to be less than T , the difference T−ϵ − T must be negative and using the same syllogism it turns out that the new total delay T−ϵ − T is lower than T if the quantity −li(ϕi)− ϕil ′ i(ϕi) + lj(ϕj) + ϕjl ′ j(ϕj) is negative. Therefore, if we reduce the flow ϕi by ϵ while at the same time increase the flow ϕj by the same amount we will obtain a better total delay if li(ϕi) + ϕil ′ i(ϕi) > lj(ϕj) + ϕjl ′ j(ϕj). (3) By consider both Equations 2 and 3 we deduce that an optimal flow (ϕi, ϕj) ∈ IntS1 implies li(ϕi) + ϕil ′ i(ϕi) = lj(ϕj) + ϕjl ′ j(ϕj), (4) which completes the proof. We can generalize the above as follows. Theorem 1. Consider a network Nn = (l1(x), . . . , ln(x)), then it holds li(ϕi) + ϕil ′ i(ϕi) = lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0 and li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi = 0, ϕj > 0, provided that ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is system optimum of the network. Proof. We only have to consider the case of a system optimum ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 on Nn such that there exists an i ∈ In with ϕi = 0. Using a similar argument as in the previous proposition we get that if there exists any j ∈ In such that li(ϕi) + ϕil ′ i(ϕi) < lj(ϕj) + ϕjl ′ j(ϕj), (5) then we will achieve lower total delay by ϵ-reducing ϕj while at the same time ϵ-increasing ϕi. Since x ∈ Sn−1 is system optimum this is not possible. Thus, taking also into account that ϕi = 0, it must hold li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi = 0 and ϕj > 0. Now, for differentiable latency functions li(x), we construct the following functions pi(x) = li(x) + xl′i(x). In this way, for every network Nn = (l1(x), . . . , ln(x)), we construct a corresponding (Pigovian) network PNn = (p1(x), . . . , pn(x)). Theorem 1 is then reformulated to describe the relationship between the two networks. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2457 Theorem 2. Consider a network Nn = (l1(x), . . . , ln(x)) and a flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1, then if ϕ is system optimum of Nn it is also user equilibrium of PNn = (p1(x), . . . , pn(x)). Proposition 1 allows us now the achieve the following uniqueness result. Proposition 3. A convex network Nn = (l1(x), . . . , ln(x)) has a unique system optimum. Proof. All the latency functions are differentiable in [0, 1], hence the total delay n∑ i=1 ϕili(ϕi) has at least one minimum. Therefore, there is at least one system optimum of Nn. Moreover, we know that the latency functions are differentiable and convex and so pi(x) will be strictly increasing and continuous. Thus, according to Proposition 1 there is a unique user equilibrium of PNn = (p1(x), . . . , pn(x)). Ther result follows by applying Theorem 2. The following characterization of system optimums is achieved by combining the pre- vious results. Theorem 3. Given a convex network Nn = (l1(x), . . . , ln(x)) and a flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 the following conditions are equivalent. i) The flow ϕ is the system optimum of Nn. ii) The flow ϕ is the user equilibrium of PNn = (p1(x), . . . , pn(x)). iii) It holds li(ϕi) + ϕil ′ i(ϕi) = lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0 and li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In, with ϕi = 0, and ϕj > 0. iv) It holds lk(ϕk) + ϕkl ′(ϕk) = min i∈In {li(ϕi) + ϕil ′ i(ϕi)}, for every ϕk > 0. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2458 5. Wardrop Optimal Networks Flows that are at the same time system optimum and user equilibrium are called Wardrop optimal flows (WOFs). In this section we will investigate networks admitting such flows i.e., Wardrop optimal networks (WONs). First we need to identify some nec- essary conditions for system optimums. By applying Theorem 3 we get the following two propositions. Proposition 4. If the flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is WOF of the network Nn = (l1(x), . . . , ln(x)) then it holds i) ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In, with ϕi, ϕj > 0, ii) li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In, with ϕi = 0 and ϕj > 0. Proposition 5. If the flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is user equilibrium of the convex network Nn = (l1(x), . . . , ln(x)) and the following conditions hold i) ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In, with ϕi, ϕj > 0, ii) li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In, with ϕi = 0 and ϕj > 0, then the flow ϕ is also system optimum. Combining the above propositions we arrive at the following result. Theorem 4. If the flow (ϕ1, . . . , ϕn) ∈ Sn−1 is a user equilibrium of a convex network Nn = (l1(x), . . . , ln(x)), then the following conditions are equivalent i) It holds ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, and li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi = 0, and ϕj > 0. ii) The flow ϕ is a system optimum. On the other hand, we get the following requirements for a flow that is a system optimum. Proposition 6. If the flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is system optimum of a network Nn = (l1(x), . . . , ln(x)) and it holds li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, then it is also a user equilibrium. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2459 Hence we can arrive at the next Theorem. Theorem 5. Given a flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 of a convex network Nn = (l1(x), . . . , ln(x)), the following conditions are equivalent: i) The flow ϕ Wardrop optimal. ii) It holds: li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi = 0, and ϕj > 0. If we only consider internal flows, then we get the following corollary as a particular case of the above result. Corollary 1. Given a flow ϕ = (ϕ1, . . . , ϕn) ∈ Int(Sn−1) of a convex network Nn = (l1(x), . . . , ln(x)), the following conditions are equivalent: i) The flow ϕ Wardrop optimal. ii) It holds: li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. The next result provides some insight on the effect of appropriate transformations on the latency functions of our networks. Theorem 6. If the flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is the WOF of a convex network Nn = (l1(x), . . . , ln(x)), then it is also WOF of the network f(Nn) = (f(l1(x)), . . . , f(ln(x))), where f(x) : R → R is a a continuous, strictly increasing and convex function. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2460 Proof. Since ϕ is WOF of Nn we get li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, (6) from where we can derive the first item of Theorem 5 for the set f(Nn): f(li(ϕi) = f(lj(ϕj)), for every i, j ∈ In with ϕi, ϕj > 0. Since ϕ is also optimal flow of Ln, we have ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, (7) and li(0) ≥ lj(ϕj) + ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi = 0, and ϕj > 0. (8) For ϕi, ϕj > 0, it holds ϕi(f(li(ϕi))) ′ = ϕif ′(li(ϕi))l ′ i(ϕi) (6),(7) = ϕjf ′(lj(ϕj))l ′ j(ϕj) = ϕj(f(lj(ϕj))) ′. (9) Hence the second condition of Theorem 5 is satisfied by ϕ. Now let ϕi = 0 and ϕj > 0. Since f is increasing, from Equation 8 we obtain f(li(0)) ≥ f(lj(ϕj) + ϕjl ′ j(ϕj)). We need to prove the third condition of Theorem 5 which is f(li(0)) ≥ f(lj(ϕj)) + ϕj (f(lj(ϕj))) ′ , for every i, j ∈ In with ϕi = 0, and ϕj > 0. Therefore, it suffices to show that f(lj(ϕj) + ϕjl ′ j(ϕj)) ≥ f(lj(ϕj)) + ϕj (f(lj(ϕj))) ′ ⇒ f(lj(ϕj) + ϕjl ′ j(ϕj))− f(lj(ϕj)) ≥ ϕjf ′(lj(ϕj)) l ′ j(ϕj) ⇒ f(lj(ϕj) + ϕjl ′ j(ϕj))− f(lj(ϕj)) ϕjl′j(ϕj) ≥ f ′(lj(ϕj)). If we set a = lj(ϕj) and b = ϕjl ′ j(ϕj), the last inequality can be rewritten as f(a+ b)− f(a) b ≥ f ′(a). Since b > 0, the left hand side of the above inequality is the average increase of f(x) at the interval [a, a+b] and the right hand side is the rate of change of f(x) at a. Therefore, from the convexity of f(x), we deduce that the inequality holds true. The proof is completed. The above Theorem shows that WOFs are preserved by continuous, strictly increasing and convex functions. Nevertheless, this does not hold for a system optimum which is not user equilibrium. Indeed, as it shown in Example 1 the system optimum of the network of Figure 1 does not remain the same after taking the image of N via the continuous, strictly increasing and convex function f(x) = x2. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2461 Example 2. Let us examine the linear network W1 = {x 2 , x 3} shown in Fig. 2a. The system optimum that minimizes the average delay of the network and the user equilibrium that equates delay on the two links are identical and equal with ϕ = (0.4, 0.6). Similarly for the quadratic network W2 = {4x2, x2} of Fig. 2b, it can easily be verified that the system optimum and the user equilibrium are identical and equal with ϕ = (1/3, 2/3). l1(x) = x/2 l2(x) = x/3 (a) W1 : Linear Wardrop optimal network l1(x) = 4x2 l2(x) = x2 (b) W2 : Quadratic Wardrop optimal network Figure 2: Two Wardrop optimal networks The next corollaries illustrate the effect of some fundamental transformations onWOFs. Corollary 2. If a flow ϕ ∈ Sn−1 is WOF of a convex network Nn = (l1(x), . . . , ln(x)) then it is also a WOF of the following networks. i) Nn + b = (l1(x) + b, . . . , ln(x) + b), for every b > 0. ii) aNn = (al1(x), . . . , aln(x)), for every a > 0. For the particular case of internal flows, we can also state the following. Corollary 3. If the flow ϕ = (ϕ1, . . . , ϕn) ∈ intSn−1 is the WOF of a convex network Nn = (l1(x), . . . , ln(x)), then it is also WOF of f(Nn) = (f(l1(x)), . . . , f(ln(x))), where f(x) : R → R is a continuous, strictly increasing function. Next we examine networks with identical latency functions. Proposition 7. If the latency functions across all links of a network are identical then the WOF is uniformly distributed. Proof. It suffices to observe that ϕ = ( 1n , . . . , 1 n) is the WOF of Nn. Similarly we have Proposition 8. Any internal flow p = (p1, · · · , pn) ∈ intSn−1 is the WOF of Nn = (ϕ1 p1 , . . . , ϕn pn ). This result together with Corollary 3, gives the following proposition. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2462 Proposition 9. An internal flow p = (p1, · · · , pn) ∈ intSn−1 is the WOF of Nn = (f(ϕ1 p1 ), . . . , f(ϕn pn )), where f(x) is any continuous, strictly increasing function. By using Theorem 5 we obtain the next proposition. Proposition 10. If a flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is at the same time, WOF of the convex networks Nn = (l1(x), . . . , ln(x)) and Nn = (l1(x), . . . , ln(x)) then it is also WOF of NnNn = (l1(x)l1(x), . . . , ln(x)ln(x)). Proof. Since ϕ is WOF of the networksNn andNn, from the first condition of Theorem 5 for the two networks we have li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, (10) and li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (11) By multiplication of the two we get the first condition for the network NnNn: li(ϕi)li(x) = lj(ϕj)lj(x), for every i, j ∈ In with ϕi, ϕj > 0, (12) which establishes the first condition of Theorem 5 for NnNn. From the second condition of Theorem 5 for the networks Nn and Nn we have ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, (13) and ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (14) To prove the second condition for NnNn we need to prove that for every ϕi, ϕj > 0 it holds that ϕi(li(ϕi)li(ϕi)) ′ = ϕj(lj(ϕj)lj(ϕj)) ′, (15) or equivalently ϕil ′ i(ϕi)li(ϕi) + ϕili(ϕi)l ′ i(ϕi) = ϕjl ′ j(ϕj)lj(ϕj) + ϕjlj(ϕj)l ′ j(ϕj). (16) By multiplying Equations 11 and 13 we get ϕil ′ i(ϕi)li(ϕi) = ϕjl ′ j(ϕj)lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (17) By multiplying Equations 10 and 14 we get ϕili(ϕi)l ′ i(ϕi) = ϕjlj(ϕj)l ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (18) Equation 16 is now obtained by adding Equations 17 and 18. A. Kalampakas / Eur. J. Pure Appl. Math, 17 (4) (2024), 2448-2466 2463 Now, for the remaining part of the proof, from the last condition of Theorem 5 for Nn and Nn, it holds that for every i, j ∈ In, with ϕi = 0 and ϕj > 0 li(0) ≥ lj(ϕj) + ϕj l ′ j(ϕj) and li(0) ≥ lj(ϕj) + ϕj l ′ j(ϕj). By multiplying the above inequalities we get li(0)li(0) ≥ lj(ϕj)lj(ϕj) + lj(ϕj)ϕj l ′ j(ϕj) + lj(ϕj)ϕj l ′ j(ϕj) + ϕj l ′ j(ϕj)ϕj l ′ j(ϕj). (19) From this, we get the third condition of Theorem 5 for the network NnNn, which is: li(0)li(0) ≥ lj(ϕj)lj(ϕj) + ϕj ( lj(ϕj)lj(ϕj) )′ , (20) or equivalently li(0)li(0) ≥ lj(ϕj)lj(ϕj) + ϕjl ′ j(ϕj)lj(ϕj) + ϕj lj(ϕj)ϕjl ′ j(ϕj). (21) In a similar way, we will establish the next proposition. Proposition 11. If the flow ϕ = (ϕ1, . . . , ϕn) ∈ Sn−1 is WOF of the convex networks Nn = (l1(x), . . . , ln(x)) and Nn = (l1(x), . . . , ln(x)), then it is also WOF of Nn +Nn = (l1(x) + l1(x), . . . , ln(x) + ln(x)). Proof. Since ϕ is WOF of the networksNn andNn, from the first condition of Theorem 5, we have that for the two networks it holds li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0, (22) and li(ϕi) = lj(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (23) By adding the two we get the first condition for the network Nn +Nn li(ϕi) + li(x) = lj(ϕj) + lj(x), for every i, j ∈ In with ϕi, ϕj > 0, (24) which settles the first condition of Theorem 5 for Nn + Nn. For the next condition of Theorem 5, assume that for the networks Nn and Nn we have ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (25) and ϕil ′ i(ϕi) = ϕjl ′ j(ϕj), for every i, j ∈ In with ϕi, ϕj > 0. (26) By adding Equations 25 and 26 we get ϕil ′ i(ϕi) + ϕil ′ i(ϕi) = ϕjl ′ j(ϕj) + ϕjl ′ j(ϕj), (27) BIBLIOGRAPHY 2464 or equivalently ϕi(li(ϕi) + li(ϕi)) ′ = ϕj(lj(ϕj) + lj(ϕj)) ′, (28) as desired. Now for the remaining part of the proof, if for Nn and Nn it holds li(0) ≥ lj(ϕj) + ϕj l ′ j(ϕj) and li(0) ≥ lj(ϕj) + ϕj l ′ j(ϕj), for every i, j ∈ In with ϕi = 0 and ϕj > 0, then by adding the above inequalities we get li(0) + li(0) ≥ lj(ϕj) + lj(ϕj) + ϕj(l ′ j(ϕj) + l ′ j(ϕj)). (29) From the above, the last condition of Theorem 5 for the network Nn +Nn follows. 6. Conclusion and Future Work We have investigated directed, parallel networks with congestion externalities and their equilibriums. We identified necessary and sufficient conditions for achieving the system optimum and we introduced Wardrop optimal networks admitting the same user and sys- tem equilibrium. In addition we establish a characterization of Wardrop optimal networks which allows us to identify important closure properties of the related class of networks. Future research directions deriving from the results presented in this paper include the investigation of Wardrop optimal flows in networks with more general underlying graph structures by analyzing all potential paths from the origin to the destination, similarly to the approach introduced in [15]. Additionally, this framework could be utilized for the algebraic recognition of such networks, thereby enabling the use of graph recognizability to identify graph properties, such as determining if a graph is Eulerian [9] and k-colorable [11]. Bibliography [1] D. Acemoglu and A. Ozdaglar. Competition and efficiency in congested markets. Mathematics of Operations Research, 32(1):1 – 31, 2007. [2] A. Bagdasaryan, A. Kalampakas, and M. Saburov. Dynamic traffic flow assignment on parallel networks. In New Technologies, Development and Application VI, pages 702–711. Springer Nature Switzerland, 2023. [3] A. Bagdasaryan, A. Kalampakas, and M. Saburov. Discrete-time replicator equations on parallel neural networks. In Engineering Applications of Neural Networks, pages 492–503. Springer Nature Switzerland, 2024. [4] A. Bagdasaryan, A. Kalampakas, and M. Saburov. Dynamics of replicator equations on wardrop optimal networks. Russian Mathematical Surveys, 79:176–178, 2024. BIBLIOGRAPHY 2465 [5] A. Bagdasaryan, A. Kalampakas, M. Saburov, and S. Spartalis. Optimal traffic flow distributions on dynamic networks. In Engineering Applications of Neural Networks, pages 178–190. Springer Nature Switzerland, 2023. [6] M. J. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. RAND Corporation, 1955. [7] S. Dafermos and F. Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards-B. Mathematical Sciences, 73(2):91 – 118, 1969. [8] R. Hwang, M. Gen, and H. Katayama. A comparison of multiprocessor task schedul- ing algorithms with communication costs. Computers and Operations Research, 35(3):976–993, 2008. Part Special Issue: New Trends in Locational Analysis. [9] A. Kalampakas. The syntactic complexity of eulerian graphs. Lecture Notes in Com- puter Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4728 LNCS:208 – 217, 2007. [10] A. Kalampakas. Graph automata: The algebraic properties of abelian relational graphoids. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7020 LNCS:168 – 182, 2011. [11] A. Kalampakas. Graph automata and graph colorability. European Journal of Pure and Applied Mathematics, 16(1):112–120, Jan. 2023. [12] A. Kalampakas and E. Aifantis. Random walk on graphs: An application to the double diffusivity model. Mechanics Research Communications, 43:101 – 104, 2012. [13] A. Kalampakas, A. Bagdasaryan, M. Saburov, and S. Spartalis. User equilibrium and system optimality conditions for flow distributions on congested networks. In En- gineering Applications of Neural Networks, pages 203–214. Springer Nature Switzer- land, 2023. [14] A. Kalampakas, A. Bagdasaryan, M. Saburov, and S. Spartalis. User equilibrium and system optimality conditions for flow distributions on congested networks. In Engi- neering Applications of Neural Networks, pages 203 – 214. Springer Nature Switzer- land, 2023. [15] A. Kalampakas and S. Spartalis. Hyperoperations on directed graphs. Journal of Discrete Mathematical Sciences and Cryptography, 27(3):1011–1025, 2024. [16] A. Kalampakas, S. Spartalis, and L. Iliadis. Syntactic recognizability of graphs with fuzzy attributes. Fuzzy Sets and Systems, 229:91 – 100, 2013. BIBLIOGRAPHY 2466 [17] A. Kalampakas, S. Spartalis, L. Iliadis, and E. Pimenidis. Fuzzy graphs: Algebraic structure and syntactic recognition. Artificial Intelligence Review, 42(3):479 – 490, 2014. [18] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control for communication net- works: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49(3):237–252, 1998. [19] F. H. Knight. Some Fallacies in the Interpretation of Social Cost. The Quarterly Journal of Economics, 38(4):582–606, 1924. [20] Y.A. Korilis, A.A. Lazar, and A. Orda. Achieving network optima using stackelberg routing strategies. IEEE/ACM Transactions on Networking, 5(1):161–173, 1997. [21] S.H. Low and D.E. Lapsley. Optimization flow control. i. basic algorithm and con- vergence. IEEE/ACM Transactions on Networking, 7(6):861–874, 1999. [22] V. Morandi. Bridging the user equilibrium and the system optimum in static traffic assignment: a review. 4OR, 22(1):89 – 119, 2024. [23] A. Nagurney. Spatial price equilibrium, pages 3646 – 3652. Springer US, Boston, MA, 2009. [24] A. Orda, R. Rom, and N. Shimkin. Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking, 1(5):510–521, 1993. [25] M. Patriksson. The Traffic Assignment Problem: Models and Methods. VSP, Utrecht, The Netherlands, 1994. [26] A. C. Pigou. The Economics of Welfare. Macmillan, London, 1920. [27] M. Saburov. On replicator equations with nonlinear payoff functions defined by the ricker models. Adv. Pure Appl. Math., 12:39–156, 2021. [28] S. Sanghavi and B. Hajek. Optimal allocation of a divisible good to strategic buy- ers. In 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601), volume 3, pages 2748–2753 Vol.3, 2004. [29] M.K. Sharma, Sadhna, A.K. Bhargava, S. Kumar, L. Rathour, L.N. Mishra, and S. Pandey. A fermatean fuzzy ranking function in optimization of intuitionistic fuzzy transportation problems. Advanced Mathematical Models and Applications, 7(2):191– 204, 2022. [30] J. G. Wardrop. Some theoretical aspects of road traffic research. Proceedings of the Institute of Civil Engineers, Part II, 1, 325-378, 3:325–362, 1952.