A sensitivity analysis of the PoA in non-atomic congestion games

This paper continues the studies of Englert et al. [2010], Takalloo and Kwon [2020] and Cominetti et al. [2020]. We consider a general traffic network that have multiple O/D pairs and general cost functions that may include tolls. We view the PoA as a real-valued map of the demands and the cost functions of that network, and then analyze the sensitivity of the resulting map when both the demands and the cost functions may change.

To that purpose, we need first a well defined measure for simultaneous changes of the demands and the cost functions in a traffic network with multiple O/D pairs.

We thus fix in our analysis an arbitrary directed network $G=(V,A)$ and an arbitrary finite set $\mathcal{K}$ of O/D pairs in that network, and consider only the cost functions $\tau_{a}(\cdot)$ of arcs $a\in A$ and the demands $d_{k}$ of O/D pairs $k\in\mathcal{K}$ as “variables”. Each pair $\Gamma=(\tau,d)$ consisting of a cost function vector $\tau=(\tau_{a})_{a\in A}$ and a demand vector $d=(d_{k})_{k\in\mathcal{K}}$ then represents a “state” of the network and corresponds to an instance of the traffic game (Roughgarden and Tardos [2002]) defined on the network. We then view the collection of all these states as a game space, and the PoA in the network as a real-valued map $\rho(\cdot)$ from this space to the unbounded interval $[1,\infty).$ Then the value $\rho(\Gamma)$ at a point $\Gamma=(\tau,d)$ of the game space is the resulting PoA when the network is at state $\Gamma,$ i.e., the resulting PoA when the network has the cost function vector $\tau$ and the demand vector $d.$

By adapting the $L^{\infty}$-norms of functions and vectors, we define a binary operator $\text{Dist}(\cdot,\cdot),$ see (3.3), on the game space by putting

$$\text{Dist}(\Gamma,\Gamma^{\prime})\!=\!\max\left\{|\!|d\!-\!d^{\prime}|\!|_{\infty},\ \max_{a\in A,x\in[0,\min\{T(d),T(d^{\prime})\}]}|\tau_{a}(x)\!-\!\sigma_{a}(x)|,\ |\!|\tau(T(d))\!-\!\sigma(T(d^{\prime}))|\!|_{\infty}\right\}$$

for two arbitrary points $\Gamma=(\tau,d)$ and $\Gamma^{\prime}=(\sigma,d^{\prime})$ of the game space, where $T(d)=\sum_{k\in\mathcal{K}}d_{k}$ and $T(d^{\prime})=\sum_{k\in\mathcal{K}}d^{\prime}_{k}$ are the total demands of the demand vectors $d$ and $d^{\prime}$ respectively, $\tau(T(d))=(\tau_{a}(T(d)))_{a\in A}$ and $\sigma(T(d^{\prime}))=(\sigma_{a}(T(d^{\prime})))_{a\in A}.$

This binary operator $\text{Dist}(\cdot,\cdot)$ is actually a metric on the game space w.r.t. an equivalence relation defined in (3.1), see Lemma 4. The game space then becomes a metric space, and a simultaneous change of the cost functions and the demands is then quantified by the “distance” $|\!|\Gamma-\Gamma^{\prime}|\!|:=\text{Dist}(\Gamma,\Gamma^{\prime})$ between two points $\Gamma$ and $\Gamma^{\prime}$ of the game space.

With this metric, our sensitivity analysis of the PoA in the network then transforms to an analysis of the pointwise Hölder continuity of the map $\rho(\cdot)$ on the game space, aiming at finding for each point $\Gamma=(\tau,d)$ a Hölder exponent $\gamma_{\Gamma}>0$ s.t. $|\rho(\Gamma)-\rho(\Gamma^{\prime})|<\varkappa_{\Gamma}\cdot|\!|\Gamma-\Gamma^{\prime}|\!|^{\gamma_{\Gamma}}$ when $|\!|\Gamma-\Gamma^{\prime}|\!|<\epsilon_{\Gamma}$ for two positive constants $\varkappa_{\Gamma},\epsilon_{\Gamma}>0$ depending only on $\Gamma.$ Trivially, the larger the Hölder exponent $\gamma_{\Gamma}$ at a point $\Gamma=(\tau,d)$, the less sensitive is the PoA at the network state $\Gamma$ w.r.t. a small change $|\!|\Gamma-\Gamma^{\prime}|\!|$ of the state $\Gamma$.

