text:
\subsection{Rates in the light traffic regime}

First we present  the proof of \cref{prop:Pigou-light} on the light traffic rates in the case of a Pigou network.

\begin{Proof}[Proof of \cref{prop:Pigou-light}]
Let $\debug x$ denote the flow on edge $\debug e_{1}$.
At equilibrium, the costs on both edges must be equal so that $(\eq\debug x)^{\debug d_1}=(\debug M-\eq\debug x)^{\debug d_2}$, which is equivalent to
$\eq\debug x+(\eq\debug x)^{\debug d_1/\debug d_2}=\debug M$. Since $M$ tends to 0 it follows that $\eq\debug x$ will be small and since
$\debug d_1<\debug d_2$ the  term $(\eq\debug x)^{\debug d_1/\debug d_2}$ dominates the right hand side. Therefore
\begin{equation}
\eq\debug x
	= \debug M^{\debug d_2/\debug d_1}(1+o(1))
\end{equation}
so the equilibrium cost $\Eq(\debug \Gamma_{\debug M}) = \debug M \cdot \debug c_{1}(\eq\debug x)= \debug M \cdot \debug c_{2}(\debug M-\eq\debug x)$ scales as
\begin{equation}
\Eq(\debug \Gamma_{\debug M})
	= \debug M \cdot \left[\debug M-\debug M^{\debug d_2/\debug d_1}(1+o(1))\right]^{\debug d_2}
	= \debug M^{\debug d_2+1} - \debug d_2\debug M^{\debug d_2+\debug d_1/\debug d_2}+o(\debug M^{\debug d_2+\debug d_1/\debug d_2}).
\end{equation}

Similarly, if $\opt{\debug x}$ is the optimal flow on edge $\debug e_{1}$, both edges have the same marginal cost
\begin{equation}
(1+\debug d_1)\opt{\debug x}^{\debug d_1}
	= (1+\debug d_2)(\debug M-\opt{\debug x})^{\debug d_2}.
\end{equation}
Therefore, if we let
\begin{equation}
\label{eq:pigou alt light}
\debug \rho
	= \left(\frac{1+\debug d_2}{1+\debug d_1}\right)^{1/\debug d_2},
\end{equation}
we get $\debug \rho\opt{\debug x}+\opt{\debug x}^{\debug d_1/\debug d_2}=\debug \rho\debug M$ as before, and hence
\begin{equation}
\opt{\debug x}
	=(\debug \rho\debug M)^{\debug d_2/\debug d_1}(1+o(1)).
\end{equation}
It follows that the optimal cost scales as
\begin{flalign}
\Opt(\debug \Gamma_{\debug M})
	&=\opt{\debug x} \cdot \debug c_{1}(\opt{\debug x})+(\debug M-\opt{\debug x})\cdot\debug c_{2}(\debug M-\opt{\debug x})
	\notag\\
	&=\left[(\debug \rho\debug M)^{\debug d_2/\debug d_1}(1+o(1))\right]^{\debug d_1+1}
+\left[\debug M-(\debug \rho\debug M)^{\debug d_2/\debug d_1}(1+o(1))\right]^{\debug d_2+1}\notag\\
	&=(\debug \rho\debug M)^{\debug d_2+\debug d_2/\debug d_1} +\debug M^{\debug d_2+1} - (\debug d_2+1)\debug M^{\debug d_2}(\debug \rho\debug M)^{\debug d_2/\debug d_1} +o(\debug M^{\debug d_2+\debug d_2/\debug d_1})
	\notag\\
	&=\debug M^{\debug d_2+1} - \debug \rho^{\debug d_2/\debug d_1}\left[(\debug d_2+1)-\debug \rho^{\debug d_2}\right]\debug M^{\debug d_2+\debug d_2/\debug d_1}+o(\debug M^{\debug d_2+\debug d_2/\debug d_1})
	\notag\\
	&=\debug M^{\debug d_2+1} - (\debug b + \debug d_2) \debug M^{\debug d_2+\debug d_2/\debug d_1}+o(\debug M^{\debug d_2+\debug d_2/\debug d_1})
\end{flalign}
where the last equality follows from the identity $\debug \rho^{\debug d_2/\debug d_1}\left[(\debug d_2+1)-\debug \rho^{\debug d_2}\right]=\debug b+\debug d_2$.

Combining the previous expressions we get
\begin{flalign}
\PoA(\debug \Gamma_{\debug M})
	=\frac{\Eq(\debug \Gamma_{\debug M})}{\Opt(\debug \Gamma_{\debug M})}&=\frac{\Opt(\debug \Gamma_{\debug M}) + \debug b\debug M^{\debug d_2+\debug d_2/\debug d_1}+o(\debug M^{\debug d_2+\debug d_2/\debug d_1})}{\Opt(\debug \Gamma_{\debug M})}
	\notag\\
	&=1+\frac{\debug b\debug M^{\debug d_2+\debug d_2/\debug d_1}+o(\debug M^{\debug d_2+\debug d_2/\debug d_1})}{\debug M^{\debug d_2+1}+o(\debug M^{\debug d_2+1})}
	\notag\\
	&=1 + \debug b\debug M^{\debug a}+o(\debug M^{\debug a}).
\end{flalign}

To complete our proof, it remains to show that $\debug b>0$.
After a small rearrangement, this is equivalent to establishing the inequality
\begin{equation}
\parens*{\frac{1 + \debug d_{2}}{1 + \debug d_{1}}}^{1+\debug d_{1}}
	= \parens*{1 + \frac{\debug d_{2} - \debug d_{1}}{1 + \debug d_{1}}}^{1+\debug d_{1}}
	> \parens*{1 +\frac{\debug d_{2} - \debug d_{1}}{\debug d_{1}}}^{\debug d_{1}}
	= \parens*{\frac{\debug d_{2}}{\debug d_{1}}}^{\debug d_{1}},
\end{equation}
which itself follows from the fact that the function $(1+\debug g/x)^{x}$ is increasing in $x$ whenever $\debug g$ is positive.
\end{Proof}

Now we prove the following more general version of \cref{thm:rate-light}.
\begin{theorem}
\label{thm:rate-light-seq}
Let $\debug \Gamma_{\debug n}$ be a sequence of nonatomic routing games satisfying the assumptions of Theorem
\ref{thm:multi-variable}, with $\debug M_\debug n\to 0$. Suppose further that the edge costs are polynomials as in \eqref{eq:polynomials},
and let $\debug a=\debug q/\slow\debug q-1$ with $\debug q$ and $\slow\debug q$ given by \eqref{eq:ord-net-light}
and \eqref{eq:gap-light} respectively.
Then, there exist non-negative constants $\debug K_{1}\geq 0$ and $\debug K_{\adegr}\geq 0$ such that
\begin{equation}
\label{eq:rate-light-seq}
\PoA(\debug \Gamma_{\debug n})
	\leq 1 + \debug K_{1}\debug M_{\debug n} + \debug K_{\adegr}\debug M_{\debug n}^{\debug a}
\end{equation}
with $\debug K_{\adegr}=0$ whenever $\slow\mathcal{\debug E}=\varnothing$.
\end{theorem}

\begin{Proof} Let $\eq{\debug y}_{\debug n},\opt{\debug y}_{\debug n}\in\mathcal{\debug Y}$ be an equilibrium and an optimum flow
for $\debug \Gamma_{\debug n}$ with induced edge flows $\eq\debug x_{\debug e,\debug n}=\debug M_{\debug n}\;\debug \zeta_{\debug e}(\eq\debug y_{\debug n},\debug \lambda_{\debug n})$ and $\opt\debug x_{\debug e,\debug n}=\debug M_{\debug n}\;\debug \zeta_{\debug e}(\opt\debug y_{\debug n},\debug \lambda_{\debug n})$.
The social cost of $\eq{\debug y}_{\debug n}$ can be estimated as
\begin{flalign}
\debug L_{\debug n}(\eq{\debug y}_{\debug n})
	&=\sum_{\debug e\in\mathcal{\debug E}}
	\eq\debug x_{\debug e,\debug n}\;\debug c_{\debug e}\parens{\eq\debug x_{\debug e,\debug n}}
	=\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\debug c_{\debug e,\debug k} \cdot \parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&=\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\bracks*{\frac{\debug q+1}{\debug k+1} + \frac{\debug k-\debug q}{\debug k+1}}
	\debug c_{\debug e,\debug k} \cdot \parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&= (\debug q+1) \sum_{\debug e\in\mathcal{\debug E}} \debug C_{\debug e}({\eq\debug x_{\debug e,\debug n}})+
\sum_{\debug e\in\mathcal{\debug E}}\sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}\frac{\debug k-\debug q}{\debug k+1}\debug c_{\debug e,\debug k}\cdot\parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&\le (\debug q+1)\sum_{\debug e\in\mathcal{\debug E}}\debug C_{\debug e}({\opt\debug x_{\debug e,\debug n}})+
\sum_{\debug e\in\mathcal{\debug E}}\sum_{\debug k=\debug q+1}^{\debug d_{\debug e}}\frac{\debug k-\debug q}{\debug k+1}\debug c_{\debug e,\debug k}\cdot\parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
\label{oooo-light}
\end{flalign}
where $\debug C_{\debug e}$ is the primitive of $\debug c_{\debug e}$ and for the last inequality we used the fact that ${\eq\debug x_{\debug e,\debug n}}$ minimizes the first sum,
and in the double sum we dropped the negative terms with $\debug k\leq\debug q$.
Now, the first sum in \eqref{oooo-light} can be further bounded as
 \begin{flalign}
(\debug q+1)\sum_{\debug e\in\mathcal{\debug E}}\debug C_{\debug e}({\opt\debug x_{\debug e,\debug n}})
	&= \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}} \frac{\debug q+1}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&= \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	+ \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\frac{\debug q-\debug k}{\debug k+1} \debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&\leq \Opt(\debug \Gamma_{\debug n})
	+ \sum_{\debug e\in\slow\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug q-1}\frac{\debug q-\debug k}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag
\end{flalign}
where  we used the optimality of $\opt\debug x_{\debug n}$ in the first double sum,
and we dropped the negative terms in the second.
Note that in the latter only the slow edges with $\debug q_\debug e<\debug q$ are relevant. Combining these estimates we get
\begin{equation}\label{eq:ooo-light}
\debug L_{\debug n}(\eq{\debug y}_{\debug n})
	\leq
	\Opt(\debug \Gamma_{\debug n})
	+ \sum_{\debug e\in\slow\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug q-1}\frac{\debug q-\debug k}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	+
\sum_{\debug e\in\mathcal{\debug E}}\sum_{\debug k=\debug q+1}^{\debug d_{\debug e}}\frac{\debug k-\debug q}{\debug k+1}\debug c_{\debug e,\debug k}\cdot\parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\end{equation}

Let us call $\debug L_{\debug n}^{\textup{I}}$ the first double sum  in \eqref{eq:ooo-light} and $\debug L_{\debug n}^{\textup{II}}$ the second.
In order to bound $\debug L_{\debug n}^{\textup{II}}$ we assume that $\debug n$  is large enough so that
$\debug M_\debug n\leq 1$. This assumption is done for convenience and it only affects the value of the constants $\debug K_{1}$ and $\debug K_{\adegr}$:
by redefining them appropriately, the bound \eqref{eq:rate-light-seq} will hold for all $\debug n$. Then  by setting
\begin{equation}
\debug G =\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q+1}^{\debug d_\debug e} \frac{\debug k-\debug q}{\debug k+1} \debug c_{\debug e,\debug k},
\end{equation}
and noting that $\eq\debug x_{\debug e,\debug n}\leq\debug M_\debug n$, we get
\begin{equation}\label{eq:obj-II-light}
\debug L_{\debug n}^{\textup{II}}\leq\sum_{\debug e\in\mathcal{\debug E}}\sum_{\debug k=\debug q+1}^{\debug d_{\debug e}}\frac{\debug k-\debug q}{\debug k+1}\debug c_{\debug e,\debug k}\cdot\debug M_{\debug n}^{\debug k+1}\leq \debug G\debug M_{\debug n}^{\debug q+2}.
\end{equation}

