Author(s) :
Tobias Harks,
Guido Schäfer,
Martin Sieg
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 36-2008
MSC 2000
- 90B20 Traffic problems
-
90C11 Mixed integer programming
Abstract :
We consider the problem of computing tolls in non-atomic network routing
games such that a predetermined flow is realized as Nash flow. It is a
well-known fact that marginal cost tolls give rise to a Nash flow that
minimizes the total travel time. In this paper, we study the problem of
computing such tolls such that an additional toll-dependent objective
function is optimized. We consider a broad class of objective functions,
including convex and min-max functions, and show that such tolls can
be computed in polynomial time.
We also consider the problem of computing tolls such that the number
of tolled arcs is minimized. We prove that this problem is NP-hard and
APX-hard, even for very restricted single-commodity networks,
and give first approximation results.