As our first result, we show that both the equilibrium cost and the socially optimal cost are continuous maps (w.r.t. the metric) on the whole game space. This implies directly that the map $\rho(\cdot)$ is continuous on the whole game space, see Theorem 6. Hence, the PoA changes only slightly when the changes of the cost functions and the demands are very small in terms of the metric.

We then show that $\rho(\cdot)$ is not uniformly Hölder continuous on the whole game space, i.e., there are no constants $\gamma,\varkappa>0$ such that

$$|\rho(\Gamma)-\rho(\Gamma^{\prime})|{\leq}\varkappa\cdot|\!|\Gamma-\Gamma^{\prime}|\!|^{\gamma}\quad\forall\Gamma,\Gamma^{\prime}\in\mathcal{G}(G,\mathcal{K},\mathcal{S}),$$

see Theorem 8a). Moreover, we show that no point $\Gamma$ of the game space has the whole game space as its Hölder neighborhood, see Theorem 8b). Here, a Hölder neighborhood of a game $\Gamma$ refers to an open subset $U_{\Gamma}$ of the game space with $\Gamma\in U_{\Gamma},$ for which there are constants $\gamma_{\Gamma},\varkappa_{\Gamma}>0$ depending only on $\Gamma$ s.t. $|\rho(\Gamma)-\rho(\Gamma^{\prime})|{\leq}\varkappa_{\Gamma}\cdot|\!|\Gamma-\Gamma^{\prime}|\!|^{\gamma_{\Gamma}}$ for each $\Gamma^{\prime}\in U_{\Gamma}.$

Hence, $\rho(\cdot)$ may only be pointwise and locally Hölder continuous on the game space. In particular, Theorem 8a) implies that $\rho(\cdot)$ is not Lipschitz continuous on the whole game space.

Along with Theorem 8, our first Hölder continuity result shows that $\rho(\cdot)$ is pointwise Hölder continuous with Hölder exponent $\frac{1}{2}$ at each point $\Gamma=(\tau,d)$ where the cost functions $\tau_{a}(\cdot)$ are Lipschitz continuous on the interval $[0,T(d)],$ see Theorem 9. Hence, the change of the PoA is bounded from above by $\varkappa_{\Gamma}\cdot\sqrt{|\!|\Gamma-\Gamma^{\prime}|\!|}$ for a Hölder constant $\varkappa_{\Gamma}>0$ when the network undergoes only a small change $|\!|\Gamma-\Gamma^{\prime}|\!|$ at a state $\Gamma=(\tau,d)$ with Lipschitz continuous cost functions $\tau_{a}(\cdot)$ on $[0,T(d)].$ Since the interval $[0,T(d)]$ is compact, this result applies obviously to all continuously differentiable cost functions. Because of Theorem 8b), however, it may not apply when the network undergoes a large change of the cost functions and/or the demands in terms of the metric.

To obtain this result, we show first that $|\rho(\Gamma)-\rho(\Gamma^{\prime})|{\leq}\varkappa_{1,\Gamma}\cdot\sqrt{|\!|\Gamma-\Gamma^{\prime}|\!|}$ for a constant $\varkappa_{1,\Gamma}>0$ when $\Gamma=(\tau,d)$ and $\Gamma^{\prime}=(\sigma,d)$ have the same demand vector $d,$ the change $|\!|\Gamma-\Gamma^{\prime}|\!|$ is small and the cost functions $\tau_{a}(\cdot)$ of $\Gamma$ are Lipschitz continuous on $[0,T(d)],$ see Lemma 10. We then show that $|\rho(\Gamma)-\rho(\Gamma^{\prime})|{\leq}\varkappa_{2,\Gamma}\cdot\sqrt{|\!|\Gamma-\Gamma^{\prime}|\!|}$ for a constant $\varkappa_{2,\Gamma}>0$ when $\Gamma=(\tau,d)$ and $\Gamma^{\prime}=(\tau,d^{\prime})$ have the same cost functions $\tau_{a}(\cdot)$, the change $|\!|\Gamma-\Gamma^{\prime}|\!|$ is small and the cost functions $\tau_{a}(\cdot)$ are Lipschitz continuous on $[0,T(d)],$ see Lemma 11.

Lemma 10 and Lemma 11 then imply Theorem 9. In particular, Lemma 11 generalizes the sensitivity results of Englert et al. [2010] and Takalloo and Kwon [2020] by considering more general cost functions and removing the requirement that the demands of different O/D pairs increase synchronously by the same factor. However, this comes at the cost of a weaker Hölder exponent $\frac{1}{2}$ than that of Englert et al. [2010] and Takalloo and Kwon [2020], who obtain a Hölder exponent of $1$.