In order to bound $\debug L_{\debug n}^{\textup{I}}$ we note that this term vanishes when $\slow\mathcal{\debug E}$ is empty.
Otherwise, consider any edge $\debug e\in\slow\mathcal{\debug E}$ that contributes to the sum with $\opt\debug x_{\debug e,\debug n}>0$.
We note that the optimum flow $\opt{\debug y}_{\debug n}$ is an equilibrium for the marginal cost functions
\begin{equation}\label{}
\opt\debug c_\debug e(\debug x)=\debug c_\debug e(\debug x)+\debug x\;\debug c_{\debug e}'(\debug x)=\sum_{\debug k=\debug q_\debug e}^{\debug d_\debug e}(\debug k+1)\debug c_{\debug e,\debug k}\debug x^\debug k.
\end{equation}
The edge $\debug e$ must therefore belong to an optimal path $\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}$ (w.r.t. the costs
$\opt\debug c_\debug e(\debug x)$) for some $\debug \play\in\debug \players$.
Hence, taking any alternative path $\route'\in\mathcal{\debug \nRoutes}^{\debug \play}$ which is not slow, i.e.,\xspace with $\debug q_{\edge'}\geq\debug q$
for all $\edge'\in\route'$, and denoting
\begin{equation}
\debug B
	=\sum_{\edge'\not\in\slow\mathcal{\debug E}}\sum_{\debug k=\debug q_{\edge'}}^{\debug d_{\edge'}}(\debug k+1)\debug c_{\edge',\debug k},
\end{equation}
we get the bound (recall that $\debug M_\debug n\leq 1$)
\begin{equation}\label{eq:eee-light}
\opt\debug c_{\debug e}(\opt\debug x_{\debug e,\debug n})
	\leq \sum_{\edge'\in\debug p}\opt\debug c_{\edge'}(\opt\debug x_{\debug e,\debug n})
	\leq \sum_{\edge'\in\route'}\opt\debug c_{\edge'}(\opt\debug x_{\debug e,\debug n})
	\leq \sum_{\edge'\in\route'}\opt\debug c_{\edge'}(\debug M_{\debug n})
	\leq \debug B\debug M_{\debug n}^{\debug q}.
\end{equation}
In particular, letting $\opt\debug c_{0}=\min_{\debug e\in\slow\mathcal{\debug E}}(\debug q_\debug e+1)\debug c_{\debug e,\debug q_{\debug e}}$ we have
\begin{equation}
\opt\debug c_{0}\cdot\left(\opt\debug x_{\debug e,\debug n}\right)^{\debug q_{\debug e}}\leq
(\debug q_\debug e+1)\debug c_{\debug e,\debug q_{\debug e}}\cdot\left(\opt\debug x_{\debug e,\debug n}\right)^{\debug q_{\debug e}}
	\leq \opt\debug c_{\debug e}\parens{\opt\debug x_{\debug e,\debug n}}
	\leq \debug B\debug M_{\debug n}^{\debug q}.
\end{equation}
Now, for $\debug n$ large we have $\debug B\debug M_{\debug n}^{\debug q}/\opt\debug c_0\leq 1$
and since $\debug q_\debug e\leq\slow\debug q$ we obtain
$\opt\debug x_{\debug e,\debug n}\le\left(\debug B\debug M_{\debug n}^{\debug q}/\opt\debug c_{0}\right)^{1/\slow\debug q}$.
Combining this latter bound with \eqref{eq:eee-light},  and
denoting $\debug D = \debug B\left(\debug B/\opt\debug c_{0}\right)^{1/\slow\debug q}|\slow\mathcal{\debug E}|$, we deduce
\begin{flalign}\label{eq:obj-I-light}
\debug L_{\debug n}^{\textup{I}} &=
\sum_{\debug e\in\slow\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug q-1}\frac{\debug q-\debug k}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}\nonumber \\
	&\leq
\sum_{\debug e\in\slow\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug q-1}(\debug k+1)	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}\nonumber \\
&\leq
\sum_{\debug e\in\slow\mathcal{\debug E}} \opt\debug x_{\debug e,\debug n}\;\opt\debug c_{\debug e}(\opt\debug x_{\debug e,\debug n})\nonumber \\
	&\leq \sum_{\debug e\in\slow\mathcal{\debug E}} \parens*{\debug B\debug M_{\debug n}^{\debug q}/\opt\debug c_{0}}^{1/\slow\debug q}\debug B\debug M_{\debug n}^{\debug q} \nonumber\\
&\le\debug D\debug M_{\debug n}^{\debug q+\debug q/\slow\debug q}.
\end{flalign}

Plugging \eqref{eq:obj-I-light} and \eqref{eq:obj-II-light} into \eqref{eq:ooo-light} we get
\begin{flalign}
\label{eq:poapol-light}
\PoA(\debug \Gamma_{\debug n})
	=\frac{\debug L_{\debug n}(\eq{\debug y}_{\debug n})}{\Opt(\debug \Gamma_{\debug n})}
	&\leq \frac{\Opt(\debug \Gamma_{\debug n}) + \debug G\debug M_{\debug n}^{\debug q+2} + \debug D\debug M_{\debug n}^{\debug q+\debug q/\slow\debug q}}{\Opt(\debug \Gamma_{\debug n})}.
\end{flalign}

Now, if we set $\debug H=\min_{\debug e\in\mathcal{\debug E}}\debug c_{\debug e,\debug q_{\debug e}}$, we have the following lower bound for the optimal cost
\begin{flalign}
\Opt(\debug \Gamma_{\debug n})
	&= \sum_{\debug e\in\mathcal{\debug E}}
	\opt\debug x_{\debug e,\debug n}
	\cdot \debug c_{\debug e}(\opt\debug x_{\debug e,\debug n})
	\geq \debug H \sum_{\debug e\in\mathcal{\debug E}}
	\parens{\opt\debug x_{\debug e,\debug n}}^{\debug q_{\debug e}+1}.
\end{flalign}

We claim that the latter is of order at least $O(\debug M_{\debug n}^{\debug q+1})$. Indeed, let us take $\varepsilon>0$ with $\sum_{\debug \play\in\tight\debug \players} \debug \lambda_{\debug n}^\debug \play\geq\varepsilon$ for sufficiently large $\debug n$.
For each $\debug n\in\mathbb{N}$ we may find $\debug \play\in\tight\debug \players$ such that $\debug \lambda_{\debug n}^{\debug \play} \geq \varepsilon/\abs{\tight\debug \players}$ and, similarly, there exists a path $\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}$ with $\opt\debug y_{\debug p,\debug n} \geq 1/\abs{\mathcal{\debug \nRoutes}^{\debug \play}}\geq 1/\abs{\mathcal{\debug \nRoutes}}$.
Then, setting $\kappa=1/(\abs{\tight\debug \players}\times\abs{\mathcal{\debug \nRoutes}})$ we have $\debug \zeta_{\debug e}(\opt\debug y_\debug n,\debug \lambda_{\debug n}) \geq \kappa\varepsilon$ and therefore $\opt\debug x_{\debug e,\debug n} \geq \debug M_\debug n\kappa\varepsilon$ for all $\debug e\in\debug p$.
For $\debug n$ large we may assume that $\debug M_{\debug n}\kappa\varepsilon\leq 1$ and, since the path $\debug p$ contains at least one edge $\debug e\in\debug p$ with $\debug q_{\debug e}\leq\debug q$, setting $\bar{\debug H}= \debug H(\kappa\varepsilon)^{\debug q+1}$ we get
\begin{equation}
\Opt(\debug \Gamma_{\debug n})
	\geq \debug H\left(\debug M_{\debug n}\kappa\varepsilon\right)^{\debug q_{\debug e}+1}\ge\bar{\debug H}\debug M_{\debug n}^{\debug q+1}.
\end{equation}

This lower bound, combined with \eqref{eq:poapol-light}, yields \eqref{eq:rate-light-seq} with $\debug K_{1}=\debug G/\bar{\debug H}$ and $\debug K_{\adegr}=\debug D/\bar{\debug H}$.
We conclude by noting that when $\slow\mathcal{\debug E}=\varnothing$ we have $\debug L_{\debug n}^{\textup{I}} = 0$ and therefore we may take $\debug K_{\adegr}=0$.
\end{Proof}

\subsection{Rates in the heavy traffic regime}

We proceed with the proof of \cref{prop:Pigou-heavy} on the heavy traffic rates in the case of a Pigou network.
\begin{Proof}[Proof of \cref{prop:Pigou-heavy}]
Let $\debug x$ denote the flow on edge $\debug e_{2}$.
At equilibrium, the costs on both edges must be equal so $(\eq\debug x)^{\debug d_{2}}=(\debug M-\eq\debug x)^{\debug d_{1}}$, which is equivalent to  $\eq\debug x+(\eq\debug x)^{\debug d_{2}/\debug d_{1}} = \debug M$.
It thus follows that
\begin{equation}
\eq\debug x
	= \debug M^{\debug d_{1}/\debug d_{2}}(1+o(1)),
\end{equation}
implying in turn that the equilibrium cost $\Eq(\debug \Gamma_{\debug M}) = \debug M \cdot \debug c_{2}(\eq\debug x)= \debug M \cdot \debug c_{1}(\debug M-\eq\debug x)$ scales as
\begin{equation}
\Eq(\debug \Gamma_{\debug M})
	= \debug M \cdot \left[\debug M-\debug M^{\debug d_{1}/\debug d_{2}}(1+o(1))\right]^{\debug d_{1}}
	= \debug M^{1+\debug d_{1}} - \debug d_{1}\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}}+o(\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}}).
\end{equation}
Similarly, if $\opt{\debug x}$ is the optimal flow on edge $\debug e_{2}$, both edges have the same marginal cost, namely
\begin{equation}
(1+\debug d_{2})\opt{\debug x}^{\debug d_{2}}
	= (1+\debug d_{1})(\debug M-\opt{\debug x})^{\debug d_{1}},
\end{equation}
and hence
\begin{equation}
\opt{\debug x}
	=(\debug \theta\debug M)^{\debug d_{1}/\debug d_{2}}(1+o(1)),
\end{equation}
where we set
\begin{equation}
\label{eq:pigou alt}
\debug \theta
	= \left(\frac{1+\debug d_{1}}{1+\debug d_{2}}\right)^{1/\debug d_{1}}.
\end{equation}
Therefore, the optimal social cost scales as
\begin{flalign}
\Opt(\debug \Gamma_{\debug M})
	&=(\debug M-\opt{\debug x})\cdot\debug c_{1}(\debug M-\opt{\debug x})+\opt{\debug x} \cdot \debug c_{2}(\opt{\debug x})
	\notag\\
	&= \bracks[\big]{\debug M-(\debug \theta\debug M)^{\debug d_{1}/\debug d_{2}}(1+o(1))}^{\debug d_{1}+1}
	+ \bracks[\big]{(\debug \theta\debug M)^{\debug d_{1}/\debug d_{2}}(1+o(1))}^{\debug d_{2}+1}
	\notag\\
	&=\debug M^{\debug d_{1}+1} - (\debug d_{1}+1)\debug M^{\debug d_{1}}(\debug \theta\debug M)^{\debug d_{1}/\debug d_{2}}
	+ (\debug \theta\debug M)^{\debug d_{1} + \debug d_{1}/\debug d_{2}} +o(\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}})
	\notag\\
&=\debug M^{\debug d_{1}+1}
	- \debug \theta^{\debug d_{1}/\debug d_{2}} \bracks{(\debug d_{1}+1) - \debug \theta^{\debug d_{1}}} \debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}}
	+o(\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}}),\\
	&=\debug M^{\debug d_{1}+1}
	- (\debug b + \debug d_{1}) \debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}}
	+o(\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}}),
\end{flalign}
where $\debug b$ is defined as in \eqref{eq:Pigou-heavy}.

Combining the previous expressions, we then get
\begin{flalign}
\PoA(\debug \Gamma_{\debug M})
	&= \frac{\Opt(\debug \Gamma_{\debug M}) + \debug b\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}} + o(\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}})}{\Opt(\debug \Gamma_{\debug M})}\\
	&= 1 + \frac{\debug b\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}} + o(\debug M^{\debug d_{1} + \debug d_{1}/\debug d_{2}})}{\debug M^{\debug d_{1}+1} + o(\debug M^{\debug d_{1}+1})}
	\notag\\[.5ex]
	&= 1 + \debug b\debug M^{-\debug a} + o\parens*{\debug M^{-\debug a}},
\end{flalign}
which establishes the first part of \cref{prop:Pigou-heavy}.
Finally, the positivity of $\debug b>0$, follows again from the fact that $(1-\debug g/x)^{x}$  increased
with $x$ when $\debug g>0$.
\end{Proof}

The following more general result subsumes \cref{thm:rate-heavy}.

\begin{theorem}
\label{thm:rate-heavy_sequential}
Let $\debug \Gamma_{\debug n}$ be a sequence of nonatomic routing games satisfying the assumptions of Theorem
\ref{thm:multi-variable}, with $\debug M_\debug n\to\infty$. Suppose further that the edge costs are polynomials as in \eqref{eq:polynomials},
and let $\debug a=1-\debug d/\slow\debug d$ with $\debug d$ and $\slow\debug d$ given by \eqref{eq:ord-net-heavy}
and \eqref{eq:gap-heavy}.  Then there exist non-negative constants $\debug K_{1}\geq 0$ and $\debug K_{\adegr}\geq 0$ such that
\begin{equation}
\label{eq:rate-heavy-seq}
\PoA(\debug \Gamma_{\debug n})
	\leq 1 + \frac{\debug K_{1}}{\debug M_{\debug n}} + \frac{\debug K_{\adegr}}{\debug M_{\debug n}^{\debug a}}
\end{equation}
with $\debug K_{\adegr}=0$ whenever $\slow\mathcal{\debug E}=\varnothing$.
\end{theorem}

\begin{Proof}
The proof follows a similar pattern as the one of
\cref{thm:rate-light-seq}.
Let again $\eq{\debug y}_{\debug n},\opt{\debug y}_{\debug n}\in\mathcal{\debug Y}$ be an equilibrium and an optimum for $\debug \Gamma_{\debug n}$, respectively. Denote $\eq\debug x_{\debug e,\debug n}=\debug M_{\debug n}\;\debug \zeta_{\debug e}(\eq\debug y_{\debug n},\debug \lambda_{\debug n})$
and $\opt\debug x_{\debug e,\debug n}=\debug M_{\debug n}\;\debug \zeta_{\debug e}(\opt\debug y_{\debug n},\debug \lambda_{\debug n})$ the corresponding
induced edge flows.
As before, the social cost of $\eq{\debug y}_{\debug n}$ can be estimated as
\begin{flalign}
\debug L_{\debug n}(\eq{\debug y}_{\debug n})
	&=\sum_{\debug e\in\mathcal{\debug E}}
	\eq\debug x_{\debug e,\debug n}\;\debug c_{\debug e}\parens{\eq\debug x_{\debug e,\debug n}}
	=\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\debug c_{\debug e,\debug k} \cdot \parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&=\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\bracks*{\frac{\debug d+1}{\debug k+1} + \frac{\debug k-\debug d}{\debug k+1}}
	\debug c_{\debug e,\debug k} \cdot \parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&= (\debug d+1) \sum_{\debug e\in\mathcal{\debug E}} \debug C_{\debug e}({\eq\debug x_{\debug e,\debug n}})+
