Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Computing Optimal Network Tolls
Author(s): Harks, Tobias
Schäfer, Guido
Sieg, Martin
Type: Research Paper
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. Finally, we empirically evaluate the performance of our approximation algorithm on a set of real-world test instances.
Subject(s): network games
network tolls
Issue Date: 13-Jun-2008
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90B20 Traffic problems
90C11 Mixed integer programming
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2008, 36
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 163.55 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.