The above Hölder continuity results build essentially upon Lemma 1c) in Section 2.3, which shows that the total cost of an $\epsilon$-approximate Wardrop equilibrium (Wardrop [1952]) deviates by at most $O(\sqrt{\epsilon})$ from that of a precise Wardrop equilibrium. This is already a tight upper bound on the cost deviation for arbitrary Lipschitz continuous cost functions on $[0,T(d)],$ see Example 2, and we are thus presently unable to improve the Hölder exponent $\frac{1}{2}$ in Theorem 9, Lemma 10 and Lemma 11, see Remark 4.2. Nevertheless, a stronger Hölder exponent is still possible when the cost functions have special properties similar to those in the work of Englert et al. [2010], Cominetti et al. [2020], and Takalloo and Kwon [2020].

When the cost functions $\tau_{a}(\cdot)$ of a point $\Gamma=(\tau,d)$ are constants or have strictly positive derivatives on the interval $[0,T(d)],$ we obtain the stronger result that $\rho(\cdot)$ is pointwise Hölder continuous with Hölder exponent $1$ at the point $\Gamma,$ see Theorem 12. Hence, the resulting change of the PoA is bounded from above by $\varkappa_{\Gamma}\cdot|\!|\Gamma-\Gamma^{\prime}|\!|$ for a constant $\varkappa_{\Gamma}>0$ when the network undergoes a small change $|\!|\Gamma-\Gamma^{\prime}|\!|$ at such a state $\Gamma$. Again by Theorem 8, this may not hold when the network undergoes a large change of the cost functions and/or demands in terms of the metric.

Finally, we demonstrate that our Hölder continuity results also help to analyze the convergence rate of the PoA in traffic networks, which is an emerging research topic initiated recently by Colini-Baldeschi et al. [2017, 2020], see Section 1.2 or Section 5.1 for an overview of the related work on this new topic.

For $T(d)\to 0$, Colini-Baldeschi et al. [2017, 2020] have obtained the first convergence result stating that the PoA converges to $1$ at a rate of $O(T(d))$ when the cost functions are of the form $\tau_{a}(x)=\sum_{n\in\mathbb{N}}\xi_{a,n}\cdot x^{n}$ for each $a\in A$ and each $x\in[0,\infty)$, and the demands of all O/D pairs follow a specific decreasing pattern, i.e., all of them decrease to $0$ at the same rate of $\Theta(T(d)),$ see Section 1.2 or Section 5.1. With Theorem 12a), we show a stronger result that the PoA converges to $1$ at a rate of $O(T(d))$ as $T(d)\to 0$ regardless of the decreasing pattern of the demands when the cost functions are strictly positive and Lipschitz continuous within a small neighborhood around the origin $0$, see Corollary 5.1.

When $T(d)\to\infty,$ it has been shown by Colini-Baldeschi et al. [2017, 2020] and Wu et al. [2021] that the PoA converges to $1$ as $T(d)\to\infty$ for arbitrary regularly varying cost functions. For the special case of arbitrary polynomials as cost functions, Colini-Baldeschi et al. [2017, 2020] obtained the first convergence rate of $O(\frac{1}{T(d)})$ for the PoA when the demands of all O/D pairs grow to $\infty$ at the same rate of $\Theta(T(d))$. For the more specific case of BPR cost functions (Bureau of Public Roads [1964]) with degree $\beta\geq 0$, Wu et al. [2021] showed a stronger convergence rate of $O(\frac{1}{T(d)^{\beta}})$ for the PoA when the total demand $T(d)$ grows to $\infty.$ See Section 5 for an overview of related results on the convergence rates of the PoA. With Theorem 9, we show that the PoA converges to $1$ at a rate of $O(\sqrt{1/\ln(T(d)+1)})$ as $T(d)\to\infty$ for regularly varying (Bingham et al. [1987]) cost functions of the form $\zeta_{a}\cdot x^{\beta}\cdot\ln^{\alpha}(x+1),$ $\beta>0,\ \alpha\geq 0,$ see Corollary 5.2. This is the first explicit convergence rate of the PoA in traffic networks with regularly varying cost functions that are not polynomials for the case $T(d)\to\infty$.