\sum_{\debug e\in\mathcal{\debug E}}\sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}\frac{\debug k-\debug d}{\debug k+1}\debug c_{\debug e,\debug k}\cdot\parens{\eq\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&\le (\debug d+1)\sum_{\debug e\in\mathcal{\debug E}}\debug C_{\debug e}({\opt\debug x_{\debug e,\debug n}})+
\sum_{\debug e\in\slow\mathcal{\debug E}}{\eq\debug x_{\debug e,\debug n}}\cdot\debug c_{\debug e}({\eq\debug x_{\debug e,\debug n}}),\label{oooo}
\end{flalign}
where  in the last inequality we used the fact that ${\eq\debug x_{\debug e,\debug n}}$ minimizes the first sum, while in the double sum we dropped the edges $\debug e\not\in\slow\mathcal{\debug E}$ since $(\debug k-\debug d)/(\debug k+1)\le 0$ for all $\debug k\leq\debug d_{\debug e}\leq\debug d$, and we used the inequality $(\debug k-\debug d)/(\debug k+1)\le 1$ to bound the remaining terms $\debug e\in\slow\mathcal{\debug E}$ by factoring out ${\eq\debug x_{\debug e,\debug n}}$ and using the expression \eqref{eq:polynomials} for $\debug c_{\debug e}(\debug x)$.
Now, the first sum in \eqref{oooo} can be further bounded as
 \begin{flalign}
(\debug d+1)\sum_{\debug e\in\mathcal{\debug E}}\debug C_{\debug e}({\opt\debug x_{\debug e,\debug n}})
	&= \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}} \frac{\debug d+1}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&= \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	+ \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d_{\debug e}}
	\frac{\debug d-\debug k}{\debug k+1} \debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1}
	\notag\\
	&\leq \Opt(\debug \Gamma_{\debug n})
	+ \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d-1}\frac{\debug d-\debug k}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1},
	\notag
\end{flalign}
where in the inequality we used the optimality of $\opt\debug x_{\debug n}$ for the first sum and we dropped the negative terms in the second sum. Putting all this together we obtain the bound
\begin{equation}\label{eq:boundLnyn}
\debug L_{\debug n}(\eq{\debug y}_{\debug n})
	\leq
	\Opt(\debug \Gamma_{\debug n})
	+ \sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d-1}\frac{\debug d-\debug k}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \parens{\opt\debug x_{\debug e,\debug n}}^{\debug k+1} +
\sum_{\debug e\in\slow\mathcal{\debug E}}{\eq\debug x_{\debug e,\debug n}}\cdot\debug c_{\debug e}({\eq\debug x_{\debug e,\debug n}}).
	\end{equation}

Now,  call $\debug L_{\debug n}^{\textup{I}}$ the first double sum and $\debug L_{\debug n}^{\textup{II}}$ the last sum in \eqref{eq:boundLnyn}.
In order to bound $\debug L_{\debug n}^{\textup{I}}$ we assume that $\debug n$ is large enough so that $\debug M_\debug n\geq 1$.
Then, denoting
\begin{equation}
\debug G
	=\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d-1} \frac{\debug d-\debug k}{\debug k+1} \debug c_{\debug e,\debug k}
\end{equation}
and using the fact that ${\opt\debug x_{\debug e,\debug n}} \leq \debug M_\debug n$, we can bound $\debug L_{\debug n}^{\textup{I}}$ as
\begin{equation}
\label{eq:obj-I}
\debug L_{\debug n}^{\textup{I}}
	\leq\sum_{\debug e\in\mathcal{\debug E}} \sum_{\debug k=\debug q_\debug e}^{\debug d-1} \frac{\debug d-\debug k}{\debug k+1}
	\debug c_{\debug e,\debug k} \cdot \debug M_{\debug n}^{\debug k+1}
\leq
	\debug G\debug M_{\debug n}^{\debug d}.
\end{equation}

