Bounding the Inefficiency of Risk-Averse Selfish Routing with Nonadditive CVaR

1 Introduction

Modern AI-driven systems increasingly rely on large populations of autonomous agents that make decentralized decisions under uncertainty, including packet routing in communication networks, traffic assignment in intelligent transportation systems, and task allocation in distributed robotic and cloud platforms. In such systems, agents are not only sensitive to average performance but are particularly averse to rare yet severe delays that can critically degrade quality of experience (QoE), safety, or reliability. For example, in communication networks, variability in packet delays-commonly referred to as jitter-disrupts interactive audio, video streaming, and real-time services, leading agents to abandon sessions or reduce quality [Stockhammer, 2011; Jiang et al., 2012; Elbamby et al., 2019]. Similarly, in traffic networks, time variability undermines confidence in arrival time predictions, increasing the risk of arriving late or early, both of which incur substantial costs [Ord´onez and Stier-Moses, 2010; Zang et al., 2018a; Zang et al., 2018b; Jian et al., 2024; Zang et al., 2026a].

∗Corresponding author: David Z.W. Wang.

These rare but severe delays, often referred to as tail latency, have been identified as a dominant performance bottleneck in large-scale systems and a key driver of agent behavior. To capture sensitivity to tail latency, a growing body of work in AI, operations research, and economics has adopted riskaverse decision criteria. Among these, Conditional Value-atRisk (CVaR) has emerged as a principled and widely used measure for modeling tail-risk aversion, with applications in robust optimization, safe reinforcement learning, and riskaware planning. Unlike mean-variance criteria, CVaR explicitly captures the expected severity of tail events [Rockafellar and Uryasev, 2002], making it well suited for agents seeking to hedge against tail latency rather than symmetric variability.

When risk-averse agents interact in a shared network, their individual attempts to avoid tail latency generate congestion externalities and significantly degrade system efficiency. A central question in multi-agent systems and algorithmic game theory is how to quantify and bound this inefficiency. One such measure is the price of risk aversion (PRA) [Lianeas et al., 2019], defined as the worst-case ratio between the total system cost at a risk-averse equilibrium and that at a riskneutral equilibrium.

Prior work on PRA has largely focused on additive meanvariance objectives, which enable analysis via classical techniques such as alternating paths but fail to capture tail latency and rely on additivity assumptions that do not hold for CVaR, which is inherently nonadditive. In this paper, we study nonatomic selfish routing games in which agents minimize the CVaR of path latency. CVaR admits a clear behavioral interpretation for routing under tail risk:

How much time should an agent budget for common risks, and how severe should the agent expect delays be under tail risk?

Because delays in the networks depend endogenously on aggregate traffic through congestion effects, individual routing decisions cannot be analyzed in isolation. Instead, agents' risk-averse shortest path problems are embedded in a noncooperative game in which each agent seeks to minimize its own CVaR-based latency, namely selfish routing behavior. The resulting equilibrium concept extends the classical Wardrop equilibrium [Wardrop, 1952; Beckmann et al., 1956] to stochastic networks with risk-averse agents. Our key insight is that worst-case inefficiency under CVaR is governed by a dependence structure we term tail risk concentration, under which extreme delays across network components are synchronized. We show that although CVaR is nonadditive in general, it becomes additive under this worst-case dependence, enabling tight inefficiency analysis.

The main contributions are summarized as follows.

• Tail-risk-averse routing model. We study nonatomic selfish routing games in which agents minimize the Conditional Value-at-Risk (CVaR) of path latency, capturing aversion to rare but severe delays that are not adequately modeled by mean-variance or standard deviation rule.
• Tail risk concentration and CVaR. We formalize tail risk concentration as a worst-case dependence structure under which extreme delays across network components are synchronized. We prove that CVaR penalizes this structure and that tail risk concentration maximizes pathlevel CVaR aggregation. Leveraging this insight, we show that although CVaR is nonadditive in general, it becomes additive under tail risk concentration. This result enables a surrogate edge-based formulation that coincides with true path-level CVaR, making tight inefficiency analysis feasible.
• Tight bounds on the price of risk aversion. We show that for arbitrary latency functions, PRA ≤ 1 + SCVaRmax e · ⌈(n-1)/2⌉, implying that the PRA grows linearly with both the maximum edge-level upper-tail cost and the network size. We further establish the tightness of this bound by constructing a family of Braesstype networks with an asymptotically lower bound.
• Implications for multi-agent systems. Our results provide worst-case performance guarantees for decentralized, risk-averse routing, clarifying how tail-risk aversion of agents amplifies congestion externalities.

