Computing Optimal Network Tolls
| dc.contributor.author | Harks, Tobias | |
| dc.contributor.author | Schäfer, Guido | |
| dc.contributor.author | Sieg, Martin | |
| dc.date.accessioned | 2021-12-17T10:07:38Z | |
| dc.date.available | 2021-12-17T10:07:38Z | |
| dc.date.issued | 2008-06-13 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15626 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14399 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | network games | en |
| dc.subject.other | network tolls | en |
| dc.title | Computing Optimal Network Tolls | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2008, 36 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90B20 Traffic problems | en |
| tub.subject.msc2000 | 90C11 Mixed integer programming | en |
Files
Original bundle
1 - 1 of 1