In order to bound $\debug L_{\debug n}^{\textup{II}}$ we note that this term vanishes whenever $\slow\mathcal{\debug E}$ is empty.
Otherwise, consider any edge $\debug e\in\slow\mathcal{\debug E}$ that contributes to the sum with $\eq\debug x_{\debug e,\debug n}>0$. Since $\eq{\debug y}_{\debug n}$ is an equilibrium, the edge $\debug e$ must belong to a path $\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}$ with minimal cost for some $\debug \play\in\debug \players$.
Hence, taking any alternative path $\route'\in\mathcal{\debug \nRoutes}^{\debug \play}$ which is not slow, and denoting
\begin{equation}
\debug B
	=\sum_{\edge'\not\in\slow\mathcal{\debug E}}\sum_{\debug k=\debug q_\edge'}^{\debug d_{\edge'}}\debug c_{\edge',\debug k},
\end{equation}
we get the bound
\begin{flalign}
\debug c_{\debug e}(\eq\debug x_{\debug e,\debug n})
	&\leq \sum_{\edge'\in\debug p}\debug c_{\edge'}(\eq\debug x_{\debug e,\debug n})
	\leq \sum_{\edge'\in\route'}\debug c_{\edge'}(\eq\debug x_{\debug e,\debug n})
	\leq \sum_{\edge'\in\route'}\debug c_{\edge'}(\debug M_{\debug n})
	\leq \debug B\debug M_{\debug n}^{\debug d}.\label{eee}
\end{flalign}
In particular, letting $\debug c_{0}=\min_{\debug e\in\slow\mathcal{\debug E}}\debug c_{\debug e,\debug d_{\debug e}}$ we have
\begin{equation}
\debug c_{0}\cdot\left(\eq\debug x_{\debug e,\debug n}\right)^{\debug d_{\debug e}}\leq
\debug c_{\debug e,\debug d_{\debug e}}\cdot\left(\eq\debug x_{\debug e,\debug n}\right)^{\debug d_{\debug e}}
	\leq \debug c_{\debug e}\parens{\eq\debug x_{\debug e,\debug n}}
	\leq \debug B\debug M_{\debug n}^{\debug d}.
\end{equation}
Now, for $\debug n$ large we have $\debug B\debug M_{\debug n}^{\debug d}/\debug c_0\geq 1$
and since $\debug d_\debug e\geq\slow\debug d$ we get
$\eq\debug x_{\debug e,\debug n}\le\left(\debug B\debug M_{\debug n}^{\debug d}/\debug c_{0}\right)^{1/\slow\debug d}$.
Combining this latter bound with \eqref{eee},  and
denoting $\debug D = \debug B\left(\debug B/\debug c_{0}\right)^{1/\slow\debug d}|\slow\mathcal{\debug E}|$, we deduce
\begin{equation}
\label{eq:obj-II}
\debug L_{\debug n}^{\textup{II}} = \sum_{\debug e\in\slow\mathcal{\debug E}}{\eq\debug x_{\debug e,\debug n}}\cdot\debug c_{\debug e}({\eq\debug x_{\debug e,\debug n}})
	\leq \sum_{\debug e\in\slow\mathcal{\debug E}} \parens*{\debug B\debug M_{\debug n}^{\debug d}/\debug c_{0}}^{1/\slow\debug d}\debug B\debug M_{\debug n}^{\debug d}
\le\debug D\debug M_{\debug n}^{\debug d+\debug d/\slow\debug d}.
\end{equation}

Plugging \eqref{eq:obj-I} and \eqref{eq:obj-II} into \eqref{eq:boundLnyn} we get
\begin{flalign}
\label{eq:poapol}
\PoA(\debug \Gamma_{\debug n})
	=\frac{\debug L_{\debug n}(\eq{\debug y}_{\debug n})}{\Opt(\debug \Gamma_{\debug n})}
	&\leq \frac{\Opt(\debug \Gamma_{\debug n}) + \debug G\debug M_{\debug n}^{\debug d} + \debug D\debug M_{\debug n}^{\debug d+\debug d/\slow\debug d}}{\Opt(\debug \Gamma_{\debug n})}.
\end{flalign}

Now, if we set $\debug H=\min_{\debug e\in\mathcal{\debug E}}\debug c_{\debug e,\debug d_{\debug e}}$, we have the following lower bound for the optimal cost
\begin{flalign}
\Opt(\debug \Gamma_{\debug n})
	&= \sum_{\debug e\in\mathcal{\debug E}}
	\opt\debug x_{\debug e,\debug n}
	\cdot \debug c_{\debug e}(\opt\debug x_{\debug e,\debug n})
	\geq \debug H \sum_{\debug e\in\mathcal{\debug E}}
	\parens{\opt\debug x_{\debug e,\debug n}}^{\debug d_{\debug e}+1}.
\end{flalign}

We claim that the latter is of order at least $O(\debug M_{\debug n}^{\debug d+1})$. Indeed, let us take $\varepsilon>0$ with $\sum_{\debug \play\in\tight\debug \players} \debug \lambda_{\debug n}^\debug \play\geq\varepsilon$ for sufficiently large $\debug n$.
For each $\debug n\in\mathbb{N}$ we may find $\debug \play\in\tight\debug \players$ such that $\debug \lambda_{\debug n}^{\debug \play} \geq \varepsilon/\abs{\tight\debug \players}$ and, similarly, there exists a path $\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}$ with $\opt\debug y_{\debug p,\debug n} \geq 1/\abs{\mathcal{\debug \nRoutes}^{\debug \play}}\geq 1/\abs{\mathcal{\debug \nRoutes}}$.
Then, setting $\kappa=1/(\abs{\tight\debug \players}\times\abs{\mathcal{\debug \nRoutes}})$ we have $\debug \zeta_{\debug e}(\opt\debug y_\debug n,\debug \lambda_{\debug n}) \geq \kappa\varepsilon$ and therefore $\opt\debug x_{\debug e,\debug n} \geq \debug M_\debug n\kappa\varepsilon$ for all $\debug e\in\debug p$.
For $\debug n$ large we may assume that $\debug M_{\debug n}\kappa\varepsilon\geq 1$ and, since the path $\debug p$ contains at least one edge $\debug e\in\debug p$ with $\debug d_{\debug e}\geq\debug d$, setting $\bar{\debug H }= \debug H (\kappa\varepsilon)^{\debug d+1}$ we get
\begin{equation}
\Opt(\debug \Gamma_{\debug n})
	\geq \debug H\left(\debug M_{\debug n}\kappa\varepsilon\right)^{\debug d_{\debug e}+1}\ge\bar{\debug H}\debug M_{\debug n}^{\debug d+1}.
\end{equation}

This lower bound, combined with \eqref{eq:poapol}, yields \eqref{eq:rate-heavy-seq} with $\debug K_{1}=\debug G/\bar{\debug H}$ and $\debug K_{\adegr}=\debug D/\bar{\debug H}$.
We conclude by noting that when $\slow\mathcal{\debug E}=\varnothing$ we have $\debug L_{\debug n}^{\textup{II}} = 0$ and therefore we may take $\debug K_{\adegr}=0$.
\end{Proof}

\subsection{Sioux Falls: a representative case study}
\label{sec:Sioux-Falls}

To motivate our analysis, we begin by examining the behavior of the \acl{PoA} in the road network of Sioux Falls, a standard case study in the transportation literature.
For concreteness, the network's (two-way) arterial roads are shown in \cref{fig:SiouxFalls-network} and their delay functions are taken to be of the \acs{BPR} (\acl{BPR}) type
\begin{equation}
\label{eq:BPR}
\debug c_{\debug e}(\debug x)
	= a_{\debug e} + b_{\debug e} \debug x^{\debug d_\debug e}
\end{equation}
with coefficients $a_{\debug e}, b_{\debug e}$ and degrees $d_{\debug e}$ (typically $d_{\debug e}=4$) taken from the standard reference work of \citet[Table~1]{LMP75}.
To analyze the network's \acl{PoA} as a function of the total traffic inflow, we considered all $528$ \ac{OD} pairs with nonzero inflow, and for each \ac{OD} pair $\debug \play\in\debug \players$, we restricted $\mathcal{\debug \nRoutes}_{\debug \play}$ to contain only the five shortest paths in terms of free-flow travel time (i.e.,\xspace the time taken to traverse a path when empty).
We then scaled up or down these inflows preserving the ratios between different \ac{OD} pairs and we plotted the network's \acl{PoA} for various values of the total inflow $\debug M$.

\begin{figure}[t]
\centering
\footnotesize
\subfigure[The Sioux Falls road network.]{%
\begin{tikzpicture}
\node (graph) at (0,0) {\includegraphics[width=.36\textwidth]{Figures/SiouxFalls.pdf}};
\node (phantom) at (0,-2.3) {};
\end{tikzpicture}
\label{fig:SiouxFalls-network}}
\hfill
\subfigure[Anarchy and efficiency in Sioux Falls.]{%
\includegraphics[width=.5\textwidth]{Figures/SiouxFalls-PoA.pdf}
\label{fig:SiouxFalls-PoA}}
\caption{The \acl{PoA} in the Sioux Falls metropolitan area as a function of the traffic inflow.}
\vspace{-1em}
\label{fig:SiouxFalls}
\end{figure}

As can be seen from \cref{fig:SiouxFalls-PoA}, the network's \acl{PoA} is identically equal to $1$ when the total inflow is small enough (approximately up to $3.7\times10^{4}$ trips per hour);
for intermediate values of $\debug M$, the \acl{PoA} becomes strictly greater than $1$,
and, ultimately, it decreases monotonically to $1$ in the heavy traffic limit.
Interestingly, \cite{LMP75} report a value of $\debug M_{\textrm{avg}} \approx 3.6\times 10^{5}\,\textrm{trips/hour}$ for the network's median traffic inflow;
this value is well within the range where the \acl{PoA} decreases monotonically to $1$ and, indeed, the observed value is approximately equal to $1.005$, indicating a $0.5\%$ difference between socially optimum and equilibrium flows under median traffic conditions.

Similar conclusions have been drawn in the literature from empirical studies in London, New York and Boston \citep{YouGasJeo:PRL2008}, as well as Sioux Falls with different subsets of \ac{OD} pairs and connecting paths per pair \citep{OHaConWat:TRB2016}.
In particular, in all cases, it was observed that there is an initial interval of values of $\debug M$ for which the \acl{PoA} is identically equal to $1$;
our first result shows that this is not mere happenstance:

\begin{proposition}
\label{prop:BPR-light}
If the network's cost functions are of the form \eqref{eq:BPR} with $a_{\debug e}, b_{\debug e}>0$ and $\debug d_{\debug e}\equiv\debug d$ for all $\debug e\in\mathcal{\debug E}$, we have $\PoA(\debug \Gamma_{\debug M})=1$  for all sufficiently small $\debug M$.
\end{proposition}

In fact, as the following result shows, this behavior arises whenever each \ac{OD} pair admits a single ``best'' path under zero inflow:

\begin{proposition}
\label{prop:PoA-equal-one}
Let $\routes_{\min}^{\debug \play}=\argmin_{\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}}\debug c_{\debug p}(0)$ denote the set of minimal cost paths of the $\debug \play$-th \ac{OD} pair under zero inflow.
If $\routes_{\min}^{\debug \play}$ is a singleton for all $\debug \play\in\debug \players$, we have $\PoA(\debug \Gamma_{\debug M})=1$ for all sufficiently small $\debug M$.
\end{proposition}

The above results (both proven in \cref{app:example}) provide a reasonable theoretical justification for the light traffic behavior of the \acl{PoA} that is observed in \cref{fig:SiouxFalls} (the heavy traffic limit is discussed in detail in the next sections).
At the same time however, the \acs{BPR} and ``unique best path'' assumptions in \cref{prop:BPR-light,prop:PoA-equal-one} respectively suggest that there is a finer mechanism at play which becomes apparent when the total cost at low traffic depends more delicately on the distribution of traffic in the network.
We make this precise in the following section where we provide an example of a three-link network where the \acl{PoA} oscillates between two values strictly greater than $1$, for all values of the traffic inflow.

\subsection{A network where selfish routing is always inefficient}
\label{sec:counterexample}

To construct an example of an ``always inefficient'' network, our approach will be to take a network with a certain degree of periodicity, obtain an explicit handle for its \acl{PoA} over a compact interval, and then tessellate this behavior over the entire traffic spectrum $(0,\infty)$.
To carry this out, let $\debug \Gamma_{\debug M}$ be a nonatomic routing game consisting of a single \ac{OD} pair with traffic inflow $\debug M$.
This traffic is to be routed over the three-link parallel graph of \cref{fig:parallel} with cost functions
\begin{subequations}
\label{eq:cost-ex}
\begin{flalign}
\debug c_{1}(\debug x_{1})
	&= \debug x_{1}^{\debug d} \, \bracks*{1 + \tfrac{1}{2} \sin(\log\debug x_{1})},
	\\
\debug c_{2}(\debug x_{2})
	&= \debug x_{2}^{\debug d},
	\\
\debug c_{3}(\debug x_{3})
	&= \debug x_{3}^{\debug d} \, \bracks*{1 + \tfrac{1}{2} \cos(\log\debug x_{3})},
\end{flalign}
\end{subequations}
where $\debug d$ is a positive integer.
It is easy to see that these cost functions are increasing, strictly convex and smooth on $[0,\infty)$ for all $\debug d\geq 2$, and they all grow as $\Theta(\debug x^{\debug d})$ at both traffic limits ($\debug x\to0$ and $\debug x\to\infty$).
Furthermore, the functions $\debug x_{\debug e} \debug c_{\debug e}(\debug x_{\debug e})$ are \emph{strictly} convex, so the optimum traffic allocation problem \eqref{eq:SO} admits a unique solution.
Hence, the only way for the game's \acl{PoA} to be equal to $1$ is when the game's (also unique) \acl{WE} coincides with the network's \acl{SO} flow.

As we show in \cref{app:example}, the equations determining the network's equilibrium and optimum flows never admit a common solution, so the \acl{PoA} is strictly greater than $1$ over any compact interval (showing in this way that the conclusion of \cref{prop:BPR-light,prop:PoA-equal-one} already fails for this example).
Moreover, the trigonometric terms in \eqref{eq:cost-ex} imply that these equations are periodic in a logarithmic scale (i.e.,\xspace in $\log\debug M$).
Hence, combining these two properties, we obtain:

\begin{proposition}
\label{prop:example}
In the three-link parallel network defined above,
$\PoA(\debug \Gamma_{\debug M})$ is periodic in $\log\debug M$ and oscillates between two values strictly greater than $1$.
\end{proposition}

\citet{ColComSca:SAGT2016} already provided examples of networks where $\limsup_{\debug M\to\infty}\PoA(\debug \Gamma_{\debug M}) >1$ but the cost functions involved were fairly irregular and the $\liminf$ of the \acl{PoA} was still $1$ (i.e.,\xspace selfish routing was still efficient infinitely often).
By contrast, in the above example, the \acl{PoA} is bounded away from $1$ for \emph{all} possible demands, and this despite the fact that the network's cost functions are smooth, strictly convex and grow as $\Theta(\debug x^{\debug d})$ at both ends of the congestion spectrum.
This is a considerable sharpening of the example of \citet{ColComSca:SAGT2016} as it shows that there are cases where efficiency is \emph{never} achieved at equilibrium \textendash\ not even asymptotically.

\subsection{Our contributions}
\label{sec:results}

Our first result is a cautionary tale:
we show that the \acl{PoA} may oscillate between two bounds strictly greater than $1$ for all values of the traffic inflow, even in simple parallel-link networks with a single \ac{OD} pair (cf.~\cref{fig:parallel}).
The cost functions in our example are convex and differentiable, so neither convexity nor smoothness seem to play a major role in the efficiency of selfish routing.
Moreover, our construction only involves a three-link network, so such phenomena may arise in any network containing such a three-link component.

\begin{figure}[t]
\centering
\footnotesize
\subfigure{\input{Figures/Parallel}}
\hfill
\subfigure{\includegraphics[width=.48\textwidth,]{Figures/Parallel-d2.pdf}}
\caption{A network where selfish routing remains inefficient for both light and heavy traffic.}
\vspace{-3ex}
\label{fig:parallel}
\end{figure}

Heuristically, the reason for this irregular \textendash\ and, perhaps, counter-intuitive \textendash\ behavior is that the growth rate of the network's cost functions exhibits higher-order oscillations which persist at any scale, in both light and heavy traffic.
To dispense with such pathologies, we focus on networks whose cost functions $\debug c_\debug e(\debug x)$ are asymptotically comparable to a \emph{benchmark function} $\debug c(\debug x)$ which is itself assumed to be \emph{regularly varying} (cf.~\cref{def:regvar}).
In so doing, we obtain a classification of the network's edges, paths, and \ac{OD} pairs as \emph{fast}, \emph{slow} or \emph{tight} relative to the chosen benchmark.
Then, thanks to this classification, we obtain the following general result:
\emph{If the routing cost of the ``most costly'' \ac{OD} pair in the network behaves like the benchmark, the network's \acl{PoA} converges to $1$ in both light and heavy traffic.}

Polynomial cost functions satisfy all of the above requirements, leading to the comprehensive asymptotic principle:
\smallskip
\begin{quotation}
\centering
\itshape
In networks with polynomial costs,\\
the \acl{PoA} becomes $1$ under both light and heavy traffic.
\end{quotation}
\smallskip
In other words, a benevolent social planner with full control of traffic assignment would not do any better than selfish agents in conditions of high or low congestion.
In particular, only if the traffic falls in an intermediate regime can there be a substantial gap between optimum and equilibrium states.

To assess how wide this intermediate regime might be in practice, we also examine the speed at which the \acl{PoA} converges to $1$ as a function of the traffic inflow.
Specializing to networks with polynomial costs, we find that in both regimes
the convergence follows a power law with respect to the total traffic inflow, and we derive explicit sharp estimates for the corresponding rates.

\subsection{Related work}
\label{sec:related}

Establishing worst-case bounds for the \acl{PoA} under different conditions has been a staple of the literature on congestion games ever since the seminal result of \cite{RouTar:JACM2002}.
In words, this result states that in networks with affine costs the \acl{PoA} is no higher than $4/3$, independently of the network topology and/or the number of \ac{OD} pairs in the network.
Furthermore, this bound is sharp in that, for every $\debug M>0$, there exists a network with traffic inflow $\debug M$ and affine costs such that the \acl{PoA} is \emph{exactly} equal to $4/3$.
Importantly, our analysis shows that the order of the quantifiers in the above statement \emph{cannot be exchanged:}
in any network with affine costs, the \acl{PoA} gets arbitrarily close to $1$ if the traffic inflow is sufficiently large or small.

Worst-case bounds for the \acl{PoA} have been obtained for larger classes of cost functions.
For polynomial costs with degree at most $\debug d$, \cite{Rou:JCSS2003} showed that the worst possible instance grows as $\Theta(\debug d/\log\debug d)$ while \cite{DumGai:INE2006} provided sharper bounds for monomials of maximum degree $\debug d$ and minimum degree $\debug q$.
Extending the above results, \cite{RouTar:GEB2004} provided a unifying result for costs that are differentiable with $\debug x\debug c(\debug x)$ convex, while \cite{CorSchSti:MOR2004,CorSchSti:GEB2008} considered less regular classes of cost functions.
\cite{CorSchSti:OR2007} also studied the \acl{PoA} when the goal is to minimize the maximum \textendash\ rather than the average \textendash\ latency in the network.
For a survey, the reader is referred to \cite{Rou:AGT2007}.

In a more practical setting, \cite{YouGasJeo:PRL2008} studied the difference between optimal and actual system performance in real transportation networks, focusing in particular on Boston's road network.
They observed that the \acl{PoA} depends crucially on the total traffic inflow:
it starts at $1$, it then grows with some oscillations, and ultimately returns to $1$ as the flow increases.
\cite{GonGraAndLyg:IEEECDC2015} studied optimal scheduling for the electricity demand of a fleet of plug-in electric vehicles:
without using the term, they showed that the \acl{PoA} goes to $1$ as the number of vehicles grows.
\cite{ColTao:EC2016} showed that in large Walrasian auctions and in large Fisher markets the \acl{PoA} goes to one as the market size increases.
Finally, \cite{FelImmLucRouSyr:STOC2016} took a different asymptotic approach and considered atomic games where the number of players grows to infinity.
Applying the notion of $(\lambda,\mu)$-smoothness to the resulting sequence of atomic games, they showed that the \acl{PoA} converges to the corresponding nonatomic limit.

From an analytic standpoint, the closest antecedent to our paper is the recent work of \cite{ColComSca:SAGT2016} who
studied the heavy traffic limit of the \acl{PoA} in parallel networks with a single \ac{OD} pair.
Their analysis identified that regular variation plays an important role in this setting;
however, it offered no insights into non-parallel networks with multiple \ac{OD} pairs or the light traffic regime.
Our paper provides an in-depth answer to these questions:
we show that
\begin{inparaenum}
[(\itshape a\upshape)]
\item
regular variation yields asymptotic efficiency under both light and heavy traffic conditions;
\item
the topology of the network doesn't matter;
and
\item
the existence of several \ac{OD} pairs doesn't matter as long as they admit a common benchmark (which is always the case if the network's cost functions are polynomial).
\end{inparaenum}

Building on a previous unpublished version of the present paper, \citet{WuMohChe:ArXiv2017} introduced a class of congestion games, called \emph{scalable}, whose \acl{PoA} converges to $1$ as the total demand diverges.
They also computed the rate of convergence of the \acl{PoA} for the special case of \acs{BPR} cost functions of the same degree.
\cite{Sti:Springer2014} also studied the behavior of the \acl{PoA} for queueing networks in heavy traffic under various assumptions on the structure of the network and on the stochastic properties of the queues.
His results can be used for the analysis of network routing models with capacity constraints.

Our work should also be compared to that of \cite{MonBenPil:ArXiv2017} who performed an empirical study of the \acl{PoA} based on data from thousands of commuting students in Singapore.
Focusing on the network's ``stress of catastrophe'' (an empirical majorant of the network's \acl{PoA}), they showed that routing choices are near-optimal and the incurred \acl{PoA} is much lower than what traditional worst-case bounds suggest.
Interestingly, the study of \cite{MonBenPil:ArXiv2017} also suggests that the Singapore road network is often lightly congested:
as such, their results can be seen as a practical validation of the light traffic results presented here (and, conversely, our results provide a theoretical justification for their empirical observations).

\subsection{Outline of the paper}
\label{sec:outline}

The paper is organized as follows.
In \cref{sec:model}, we introduce the basic model and concepts that will be used in the rest of the paper.
\cref{sec:example} provides two motivating examples for the analysis to follow.
In \cref{sec:single}, we treat networks with a single \ac{OD} pair, whereas \cref{sec:multi} examines networks with multiple \ac{OD} pairs.
The more complicated case of variable relative inflows is treated  in \cref{sec:variable}.
Finally, in \cref{sec:rate}, we study the rate of convergence of the \acl{PoA} in light and heavy traffic.
To streamline our presentation, the proofs of our main results have been relegated to a series of appendices at the end of the paper.
\section{Introduction}
\label{sec:introduction}
\input{Introduction}

\section{Model and preliminaries}
\label{sec:model}
\input{Model}

\section{First results}
\label{sec:example}
\input{Example}

\section{Networks with a single \ac{OD} pair}
\label{sec:single}
\input{Single}

\section{Networks with multiple \ac{OD} pairs}
\label{sec:multi}
\input{Multiple}

\section{Networks with variable inflow rates}
\label{sec:variable}
\input{Variable}

