2015/09/24 by Soumya Basu, Basu, Soumya, Thanasis Lianeas +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Transportation Planning and Optimization #cs.GT
paper · pdf · doi:10.48550/arxiv.1509.07260
openalex publication_date 2015/09/24 · arxiv created 2015/09/25 · arxiv updated 2015/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 an equilibrium flow. A solution where the minimum number of edges are tolled may be preferable over others due to its ease of implementation in real networks. In this paper we consider the minimum tollbooth (MINTB) problem, which seeks social optimum inducing tolls with minimum support. We prove for single commodity networks with linear latencies that the problem is NP-hard to approximate within a factor of 1.1377 through a reduction from the minimum vertex cover problem. Insights from network design motivate us to formulate a new variation of the problem where, in addition to placing tolls, it is allowed to remove unused edges by the social optimum. We prove that this new problem remains NP-hard even for single commodity networks with linear latencies, using a reduction from the partition problem. On the positive side, we give the first exact polynomial solution to the MINTB problem in an important class of graphs---series-parallel graphs. Our algorithm solves MINTB by first tabulating the candidate solutions for subgraphs of the series-parallel network and then combining them optimally.