Altogether, we have considerably enhanced the sensitivity results of Englert et al. [2010], Takalloo and Kwon [2020] and Cominetti et al. [2020] by considering general traffic networks and simultaneous changes of demands and cost functions. Our results establish the first sensitivity analysis of the PoA for simultaneous changes of demands and cost functions in traffic networks with multiple O/D pairs.

These sensitivity results give also new insights into congestion pricing with tolls. Tolls change the cost functions, and so—due to our sensitivity results—tolls need to be considerable in order to reduce the PoA significantly. This has, e.g., been observed by Harks et al. [2015]. They consider tolls on a limited number of streets and use steepest descent methods to reduce the PoA. Their empirical calculations stabilize quickly with decreasing changes of the tolls, as justified in hindsight by our results. Furthermore, our results help to analyze the convergence rates of the PoA when the total demand $T(d)$ tends to zero or infinity.

Although we use the terminology of traffic networks in this paper, our analysis and results do not depend on this view and carry over naturally to arbitrary non-atomic congestion games.

Koutsoupias and Papadimitriou [1999] proposed to quantify the inefficiency of equilibria in arbitrary congestion games from a worst-case perspective. This then resulted in the concept of the price of anarchy (PoA) that is usually defined as the ratio of the worst case equilibrium cost over the socially optimal cost, see Papadimitriou [2001].

The paper is organized as follows. We develop our approach for general non-atomic congestion games but with the terminology of traffic networks. These are introduced in Section 2. Section 3 defines the metric and the topological space for games with the same combinatorial structure. Section 4 then presents our techniques and sensitivity analysis results. Section 5 demonstrates that our results also facilitate the analysis of the convergence rate of the PoA when the total demand tends to $0$ or $\infty.$ We conclude with a short summary and discussion in Section 6.

We define an arbitrary non-atomic congestion game with the terminology of traffic games (see, e.g., Nisan et al. [2007]; Roughgarden and Tardos [2002]), since this is more intuitive. A non-atomic congestion game $\Gamma$ is then associated with a traffic network $G=(V,A)$, and consists of a tuple $(\mathcal{K},\mathcal{S},\tau,d)$ with components defined in G1–G5 below.

• G1

  $\mathcal{K}$ is a finite non-empty set of groups or populations of users. Every group $k\in\mathcal{K}$ corresponds to a (transport) origin-destination (O/D) pair in the network $G.$ We will write an O/D pair $k\in\mathcal{K}$ as $(o_{k},t_{k})\in V^{2}$ when the origin $o_{k}$ and the destination $t_{k}$ are specified.

• G2

  $\mathcal{S}=\cup_{k\in\mathcal{K}}\mathcal{S}_{k},$ where each $\mathcal{S}_{k}\subseteq 2^{A}\setminus\emptyset$ denotes a non-empty collection of $(o_{k},t_{k})$-paths that are (pure) strategies available only to users of O/D pair $k$. Here, a $(o_{k},t_{k})$-path is a non-empty subset of the arc set $A$ that is loop-free and leads from the origin $o_{k}$ to the destination $t_{k}.$ The sets $\mathcal{S}_{k}$ are then mutually disjoint, i.e., $\mathcal{S}_{k}\cap\mathcal{S}_{k^{\prime}}=\emptyset$ for any two distinct O/D pairs $k,k^{\prime}\in\mathcal{K}.$

• G3

  $\tau=(\tau_{a})_{a\in A}$ is a cost function vector, in which each $\tau_{a}:[0,\infty)\to[0,\infty)$ is a continuous and non-decreasing latency or cost function of arc $a\in A$ that depends on the flow value of arc $a$ and includes also all other extra cost for using arc $a$ such as tolls.

• G4

  $d=(d_{k})_{k\in\mathcal{K}}$ is a demand vector whose component $d_{k}\geq 0$ denotes the demand to be transported by (users of) O/D pair $k\in\mathcal{K}$ using paths in $\mathcal{S}_{k}.$ So $\Gamma$ has the total (transport) demand $T(d):=\sum_{k\in\mathcal{K}}d_{k}.$

• G5

  Users are non-cooperative. Each user of an arbitrary O/D pair $k\in\mathcal{K}$ is infinitesimal, i.e., controls an infinitesimal fraction of the demand $d_{k}$, and must satisfy that by choosing a path $s\in\mathcal{S}_{k}$. The demand $d_{k}$ will then be arbitrarily split among paths in $\mathcal{S}_{k}$ for each O/D pair $k\in\mathcal{K}.$