2 RelatedWork

Increasing efforts have been devoted to selfish routing under risk with risk-averse agents. For example, [Ord´onez and Stier-Moses, 2010] used a constant safety margin to represent agents' risk aversion and analyzed routing games under stochastic delays, establishing connections between riskaverse equilibria and percentile-based equilibria. Focusing on models closer to the present setting, [Nikolova and StierMoses, 2014] established the existence of a mean-risk traffic assignment when travel time variability is represented by standard deviations. [Slumbers et al., 2023] developed a game-theoretic framework in which agents trade off expected rewards against variability while accounting for others' actions. Please refer to [Cominetti, 2015; Zang et al., 2022] for comprehensive reviews of risk-averse selfish routing models.

However, the network efficiency of risk-averse selfish routing has received limited attention, despite extensive work on the price of anarchy (PoA), defined as the worst-case ratio between the cost of a Nash equilibrium and that of the socially optimal solution [Roughgarden and Tardos, 2002; Roughgarden, 2003; Koutsoupias and Papadimitriou, 2009]. The PoA has been studied under increasingly general latency functions and network structures [Correa et al., 2004; Roughgarden, 2006; Correa et al., 2008]. [Nikolova and Stier-Moses, 2014; Zhuang et al., 2023] extended this framework to routing games under stochastic delays and riskaversion of agents. Related but distinct from the PoA, the price of risk captures how perturbations or random player ordering affect equilibrium results [Balcan et al., 2013].

The studies most related to this paper are [Lianeas et al., 2016; Lianeas et al., 2019; Cole et al., 2018], which adopt a mean-variance framework to model risk-averse selfish routing and derive inefficiency bounds using the price of risk aversion (PRA). However, as noted by [Nikolova and StierMoses, 2014], combining mean latency with variance or standard deviation is difficult to interpret since they have different units, complicating economic interpretation. Moreover, variance-based measures capture only symmetric fluctuations and therefore fail to consider tail latency, whereas the PRA is inherently concerned with worst-case inefficiency.

3 CVaR-Based Selfish Routing

In this section, we introduce tail risk and its concentration, show that CVaR penalizes tail risk concentration, and formulate a CVaR-based selfish routing model.

We consider a network G = (V,E) with |V | = n, total demand d, and W source-sink pairs. For expositional convenience, we set the demand to d = 1 in Section 5.2 and set it to be the general case in Section 5.3. Let R denote the set of all feasible paths. Users' routing decisions are represented by a nonnegative path-flow vector q = (qr)r∈R satisfying ∑r∈R qr = d. The induced flow on an edge e ∈ E is ve = ∑r∋e qr. The feasible flow set is Ω = {q ≥ 0 | Λq = d, ∆q = v}, where ∆ = [δer] is the edge-path incidence matrix with δer = 1 if path r uses edge e and 0 otherwise, and Λ = [λrw] is the source-sink-path incidence matrix with λrw = 1 if path r connects source-sink pair w ∈ W and 0 otherwise. Throughout this section, we use the term latency variability to encompass travel time, queuing time, and delay variability across various network settings.

3.1 Tail Risk and Tail Risk Concentration

Latency variability in networks does not arise arbitrarily. Rather, it originates from identifiable sources of risks acting on both the supply side and the demand side. This observation applies broadly to road networks [Zang et al., 2022], communication networks [Haque et al., 2015], cloud computing systems [Li et al., 2014], and other congestion-prone service networks [Dean and Barroso, 2013]. Figure 1 conceptually illustrates how these heterogeneous sources of risks jointly induce latency variability. Let Ξ denote the set of all sources of risks contributing to latency variability.

Among these risk sources, we formally distinguish τ-tail risk in Definition 1, motivated by the notion of tail events developed in the finance and economic literature [Wang and Zitikis, 2021]. While multiple risks may occur with identical probabilities, not all of them are equally consequential. The way we define the τ-tail risk makes it to be the risk leading to the worst upper-tail realizations of latency with probability 1 - τ, as illustrated in Figure 1. This interpretation is theoretically supported by the following Proposition 1. Potential sources that can generate τ-tail risk include incidents, correlated demand surges, cascading failures, synchronized congestion, and resource contention. We will further elaborate this in Remark 1.

