New Complexity Results and Algorithms for the Minimum Tollbooth Problem

Soumya Basu, Thanasis Lianeas, Evdokia Nikolova

The inefficiency of the Wardrop equilibrium of nonatomic routing games can be eliminated by placing tolls on the edges of a network so that the socially optimal flow is induced as…