Corollary 2.8 — with polynomial latencies of degree $p$ and nonnegative coefficients, $\rho(G,r,\ell)\le p+1$

Consider a routing instance whose routes are given by $0/1$ edge–route incidence columns, each serving one commodity $i$ with positive rate $r_i$, and whose latency functions are polynomials

for a positive integer $p$ and nonnegative reals $a_{e,i}$ ($0\le i\le p$). Write $C(f)=\sum_P\ell_P(f)f_P$ for the cost of a flow.

Corollary 2.8. If $f$ is a flow at Nash equilibrium (Definition 2.1) and $f^*$ is any feasible flow, then

Equivalently, $\rho(G,r,\ell)\le p+1$: selfish routing costs at most $p+1$ times the optimum. For linear latencies ($p=1$) this gives the factor $2$, later improved to $4/3$ in §4 of the paper.

Formalization Note The paper's $\rho(G,r,\ell)=C(f)/C(f^*)\le p+1$, with $f^*$ optimal, is stated as an inequality against every feasible flow, which is equivalent once an optimal flow exists and avoids dividing by a cost that may be $0$. The degree $p$ is a common upper bound: $a_{e,p}=0$ is allowed. Coefficients are required nonnegative only for $i\le p$, the ones that occur. Polynomials with nonnegative coefficients are nonnegative, nondecreasing and continuous on $[0,\infty)$, so no other latency hypothesis is needed. Routes are $0/1$ incidence columns, a generalization of the simple paths of a graph.