Definition 1 (τ-tail risk). A τ-tail risk of latency x is a risk ξ ∈ Ξ with P(ξ) = 1 - τ such that x(ω) ≥ x(ω′ ) holds for all ω ∈ ξ and ω′ ∈ ξ c , where ξ c denotes the complement of ξ.

A path typically consists of multiple edges, so edge-level tail risk will aggregate to the path level. If a path is properly diversified, agents may benefit from diversification such that path-level tail risk is lower than the sum of edge-level risks. However, consider a path composed of several edges that share a common tail risk ξ. When tail risk ξ occurs-such as congestion, hardware faults, or wireless interference-each edge simultaneously realizes its worst latency. This represents the most problematic form of tail risk concentration in latency variability, as it leads to extreme delays. Such synchronized tail risk can cause severe congestion spillovers and impose substantial losses on both agents and the network as a whole. Definition 2 formalizes this worst-case scenario, in which edge-level tail risks are fully concentrated at the path level, following [Wang and Zitikis, 2021; Zang et al., 2026b].

Definition 2 (Tail risk concentration). For a path latency x, if its all edge latency shares a common τ-tail risk, we say it shows tail risk concentration.

Proposition 1 shows that among all risks with the same probability 1-τ , τ -tail risk of Definition 1 leads to the largest possible tail latency, while Lemma 1 characterizes the relationship between path-level tail risk and edge-level tail risk, thereby providing a mechanism through which edge tail risks aggregate to the path level.

Proposition 1 (τ-tail risk maximizes expected tail latency). Let x be a random variable and let Ux ∼ U[0, 1] be such that x = F -1 x (Ux) almost surely. For a τ-tail risk ξA, it can be defined as ξA := {Ux ≥ τ} with its indicator 1ξA . Then for every risk ξB ∈ Ξ with P(ξB) = 1 - τ , we have

Proof. Ux works because any random variable can be generated from a Uniform(0,1) random variable by applying its quantile function. By definition, E[1ξA - 1ξB ] = 0 and thus we have E[x(1ξA - 1ξB )] = E[(x - Q)(1ξA - 1ξB )] for all constant Q ∈ R. Let Q = F -1 x (τ) which is the τ-quantile of x and recall that we have x = F -1 x (Ux). If F -1 x (Ux) > Q, then Ux > τ, 1ξA = 1 and so E[(x-Q)(1ξA -1ξB )] ≥ 0; if F -1 x (Ux) < Q, then Ux < τ, 1ξA = 0 and so E[(x - Q)(1ξA - 1ξB )] ≥ 0; if F -1 x (Ux) = Q, then x-Q = 0 and so E[(x-Q)(1ξA -1ξB )] = 0. In summary, we have E[(x - Q)(1ξA - 1ξB )] = 0. So, E[x 1ξA ] ≥ E[x 1ξB ].

Lemma 1 (Common tail risk). The risk ξ is a τ-tail risk of path latency if ξ is a τ-tail risk of its all edge latency.

Proof. Consider all edges of a path share a common τ-tail risk source ξτ . First, assume that path r consists of only two edges, namely edge ea and edge eb. We first show that the tail risk ξτ is also a tail risk for path r. By definition, we have the following inequality for all scenarios ω ∈ ξτ and ω′ ∈ ξ c τ :

The above shows that ξτ is an τ-tail risk source of xa+xb. Next, consider a path r consisting of n edges, denoted by e1, . . . , en, which share a common tail risk. By induction, we conclude that ξτ is an τ-tail risk of x1 + · · · + xn. Namely, ξτ is an τ-tail risk of the path latency.

3.2 CVaRMinimization Penalizes Tail Risk Concentration

In the context of network latency, the Conditional Value at Risk (CVaR) at the confidence level τ can be defined as the conditional expectation of the latency x exceeding the corresponding Value at Risk (VaR). Namely,

where VaR is defined by a chance constraint at confidence level τ as follows [McNeil et al., 2015]:

Then, based on the above Equations (2) and (3) and previous works [Pflug, 2000; Rockafellar et al., 2000; Rockafellar and Uryasev, 2002], the defined CVaR can be equivalently written as the following minimization problem:

