Title: Demand-Independent Optimal Tolls,
Abstract: Wardrop equilibria in nonatomic congestion games are in general inefficient
as they do not induce an optimal flow that minimizes the total travel time.
Network tolls are a prominent and popular way to induce an optimum flow in
equilibrium. The classical approach to find such tolls is marginal cost pricing
which requires the exact knowledge of the demand on the network. In this paper,
we investigate under which conditions demand-independent optimum tolls exist
that induce the system optimum flow for any travel demand in the network. We
give several characterizations for the existence of such tolls both in terms of
the cost structure and the network structure of the game. Specifically we show
that demand-independent optimum tolls exist if and only if the edge cost
functions are shifted monomials as used by the Bureau of Public Roads.
Moreover, non-negative demand-independent optimum tolls exist when the network
is a directed acyclic multi-graph. Finally, we show that any network with a
single origin-destination pair admits demand-independent optimum tolls that,
although not necessarily non-negative, satisfy a budget constraint.