We study the negative consequences of selfish behavior in a congested
network and economic means of influencing such behavior. We consider 
a model of selfish routing in which the latency experienced by network 
traffic on an edge of the network is a function of the edge congestion,
and network users are assumed to selfishly route traffic on minimum-
latency paths.  The quality of a routing of traffic is measured by the 
sum of travel times (the total latency).

It is well known that the outcome of selfish routing (a Nash
equilibrium)  does not minimize the total latency.  An ancient 
strategy for improving the selfish solution is the principle of 
marginal cost pricing, which asserts that on each edge of the network, 
each network user on the edge should pay a tax offsetting the 
congestion effects caused by its presence.  By pricing network edges
according to this principle, the inefficiency of selfish routing can
always be eradicated.

This result, while fundamental, assumes a very strong homogeneity 
property: all network users are assumed to trade off time and money in 
an identical way.  The guarantee also ignores both the algorithmic 
aspects of edge pricing and the unfortunate possibility that an 
efficient routing of traffic might only be achieved with exorbitant 
taxes.  Motivated by these shortcomings, we extend this classical work 
on edge pricing in several different directions and prove the following 
results.

- We prove that the edges of a single-commodity network can always be 
  priced so that an optimal routing of traffic arises as a Nash 
  equilibrium, even for very general heterogeneous populations of 
  network users.

- When there are only finitely many different types of network users 
  and all edge latency functions are convex, we show how to compute 
  such edge prices efficiently.

- We prove that an easy-to-check mathematical condition on the 
  population of heterogeneous network users is both necessary and 
  sufficient for the existence of edge prices that induce an optimal
  routing while requiring only moderate taxes.