\section{Rate of convergence}
\label{sec:rate}
\input{Rate}

\section{Discussion}
\label{sec:discussion}
\input{Discussion}

\subsection{Network model}
\label{sec:network}

Following \cite{BecMcGWin:Yale1956} and \cite{RouTar:JACM2002}, the basic component of our model will be a directed multi-graph $\mathcal{\debug G}\equiv\mathcal{\debug G}(\mathcal{\debug V},\mathcal{\debug E})$ with vertex set $\mathcal{\debug V}$ and edge set $\mathcal{\debug E}$ (both finite).
We further assume that there is a finite set
of \acdef{OD} pairs indexed by $\debug \play\in\debug \players$, each with an individual \emph{traffic demand} $\debug m^{\debug \play}\geq 0$ that is to be routed from the pair's \emph{origin node} $\debug O^{\debug \play}\in\mathcal{\debug V}$ to its \emph{destination} $\debug D^{\debug \play}\in\mathcal{\debug V}$.
To route this traffic, the $\debug \play$-th \ac{OD} pair employs a set $\mathcal{\debug \nRoutes}^{\debug \play}$ of \emph{paths} joining $\debug O^{\debug \play}$ to $\debug D^{\debug \play}$, with each path $\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}$ comprising a sequence of edges that meet head-to-tail in the usual way;
specifically, we do not assume that $\mathcal{\debug \nRoutes}^{\debug \play}$ is necessarily the set of \emph{all} paths joining $\debug O^{\debug \play}$ to $\debug D^{\debug \play}$, but only some subset thereof.%
\footnoteOR{This distinction is particularly relevant for packet-switched networks (such as the Internet) where only paths with a low hop count are typically employed.}
For bookkeeping reasons, we will also make the following standing assumptions throughout our paper:
\vspace{.5ex}
\begin{enumerate}
[\indent\itshape a\upshape)]
\addtolength{\itemsep}{.5ex}
\item
The \emph{total inflow rate} $\debug M = \sum_{\debug \play\in\debug \players} \debug m^{\debug \play}$ is positive (so there is a nonzero amount of traffic in the network).
\item
The path sets $\mathcal{\debug \nRoutes}^{\debug \play}$ are disjoint (which in particular holds trivially if all pairs $(\debug O^{\debug \play},\debug D^{\debug \play})$ are distinct).
\end{enumerate}
\vspace{.5ex}

Now, writing $\mathcal{\debug \nRoutes} \equiv \bigcup_{\debug \play\in\debug \players} \mathcal{\debug \nRoutes}^{\debug \play}$ for the union of all such paths, the set of feasible \emph{routing flows} $\debug f = (\debug f_{\debug p})_{\debug p\in\mathcal{\debug \nRoutes}}$ in the network is defined as
\begin{equation}
\label{eq:flows}
\textstyle
\mathcal{\debug F}
	= \setdef*{\debug f\in\mathbb{R}_{+}^{\mathcal{\debug \nRoutes}}}{\text{$\sum_{\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}} \debug f_{\debug p} = \debug m^{\debug \play}$ for all $\debug \play\in\debug \players$}}.
\end{equation}
In turn, a routing flow $\debug f\in\mathcal{\debug F}$ induces a \emph{load} on each edge $\debug e\in\mathcal{\debug E}$ as
\begin{equation}
\label{eq:load}
\debug x_{\debug e}
	= \sum_{\debug p\ni\debug e} \debug f_{\debug p},
\end{equation}
and we write $\debug x = (\debug x_{\debug e})_{\debug e\in\mathcal{\debug E}}$ for the corresponding \emph{load profile} on the network.
Given all this, the delay (or latency) experienced by an infinitesimal traffic element traversing edge $\debug e$ is determined by a nondecreasing continuous \emph{cost function} $\debug c_{\debug e}\colon[0,\infty)\to[0,\infty)$:
more precisely, if $\debug x = (\debug x_{\debug e})_{\debug e\in\mathcal{\debug E}}$ is the load profile induced by a feasible routing flow $\debug f = (\debug f_{\debug p})_{\debug p\in\mathcal{\debug \nRoutes}}$, the incurred delay on edge $\debug e\in\mathcal{\debug E}$ is $\debug c_{\debug e}(\debug x_{\debug e})$.
Hence, with a slight abuse of notation, the associated cost of path $\debug p\in\mathcal{\debug \nRoutes}$ will be given by
\begin{equation}
\label{eq:cost-path}
\debug c_{\debug p}(\debug f)
	= \sum_{\debug e\in\debug p} \debug c_{\debug e}(\debug x_{\debug e}).
\end{equation}

Putting together all of the above, the tuple $\debug \Gamma = (\mathcal{\debug G},\debug \players,\{\debug m^{\debug \play}\}_{\debug \play\in\debug \players},\{\mathcal{\debug \nRoutes}^{\debug \play}\}_{\debug \play\in\debug \players},\{\debug c_{\debug e}\}_{\debug e\in\mathcal{\debug E}})$ will be referred to as a \emph{\textpar{nonatomic} routing game}.
When we want to explicitly keep track of the total inflow rate $\debug M = \sum_{\debug \play}\debug m^{\debug \play}$, we write $\debug \Gamma_{\debug M}$ instead of $\debug \Gamma$;
also, when there is a single \ac{OD} pair, we will drop all reference to $\debug \play$ and $\debug \players$ altogether.

\subsection{Equilibrium, optimality, and the \acl{PoA}}
\label{sec:PoA}

In routing games, the notion of \acl{NE} is captured by Wardrop's first principle:
\emph{at equilibrium, the delays along utilized paths are equal and no higher than those that would be experienced by an infinitesimal traffic element going through an unused route} \citep{War:PICE1952}.