where [x]+ = max{0, x} and c is a constant.

Equation (2) shows that CVaR pays particular attention to the tail latency which is caused by τ-tail risk. Specifically, we can rewrite CVaR as follows.

where F is the cumulative distribution function (CDF) of x.

The first part, namely VaRτ(x), in CVaR of Eq. (5) considers the common latency that travellers could frequently encounter at the confidence level τ, while the second part, 1 1-τ ∫ 1 τ (F -1 (w)-F -1 (τ)) dw, is expected value of the tail latency with respect to VaRτ (x) where tail latency is actually caused by τ-tail risk. Consequently, for routing agents in networks, CVaR simultaneously addresses both questions: How much time should an agent budget for common risk, and how severe should the agent expect delays be under tail risk?

Theorem 2 shows that CVaR minimization penalizes tail risk concentration: for a given path, tail risk concentration across edges maximizes CVaR aggregation, while the subadditivity of CVaR ensures that the path-level CVaR is never greater than the sum of edge-based CVaRs.

Theorem 2. CVaR minimization penalizes tail risk concentration at path.

Proof. Consider a path r has n edges with xi, i = 1, ..., n as their latency and x1, ..., xn share a common τ-tail risk. Let ξτ be this common τ-tail risk. According to Lemma 1, then ξτ is also a τ-tail risk of this path latency x. Based on Proposition 1 and [Embrechts and Wang, 2015], we can derive the following dual representation of CVaR in Equation (4):

According to Proposition 1, we have E [x1ξτ ] ≥ E [x1ξB ] for tail risk ξτ with probability 1-τ . Consequently, by equation (6), we have CVaRτ (x) = E[x|ξτ ]. In other words, ξτ is the risk that makes Equation (6) hold without the maximization operator. Consequently, we have

Recalling the subadditivity of CVaR, we should have the inequality of CVaRτ (x) ≤ ∑ni=1 CVaRτ (xi). However, τ-tail risk concentration of x1, ..., xn makes such inequality become equality, thereby maximizing CVaR aggregation. In other words, CVaR minimization penalizes tail risk concentration at path. This complements the proof.

3.3 Selfish Routing with Nonadditive CVaR

Based on Theorem 2, each agent in a CVaR-based selfish routing model seeks to minimize the CVaR of its experienced path latency. In a network setting, such decentralized CVaR minimization induces a noncooperative routing game. We refer to the resulting equilibrium as a CVaR-based network equilibrium (CNE). Owing to the nonadditivity of CVaR, the CNE generally cannot be characterized through an additive path-cost or convex optimization formulation; instead, it admits a variational inequality (VI) formulation in Proposition 2 based on [Chen and Zhou, 2010].

Proposition 2 (VI formulation of CNE). A path flow vector q∗ ∈ Ω is said to be CNE path flow pattern if and only if it solves the following variational inequality problem:

4 Price of Risk Aversion

In this section, we define the price of risk aversion.

4.1 Preliminaries of Routing Equilibria for Agents

We denote a risk-neutral selfish routing instance by (G, d, l), where l specifies the latency functions. This notation represents the class of risk-neutral routing games in which agents minimize expected path latency. Under risk, we denote a corresponding risk-averse selfish routing instance by (G, d, l, Ξ, τ). This notation represents the class of riskaverse routing games in which agents minimize a CVaRbased latency criterion.

For (G, d, l), the path cost is deterministic and can be computed as the expected latency along a path r:

Let x = µ + σX where X is the standardized latency with CDF Φ(X); µ and σ represent the mean and standard deviation of x, respectively. We would have VaRτ(x) = µ + σ · Φ-1 X (τ) according to [Wu and Nie, 2011; Zang et al., 2024]. Consequently, CVaR at Eq. (5) can be rewritten as

Accordingly, for (G, d, l, Ξ, τ), CVaR of path r is given by

Then, based on [Wardrop, 1952] and [Chen and Zhou, 2010], Definition 3 describes risk-neutral network equilibrium (NE) and CVaR-based network equilibrium (CNE).

Definition 3 (Network equilibrium and CVaR-based network equilibrium). For risk-neutral users, at NE, all used paths have equal and minimal expected latency; for risk-averse users with CVaR-based criterion, at CNE, all used paths have equal and minimal CVaR of path latency.

4.2 Defining Price of Risk Aversion

