Taxing subnetworks

Martin Hoefer*, Lars Olbrich, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Citations (Scopus)


We study taxes in the well-known game theoretic traffic model due to Wardrop. Given a network and a subset of edges, on which we can impose taxes, the problem is to find taxes inducing an equilibrium flow of minimal network-wide latency cost. If all edges are taxable, then marginal cost pricing is known to induce the socially optimal flow for arbitrary multi-commodity networks. In contrast, if only a strict subset of edges is taxable, we show NP-hardness of finding optimal taxes for general networks with linear latency functions and two commodities. On the positive side, for single-commodity networks with parallel links and linear latency function, we provide a polynomial time algorithm for finding optimal taxes.

Original languageEnglish
Title of host publicationInternet and Network Economics
Subtitle of host publication4th International Workshop, WINE 2008, Proceedings
EditorsChristos Papadimitriou, Shuzhong Zhang
Number of pages9
ISBN (Electronic)978-3-540-92185-1
Publication statusPublished - 1 Dec 2008
Externally publishedYes
Event4th International Workshop on Internet and Network Economics, WINE 2008: Internet And Network Economics (WINE 2008) - Shanghai, China, Shanghai, China
Duration: 17 Dec 200820 Dec 2008
Conference number: 4

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5385 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Workshop on Internet and Network Economics, WINE 2008
Abbreviated titleWINE 2008
Other17-20 Dec, 2008

Cite this