A (pure) strategy profile (or simply, profile) over all users is expressed as a multi-commodity (path) flow $f=(f_{s})_{s\in\mathcal{S}}=(f_{s})_{s\in\mathcal{S}_{k},k\in\mathcal{K}}$ of the network $G$ with $\sum_{s^{\prime}\in S_{k}}f_{s^{\prime}}=d_{k}$ for each O/D pair $k\in\mathcal{K}.$ Herein, the flow value $f_{s}\geq 0$ is just the demand transported along the path $s\in\mathcal{S}.$ The flow value $f_{a}$ of an arc $a\in A$ is then obtained as $f_{a}:=\sum_{s\in\mathcal{S}:a\in s}f_{s}$. Hence, an arc $a\in A$ has the cost $\tau_{a}(f_{a}),$ a path $s\in\mathcal{S}$ has the cost $\tau_{s}(f):=\sum_{a\in A:a\in s}\tau_{a}(f_{a}),$ and all users have the total cost $C(\Gamma,f):=\sum_{s\in\mathcal{S}}f_{s}\cdot\tau_{s}(f)=\sum_{a\in A}f_{a}\cdot\tau_{a}(f_{a})$.

We call the triple $(G,\mathcal{K},\mathcal{S})$ the combinatorial structure of $\Gamma$, and denote $\Gamma$ by simply the pair $(\tau,d)$ when its combinatorial structure $(G,\mathcal{K},\mathcal{S})$ is given.

Viewed as a general non-atomic congestion game, the arcs $a\in A$ and paths $s\in\mathcal{S}$ correspond to resources and (pure) strategies of users, see, e.g., Dafermos and Sparrow [1969], Rosenthal [1973] and Correa et al. [2005]. Although we chose to use the terminology of traffic games, the analysis and results are independent of this view and carry over to general non-atomic congestion games.

A flow $f^{*}=(f^{*}_{s})_{s\in\mathcal{S}}$ of $\Gamma$ is called a social optimum (SO) if it has the minimum total cost, i.e., $C(\Gamma,f^{*})\leq C(\Gamma,f)$ for an arbitrary flow $f$ of $\Gamma.$

A flow $\tilde{f}=(\tilde{f}_{s})_{s\in\mathcal{S}}$ of $\Gamma$ is called a Wardrop equilibrium (WE) if it fulfills Wardrop’s first principle (Wardrop [1952]), i.e.,

$$\forall k\in\mathcal{K}\ \forall s,s^{\prime}\in\mathcal{S}_{k}\Big{(}\tilde{f}_{s}>0\implies\tau_{s}(\tilde{f})\leq\tau_{s^{\prime}}(\tilde{f})\Big{)}.$$

(2.1)

Clearly, every WE flow $\tilde{f}$ of $\Gamma$ satisfies condition (2.2):

$$\forall k\in\mathcal{K}\ \forall s\in\mathcal{S}_{k}:\quad\tilde{f}_{s}>0\implies\tau_{s}(\tilde{f})=L_{k}(\tau,d):=\min_{s^{\prime}\in\mathcal{S}_{k}}\tau_{s^{\prime}}(\tilde{f}).$$

(2.2)

We call the constant $L_{k}(\tau,d)$ in condition (2.2) the user cost of O/D pair $k\in\mathcal{K}.$ The total cost of WE flows $\tilde{f}$ is then expressed equivalently by

$$C(\Gamma,\tilde{f})=\sum_{s\in\mathcal{S}}\tilde{f}_{s}\cdot\tau_{s}(\tilde{f})=\sum_{k\in\mathcal{K}}L_{k}(\tau,d)\cdot d_{k}.$$

(2.3)

Trivially, a flow $\tilde{f}$ of $\Gamma$ is a WE if and only if $\tilde{f}$ satisfies the variational inequality

$$\sum_{a\in A}\tau_{a}(\tilde{f}_{a})\cdot(g_{a}-\tilde{f}_{a})=\sum_{s\in\mathcal{S}}\tau_{s}(\tilde{f})\cdot(g_{s}-\tilde{f}_{s})>0$$

(2.4)

for an arbitrary flow $g=(g_{s})_{s\in\mathcal{S}}$ of $\Gamma,$ see, e.g., Dafermos [1980].

