Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing

1 Introduction

A primary objective in many networked systems subject to congestion such as the Internet and transportation networks

⇤ The majority of this work was done before the author joined Facebook.

Nicolas E. Stier-Moses

Facebook Core Data Science⇤ nstier@fb.com

is minimizing latencies. A secondary objective in such systems, which has received considerably less attention than the first, is reducing variability. In telecommunication networks, variability amounts to jitter, which causes severe degradation in the quality of audio and video streams. In transportation networks, variability reduces the likelihood of correctly estimating the time of arrival. Consequently, this miscalculation can make the travelers late, which may have very bad consequences, or early which is less dramatic but sometimes inconvenient. This is of paramount importance for many routing services in online platforms such as Waze or Uber.

In both settings, a reasonable goal from the perspective of the agent (packet or traveler) is to consider a multi-objective shortest path problem with respect to both expected latency and its variability. A path with slightly larger expected latency and no variability may be preferred to one with a highly-variable lower-expectation latency, even if the latter stochastically dominates the former. As commonly done in settings with multiple objectives, we consider their linear combination, in this case given by the mean-variance latency of a path choice. The coefficient that is used to sum the two terms into one objective function typically represents agents' risk aversion, and is readily interpreted as how much agents can allow the expected latency to increase to reduce the variance. Since the networks we study are subject to congestion effects, we need to embed these agents' subproblems into a game setting in which each agent has to minimize that objective. This game has the structure as a routing game and its equilibrium concept is an extension of Wardrop equilibria [Wardrop, 1952; Beckmann et al., 1956]. For surveys that discuss the role of these games in the context of telecommunication and transportation networks, see, respectively, Altman et al. [2006] and Correa and Stier-Moses [2011].

Related Work There has been an increased effort in recent years to model risk-averse preferences in routing games and understand the effect of such player preferences on network equilibria [Ord´o˜nez and Stier-Moses, 2010; Nikolova and Stier-Moses, 2011; Nie, 2011; Angelidakis et al., 2013; Piliouras et al., 2013; Nikolova and Stier-Moses, 2014; 2015; Cominetti and Torrico, 2013; Fotakis et al., 2015]. We refer the reader to a recent survey [Cominetti, 2015] for a more extensive review of equilibrium routing under uncertainty.

In an effort to decouple the effect of risk attitudes from the effect of selfish behavior on the degradation of system performance, the price of risk aversion (PRA) has been defined as the worst-case ratio of the cost of a risk-averse equilibrium to that of a risk-neutral equilibrium (namely, the equilibria when agents are risk-averse and risk-neutral, respectively) and has been shown to be upper-bounded by 1 + γn◁2, where  is the worst-case variance-to-mean ratio of an edge at equilibrium, γ is the coefficient of risk-aversion and n is the number of vertices in the graph [Nikolova and Stier-Moses, 2015].

Meir and Parkes [2015] defined biased smoothness and provide a technique that can be used to compare an equilibrium under modified cost functions to the social optimum of the original game. As an example of this technique, they derive an upper bound on the price of risk aversion of (1 + γ)(1 - θ)-1 when cost functions are (1↪ θ)-smooth. As we establish in this paper, this upper bound and that of Nikolova and Stier-Moses [2015] are of a different type, i.e., functional (based on the latency function classes) vs. structural (based on the network topology), which is why they cannot be compared directly. In our paper, we present a new lower bound of this functional form, as well as a simpler proof of the functional upper bound that relies on a generalization of the earlier price of anarchy proof based on variational inequalities [Correa et al., 2008]. Consequently, this method makes possible a more direct comparison with the existing literature including the traditional price of anarchy proofs.

Our contributions Related to AI research on autonomous agents, our results shed light in how risk aversion experienced by agents impact system-wide metrics. The main technical contributions are the first lower bounds to the price of risk-aversion, which are tight or asymptotically tight. We also provide a simplified analysis of the upper bound of Meir and Parkes [2015] for the price of risk-aversion, as well as new tight bounds for a class of graphs that apply to both mean-variance and mean-stdev risk-averse objectives. Our main conceptual contribution is a new structural vs. functional perspective on the price or risk-aversion, demonstrating that bounds can be given either in terms of the network structure or in terms of the class of edge latency functions that are allowed. As such, we also provide an understanding of the connection of two prior upper-bound results on the price of risk-aversion [Nikolova and Stier-Moses, 2015; Meir and Parkes, 2015], as well as a connection to the extensive literature on price of anarchy, which has so far provided only functional bounds.