To investigate the network inefficiency caused by risk-averse users, we use the total system cost, denoted by C, as the network performance metric to make a fair comparison between NE and CNE. Specifically, total cost is evaluated by

Let qx and qz be CNE flow vector and NE flow vector, respectively. Then, we can define the price of risk aversion (PRA) as the worst-case ratio of C(qx ) of CNE to C(qz ) of NE in Definition 4.

Definition 4 (Price of risk aversion in [Lianeas et al., 2019]). For an instance family F of a routing game under latency variability, the price of risk aversion (PRA) is given by

Such definition of PRA enables us to isolate the inefficiency arising from selfish behavior, as measured by the price of anarchy (PoA) [Roughgarden and Tardos, 2002; Roughgarden, 2003], from those resulted from risk aversion per se. In other words, the ways of defining PRA makes us focus on the network inefficiency due solely to risk aversion.

5 Bounds of PRA

This section bounds the PRA. The main challenge is due to the nonadditivity of CVaR and we tackle it by proving that CVaR is τ-additive for tail risk concentration in Theorem 4.

5.1 Alternating Path

The derivation of the upper bound of PRA depends on the alternating path constructed by [Lianeas et al., 2019].

Consider CNE flows qx and NE flows qz for instances (G, d, l, Ξ, τ) and (G, d, l), respectively. Then, for an edge e of G, we have the following terminologies:

• (qx , qz )-light if qx e ≤ qz e ;
• qz e > 0; (qx , qz )-heavy if qx > qz e ;
• (qx , qz )-null if qx e = qz e = 0.

Note that we do not need to consider the scenario of (qx , qz )-null for an edge as it can be removed from the network G due to no flow on both CNE and NE. Then, define two set of edges to partition of the edge set E as follows:

Under the assumption that every edge of the network at least carries positive flow in one of the equilibria qx and qz , we can have qz e > 0 for each e ∈ A and qx e > 0 for each e ∈ B. With these terminologies, we can have the definition of alternating path in Definition 5. Alternating paths allow us to exploit network structure to bound the PRA. Besides, there exists a alternating path for any instance (G, d, l, Ξ, τ) due to flow conservation and definitions of light and heavy edges.

Definition 5 ([Lianeas et al., 2019]). An undirected path is called an (qx , qz )-alternating path if it consists only of forward light edges and backward heavy edges. For any instance (G, d, l, Ξ, τ), there is a (qx , qz )-alternating path.

5.2 Upper Bound

The following Lemma 3 is a rough bound to say that C(qx ) of CNE is bounded by any path CVaR cost of this network.

Lemma 3 (Rough bound of C(qx )). Let r ∈ R be any path, regardless of whether it carries positive flow at equilibrium. The total system cost at CNE, denoted by C(qx ), admits an upper bound determined by the CVaR cost of path r. Namely,

where SCVaRr = CVr · 1 1-τ ∫ 1 τ Φ-1 r (p) dp and CV denotes the coefficient of variation of the latency of path r.

Proof. At equilibrium, we have that CVaRr′ ≤ CVaRr for all r′ ∈ R that carry positive flow according to Definition 3. This means that lr′(qx ) + 1 1-τ ∫ 1 τ Φ-1 r′ (w) dw · σr′(qx ) ≤

lr(qx )+ 1

1-τ

r (w) dw·σr(qx ) based on Eq.(10). Thus,

τ Φ-1

According to the inequality for l1-norm and l2-norm, we have

where the first inequality is by l2-norm ≤ l1-norm.

To make further bounds, we have to use the additivity of risk measure, while we know the CVaR is not additive. To this end, Theorem 4 finds that edge-based CVaR naturally serves as a surrogate CVaR as this surrogate does coincide with the true path-level CVaR when tail risk of edges are concentrated at the path. Its proof is based on equation (7) in the proof of Theorem 2. Now, we can formulate CNE as a edge-based mathematical programming based on [Xu et al., 2017; Zang et al., 2026b] in Corollary 4.1.

Theorem 4 (τ -additive CVaR for common tail risk). The path CVaR is additive if all its edges share a common tail risk.

Corollary 4.1 (MP of CNE). The edge-based CNE can be formulated as a mathematical programming (MP):

∫ 1