Formally, a routing flow $\eq{\debug f}$ is said to be a \acdef{WE} of $\debug \Gamma$ if, for all $\debug \play\in\debug \players$, we have
\begin{equation}
\label{eq:Wardrop}
\debug c_{\debug p}(\eq{\debug f})
	\leq \debug c_{\route'}(\eq{\debug f})
	\quad
	\text{for all $\debug p,\route'\in\mathcal{\debug \nRoutes}^{\debug \play}$ such that $\eq{\debug f}_{\debug p}>0$}.
\end{equation}
From the work of \cite{BecMcGWin:Yale1956}, it is known that \aclp{WE} coincide with the solutions of the (convex) minimization problem
\begin{equation}
\label{eq:WE}
\tag{WE}
\begin{aligned}
\textrm{minimize}
	&\quad
	\sum_{\debug e\in\mathcal{\debug E}} \debug C_{\debug e}(\debug x_{\debug e}),
	\\
\textrm{subject to}
	&\quad
	\debug x_{\debug e} = \sum_{\debug p\ni\debug e} \debug f_{\debug p},
	\;
	\debug f\in\mathcal{\debug F},
\end{aligned}
\end{equation}
where
$\debug C_{\debug e}(\debug x_{\debug e}) = \int_{0}^{\debug x_{\debug e}} \debug c_{\debug e}(w) \:d w$ denotes the primitive of $\debug c_{\debug e}$.
Analogously, \acdef{SO} flows are defined as solutions of the total cost minimization problem
\begin{equation}
\label{eq:SO}
\tag{SO}
\begin{aligned}
\textrm{minimize}
	&\quad
	\sum_{\debug p\in\mathcal{\debug \nRoutes}} \debug f_{\debug p} \debug c_{\debug p}(\debug f_{\debug p}),
	\\
\textrm{subject to}
	&\quad
	\debug f\in\mathcal{\debug F}.
\end{aligned}
\end{equation}

By a simple rearrangement of terms, the objective function of \eqref{eq:SO} can be rewritten as $\debug L(\debug x) = \sum_{\debug e\in\mathcal{\debug E}} \debug x_{\debug e} \debug c_{\debug e}(\debug x_{\debug e})$, so the value of the above problem can be expressed equivalently (and somewhat more concisely) as
\begin{equation}
\Opt(\debug \Gamma)
	= \min_{\debug x\in\mathcal{\debug X}} \debug L(\debug x),
\end{equation}
where $\mathcal{\debug X} = \setdef{x\in\mathbb{R}_{+}^{\mathcal{\debug E}}}{\debug x_{\debug e} = \sum_{\debug p\ni\debug e} \debug f_{\debug p}, \debug f\in\mathcal{\debug F}}$ denotes the set of all load profiles of the form \eqref{eq:load}.
Thus, to quantify the gap between solutions to \eqref{eq:WE} and \eqref{eq:SO}, let
\begin{equation}
\label{eq:values}
\Eq(\debug \Gamma)
	= \debug L(\eq\debug x)
\end{equation}
where $\eq\debug x$ is the load profile induced by a \acl{WE} $\eq\debug f$ of $\debug \Gamma$ (by a standard result of \cite{BecMcGWin:Yale1956}, all such flows incur the same total cost).
The game's \acdef{PoA} is then defined as
\begin{equation}
\label{eq:PoA}
\PoA(\debug \Gamma)
	= \frac{\Eq(\debug \Gamma)}{\Opt(\debug \Gamma)}.
\end{equation}
For this ratio to be well-defined, we must have $\Opt(\debug \Gamma)>0$;
otherwise, if this is not the case, we will vacuously set $\PoA(\debug \Gamma) = 1$.
To avoid such technicalities, we will tacitly assume that $\Opt(\debug \Gamma)>0$ throughout.

Of course, $\PoA(\debug \Gamma) \geq 1$ with equality if and only if \aclp{WE} are also socially efficient.
Our main objective in what follows will be to study the asymptotic behavior of this ratio when $\debug M\to0$ or $\debug M\to\infty$.

\subsection{The light traffic case}
\label{sec:rate-light}

We begin with the light traffic limit ($\debug \omega=0$).
To motivate our analysis, we start with a simple example of a Pigou network with monomial costs as shown in \cref{fig:Pigou-poly}:
for $\debug d_{1},\debug d_{2}>0$, the zero-flow travel time of both links is zero, so \cref{prop:PoA-equal-one} does not apply.
Instead, as we show below, the network's \acl{PoA} decays to $1$ following a power law:

\begin{figure}[t]
\centering
\footnotesize
\input{Figures/Parallel3}
\vspace{-4ex}
\caption{A two-link Pigou network with monomial costs.}
\label{fig:Pigou-poly}
\vspace{-2ex}
\end{figure}

\begin{proposition}
\label{prop:Pigou-light}
Consider a two-link parallel network with cost functions $\debug c_{1}(\debug x) = \debug x^{\debug d_{1}}$ and $\debug c_{2}(\debug x) = \debug x^{\debug d_{2}}$, $0<\debug d_{1} < \debug d_{2}$, and a single \ac{OD} pair with inflow $\debug M$.
Then
\begin{equation}
\label{eq:Pigou-asym-light}
\PoA(\debug \Gamma_{\debug M})=1+\debug b\debug M^{\debug a}+o(\debug M^{\debug a})
\end{equation}
where
\begin{flalign}
\label{eq:Pigou-exp-light}
\debug a
	&=\debug d_{2}/\debug d_{1} - 1,
\intertext{and}
\label{eq:Pigou-light}
\debug b
	&= \debug d_{1} \parens*{\frac{1+\debug d_{2}}{1+\debug d_{1}}}^{1+1/\debug d_{1}} - \debug d_{2}
	> 0.
\end{flalign}
\end{proposition}

\begin{figure*}[t]
\centering
\footnotesize
\subfigure{\includegraphics[width=.475\textwidth]{Figures/PigouPoA-d2-light.pdf}}
\hfill
\subfigure{\includegraphics[width=.475\textwidth]{Figures/NormalizedPigouPoA-d2-light.pdf}}
\caption{The rate of convergence of the \acl{PoA} in a lightly congested Pigou network as in \cref{fig:Pigou-poly}.
The figure on the left shows the \acl{PoA} as a function of the total traffic inflow $\debug M$ for different values of the
exponents $\debug d_1$ and $\debug d_2$.
In the figure to the right, the \acl{PoA} has been rescaled by $\debug M^{-\debug a}$ with $a=\debug d_2/\debug d_1-1$, showing that $\PoA(\debug \Gamma_{\debug M}) \sim 1 + \debug b\debug M^{\debug a}$ for some $\debug b>0$;
the horizontal asymptotes correspond precisely to the expression \eqref{eq:Pigou-light} for $\debug b$.}
\label{fig:Pigou-light}
\end{figure*}

In words, \cref{prop:Pigou-light} shows that the rate of convergence of the \acl{PoA} is controlled by the ratio $\debug d_{2}/\debug d_{1}$:
the largest the ratio of degrees, the fastest the decay of the \acl{PoA} (for a numerical illustration, see \cref{fig:Pigou-light}).
This behavior is consistent with \cref{prop:PoA-equal-one} which predicts that $\PoA(\debug \Gamma_{\debug M}) \equiv 1$ if $\debug M$ is small enough and $\debug d_{1} = 0$.
Indeed, taking $\debug d_{1}\to0$ in \eqref{eq:Pigou-asym-light} shows that $\PoA(\debug \Gamma_{\debug M}) = 1 + \bigoh(\debug M^{\debug a})$ for any $\debug a>0$, suggesting in turn that the rate of decay of $\PoA(\debug \Gamma_{\debug M})$ is qualitatively different in this case.

Another case worth noting is when $\debug d_{1} = \debug d_{2}$, i.e.,\xspace when both links are equivalent in terms of performance.
In this case, $\PoA(\debug \Gamma_{\debug M})$ is identically equal to $1$ for all values of $\debug M$ (\cref{prop:BPR-light} already guarantees as much when $\debug M$ is not large).
However, \eqref{eq:Pigou-asym-light} would seem to suggest that the \acl{PoA} can remain large as $\debug M\to0$ (since $\debug a = 1 - 1 = 0$ when $\debug d_{1} = \debug d_{2}$).
The solution of this apparent paradox is provided by looking at the multiplicative constant $\debug b$:
when $\debug d_{1} = \debug d_{2}$, we also have $\debug b=0$, so the resulting contribution to the \acl{PoA} is $0$ \textendash\ not $\Omega(1)$.

The above highlights the importance of the relative rate of decay of the network's edge costs as a function of the inflow.
Since monomials with lower exponents are more costly in the low traffic limit, this rate is dominated by the smallest power in \eqref{eq:polynomials}.
Thus, motivated by the index machinery of \cref{sec:single,sec:multi}, we respectively define the \emph{order} of an edge $\debug e\in\mathcal{\debug E}$, that of a path $\debug p\in\mathcal{\debug \nRoutes}$, of an \ac{OD} pair $\debug \play\in\debug \players$, and that of the network itself as
\begin{subequations}
\label{eq:ord-light}
\begin{flalign}
\label{eq:ord-edge-light}
\debug q_{\debug e}
	&= \min_{\vphantom{\debug k>0}}\setdef{\debug k}{\debug c_{\debug e,\debug k} > 0}
	\\
\label{eq:ord-path-light}
\debug q_{\debug p}
	&= \min_{\debug e\in\debug p}\debug q_{\debug e},
	\\
\label{eq:ord-pair-light}
\debug q^{\debug \play}
	&= \max_{\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}} \debug q_{\debug p},
	\\
\label{eq:ord-net-light}
\debug q
	&= \min_{\debug \play\in\debug \players} \debug q^{\debug \play}.
\end{flalign}
\end{subequations}
In view of the above, the network is tight with respect to the benchmark function $\debug c(\debug x)=\debug x^{\debug q}$, and an edge $\debug e\in\mathcal{\debug E}$ is fast when $\debug q_\debug e>\debug q$, tight when $\debug q_\debug e=\debug q$, and slow if $\debug q_\debug e<\debug q$.
We then denote the set of the network's slow edges as
\begin{flalign}
\label{eq:slow-light}
\slow\mathcal{\debug E}
	&= \setdef{\debug e\in\mathcal{\debug E}}{\debug q_{\debug e} < \debug q},
\intertext{and we write}
\label{eq:gap-light}
\slow\debug q
	&= \max_{\debug e\in\slow\mathcal{\debug E}} \debug q_{\debug e}
\end{flalign}
for the order of the fastest edge in $\slow\mathcal{\debug E}$ (again employing the standard convention that $\max\varnothing = -\infty$, so $\slow\debug q = -\infty$ when there are no slow edges).

Building on the intuition gained from \cref{prop:Pigou-light}, our main quantitative result for low traffic is that the network's \ac{PoA} decays to $1$ following a power law that depends only on the ratio between the order of the network ($\debug q$) and that of its fastest slow edge ($\slow\debug q$):

\begin{theorem}
\label{thm:rate-light}
Let $\debug \Gamma_{\debug M}$ be a nonatomic routing game with polynomial costs, total inflow $\debug M$, and fixed relative inflows.
Then, there exist non-negative constants $\debug K_{1}\geq 0$ and $\debug K_{\adegr}\geq 0$ such that
\begin{equation}
\label{eq:rate-light}
\PoA(\debug \Gamma_{\debug M})
	\leq 1 + \debug K_{1}\debug M + \debug K_{\adegr}\debug M^{\debug a},
\end{equation}
where $\debug a = \debug q/\slow\debug q - 1$ and $\debug K_{\adegr}=0$ whenever $\slow\mathcal{\debug E}=\varnothing$.
\end{theorem}

\cref{thm:rate-light} was stated for networks with fixed relative inflows for simplicity only:
in \cref{app:rate}, we state and prove a more general result for networks with variable relative inflows as in \cref{sec:multi}.
In terms of intuition, we only note here that \cref{thm:rate-light} complements the insights gained from \cref{prop:BPR-light,prop:PoA-equal-one} in an important way:
when there is no single ``best path'' under zero inflow, the network's \acl{PoA} is no longer identically equal to $1$ for small inflows but instead behaves as a power law.

\subsection{The heavy traffic case}
\label{sec:rates-heavy}

We now turn to the heavy traffic limit ($\debug \omega=\infty$).
As in the light traffic case, we start with a simple \textendash\ but illuminating \textendash\ example of a two-link Pigou network where precise results can be obtained:

\begin{figure*}[t]
\centering
\footnotesize
\subfigure{\includegraphics[width=.475\textwidth]{Figures/PigouPoA-d2-heavy.pdf}}
\hfill
\subfigure{\includegraphics[width=.475\textwidth]{Figures/NormalizedPigouPoA-d2-heavy.pdf}}
\caption{The rate of convergence of the \acl{PoA} in a heavily congested Pigou network as in \cref{fig:Pigou-poly}.
The figure on the left shows the \acl{PoA} as a function of the total traffic inflow $\debug M$ for different values of the exponents $\debug d_1$ and $\debug d_2$.
In the figure to the right, the \acl{PoA} has been rescaled by $\debug M^{\debug a}$ with $a=1-\debug d_1/\debug d_2$, showing that $\PoA(\debug \Gamma_{\debug M}) \sim 1 + \debug b/\debug M^{\debug a}$ for some $\debug b>0$;
the horizontal asymptotes correspond precisely to the expression \eqref{eq:Pigou-heavy} for $\debug b$.
}
\vspace{-1ex}

\label{fig:Pigou-heavy}
\end{figure*}

\begin{proposition}
\label{prop:Pigou-heavy}
Consider a two-link parallel network with cost functions $\debug c_{1}(\debug x) = \debug x^{\debug d_{1}}$ and $\debug c_{2}(\debug x) = \debug x^{\debug d_{2}}$, $0<\debug d_{1} < \debug d_{2}$, and a single \ac{OD} pair with inflow $\debug M$.
Then
\begin{equation}
\label{eq:Pigou-asym-heavy}
\PoA(\debug \Gamma_{\debug M})=1+\debug b\debug M^{-\debug a}+o(\debug M^{-\debug a})
\end{equation}
where
\begin{flalign}
\label{eq:Pigou-exp-heavy}
\debug a
	&= 1 - \debug d_{1}/\debug d_{2}
\intertext{and}
\label{eq:Pigou-heavy}
\debug b
	&= \debug d_{2} \parens*{\frac{1 + \debug d_{1}}{1 + \debug d_{2}}}^{1+1/\debug d_{2}} - \debug d_{1}
	> 0.
\end{flalign}
\end{proposition}

For illustration purposes, we plotted in \cref{fig:Pigou-heavy} the asymptotic behavior of the network's \acl{PoA} for different values of $\debug d_{1}$ and $\debug d_{2}$.
In the same vein as in the light traffic limit, two special cases that are of interest here are when $\debug d_{2}=\infty$ and when $\debug d_{1} = \debug d_{2}$.
In the former ($\debug d_{2}=\infty$), \cref{eq:Pigou-exp-heavy} gives $\debug a=1$, indicating a convergence rate of the order of $\bigoh(1/\debug M)$:
since $\debug a<1$ for all finite $\debug d_{2}$, this is the best possible rate that can be achieved in the heavy traffic limit.
For the latter ($\debug d_{1} = \debug d_{2}$), \cref{eq:Pigou-exp-heavy} gives $\debug a=0$, suggesting that the \acl{PoA} can remain large as $\debug M\to\infty$.
This seems to be inconsistent with the fact that the network's \acl{PoA} is identically equal to $1$ when $\debug d_{1} = \debug d_{2}$ but a closer look reveals that the multiplicative constant $\debug b$ of \eqref{eq:Pigou-heavy} is also $0$ when $\debug d_{1} = \debug d_{2}$, thus reconciling the two results.

Now, even though the above result does not apply to more general networks with polynomial costs, it still highlights the main mechanism at play.
Specifically, for large edge loads $\debug x$, the dominant term in \eqref{eq:polynomials} is the one with highest degree $\debug d_\debug e$. As we've discussed before, this indicates a complete reversal of roles between light and heavy traffic:
for $\debug d_{1} < \debug d_{2}$,  $\debug x^{\debug d_{1}}$ is \emph{slower} than $\debug x^{\debug d_{2}}$ when $\debug x\to 0$, but \emph{faster}  when $\debug x\to\infty$.
Thus, with an obvious adaptation of what we did for light traffic, we define the \emph{order} of an edge $\debug e\in\mathcal{\debug E}$, that of a path $\debug p\in\mathcal{\debug \nRoutes}$, of an \ac{OD} pair $\debug \play\in\debug \players$, and of the network itself as
\begin{subequations}
\label{eq:ord-heavy}
\begin{flalign}
\label{eq:ord-edge-heavy}
\debug d_{\debug e}
	&= \max_{\vphantom{\debug k>0}} \setdef{\debug k}{\debug c_{\debug e,\debug k} > 0}
	\\
\label{eq:ord-path-heavy}
\debug d_{\debug p}
	&= \max_{\debug e\in\debug p}\debug d_{\debug e},
	\\
\label{eq:ord-pair-heavy}
\debug d^{\debug \play}
	&= \min_{\debug p\in\mathcal{\debug \nRoutes}^{\debug \play}} \debug d_{\debug p},
	\\
\label{eq:ord-net-heavy}
\debug d
	&= \max_{\debug \play\in\debug \players} \debug d^{\debug \play}.
\end{flalign}
\end{subequations}
With all this at hand, we see that the network is tight with respect to the benchmark $\debug c(\debug x)=\debug x^{\debug d}$,
so an edge $\debug e\in\mathcal{\debug E}$ is fast when $\debug d_{\debug e}<\debug d$, tight when $\debug d_{\debug e} = \debug d$, and slow if $\debug d_{\debug e} > \debug d$.
The set of the network's slow edges is then denoted as
\begin{flalign}
\label{eq:slow-heavy}
\slow\mathcal{\debug E}
	&= \setdef{\debug e\in\mathcal{\debug E}}{\debug d_{\debug e} > \debug d},
\intertext{and we write}
\label{eq:gap-heavy}
\slow\debug d
	&= \min_{\debug e\in\slow\mathcal{\debug E}} \debug d_{\debug e}
\end{flalign}
for the order of the fastest edge in $\slow\mathcal{\debug E}$ (again employing the standard convention that $\min\varnothing = \infty$, so $\slow\debug d = \infty$ when there are no slow edges).

Mutatis mutandis, this definition is the same as in light traffic except for a reversal of the max/min operators.
Our main result for heavily congested networks confirms this intuition:

\begin{theorem}
\label{thm:rate-heavy}
Let $\debug \Gamma_{\debug M}$ be a nonatomic routing game with polynomial costs, total inflow $\debug M$, and fixed relative inflows.
Then, there exist non-negative constants $\debug K_{1}\geq 0$ and $\debug K_{\adegr}\geq 0$ such that
\begin{equation}
\label{eq:rate-heavy}
\PoA(\debug \Gamma_{\debug M})
	\leq 1 + \frac{\debug K_{1}}{\debug M} + \frac{\debug K_{\adegr}}{\debug M^{\debug a}},
\end{equation}
where $\debug a=1-\debug d/\slow\debug d$ and  $\debug K_{\adegr}=0$ whenever $\slow\mathcal{\debug E}=\varnothing$.
\end{theorem}

\begin{remark}
\label{rem:samedeg}
As in the light traffic case, if the costs are monomials of the same degree, then $\debug K_{1}=\debug K_{\adegr}=0$ and $\PoA(\debug \Gamma_{\debug M})\equiv 1$ for all $\debug M>0$.
\end{remark}

In words, given that $\debug a < 1$ when there is at least one slow edge in the network ($\debug a=1$ and $\debug K_{\adegr} = 0$ otherwise), \cref{thm:rate-heavy} states the network's \acl{PoA} converges to $1$ as $\bigoh(1/\debug M^{\debug a})$ with an $\bigoh(1/\debug M)$ subleading term.
In particular, in the presence of a single slow edge $\debug e$ with $\debug d_{\debug e} > \debug d$, the convergence exponent $\debug a$ in \eqref{eq:rate-heavy} can become as small as $1/(\debug d+1)$, thus pointing to a slower convergence rate in networks with  routing costs of high degree and a small gap between the degree of tight and slow edges.
On the other hand, if there are no slow edges  we have $\slow\mathcal{\debug E} = \varnothing$ and  we get an $\bigoh(1/\debug M)$ rate of convergence.

On this issue, \citet{WuMohChe:ArXiv2017} recently showed that if all the network's cost functions are of the \ac{BPR} type $\debug c_\debug e(\debug x)=a_\debug e+b_\debug e\debug x^\debug d$ with the
same degree $\debug d$,
then $\PoA(\debug \Gamma_{\debug M}) = 1+\bigoh(\debug M^{-\debug d})$ as $\debug M\to\infty$.
In this special case, the rate of convergence is faster than the prediction of \cref{thm:rate-heavy}, a gap which points to a sharp discontinuity that occurs when all costs have the same degree.
To see this in a concrete example, consider again the two-link Pigou network of \cref{fig:Pigou-poly}.
By symmetry, if $\debug d_1=\debug d_2$, the fraction of traffic routed on edge $1$ at optimum and at equilibrium coincide
\begin{equation}
\opt{\debug y}_{1}
	= \eq{\debug y}_{1}
	= \frac{1}{2}
	\quad
	\text{for all $\debug M > 0$},
\end{equation}
implying in turn that $\PoA(\debug \Gamma_{\debug M})$ is identically equal to $1$.
On the other hand, when $\debug d_1< \debug d_2$, both fractions $\opt{\debug y}_{1}$ and $\eq{\debug y}_{1}$ converge to $1$ as $\debug M\to\infty$.
\cref{prop:Pigou-heavy} shows that the rate of convergence of the \acl{PoA} in this case is exactly of order $\Theta(1/\debug M^{\debug a})$ and cannot be improved.

Put differently, \cref{prop:Pigou-heavy} shows that the slightest difference in edge degrees causes the rate of convergence of the \acl{PoA} to drop abruptly to $\Theta(\debug M^{-\debug a})$;
in fact, \cref{eq:Pigou-heavy} even provides an explicit expression for the proportionality constant in the high congestion rate $\Theta(\debug M^{-\debug a})$.
By this token, the bounds provided by \cref{thm:rate-heavy} are tight and cannot be improved in general, even in the class of two-link parallel networks with monomial costs.
\subsection{Regular variation and edge classification}
\label{sec:regvar}

To present a unified perspective, we will tackle both ends of the congestion spectrum simultaneously by introducing the \emph{traffic limit indicator} $\debug \omega \in \{0,\infty\}$:
letting $\debug M\to\debug \omega$ gives the \emph{light traffic limit} for $\debug \omega=0$ and the \emph{heavy traffic limit} for $\debug \omega=\infty$.
Regular variation at either limit is then defined as follows:

\begin{definition}
\label{def:regvar}
A function $\debug g\colon (0,\infty) \to (0,\infty)$ is said to be \emph{regularly varying at $\debug \omega$} if
\begin{equation}
\label{eq:regvar}
\lim_{t\to\debug \omega} \frac{\debug g(t\debug x)}{\debug g(t)}
	\quad
	\text{is finite and nonzero for all $\debug x>0$}.
\end{equation}
\end{definition}

In words, regular variation means that $\debug g(t)$ grows at the same rate when viewed at different scales (determined here by $\debug x$).
The concept itself dates back to \citet{Kar:MC1930,Kar:BSMF1933} and has been used extensively in functional analysis, probability, and large deviations theory \citep[see e.g.,\xspace][]{deHFer:Springer2006,JesMik:PIMB2006,Res:Springer2007};
for a comprehensive survey we refer the reader to \cite{BinGolTeu:CUP1989}.

Standard examples of regularly varying functions include all affine functions, polynomials, logarithms, and, more generally, all analytic functions (barring those with an essential singularity at $\debug \omega=\infty$).%
\footnoteOR{Recall here that a function $\debug g(\debug x)$ is analytic on a domain $U$ if it is equal to its Taylor series on $U$.}
On the other hand, despite being bounded from above and below as $\Theta(\debug x^{\debug d})$, the oscillatory cost functions \eqref{eq:cost-ex} used in the counterexample of \cref{sec:example} are \emph{not} regularly varying.
Indeed, at either $\debug \omega=0$ or $\debug \omega=\infty$, the limit
\begin{equation}
\lim_{t\to\debug \omega} \frac{\debug c_{1}(t\debug x)}{\debug c_{1}(t)}
	= \lim_{t\to\debug \omega} \frac{1 + \frac{1}{2} \sin(\log t + \log\debug x)}{1 + \frac{1}{2} \sin(\log t)} \debug x^{\debug d}
\end{equation}
does not exist in $(0,\infty)$ unless $\log\debug x = k\pi$ for some $k\in\mathbb{Z}$ (and likewise for $\debug c_{3}$).
In this way, regular variation provides a much finer view than polynomial growth.

With all this at hand, we will dispose of growth irregularities like the above by positing that the network's cost functions can be compared asymptotically to some regularly varying function $\debug c(\debug x)$.
Specifically, given an ensemble of cost functions $\mathcal{\debug C} = \{\debug c_{\debug e}\}_{\debug e\in\mathcal{\debug E}}$, we will say that a regularly varying function $\debug c\colon(0,\infty)\to(0,\infty)$ is a \emph{benchmark for $\mathcal{\debug C}$ at $\debug \omega$} if the following \textpar{possibly infinite} limit exists for all $\debug e\in\mathcal{\debug E}$
\begin{equation}
\label{eq:index}
\debug \alpha_{\debug e}
	= \lim_{\debug x\to\debug \omega} \frac{\debug c_{\debug e}(\debug x)}{\debug c(\debug x)}.
\end{equation}
This limit will be called the \emph{index of edge $\debug e$ at $\debug \omega$}, and $\debug e$ will be called \emph{fast}, \emph{slow}, or \emph{tight} (relative to $\debug c$ at $\debug \omega$) if $\debug \alpha_{\debug e}$ is respectively $0$, $\infty$, or in-between.
In particular, when $\debug e$ is tight, $\debug c_{\debug e}(\debug x)$  is also regularly varying and exhibits the same asymptotic behavior as the benchmark function $\debug c(\debug x)$ at $\debug \omega$;
if $\debug e$ is fast, then $\debug c_{\debug e}(\debug x) = o(\debug c(\debug x))$;
and, finally, if $\debug e$ is slow, then $\debug c(\debug x) = o(\debug c_{\debug e}(\debug x))$.
As such, a benchmark function groups the network's edges into three equivalence classes that exhibit the same qualitative behavior with respect to $\debug c(\debug x)$.

Of course, this partition depends on the chosen benchmark and the traffic limit (light or heavy):
for instance, $\debug x^{2}$ is fast with respect to $\debug x$ at $0$, but it is slow at $\infty$.
For concision, we will not keep track of this dependence explicitly and instead rely on the context to resolve any ambiguities.
However, it will be important to keep in mind that the classification of fast and slow edges could be flipped when transitioning from heavy to light traffic and vice versa.

Now, since bottlenecks along a path are caused by its slowest edges, we also define the \emph{index of a path $\debug p\in\mathcal{\debug \nRoutes}$} as
\begin{equation}
\label{eq:index-path}
\debug \alpha_{\debug p}
	= \max_{\debug e\in\debug p} \debug \alpha_{\debug e},
\end{equation}
and we say that $\debug p$ is \emph{fast}, \emph{slow}, or \emph{tight} based on whether $\debug \alpha_{\debug p}$ is $0$, $\infty$, or in-between.
Finally, given that traffic will tend to be routed along the fastest paths in the network, we define the \emph{index of the network} as
\begin{equation}
\label{eq:index-network-single}
\debug \alpha
	=\min_{\debug p\in\mathcal{\debug \nRoutes}} \debug \alpha_{\debug p},
\end{equation}
and we say that the network is itself \emph{tight} if $0<\debug \alpha<\infty$.
In words, a path is fast (resp. tight/slow) if its slowest edge is fast (resp. tight/slow), and a network is tight if its fastest path is tight.

Defined this way, tightness guarantees that the network admits a path whose cost behaves asymptotically as a (positive) multiple of the benchmark function $\debug c(\debug x)$.
The importance of this requirement is again illustrated by the cost model \eqref{eq:cost-ex} of the previous section:
if we only assumed that the network admits a path whose cost behaves as $\Theta(\debug c(\debug x))$, then we would not be able to rule out the  pathological oscillations of the example in \cref{sec:example}.

\subsection{The light traffic limit}
\label{sec:single-light}

Thanks to the above legwork, we are in a position to state our main result for lightly congested networks with a single \ac{OD} pair:

\begin{theorem}
\label{thm:single-light}
Let $\debug \Gamma_{\debug M}$ be a nonatomic routing game with a single \ac{OD} pair.
If the network is tight under light traffic \textpar{$\debug \omega=0$}, then
\begin{equation}
\lim_{\debug M\to0} \PoA(\debug \Gamma_{\debug M})
	= 1.
\end{equation}
\end{theorem}

In words, \cref{thm:single-light} simply states that if the cost of the network's fastest path is regularly varying at $0$, selfish routing becomes efficient in light traffic.
To streamline our presentation, \cref{thm:single-light} is proved in \cref{app:convergence} as a special case of a much more general statement.
Here, we focus on some immediate corollaries thereof:

\begin{corollary}
\label{cor:single-light-power}
Suppose that, for every edge $\debug e\in\mathcal{\debug E}$, the limit $\lim_{\debug x\to0} \debug c_{\debug e}(\debug x) / \debug x^{\debug q_{\debug e}}$ is finite and nonzero for some $\debug q_{\debug e}\geq0$.
Then, $\PoA(\debug \Gamma_{\debug M}) \to 1$ as $\debug M\to0$.
\end{corollary}

\begin{Proof}
Referring to $\debug q_{\debug e}$ as the \emph{order} of $\debug e$, define the order of a path $\debug p\in\mathcal{\debug \nRoutes}$ as $\debug q_{\debug p} = \min_{\debug e\in\debug p} \debug q_{\debug e}$ and that of the network as $\debug q = \max_{\debug p\in\mathcal{\debug \nRoutes}} \debug q_{\debug p}$.
Clearly,
$\lim_{\debug x\to0} \debug c_{\debug e}(\debug x)/\debug x^{\debug q} = 0$ if and only if $\debug q_{\debug e}>\debug q$;
$\lim_{\debug x\to0} \debug c_{\debug e}(\debug x)/\debug x^{\debug q} = \infty$ if and only if $\debug q_{\debug e}<\debug q$;
and
$\lim_{\debug x\to0} \debug c_{\debug e}(\debug x)/\debug x^{\debug q} \in(0,\infty)$ if and only if $\debug q_{\debug e}=\debug q$.
This shows that the network is tight with respect to $\debug c(\debug x) = \debug x^{\debug q}$ at $0$, so \cref{thm:single-light} applies.
\end{Proof}

\begin{corollary}
\label{cor:single-light-anal}
In a single \ac{OD}-network with analytic costs
we have $\PoA(\debug \Gamma_{\debug M})\to1$ as $\debug M\to0$.
\end{corollary}

\begin{Proof}
If $\debug c_{\debug e}(\debug x) = \sum_{\debug k=0}^{\infty} \debug c_{\debug k,\debug e} \debug x^{\debug k}$ for small enough $\debug x$, we have $\lim_{\debug x\to\infty} \debug c_{\debug e}(\debug x)/\debug x^{\debug q_{\debug e}} \in (0,\infty)$ for $\debug q_{\debug e} = \min\setdef{\debug k\in\mathbb{N}}{\debug c_{\debug k,\debug e}\neq0}$.
Our claim then follows from \cref{cor:single-light-power}.
\end{Proof}

\begin{corollary}
\label{cor:single-light-poly}
In a single \ac{OD}-network with polynomial costs
we have $\PoA(\debug \Gamma_{\debug M})\to1$ as $\debug M\to0$.
\end{corollary}

Of the above results, \cref{cor:single-light-anal,cor:single-light-poly} are of special practical interest because most latency models that have been proposed in the literature are polynomial or analytic at $0$.
In urban networks, the golden standard is the \ac{BPR} quartic model $\debug c_{\debug e}(\debug x) = a_{\debug e} + b_{\debug e} \debug x^{4}$, while basically all of the established queueing models used in the theory of packet-switched networks ($M/M/1$, $M/G/k$, $M/M/c$, etc.) are analytic at $0$ \citep{BG92}.

Despite appearances, the very wide applicability of \cref{thm:single-light} and its corollaries is fairly surprising.
Indeed, at first sight, one would expect that when $\debug M\to0$, traffic is so light that it doesn't really matter how it is routed.
This is indeed the case if, for instance, all paths in the network exhibit different positive costs when $\debug M=0$ (cf.~\cref{prop:PoA-equal-one}).
However, if the cost of an empty path is zero, this is no longer the case:
the optimum and equilibrium traffic assignments could be fairly different (even when the network is lightly congested), so there is no a priori reason for the price of anarchy to converge to $1$ as $\debug M\to0$ (the example of Section 3 clearly illustrates this phenomenon).
\cref{thm:single-light} shows that all that is needed for this to occur is for the network's cost functions to be faithfully represented by a common benchmark function:
when this condition is met, optimum and equilibrium costs no longer fluctuate but, instead, they converge to the same value.

\subsection{The heavy traffic limit}
\label{sec:single-heavy}

Our main result for highly congested networks with a single \ac{OD} pair is as follows:

\begin{theorem}
\label{thm:single-heavy}
Let $\debug \Gamma_{\debug M}$ be a nonatomic routing game with a single \ac{OD} pair.
If the network is tight under heavy traffic \textpar{$\debug \omega=\infty$}, then
\begin{equation}
\lim_{\debug M\to\infty} \PoA(\debug \Gamma_{\debug M})
	= 1.
\end{equation}
\end{theorem}

In words, \cref{thm:single-heavy} simply states that if the cost of the network's fastest path is regularly varying at $\infty$, selfish routing becomes efficient in heavy traffic.
To compare and contrast the light and heavy traffic regimes, we relegate the proof of \cref{thm:single-heavy} to \cref{app:convergence} and only focus here on some immediate corollaries thereof:

\begin{corollary}
\label{cor:single-heavy-bounded}
Suppose there exists a path $\debug p\in\mathcal{\debug \nRoutes}$ with bounded costs, that is, $\lim_{\debug x\to\infty}\debug c_\debug e(\debug x)<\infty$ for all $\debug e\in\debug p$.
Then, $\PoA(\debug \Gamma_{\debug M}) \to 1$  as $\debug M\to\infty$.
\end{corollary}

\begin{Proof}
Taking $\debug c(\debug x) = 1$, we get $\debug \alpha_{\debug e} = \lim_{\debug x\to\infty} \debug c_{\debug e}(\debug x)\in(0,\infty]$ for all $\debug e\in\mathcal{\debug E}$.
By assumption, there exists a path such that $0 < \debug \alpha_{\debug p} < \infty$, so \cref{thm:single-heavy} applies.
\end{Proof}

\begin{corollary}
\label{cor:single-heavy-power}
Suppose that the limit $\lim_{\debug x\to\infty} \debug c_{\debug e}(\debug x) / \debug x^{\debug q_{\debug e}}$ is finite and nonzero for some $\debug q_{\debug e}\geq0$ and all $\debug e\in\mathcal{\debug E}$.
Then, $\PoA(\debug \Gamma_{\debug M}) \to 1$ as $\debug M\to\infty$.
\end{corollary}

\begin{Proof}
Shadowing the proof of \cref{cor:single-light-power}, let $\debug q_{\debug p} = \max_{\debug e\in\debug p} \debug q_{\debug e}$ and $\debug q = \min_{\debug p\in\mathcal{\debug \nRoutes}} \debug q_{\debug p}$ (but note the reversal of the $\max$ and $\min$ operators).
Clearly,
$\lim_{\debug x\to\infty} \debug c_{\debug e}(\debug x)/\debug x^{\debug q} = 0$ if and only if $\debug q_{\debug e}<\debug q$;
$\lim_{\debug x\to\infty} \debug c_{\debug e}(\debug x)/\debug x^{\debug q} = \infty$ if and only if $\debug q_{\debug e}>\debug q$;
finally,
$\lim_{\debug x\to\infty} \debug c_{\debug e}(\debug x)/\debug x^{\debug q} \in(0,\infty)$ if and only if $\debug q_{\debug e}=\debug q$.
This shows that the network is tight with respect to $\debug c(\debug x) = \debug x^{\debug q}$ at $\infty$, so \cref{thm:single-heavy} applies.
\end{Proof}

\begin{corollary}
\label{cor:single-heavy-poly}
In a single \ac{OD}-network with polynomial costs
we have $\PoA(\debug \Gamma_{\debug M})\to1$ as $\debug M\to\infty$.
\end{corollary}

In a certain, precise sense, \cref{thm:single-light,thm:single-heavy} show that the high and low congestion regimes can be seen as different sides of the same coin.
By excluding pathological oscillations at either end of the congestion spectrum, regular variation ensures asymptotic regularity and guarantees that selfish routing becomes efficient in the limit:
specifically, tightness at $0$ guarantees efficiency in light traffic while tightness at $\infty$ guarantees efficiency in heavy traffic.
By this token, taking \cref{cor:single-light-poly,cor:single-heavy-poly} in tandem implies that selfish routing becomes efficient under both light and heavy traffic in networks with polynomial costs and a single \ac{OD} pair.

That being said, there are still important, quantitative differences between the light and heavy traffic limits.
For instance, even though \cref{cor:single-heavy-power,cor:single-heavy-poly} are direct analogues of their light traffic counterparts, the conclusion of \cref{cor:single-heavy-bounded} is false in light traffic (the three-link network of \cref{sec:example} serves again as a counterexample).
In fact, even in the case of polynomial costs (\cref{cor:single-light-poly} vs. \cref{cor:single-heavy-poly}), there is an important reversal of roles that takes place between fast and slow edges.
Specifically, edges that are fast in light traffic typically become slow under heavy traffic and vice versa (importantly however, tight edges are not re-classified under this regime change).
Nevertheless, despite this reversal, the \acl{PoA} still goes to $1$ in both cases.

redpajama_set_name: RedPajamaArXiv


Wrote at least four times about Zoe Quinn without disclosing that she was working with Quinn's Crash Override Network. They also have rather friendly public interactions, expressed the desire to meet, and Cross has frequently promoted Quinn on social media.
Wrote at least five articles discussing Feminist Frequency without disclosing her position as the non-profit company's secretary.


Do You Know When To Use Old Ginger Root And When To Use The Young?
Ginger is known to have more than twelve types of antioxidants, making it useful for treatment of many disorders. Like other spices, it has anti-inflammatory properties and is used widely for medicinal purposes.
This herb contains essential oils, protein, calcium, phosphorus, iron, vitamin C, choline, folic acid, inositol, manganese, panthotenic acid, silicon, and a small amount of vitamin B3.
Ginger root is widely used in Asian cultures. In Japan, fresh young ginger is pickled to be eaten as condiments with all their meals. The outstanding phytonutrient in ginger root in its spicy substance called gingerol. In old ginger, this nutrient is more concentrated and richer.
Young ginger is fragrant, pungent, fleshy and juicy with a mild spicy taste. Whereas old ginger is fibrous and almost dry and tends to be spicier than its young counterpart.
A recent study showed that young ginger brings down body temperature as in the case of fever. Whereas the old (dryer) ginger brings up the body temperature as in the case of a cold and suitable during winter. When going on an extended juice feasting, I recommend the use of old ginger for this reason.
OLD ginger root tends to increase body temperature.
If you tend to feel cold most of the time, as in the case of people with hypothyroidism.
When doing juice fasting, you need some body heat.
YOUNG ginger root tends to lower body temperature.
If you tend to feel warm most of the time, as in the case of people with hyperthyroidism.
Ginger root is an amazing herb and should be included in most of your juices, not only for taste, but for its myriad health benefits.
Read more about the many excellent health benefits of ginger root.


text:
NHK Newsline (stylized as NHK NEWSLiNE, formerly and also simply known as Newsline) ( NHK Nyūsurain) is a foreign news program aired on NHK's international broadcasting service NHK World TV. This program broadcasts on the hour, 24 hours a day.

History
NHK Newsline started as Day Line Japan in April 1997, with a length of 10 minutes, and airing several times a day. In 2000, the program's name was changed to Newsline. The English spoken portions of the program would gradually expand with time.

On January 30, 2009, News Watch 9 - an English-dubbed news program - was removed from the NHK World line-up. On February 2, 2009, Newsline was re-formatted in order to fill the gap left by News Watch 9, by changing to a news and information program. Newsline's time slot also changed to air at the top of every hour, 24 times a day. The length of the program was typically 30 minutes during the week, and 10 minutes on weekends and Japanese holidays. The program has been referred to as NHK Newsline since Late March 2016.

On April 1, 2019, NHK Newsline changed to a 15-20 minute format on weekdays at most times, while other Newsline-branded programs fill the remaining time until the bottom of the hour. These include Newsline In Depth, which features a variety of feature stories, and Newsline Biz, with business news. Newsline is replaced by the daily news program Newsroom Tokyo on weekdays, except holidays, at 20:00 JST (replaying at 3:00 JST the following morning).

On March 30, 2020, NHK implemented a new policy for referring to Japanese names, following the common practice in the Japanese language of listing the surname first followed by the given name. The new policy extends to all of NHK's English-language programming, including NHK Newsline. For example, Shinzō Abe (the former Prime Minister) is referred to as Abe Shinzō under the new policy.

Format
NHK Newsline updates viewers on the latest hard news with a focus mainly on Japan, the rest of Asia, and then finally around the world. Some editions feature segments focusing on Southeast Asia hosted by an anchor based in Bangkok. Feature segments follow, with business news and a global weather forecast. NHK Newsline is anchored by established NHK news presenters. The anchors speak entirely in English. English dubbing or occasional English subtitling if needed (previously just English subtitles until after 2011) are used in video footage when the spoken language is other than English. All measurements, including temperatures, are given in metric. Monetary figures are measured in Japanese yen, and figures in United States dollars are often also included. During periods of breaking news, Newsline is usually extended past its normal time slot.

Anchors and reporters

News
Weekdays (15–minute program)
08:00 JST/23:00 UTC - 12:00 JST/02:00 UTC Kyoko Tashiro  / Hiroaki Yamaguchi (every other week)
13:00 JST/03:00 UTC - 18:00 JST/09:00 UTC Rika Kawasaki / Miki Yamamoto / Erika Morishita /
19:00 JST/10:00 UTC - 07:00 JST/22:00 UTC Raja Pradhan / Yoshi Ogasawara (every other week)

Weekends (10-minute program)
08:00 JST/23:00 UTC - 12:00 JST/02:00 UTC Keiko Kitagawa
13:00 JST/03:00 UTC - 19:00 JST/10:00 UTC Gene Otani / Ramin Mellegard / Kanako Sachno
20:00 JST/11:00 UTC - 07:00 JST/22:00 UTC Ross Mihara

National holidays, New Year's Day or end of year  (10-minute program)
08:00 JST/23:00 UTC - 12:00 JST/02:00 UTC  Miki Yamamoto / Keiko Kitagawa
13:00 JST/03:00 UTC - 07:00 JST/22:00 UTC Kanako Sachno / Yoshi Ogasawara / Raja Pradhan

Politics
 Masayo Nakajima - Senior political commentator / deputy editor-in-chief NHK's Tokyo HQ
 Akihiro Mikoda - Senior political / economics commentator
 Shogo Takahashi - NHK World Executive Producer
 Takashi Ichinose - Special Affairs commentator / NHK's Tokyo HQ
 Miki Ebara - editor-in-chief, NHK's Washington Bureau
 Mayuko Ambe - Politics reporter
 Tomoko Kamata - Politics reporter
 Kimberly Gale - Politics reporter (freelance work for CBC News / NHK World)
 Kim Chan-ju - NHK Seoul Bureau

Business
(all times listed are in Japanese Standard Time)
 Akiko Okamoto - Reporter
 Gene Otani - Anchor / Presenter, Newsline Asia 24 and Direct Talk
 Shaula Vogue - Reporter / Presenter, Biz Stream and Design Talks Plus
 Ramin Mellegard - Anchor / Presenter, Newsline Biz and Newsline Asia 24

Weather
 Sayaka Mori - meteorologist for Newsroom Tokyo and other Newsline programs till 2:00 JST
 Jonathan Oh - meteorologist for Newsroom Tokyo and other Newsline programs till 2:00 JST
 Tsietsei Monare - meteorologist for Newsline Asia 24 and other Newsline programs till 20:00 JST
 Yoko Komagata - meteorologist for Newsline Asia 24 and other Newsline programs till 20:00 JST

Irregular anchors

 Yuko Fukushima - business anchor for Newsroom Tokyo (previously as regular anchor from 2009 to 2012)

Other anchors
 Catherine Kobayashi, NHK New York Bureau, anchors NHK Newsline from New York, alternating weekdays from 08:00-12:00 JST
 Minori Takao, NHK New York Bureau, anchors NHK Newsline from New York, alternating weekdays from 08:00-12:00 JST
 Dhra Dhirakaosal, NHK Bangkok Bureau, also reports for Newsline Asia 24 and Newsroom Tokyo (primarily on Thursdays & Fridays)
 Cholaphansa Narula, NHK Bangkok Bureau, also reports for Newsline Asia 24 and Newsroom Tokyo (Mostly Tuesdays)
 Roselyn Debhavalya, NHK Bangkok Bureau, also reports for Newsline Asia 24 and Newsroom Tokyo (Primarily Mondays & Wednesdays)
 Aiko Doden, Presenter, Newsline In Depth and NHK Special Affairs commentator
 Marie Yanaka, Presenter, Newsline in Depth and Business reporter
 Yoko Nishimura, anchors NHK Newsline one Sunday per month from 1100 UTC - 2200 UTC

Former on-air Staff
 Hiro Morita - Anchor (departed in 2022)
 Ai Uchida -  Anchor (departed in 2021)
 James Tengan -  Anchor (departed in 2020, Currently narrates NHK World Japan's Program Tokyo Fashion Express)
 Carley Gomez - Meteorologist (departed in 2019; now at KXTV-TV Sacramento, California)
 Robert Speta - Meteorologist (departed in 2017; now at WTLV-TV  Jacksonvile, Florida)
 Mai Shoji - Meteorologist (departed in 2015; now at Tokyo FM)
 Ron Madison - Business Anchor (departed in 2015)
 Yuko Aotani - Anchor (departed in 2015)
 John LaDue - Reporter / TSE Broadcasts
 Phoebe Amoroso - Reporter/ TSE Broadcasts
 Sherry Ann Jisu - Anchor (departed in 2015; now at Bloomberg Television)
 Miwa Gardner - Meteorologist (departed in 2012; now at Google)

Ratings
NHK Newsline is rated as one of the top English–language news programs in the Asia Pacific region. NHK Newsline competes in the Asian news market with China's CCTV-9 News on CGTN; South Korea's Arirang News on Arirang TV; Singapore's Asia Now on CNA; various news programs like Rundown and The World Tonight on the ABS-CBN News Channel from the Philippines; and Australia Network News on the Australia Network. In the United States, NHK Newsline airs on the PBS World Channel at 2:00pm Pacific Time Zone on weekdays and on Link TV daily.

See also
 BBC World News, top of the hour daily newscast aired on BBC World News
 DW News, top of the hour daily newscast aired on DW-TV
 Newshour, top of the hour daily newscast aired on Al Jazeera English

References

Footnotes

External links

 NHK World TV Anchors and Reporters

Japanese television news shows
2000 Japanese television series debuts
2000s Japanese television series
2010s Japanese television series
2020s Japanese television series
NHK original programming

redpajama_set_name: RedPajamaWikipedia


Welcome to the Republic of Vietnam Posterity website. We are the non profit organization. We do not require that you belong to any particular affiliation or possess any previous memberships to join our organization. We do ask that you support our organization through regular participation in activities. We are always looking for new members. Give us a call anytime. Our doors are always open. Call (480) Anh-Viet for details.
Tại sao chúng ta phài bỏ Quê Hương?
Cải Tạo hay Tù Nhân Lương Tâm?
Content copyright . HAUDUEVNCH.ORG. All rights reserved.


Axonius Raises $13 Million Series A to Help Enterprises Automate Cybersecurity Asset Management and Security Policy Enforcement Bessemer leads round to help cybersecurity asset management leader accelerate growth and product innovation; Amit Karp joins board of directors NEW YORK, February 12, 2019-- Cybersecurity asset management company Axonius today announced that it has raised $13 million in Series A funding. Bessemer Venture Partners led the round with participation from existing investors YL Ventures, Vertex, WTI and Emerge. The company will use the new funding to accelerate customer growth and expedite product innovations for the Axonius Cybersecurity Asset Management Platform.