Our first result is a tight lower bound to the price of risk aversion of 1 + γn◁2, with number of vertices n that are powers of two (Theorem 3), where  is the maximum variance-to-mean ratio, and γ is the degree of risk-aversion of users. This bound essentially closes the gap to the previously known upper bound and characterizes the exact price of risk aversion for an infinite number of graph sizes. We call the bound structural, since it matches the upper bound that only depends on the network structure and not on the latency functions used. Our construction of the worst-case graph family involves finding an instance in which an alternating path (a path that consists of appropriately defined forward and backward edges) goes through every vertex in the graph and alternates between forward and backward edges at every internal vertex. We achieve this by inductively defining a graph family with appropriate mean and variance functions for each edge.

Our second lower bound is an asymptotically tight functional bound (Theorem 5). It follows from the same inductively defined family of graphs but with different appropriately chosen mean and variance functions. We also give a new proof of the functional upper bound (1 + γ)(1 - θ)-1 for (1↪ θ)-smooth latency functions via a variational inequality characterization of equilibria (Theorem 4). This bound implies, for example, that the price of risk aversion is at most (1+γ)4◁3 for linear latency functions and it generalizes the classic result that the price of anarchy is (1 - θ)-1 [Roughgarden, 2003] because, when there is no variability,  = 0. We remark that for unrestricted functions, the functional upper bounds become vacuous since θ = 1, which provides further support for the structural analysis of Section 3.

Finally, we provide a closed-form formula for the price of risk aversion under the alternative mean-stdev model of riskaversion where players minimize a linear combination of the mean and standard deviation of the route travel time. This model is significantly more difficult to analyze than the meanvar model due to its non-additive nature, namely the mean plus standard deviation of a path cannot be decomposed as a sum of costs over the edges in the path. The formula is valid for a family of graphs that generalizes series-parallel graphs (specifically, the family of graphs where the domino-withears graph, shown in Fig. 3(b), is a forbidden minor). This formula extends to the mean-var model as well, and it refines our understanding on the topology of graphs for which the price of risk aversion is 1 + 2γ, as opposed to the cruder bound in terms of number of vertices only.

Both our structural and functional lower bounds also readily provide corresponding lower bounds in the mean-stdev model. Showing a structural and functional upper bound for general graphs in that model remains an open problem.

2 Model and Preliminaries

We consider a directed graph G = (V↪E) with a single source-sink pair (s↪ t) and an aggregate demand of d units of flow that need to be routed from s to t. We let P be the set of all feasible paths between s and t. We encode the players' decisions as a flow vector f = (fp)p2P 2 R♣P♣ + over all paths. Such a flow is feasible when demand is satisfied, as given by the constraint Pp2P fp = d. For notational simplicity, we denote the flow on an edge e by fe = Pp3e fp. When we need multiple flow variables, we use x↪ xp↪ xe and z↪ zp↪ ze.

The network is subject to congestion, modeled with stochastic delay functions `e(fe) + ⇠e(fe) for each edge e 2 E. Here, the deterministic function `e(fe) measures the expected delay when the edge has flow fe, and ⇠e(fe) is a random variable that represents a noise term on the delay. Functions `e(·), generally referred to as latency functions, are assumed continuous and non-decreasing. The expected latency along a path p is given by `p(f) := Pe2p `e(fe). Random variables ⇠e(fe) are pairwise independent, have expectation zero and standard deviation σe(fe), for arbitrary continuous functions σe(·). For the variational inequality characterization used in Section 4, we further assume that meanvariance objective of users, defined below, is non-decreasing. The variance along a path equals vp(f) = Pe2p σ2 e (fe), and the standard deviation (stdev) is σp(f) = (vp(f))1◁2 .

We consider the nonatomic version of the routing game where infinitely many players control an infinitesimal amount of flow each so that the path choice of a single player does not unilaterally affect the costs experienced by other players.

Players are risk-averse and strategically choose paths taking into account the variability of delays by considering a mean-var objective Qγp (f) = `p(f) + γvp(f). We refer to this objective simply as the path cost (as opposed to latency). Here, γ ≥ 0 is a constant that quantifies the risk-aversion of the players, which we assume homogeneous. The special case of γ = 0 corresponds to risk-neutrality. In the last section, we consider the mean-stdev objective where the variance in the objective is replaced with the standard deviation of the path.