Although the condition in Theorem 4 may initially appear strong, it is appropriate in the context of the PRA, as by definition (i.e., Definition 4) the PRA's focus is on worst-case ratio rather than typical or average ratio. As discussed and justified around Definition 2, tail risk concentration is the most problematic form of edge-level tail risk aggregated to path level. Therefore, bound the inefficiency using the PRA should consider such problematic form.

Remark 1 (Common tail risks in networks). In transportation networks, tail risks arise from adverse weather, synchronized signal or control failures, and major incidents in which crashes or lane blockages propagate extreme delays upstream through spillback and shockwaves [Horn and Wang, 2017]. A recent example is the malfunction of multiple Waymo autonomous vehicles that simultaneously blocked streets and disrupted traffic at several intersections in San Francisco [Abhirup and David, 2025]. In communication networks, analogous tail risks include correlated traffic surges or flash crowds that overload multiple links, synchronized packet losses or retransmissions due to buffer overflows, controlplane events such as routing updates or protocol failures, and hardware or software faults at shared infrastructure that generate network-wide delay spikes [Zhao et al., 2023]. In both domains, these risks concentrate extreme delays across the network rather than affecting edges only.

The additive form of the CVaR is quite important to use alternating path to bound the PRA. That is, with Lemma 3 and Theorem 4, we can have Lemma 5 to bound C(qx ) of CNE and C(qz ) of NE and further derive the final Theorem 6 based on the results in [Lianeas et al., 2016].

Lemma 5 (Tighter bound based on alternating path). Let π denote an alternating path, then total cost of a CNE satisfies

As for NE, total cost of a NE qz satisfies

Proof. The main idea of proving upper bound of C(qx ) is to leverage τ -additivity of CVaR in Theorem 4 and alternatingpath decomposition to compare equilibrium paths with carefully chosen alternatives, allowing equilibrium conditions to telescope into a tight upper bound on C(qx ) that depends only on edge costs along the alternating path and SCVaRmax e . The detailed proof can refer to [Lianeas et al., 2016] where the main difference is that we use CVaR as path cost while they use mean-variance cost. For the lower bound of C(qx ), please refer to Lemma 4.5 of [Nikolova and Stier-Moses, 2015].

Remark 2 (Interpretation of SCVaR and SCVaRmax e ). In Lemma 3, we introduce the scaled standardized CVaR, namely SCVaR, based on Eq.(10) as

Recalling that x = µ + σX, we should have CVaRτ (x) = µ + σSCVaRτ(X). Then, under CVaR-based selfish routing, SCVaRτ(X) represents the expected standardized latency in the worst (1 - τ) fraction of latency and depends only on the shape of the upper tail of the latency distribution. Larger values of SCVaRτ(X) indicate more severe tail latency and therefore it actually represents the the upper-tail cost added to the mean latency for agents adopting CVaR choice rule.

Consequently, SCVaRmax e :=maxe∈E SCVaRτ(Xe) represents the maximum edge-level upper-tail cost in the network.

Theorem 6. Consider an arbitrary instance (G, d, l, Ξ, τ), the upper bound of the PRA is 1 + SCVaRmax e · ⌈(n-1)/2⌉.

Proof. The claim follows from the following chain of inequalities:

where m denote the number of disjoint forward subpaths. The first and third inequalities are because of Lemma 5, while second inequality is based on how we define A and B in Eq.(13). The fourth inequality is derived by the fact that ∑e∈A∩π le(qz e ) ≤ mC(qz ). It holds because, for every forward subpath Ak ∈ π, all its edges have qz e > 0. Consequently, for an appropriate flow decomposition, there exists for each k a path rk with qz rk > 0 that contains the subpath Ak, implying cAk (qz ) ≤ lrk (qz ) = C(qz ). The equality follows from d = 1. In the worst case the path alternates edge by edge, implying that the maximum number of disjoint forward subpaths is ⌈(n - 1)/2⌉. Namely m ≤ ⌈(n - 1)/2⌉.

One may expect that the resulting bound should be governed by two intuitive elements: CVaR-related cost SCVaRmax e and network size. Somewhat unexpectedly, this dependence remains linear even under arbitrary latency functions. With Remark 2, SCVaRmax e helps us identify the most critical edge of a network affecting the PRA. Section 5.3 further shows that the upper bound in Theorem 6 is tight.

5.3 Tight Lower Bound

