Taxing subnetworks

Martin Hoefer*, Lars Olbrich, Alexander Skopalik

*Corresponding author for this work

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

15 Citations (Scopus)

Abstract

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
Pages286-294
Number of pages9
ISBN (Electronic)978-3-540-92185-1
DOIs
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

Conference

Conference4th International Workshop on Internet and Network Economics, WINE 2008
Abbreviated titleWINE 2008
CountryChina
CityShanghai
Period17/12/0820/12/08
Other17-20 Dec, 2008

Fingerprint Dive into the research topics of 'Taxing subnetworks'. Together they form a unique fingerprint.

Cite this