The variability of delays is usually not too large with respect to the expected latency. Following previous work, we assume that ve(xe)◁`e(xe) is bounded from above by a fixed constant  for all e 2 E at the equilibrium flow of interest xe 2 R+. This means that the variance cannot be larger than  times the expected latency in any edge at equilibrium.

In summary, an instance of the problem is given by the tuple (G↪ d↪ `↪ v↪ γ), which represents the topology, demand, latency functions, variability functions, and degree of player risk-aversion. The following definition captures that at equilibrium players route flow along paths with minimum cost.

Definition 1 (Equilibrium). A γ-equilibrium of a stochastic nonatomic routing game is a flow f such that for every path p 2 P with positive flow, the path cost Qγp (f)  Qγq (f) for any other path q 2 P . For a fixed risk-aversion parameter γ, we refer to a γ-equilibrium as a risk-averse Wardrop equilibrium (RAWE), denoted by x. For γ = 0, we call the equilibrium a risk-neutral Wardrop equilibrium (RNWE).

Notice that since the variance decomposes as a sum over all the edges on the path, the previous definition represents a standard Wardrop equilibrium with respect to modified costs `e(fe) + γve(fe). For the existence of the equilibrium, it is sufficient that the modified cost functions are increasing.

Our goal is to investigate the effect that risk-averse players have on the quality of equilibria. The quality of a solution that represents collective decisions can be quantified by the cost of equilibria with respect to expected delays since, over time, different realizations of delays average out to the mean by the law of large numbers. For this reason, a social planner, who is concerned about the long term, is typically risk neutral. Furthermore, the social planner may aim to reduce long-term emissions, which would be better captured by the total expected delay of all users.

Definition 2. The social cost of a flow f is defined as the sum of the expected latencies of all players: C(f) := Pp2P fp`p(f) = Pe2E fe`e(fe) .

Although one could have measured total cost as the weighted sum of the costs Qγp (f) of all users, this captures users' utilities but not the system's benefit. Such a cost function was previously considered to compute the price of anarchy [Nikolova and Stier-Moses, 2014]. In contrast, our goal is to compare across different values of risk aversion so we want the various flow costs to be measured with the same units.

The next definition captures the increase in social cost at equilibrium introduced by user risk-aversion, compared to the social cost if users were risk-neutral.

Definition 3 ([Nikolova and Stier-Moses, 2015]). Consider-

ing an instance family F of a routing game with uncertain delays, the price of risk aversion (PRA) associated with γ and  (the risk-aversion coefficient and the variance-to-mean ratio) is defined by PRA(F↪ γ↪ ) := supG↪d↪`↪v n C(x) C(z) : (G↪ d↪ `↪ v↪ γ) 2 F and v(x)  `(x)o↪ where x and z are the risk-averse and the risk-neutral Wardrop equilibria of the

corresponding instance.

3 Structural Lower Bounds

In this section, we prove two lower bounds on the price of risk aversion, both matching the upper bounds presented by Nikolova and Stier-Moses [2015]. The first bound for PRA is with respect to the minimum number of alternations among all alternating paths as defined below, while the second bound is with respect to the number of vertices in the graph. In fact, the same bounds hold in the mean-standard deviation model, but we defer that discussion to Section 5.

Given an instance, we denote a RNWE flow associated with it by z, and a RAWE flow by x. To define alternating paths, we partition the edge-set E into A = ¶e 2 E : xe  ze♦ and B = ¶e 2 E : ze < xe♦. Conceptually, an alternating path is an s-t-path in the graph where edges in B are reversed (see Fig. 3(c) for an illustration of the definition).

Definition 4 ([Nikolova and Stier-Moses, 2015]). A generalized path ⇡ = A1-B1-A2-B2-· · · -At-Bt-At+1, composed of a sequence of subpaths, is an alternating path when every edge in Ai ✓ A is directed in the direction of the path, and every edge in Bi ✓ B is directed in the opposite direction from the path. We say that such a path has t + 1 disjoint forward subpaths, and t alternations.

The definition of alternating paths was motivated by the following result.

Theorem 1 ([Nikolova and Stier-Moses, 2015]). Considering the set of instances with arbitrary mean and variance latency functions that admit an alternating path with up to ⌘ disjoint forward subpaths, PRA  1 + ⌘γ.

The theorem implies that for the set of instances on graphs with n vertices, PRA  1 + γd n-1 2 e since in that case an alternating path cannot have more than d(n - 1)◁2e disjoint forward subpaths. We are going to prove that those upper bounds are tight. To get there, we first prove a more general result that shows how instances with high price of risk aversion can be constructed.

Theorem 2. For an i 2 N>0, consider riA↪ riN 2 R≥0 such that 2i riA > (2i - 1)riN . There exists an instance based on a graph Gi (riA↪ riN ) that satisfies the following two properties.

• ÷ If riA risk-averse players are routed throughGi (riA↪ riN ), then the path cost along used paths at the RAWE flow x,

as well as the expected latency, is 1 + 2iγ. The social cost is C(x) = (1 + 2iγ)riA.

• ÷ If riN risk-neutral players are routed through Gi (riA↪ riN ), then the expected latency along each used path at the RNWE flow z is 1. The social cost is C(z) = riN .

The proof is by induction on i. We will recursively construct the instance for i by forming a Braess instance with the graph resulting for the i - 1 case. At each step we will need to find a mean latency function that makes the properties in the statement work.

Proof. For the base case i = 1, we let G1 (r1A↪ r1N ) be the Braess graph, shown in Fig. 1. Indeed, consider any r1A↪ r1N such that r1A > r1N ◁2 as indicated in the statement of the result. We define the mean latency function a1(x) to be any function that is strictly increasing for x ≥ r1N ◁2 and such that a1(r1N ◁2) = 0 and a1(r1A) = γ. Note that in order for a1(x) to be strictly increasing, it is necessary that r1A > r1N ◁2, which holds by hypothesis.

The RAWE flow x routes the r1A risk-averse players along the zig-zag path. Hence, the mean-var objective in the upperleft and the lower-right edges, as well as the mean latency, will each be γ, totalling 1 + 2γ for each player in both cases. Hence, C(x) = (1 + 21γ)r1A. Instead, the RNWE flow z routes the r1N risk-neutral players along the top and bottom paths, half and half. Hence, the cost for each player is 1 and C(z) = r1N , proving the base case.

Let us consider the inductive step where we assume we have an instance satisfying the properties for i - 1 and construct the instance for step i. Starting from riA and riN satisfying the condition in the statement for case i, we set ri-1 A = (2i riA - riN )◁2i+1 and ri-1 N = riN ◁2. We first verify that these values satisfy the hypothesis for the case i - 1. Indeed, ri-1 A > 2i-1-1 2i-1 ri-1 N because by hypothesis riA > 2i-1 2i riN , riA 2 > 2i-1 2i+1 riN which implies that riA 2 - riN 2i+1 > 2i-1 2i+1 riN - 1 2i+1 riN = 2i-1-1 2i-1 riN 2 .

The RAWE flow x routes the riA risk-averse players as follows: riA 2 - riN 2i+1 units along the upper path, riN 2i units along

Using the graph corresponding to step i - 1 and the values of ri-1 A and ri-1 N specified previously, we construct graph Gi (riA↪ riN ) with those components as shown in Fig. 2. We define the mean latency function ai(x) to be any function that is strictly increasing for x ≥ riN ◁2 and such that a1(riN ◁2) = 0 and ai( riA 2 + riN 2i+1 ) = 2i-1γ. Note that in order for ai(x) to be strictly increasing, it is necessary that riA 2 + riN 2i+1 > riN 2 , which actually holds because, by hypothesis, riA > 2i-1 2i riN , riA 2 > 2i-1 2i+1 riN .

the zig-zag path, and riA 2 - riN 2i+1 units along the lower path. The mean-var objective of the upper-left and the lower-right edges, as well as the mean latency, will each be 2i-1γ since the flow through them is equal to riA 2 + riN 2i+1 . The flow inside each of the copies of Gi-1 (ri-1 A ↪ ri-1 N ) is a RAWE for which we know, by induction, that all players perceive a path cost of 1 + 2i-1γ, which additionally, by induction, is the mean latency of all used paths. Thus, the path cost that players perceive in Gi (riA↪ riN ) under the RAWE flow x is 1 + 2iγ, which additionally is the mean latency of all used paths, and the social cost is C(x) = (1 + 2iγ)riA.

The RNWE flow z routes the riN risk-neutral players along the top and bottom paths, half and half. Hence, the path cost for perceived by each player is 1, as the mean-var objective in the upper-left and lower-right edges is equal to 0, and, by induction, passing through either of both copies of Gi-1 (ri-1 A ↪ ri-1 N ) has a mean-var objective of 1. This implies that C(z) = riN , which completes the proof.

The previous result provides a constructive way to generate instances with high price of risk aversion. Notice that the paths of the instances resulting from these constructions have at most one edge with non-zero variance. This fact is useful to extend our lower bounds to the mean-stdev model, since in that case summing and taking square roots is not needed.

Another useful observation is that the prevailing value for mean latency functions aj under the RNWE flow z is 0, and under the RAWE flow x is 2j-1 . This can be easily proved by induction and will be used when establishing functional lower bounds on the PRA in the next section.

We now use the previous result to get lower bounds for PRA matching the upper bound specified earlier.

Corollary 1. For any n0 2 N, there is an instance on a graph G with n ≥ n0 vertices such that its equilibria satisfy C(x) ≥ (1 + γd(n - 1)◁2e)C(z).

Proof. Consider an arbitrary demand d, and apply Theorem 2 with riA = riN = d and i = min¶j 2 N : n0  2j ♦ to get instance Gi (riA↪ riN ). Consequently, x and z satisfy: C(x) C(z) =

(1+2i γ)d d = 1+γ n2 ↪ because Gi (riA↪ riN ) has 2i+1 vertices by construction. The result holds, as n is a power of two.

The previous lower bound together with the upper bound given in the paragraph after Theorem 1 imply that the PRA with respect to the set of instances on graphs with up to n vertices is exactly equal to 1 + γd(n - 1)◁2e when n is a power of 2. From there, the bound is tight infinitely often. Although for other values of n the bounds are not tight, they are close together so these results provide an understanding of the asymptotic growth of the PRA. We now refine this observation to the bound in Theorem 1.

Theorem 3. The upper bound for the price of risk-aversion shown in Theorem 1 and the lower bound shown in Corollary 1 coincide for graphs of size that is a power of 2. Otherwise, the gap between them is less than 2.

In conclusion, PRA = 1 + ⌘γ when the family of instances is defined as graphs with arbitrary mean and variance functions that admit alternating paths with up to ⌘ disjoint forward subpaths, for ⌘ equal to a power of 2. We have equality because the supremum in the definition of PRA is attained by the instance constructed previously.

4 Functional Bounds

In this section, we turn our attention to instances with mean latency functions restricted to be in a certain family (as, e.g., affine functions). We prove upper and lower bounds for the PRA that are asymptotically tight as γ increases. The results rely on the variational inequality approach that was first used by Correa et al. [2008] to prove price of anarchy (POA) bounds for fixed families of functions. This approach was based on the properties of the allowed functions. Since then, these properties have been successively refined [Harks, 2011; Roughgarden and Schoppmann, 2015], and they are now usually referred to as the local smoothness property. Although not really needed for the results here, we use the latter terminology since it has become standard by now. To characterize a family of mean latency functions, we rely on the smoothness property, defined below.

Definition 5 ([Roughgarden and Schoppmann, 2015]). A function ` : R≥0 ! R≥0 is said to be (λ↪ θ)-smooth around x 2 R≥0 if y`(x)  λy`(y) + θx`(x) for all y 2 R≥0.

Using the previous definition, we construct an upper bound for the PRA when mean latency functions ¶`e♦e2E are (1↪ θ)- smooth around the RAWE flow xe for all edges e 2 E. Meir and Parkes [2015] proved a similar bound using a related approach in which they generalize the smoothness definition to biased smoothness which holds with respect to a modified latency function. In our case, the modified latency function would be `e + γve. One advantage of our approach is its simplicity; it is a straightforward generalization of the POA proof given in Correa et al. [2008]. We provide a proof corresponding to our assumptions, matching what is needed to get our asymptotically-tight lower bounds.

Theorem 4. Consider the set of general instances with mean latency functions ¶`e♦e2E that are (1↪ θ)-smooth around any RAWE flow xe for all e 2 E. Then, with respect to that set of instances, PRA  (1+γ) 1 1-θ ▷

Proof. We consider an instance within the family, a corresponding RAWE flow x, and a RNWE flow z. Further, we let A = ¶e 2 E♣xe  ze♦ and B = ¶e 2 E♣ze < xe♦. Using a variational inequality formulation for the RAWE, we get Pe2E xe(`e(xe) + γve(xe))  Pe2E ze(`e(xe) + γve(xe)) ▷ Partitioning the sum over E at both sides into terms for A and B, subtracting from it the inequality Pe2A xeve(xe) + Pe2B xeve(xe) ≥ Pe2B zeve(xe) , and further bounding ve(xe) by `e(xe), we get that C(x) = Pe2A xe`e(xe) + Pe2B xe`e(xe)  Pe2A(1+γ)ze`e(xe)+Pe2B ze`e(xe)▷ Applying the definition of A to the first term and the (1↪ θ)-smoothness condition to the second, we get: C(x)  Pe2A(1+γ)ze`e(ze)+ Pe2B (ze`e(ze)+θxe`e(xe))  (1+γ)C(z)+θC(x)▷

The bound in the previous result is similar to that for the POA for nonatomic games with no uncertainty. Indeed, the result there is that POA  (1-θ)-1 , the same without the 1+ γ factor. The values of (1 - θ)-1 have been computed for different families of functions in previous work. On the other hand, for unrestricted functions this value is infinite so the bound becomes vacuous in that case, which provides support for the structural analysis of Section 3.

To evaluate the tightness of our upper bounds, we now propose lower bounds for the PRA. More specifically, we provide a family of instances indexed by i whose latency functions are (1↪ θi)-smooth, for θi = 1 - 2-i , for which the bound is approximately tight. These instances imply lower bounds equal to 1 +γ(1 -θi)-1 = 1 +γ2i . First, notice that although the lower and upper bounds do not match, they are similar. The difference is whether the 1 is or is not multiplied by the θ factor. When the γ term is large, both bounds are essentially equal. Second, notice that for large values of i, necessarily the number of alternations of the longest alternating path must grow exponentially large to simultaneously match the structural upper bound presented in Theorem 1.

Theorem 5. For any i > 0, letting θi = 1 - 2-i , PRA ≥ 1 + γ(1 - θi)-1 for the family of instances satisfying the (1↪ θi)-smoothness property.

Proof sketch. To get the result we use the recursively constructed graph Gi of Theorem 2 for riA = riN = 1, but with the non-constant cost functions satisfying the (1↪ θi)- smoothness condition around the RAWE: for 1  j  i we

In Gi there are 2i parallel paths, i.e. paths not containing any vertical edge, and 2i -1 zig-zag paths, i.e. the rest of the paths. The RNWE flow z splits the unit flow equally along the 2i parallel paths and each aj gets 2j-1 ◁2i units of flow and has 0 cost, exactly as in Theorem 2, implying C(z) = 1. The RAWE flow x splits the unit flow equally along the 2i -1 zig-zag paths and each aj gets 2j-1 ◁(2i -1) units of flow and has cost equal to 2j-1γ, exactly as in Theorem 2, implying C(x) = 1 + 2iγ, and thus the bound for PRA follows.

To conclude, some technical work is needed for proving that the aj's are (1↪ θi)-smooth around xe for all e. The other cost functions are constants, thus (1↪ θi)-smooth.

5 The Mean-StdevModel

In this section, we turn to the mean-standard deviation model and prove upper and lower structural bounds on PRA, now assuming that  is the maximum coefficient of variation CVe(fe) among edges, where CV is defined as the ratio between the standard deviation (stdev) and the mean. The lower bounds follow from the instances used to prove the lower bounds in the mean-variance case in Section 3. Considering families of graphs with up to ⌧ forward disjoint subpaths and general mean latency and stdev functions, we prove upper bounds for the cases ⌧ = ¶1↪ 2♦, and lower bounds for arbitrary ⌧ . For ⌧  2, both bounds coincide, so the PRA for the stdev case gets characterized exactly.

Since we are now dealing with standard deviations, we redefine Qγp (f) = `p(f) + γσp(f), where σp(f) = (Pe2p σ2 e (fe))1◁2 . Given an instance based on a graph G, we refer to a RNWE flow by z and to a RAWE flow by y. Further, we denote the path cost perceived by players at the RAWE y by Qγ (y) and the expected latencies perceived by players at the RNWE z by Q0 (z). The definition for the price of risk aversion is analogous to that given in Section 2.

Our first result provides inequalities that relate the social cost at equilibrium with the perceived utilities. The first part is known and the second is a generalization.

Proposition 1. For an arbitrary instance, C(z) = d · Q0 (z) and C(y)  d · Qγ (y), where d is the traffic demand.

As in Section 3, we partition the edge-set E into two: A = ¶e 2 E : ye  ze♦ and B = ¶e 2 E : ze < ye♦. We assume that all edges in E are used by either flow y or z. This is without loss of generality because unused edges can be deleted without any consequence. The definition of B implies that ye > 0 for all e 2 B, while the assumption implies that ze > 0 for all e 2 A. To prove an upper bound on PRA, we rely again on alternating paths, the existence of which is guaranteed by Lemma 4.5 of Nikolova and StierMoses [2015]. The next result bounds the PRA for graphs that admit simple alternating paths (i.e., actual s-t paths), or alternating paths with a single alternation.

Lemma 1. For ⌧ 2 ¶1↪ 2♦, considering the set of instances on general topologies with arbitrary mean latency and stdev functions that admit alternating paths with ⌧ -1 alternations, PRA  1 + ⌧ γ.

Proof sketch. For ⌧ = 1, we simply use the equilibrium conditions together with the monotonicity of the cost functions and the stdev-to-mean ratio bound. For ⌧ = 2, we let ⇡ = A1-B1-A2 be the alternating path. Figure 3 (c) for ⌘ = 1 illustrates the topology of these subpaths.

Consider a RAWE flow y and a flow-carrying path C1-B1D1 under y. Using the equilibrium conditions for y, by separately examining on whether σ2C1 (y) + σ2B1 (y) + σ2D1 (y)  σ2A1 (y)+σ2D1 (y), and by using some properties of the square root we manage to derive in both cases that `C1 (y)+`B1 (y)+ γqσ2C1 (y) + σ2B1 (y)  (1 + γ)`A1 (y)▷ Using a similar argument for the path C1-A2 instead of A1-D1, we further derive that `D1 (y)+γσD1 (y)  (1+γ)`A2 (y)-`B1 (y)▷ Since path C1-B1-D1 is used under y, Qγ (y) = `C1 (y)+`B1 (y)+

For the RNWE flow z using the equilibrium conditions we can derive Q0 (z) ≥ `A1 (z) + `A2 (z) - `B1 (z). Combining it with the inequality above it, the fact that Q0 (z) is an upper bound for both `A1 (z) and `A2 (z), and the definition of sets A and B we get Qγ (y)  (1 + 2γ)Q0 (z)▷ The result follows since by Proposition 1: C(y)  d · Qγ (y)  d · (1 + 2γ)Q0 (z) = (1 + 2γ)C(z).

Lemma 1 for ⌧ = 1 implies that series-parallel graphs satisfy that PRA  1 + γ and it is well known that those graphs can be characterized as not containing the Braess graph. Along that line, we provide a forbidden minor characterization of Lemma 1 for ⌧ = 2: the topology of instances for which PRA  1 + 2γ is characterized by graphs not containing the domino-with-ears graph as a minor (Fig 3(b)).

Theorem 6. Instances on general topologies with arbitrary mean latency and stdev functions that do not have dominowith-ears as a minor satisfy PRA  1 + 2γ.

The proof is by contradiction: Assume that the statement is false. By Lemma 1, this implies that any alternating path has at least ⌧ ≥ 2 alternations and thus the graph of Fig. 3(c) for ⌘ = ⌧ lies inside the network. But this is a contradiction as this graph admits the domino-with-ears as a minor.

The previous proof implies that any graph that has the domino-with-ears graph as a minor cannot belong to the family of instances for which PRA  1 + 2γ. Lemma 1 and Theorem 6 together imply that PRA  1 + ⌧γ holds for the set of instances admitting alternating paths in which the number of disjoint forward subpaths is not more than ⌧, for ⌧  2. Although this does not fully generalize Theorem 1 to the standard deviations case, it is a first step in that direction.

To provide matching lower bounds for the results of this section, we note that all paths in the proof of Theorem 2 have at most one edge with nonzero variance. Thus, all the lower bounds in Section 3 work by reinterpreting the variances as standard deviations and the variance-to-mean ratios as coefficients of variation. This is summarized below.

Corollary 2. The upper bounds PRA  1 + γ and PRA  1+2γ corresponding to graphs that admit alternating paths with 1 and 2 disjoint forward subpaths, respectively, are tight.