To further derive the lower bound, we have the following Lemma 7 based on [Lianeas et al., 2016]. The construction of graphs in the proof of Lemma 7 ensures each path contains at most a single edge with positive variability. Therefore, it works for both additive and nonadditive risk models including CVaR, as it eliminates the need to aggregate risks across multiple edges in which nonadditive measures fail.

The main idea of the proof is that by constructing instances based on the Braess-like network as shown in Figure 2 (modified based on [Lianeas et al., 2016; Lianeas et al., 2019]) where the base case is left network and induction case is right network. Them, we can apply mathematical induction to show that C(qx ) = (1 + 2iSCVaRmax e ) diCNE and C(qz ) = driNE hold for each positive integer i and each demand pair diCNE , diNE ∈ R≥0 such that 2idiCNE > (2i - 1)diNE . dCNE and dNE are demands of CNE (i.e., with risk-averse users) and NE (i.e., with risk-neutral users), respectively. The instance for index i is obtained recursively by constructing a Braess-type network using the network constructed for the (i -1)th case. For each step of the construction, the key is to select an appropriate latency function such that the properties stated in Lemma 7 are satisfied. Interested readers can refer to Theorem 2 in [Lianeas et al., 2016] for more details.

Lemma 7. For each integer i ≥ 1 and for every demand pair, diCNE , diNE ∈ R≥0 such that 2idiCNE > (2i -1)diNE , there exists a graph instance Gi (diCNE , diNE ) with 2i+1 nodes that satisfies

With Lemma 7, we can show that our established upper bound in Theorem 6 is tight. This observation is refined in Theorem 8, which indicates that the supremum in the definition of PRA is achieved by explicitly constructed Braess-type instances as visually shown by Figures 2 and 3.

Theorem 8. One can construct Braess-type graphs of arbitrary size such that

Thus, the upper bound of the PRA in Theorem 6 is tight.

Proof. Fix an arbitrary demand d and invoke Lemma 7 by setting diCNE = diNE = d and choosing i = min {j ∈ N : n0 ≤ 2j }. This yields a constructed instance Gi (diCNE , diNE ). For this network, the corresponding CNE flow qx and NE flow qz satisfy

since the graph Gi (diCNE , diNE ) contains 2i+1 vertices by construction. As n is therefore a power of two, Eq.(19) is true.

The inductive construction in the proof of Lemma 7 builds the graph Gi (diCNE , diNE ) by composing two copies of Gi-1 (di-1 CNE , di-1 NE ) in a Braess-type structure, resulting in a graph with 2i+1 vertices. However, the validity of the induction does not depend on exact graph symmetry or on the number of vertices, but rather on an equilibrium-cost invariant: each inductively constructed subgraph must induce a CNE

path cost of 1 + 2i-1SCVaRmax e and a NE path cost of 1. Consequently, for any graph size n satisfying 2i < n < 2i+1 , one may modify the Braess-based construction by replacing the upper-right edge with a copy of Gi-1 (di-1 CNE , di-1 NE ) and the lower-left edge with a graph constructed recursively with n- 2i vertices that satisfies the same equilibrium-cost properties as shown in Figure 3. Since NE depends solely on perceived path costs and not on internal network structure, such asymmetric substitutions preserve the equilibrium behavior of the construction. As a result, the recursive argument and the linear growth of the PRA extend to networks of arbitrary size, including those with an odd number of vertices.

6 Conclusion

This paper establishes the first tight worst-case bounds on the inefficiency of CVaR-based selfish routing in stochastic networks. By analyzing the price of risk aversion (PRA), we show that even under arbitrary latency functions, the inefficiency induced by tail-risk-averse behavior is linearly bounded by network size and the maximum edge-level tail cost, and this bound can be tight. A key conceptual insight underlying our results is that worst-case inefficiency under CVaR is governed by tail risk concentration, a dependence structure in which extreme delays across network components are synchronized. Although CVaR is nonadditive in general, we show that it becomes effectively additive under this worst-case dependence, enabling tight inefficiency analysis despite the failure of classical additive techniques. This clarifies the role of tail dependence in amplifying congestion externalities under risk-averse decision making.

From a multi-agent systems perspective, our results provide worst-case performance for decentralized autonomous agents that optimize tail-risk-averse objectives and thus offer a theoretical bridge between individual risk-averse objectives and collective system performance in large-scale systems.

Ethical Statement

There are no ethical issues.

Acknowledgments

This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2022-031).