We consider a directed network in which every edge possesses a latency
function specifying the time needed to traverse the edge given its 
congestion.  Selfish, noncooperative agents constitute the network 
traffic and wish to travel from a source $s$ to a sink $t$ as quickly 
as possible.  Since the route chosen by one network user affects the 
congestion (and hence the latency) experienced by others, we model the 
problem as a noncooperative game.  Assuming each agent controls only a 
negligible portion of the overall traffic, Nash equilibria in this 
noncooperative game correspond to $s$-$t$ flows in which all flow paths 
have equal latency.

A natural measure for the performance of a network used by selfish 
agents is the common latency experienced by each user in a Nash 
equilibrium.  It is a counterintuitive but well-known fact that 
removing edges from a network may {\em improve} its performance; the 
most famous example of this phenomenon is the so-called {\em Braess's 
Paradox}.  This fact motivates the following network design problem: 
given such a network, which edges should be removed to obtain the best 
possible flow at Nash equilibrium?  Equivalently, given a large network 
of candidate edges to be built, which subnetwork will exhibit the best 
performance when used selfishly?

We give optimal inapproximability results and approximation algorithms
for several network design problems of this type.  For example, we 
prove that for networks with $n$ vertices and continuous, nondecreasing 
latency functions, there is no approximation algorithm for this problem 
with approximation ratio less than $n/2$ (unless $P=NP$).  We also 
prove this hardness result to be best possible by exhibiting an 
$n/2$-approximation algorithm.  For networks in which the latency of 
each edge is a linear function of the congestion, we prove that there 
is no $(\frac{4}{3}-\eps)$-approximation algorithm for the problem (for 
any $\eps > 0$, unless $P=NP$); the existence of a 
$\frac{4}{3}$-approximation algorithm follows easily from existing 
work, proving this hardness result sharp.

Moreover, we prove that an optimal approximation algorithm for these
problems is what we call the {\em trivial algorithm}: given a network
of candidate edges, build the entire network.  A consequence of this 
result is that Braess's Paradox (even in its worst-possible 
manifestation) is impossible to detect efficiently.