We study the degradation in network performance caused by the
selfish behavior of noncooperative network users. We consider
a directed network in which each edge possesses a latency
function describing the common latency incurred by all traffic
on the edge as a function of the edge congestion. Given a rate
of traffic between each pair of nodes in the network, we aspire
toward an assignment of traffic to paths in which the sum of all
travel times (the {\em total latency}) is minimized; however, in
many settings network users are free to route their traffic in a
selfish manner, without regard to the total latency. We
therefore assume that each network user routes its traffic on
the minimum-latency path available to it, given the network
congestion caused by the other users. In general such a
``selfishly motivated'' assignment of traffic to paths (a {\em
Nash equilibrium}) will not minimize the total latency; hence,
selfish behavior carries the cost of decreased network
performance. We quantify this degradation in network performance
via the {\em price of anarchy}, defined as the worst-possible
ratio between the total latency of a Nash equilibrium and of a
minimum-latency routing of the traffic.
In this paper, we show that the underlying network topology plays
no role in the determination of the price of anarchy.
Specifically, we show that under weak hypotheses on the class of
allowable edge latency functions, the worst-case ratio between the
total latency of a Nash equilibrium and of a minimum-latency
routing for any multicommodity flow network is achieved by a
single-commodity instance on a network of parallel links. In the
special case where the class of allowable latency functions
includes all of the constant functions, we prove that a network
with only two parallel links suffices to achieve the worst-possible
ratio. Informally, these results imply that the inefficiency
inherent in a flow at Nash equilibrium stems from the inability of
selfish users to discern which of two competing routes is superior
and {\em not} from the topological complexity arising from the
diverse intersections of many paths belonging to different
commodities.
Our result that simple networks always furnish worst-possible
examples also provides a powerful method for computing the price of
anarchy with respect to an arbitrary class of latency functions.
We apply this method to function classes that have been well
studied in the literature (such as degree-bounded polynomials and
functions of the form $\ell(x) = (u-x)^{-1}$ that are used to model
edges with capacity $u$), thereby obtaining the first tight
analyses of the price of anarchy for significant classes of latency
functions outside the class of linear functions.