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.