We study economic incentives for influencing selfish behavior in
networks. 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 historically measured by the
sum of all travel times, also called the total latency.
It is well known that the outcome of selfish routing (a Nash
equilibrium) does not minimize the total latency and can be
improved upon with coordination, and that marginal cost pricing
---charging each network user for the congestion effects caused
by its presence---eliminates the inefficiency of selfish routing.
However, the principle of marginal cost pricing assumes that
(possibly very large) taxes cause no disutility to network users;
this is appropriate only when collected taxes can be feasibly
returned (directly or indirectly) to the users, for example via a
lump-sum refund. If this assumption does not hold and we wish to
minimize the total user disutility (latency plus taxes paid)---
the total cost---how should we price the network edges? Intuition
may suggest that taxes should never be able to improve the cost of
a Nash equilibrium, but the famous Braess's Paradox shows this
intuition to be incorrect.
We consider strategies for pricing network edges to reduce the
cost of a Nash equilibrium. Since levying a sufficiently large
tax on an edge effectively removes it from the network, our
study generalizes previous work on network design. In this paper,
we prove the following results.
- In a large class of networks---including all networks with
linear latency functions---marginal cost taxes do not improve
the cost of the Nash equilibrium.
- The best-possible benefit from arbitrary taxes does not exceed
that of edge removal. In every network with linear latency
functions, taxes cannot improve over removing edges. There are
networks with nonlinear latency functions, however, in which
taxes are radically more powerful than edge removal.
- Strong inapproximability results known for network design carry
over to the problem of computing optimal taxes, proving this
problem computationally intractable.