We investigate the existence of optimal tolls for atomic symmetric network
congestion games with unsplittable traffic and arbitrary nondecreasing
latency functions. We focus on pure Nash equilibria, and consider a natural toll mechanism,
which we call cost-balancing tolls. A set of cost-balancing tolls
turns every path with positive traffic on its edges into a minimum-cost
path. Hence any given configuration is induced as a pure Nash equilibrium of
the modified game with the corresponding cost-balancing tolls.
We show how to compute in linear time a set of cost-balancing tolls for the
optimal solution such that the total amount of tolls paid by any player in
any pure Nash equilibrium of the modified game does not exceed the latency
on the maximum-latency path in the optimal solution.
Our main result is that for congestion games on series-parallel networks
with strictly increasing latency functions, the optimal solution is induced
as the unique pure Nash equilibrium of the game with the
corresponding cost-balancing tolls. To the best of our knowledge, only
linear congestion games on parallel links were known to admit optimal tolls
prior to this work.
To demonstrate the difficulty of computing a better set of optimal tolls, we
show that even for two-player linear congestion games on series-parallel
networks, it is NP-hard to decide whether the optimal solution is the
unique pure Nash equilibrium or there is another pure Nash equilibrium of
total cost at least $6/5$ times the optimal cost.