Since the cost functions $\tau_{a}(\cdot)$ are non-negative, continuous and non-decreasing, and since the users are infinitesimal, $\Gamma$ has essentially unique WE flows, i.e., $\tau_{a}(\tilde{f}_{a})=\tau_{a}(\tilde{f}^{\prime}_{a})$ for all $a\in A$ for two arbitrary WE flows $\tilde{f}$ and $\tilde{f}^{\prime}$ of $\Gamma,$ see, e.g., Schmeidler [1973], Smith [1979] and Roughgarden and Tardos [2002]. In particular, WE flows of $\Gamma$ coincide with (pure) Nash equilibria (NE) of $\Gamma$, see, e.g., Roughgarden and Tardos [2002] for a definition of NE flows in non-atomic congestion games.

When all cost functions $\tau_{a}(\cdot)$ are differentiable, an SO flow $f^{*}$ is also a WE flow w.r.t. the marginal cost functions $c_{a}(x):=x\cdot\tau^{\prime}_{a}(x)+\tau_{a}(x),$ and, vice versa, a WE flow is an SO flow w.r.t. the cost functions

$$\frac{1}{x}\int_{0}^{x}\tau_{a}(\xi)d\xi,$$

see, e.g., Beckmann et al. [1956] or Roughgarden and Tardos [2002]. Hence, SO flows coincide with WE flows when all cost functions $\tau_{a}(\cdot)$ are monomials of the same degree $\beta\geq 0.$

In general, SO flows and WE flows differ, see, e.g., Roughgarden and Tardos [2002]. The ratio of the worst-case total cost of a WE flow over the total cost of an SO flow is known as the Price of Anarchy (PoA, see Koutsoupias and Papadimitriou [1999] and Papadimitriou [2001]), and measures the inefficiency of WE flows. Formally, the PoA of $\Gamma$ is defined as

$$\rho(\Gamma):=\frac{C(\Gamma,\tilde{f})}{C(\Gamma,f^{*})}=\frac{\sum_{s\in\mathcal{S}}\tilde{f}_{s}\cdot\tau_{s}(\tilde{f})}{\sum_{s\in\mathcal{S}}f^{*}_{s}\cdot\tau_{s}(f^{*})},$$

(2.5)

where $\tilde{f}$ and $f^{*}$ are an arbitrary WE flow and an arbitrary SO flow of $\Gamma,$ respectively. Definition (2.5) is unambiguous since WE flows are essentially unique.

A non-atomic congestion game $\Gamma$ is actually a potential game, see, e.g., Sandholm [2001]. The (Rosenthal) potential function of $\Gamma$ is given by

$$\Phi(\Gamma,f)=\sum_{a\in A}\int_{0}^{f_{a}}\tau_{a}(x)\ dx,$$

(2.6)

and reaches its global minimum at its WE flows $\tilde{f}$, see, e.g., Roughgarden and Tardos [2002].

A flow $f$ is an $\epsilon$-approximate WE flow of $\Gamma$ for a small constant $\epsilon>0,$ if

$$\sum_{a\in A}\tau_{a}(f_{a})\cdot(f_{a}-g_{a})=\sum_{s\in\mathcal{S}}\tau_{s}(f)\cdot(f_{s}-g_{s})=\sum_{k\in\mathcal{K}}\sum_{s\in\mathcal{S}_{k}}\tau_{s}(f)\cdot(f_{s}-g_{s})\leq\epsilon$$

(2.7)

for an arbitrary flow $g=(g_{s})_{s\in\mathcal{S}}$ of $\Gamma$. The variational inequality (2.7) implies that

$$\tau_{s}(f)\leq\tau_{s^{\prime}}(f)+\frac{\epsilon}{\min_{s^{\prime\prime}\in\mathcal{S}:\ f_{s^{\prime\prime}}>0}f_{s^{\prime\prime}}}=\tau_{s^{\prime}}(f)+\Theta(\epsilon)$$

(2.8)

for two arbitrary paths $s,s^{\prime}\in\mathcal{S}_{k}$ with $f_{s}>0,$ for every O/D pair $k\in\mathcal{K}.$ Inequality (2.8) means that a unilateral change of paths in an $\epsilon$-approximate WE flow $f$ reduces the cost by at most $\Theta(\epsilon),$ and so $f$ indeed approximates a WE flow. In principle, we can alternatively define an $\epsilon$-approximate WE flow directly by inequality (2.8) (as was done, e.g., by Roughgarden and Tardos [2002]). But this does not considerably influence our analysis. We thus stick to the variational inequality definition (2.7), since it, together with the variational inequality (2.4), facilitates the cost comparison between an $\epsilon$-approximate WE flow and a precise WE flow, see, e.g., Lemma 1b).

Lemma 1 shows some useful properties of $\epsilon$-approximate WE flows. Here, a real-valued function $h(\cdot)$ is Lipschitz continuous on an interval $I\subseteq[0,\infty)$ with Lipschitz constant $M$ if $|h(x)-h(y)|\leq M\cdot|x-y|$ for all $x,y\in I.$

Lemma 1a) follows trivially from inequality (2.7). Lemma 1b) follows directly from (2.4), (2.6)–(2.7) and the fact that

$$\tau_{a}(x)\cdot(y-x)\leq\int_{x}^{y}\tau_{a}(z)\ dz\leq\tau_{a}(y)\cdot(y-x)\quad\ \forall a\in A\ \forall x\in\mathbb{R}_{\geq 0}\ \forall y\in\mathbb{R}_{\geq 0}.$$

(2.9)

Herein, $\mathbb{R}_{\geq 0}:=[0,\infty).$ Inequality (2.9) holds because every cost function $\tau_{a}(\cdot)$ is non-decreasing, non-negative and continuous. Lemma 1c) is a direct consequence of Lemma 1a)–b). It yields an approximation bound when all cost functions are Lipschitz continuous on the compact interval $[0,T(d)],$ which plays a pivotal role in the Hölder continuity analysis of the PoA in Section 4.2. Although this approximation bound is rather trivial, it is tight, see Example 2 below.

Because of Lemma 1c), we may thus want to find for a given flow $f$ an $\epsilon>0$ such that $f$ is an $\epsilon^{\prime}$-approximate WE flow for all $\epsilon^{\prime}>\epsilon,$ but not for all $\epsilon^{\prime}\in[0,\epsilon).$ We call such a constant $\epsilon\in(0,\infty)$ the approximation threshold of flow $f$ w.r.t. WE flows $\tilde{f}$ of a non-atomic congestion game $\Gamma=(\tau,d)$, and denote it by $\epsilon(\tau,d,f)$ to indicate its dependence on $\tau,$ $d$ and $f$. Note that $\epsilon(\tau,d,f)=\sum_{k\in\mathcal{K}}\sum_{s\in S_{k}}[\tau_{s}(f)-L_{k}(\tau,d,f)]\cdot f_{s}$ for each flow $f,$ where $L_{k}(\tau,d,f):=\min_{s\in\mathcal{S}_{k}}\ \tau_{s}(f)$ is the minimum path cost of O/D pair $k\in\mathcal{K}$ in flow $f.$ This follows since

$$\sum_{k\in\mathcal{K}}L_{k}(\tau,d,f)\cdot d_{k}=\min_{g\text{ is a flow of }\Gamma}\sum_{k\in\mathcal{K}}\sum_{s\in S_{k}}\tau_{s}(f)\cdot g_{s}.$$

Lemma 1c) with this approximation threshold $\epsilon(\tau,d,f)$ may then yield a tight upper bound of $|C(\Gamma,f)-C(\Gamma,\tilde{f})|$ for arbitrary Lipschitz continuous cost functions on $[0,T(d)]$, see Example 2. We will obtain a tight upper bound for this approximation threshold in Section 4.2.

To avoid unnecessary discussions, we assume that the fixed combinatorial structure $(G,\mathcal{K},\mathcal{S})$ satisfies Condition 1 below.

Condition 1

Every arc $a\in A$ belongs to some path $s\in\mathcal{S}=\cup_{k^{\prime}\in\mathcal{K}}\mathcal{S}_{k^{\prime}},$ and $|\mathcal{S}_{k}|\geq 2$ for each O/D pair $k\in\mathcal{K}$.

Condition 1 can be required w.l.o.g., as arcs $a\in A$ with $a\notin s$ for each $s\in\mathcal{S}$ play no role in a non-atomic congestion game $\Gamma=(\tau,d)$, and an O/D pair $k\in\mathcal{K}$ with a singleton path set $\mathcal{S}_{k}=\{s\}$ can be removed by using $\tau_{a}(x+d_{k})$ instead of $\tau_{a}(x)$ for each arc $a$ belonging to the unique path $s$ in $\mathcal{S}_{k}.$

The PoA $\rho(\Gamma)$ is obviously $\frac{0}{0}$ when the total demand $T(d)=0.$ In fact, even if $T(d)>0,$ the PoA may still be $\frac{0}{0}$ when we allow $\tau_{a}(x)=0$ for some $a\in A$ and some $x\in(0,\infty)$. To avoid these undefined cases of the PoA, we assume that an arbitrary non-atomic congestion game $\Gamma=(\tau,d)$ satisfies Condition 2 below.

Condition 2

$T(d)>0$ and $\tau_{a}(x)>0$ for all $a\in A$ and all $x\in(0,T(d)].$

Lemma 3 shows that $\rho(\Gamma)\in[1,\infty)$ is well defined for each non-atomic congestion game $\Gamma=(\tau,d)$ fulfilling Condition 2. The proof of Lemma 3 is trivial, and thus omitted.

As the definitions of cost functions $\tau_{a}(x)$ on the unbounded interval $(T(d),\infty)$ play no role in a non-atomic congestion game $\Gamma=(\tau,d),$ we define an equivalence relation between non-atomic congestion games as follows.

Equivalence

Two non-atomic congestion games $\Gamma=(\tau,d)$ and $\Gamma^{\prime}=(\sigma,d^{\prime})$ are equivalent, denoted by $\Gamma\simeq\Gamma^{\prime},$ when

$$d_{k}=d^{\prime}_{k}\ \forall k\in\mathcal{K}\quad\text{and}\quad\tau_{a}(x)=\sigma_{a}(x)\ {\forall a\in A\ \forall x\in[0,T(d)]=[0,T(d^{\prime})].}$$

(3.1)

While the cost function values $\tau_{a}(x)$ and $\sigma_{a}(x)$ might differ largely on the unbounded interval $(T(d),\infty),$ the corresponding non-atomic congestion games $\Gamma=(\tau,d)$ and $\Gamma^{\prime}=(\sigma,d)$ have the same game-theoretic properties when $\Gamma\simeq\Gamma^{\prime}$.

We now introduce a topology for the space of all non-atomic congestion games defined on the combinatorial structure $(G,\mathcal{K},S).$ All topological notions not explicitly defined here are standard, and we recommend Kelley [1975] as a standard reference for them.

We denote by $\mathcal{G}(G,\mathcal{K},\mathcal{S})$ the set of all non-atomic congestion games $\Gamma=(\tau,d)$ that have the fixed combinatorial structure $(G,\mathcal{K},\mathcal{S})$ and satisfy Condition 2. We call $\mathcal{G}(G,\mathcal{K},\mathcal{S})$ the $(G,\mathcal{K},\mathcal{S})$-game space (or, simply, the game space), and call each non-atomic congestion game $\Gamma=(\tau,d)\in\mathcal{G}(G,\mathcal{K},\mathcal{S})$ a game, or a point of the game space.

Clearly,

$$\mathcal{G}(G,\mathcal{K},\mathcal{S})\subsetneq\overline{\mathcal{G}}(G,\mathcal{K},\mathcal{S}):=\mathcal{C}_{+}^{\uparrow}(\mathbb{R}_{\geq 0})^{A}\times\mathbb{R}_{\geq 0}^{\mathcal{K}},$$

(3.2)

where $\mathcal{C}_{+}^{\uparrow}(\mathbb{R}_{\geq 0})$ denotes the set of all non-decreasing, non-negative and continuous functions defined on $\mathbb{R}_{\geq 0}=[0,\infty),$ $\mathcal{C}_{+}^{\uparrow}(\mathbb{R}_{\geq 0})^{A}:=\{(\tau_{a})_{a\in A}:\tau_{a}\in\mathcal{C}_{+}^{\uparrow}(\mathbb{R}_{\geq 0})\ \forall a\in A\}$ and $\mathbb{R}_{\geq 0}^{\mathcal{K}}:=\{d=(d_{k})_{k\in\mathcal{K}}:d_{k}\in\mathbb{R}_{\geq 0}\ \forall k\in\mathcal{K}\}.$ We call the super set $\overline{\mathcal{G}}(G,\mathcal{K},\mathcal{S})$ in (3.2) the generalized game space and each element $\bar{\Gamma}=(\tau,d)\in\overline{\mathcal{G}}(G,\mathcal{K},\mathcal{S})$ a generalized game. Trivially, $\overline{\mathcal{G}}(G,\mathcal{K},\mathcal{S})$ is the collection of all non-atomic congestion games with the fixed combinatorial structure $(G,\mathcal{K},\mathcal{S}).$ Note that the PoA may be undefined for some generalized games $\bar{\Gamma}\in\overline{\mathcal{G}}(G,\mathcal{K},\mathcal{S})\setminus\mathcal{G}(G,\mathcal{K},\mathcal{S}).$