Taxing subnetworks

Martin Hoefer; Lars Olbrich; Alexander Skopalik

doi:10.1007/978-3-540-92185-1_35

Taxing subnetworks

Martin Hoefer^*
, Lars Olbrich
, Alexander Skopalik

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

25 Citations (Scopus)

7 Downloads (Pure)

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 language	English
Title of host publication	Internet and Network Economics
Subtitle of host publication	4th International Workshop, WINE 2008, Proceedings
Editors	Christos Papadimitriou, Shuzhong Zhang
Publisher	Springer
Pages	286-294
Number of pages	9
ISBN (Electronic)	978-3-540-92185-1
ISBN (Print)	978-3-540-92184-4
DOIs	https://doi.org/10.1007/978-3-540-92185-1_35
Publication status	Published - 1 Dec 2008
Externally published	Yes
Event	4th International Workshop on Internet and Network Economics, WINE 2008: Internet And Network Economics (WINE 2008) - Shanghai, China, Shanghai, China Duration: 17 Dec 2008 → 20 Dec 2008 Conference number: 4

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	5385
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Workshop on Internet and Network Economics, WINE 2008
Abbreviated title	WINE 2008
Country/Territory	China
City	Shanghai
Period	17/12/08 → 20/12/08
Other	17-20 Dec, 2008

Keywords

n/a OA procedure

Access to Document

10.1007/978-3-540-92185-1_35

Cite this

@inproceedings{05b0d46141544714aeced72ac96dec18,

title = "Taxing subnetworks",

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.",

keywords = "n/a OA procedure",

author = "Martin Hoefer and Lars Olbrich and Alexander Skopalik",

year = "2008",

month = dec,

day = "1",

doi = "10.1007/978-3-540-92185-1\_35",

language = "English",

isbn = "978-3-540-92184-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "286--294",

editor = "Christos Papadimitriou and Shuzhong Zhang",

booktitle = "Internet and Network Economics",

address = "Germany",

note = "4th International Workshop on Internet and Network Economics, WINE 2008 : Internet And Network Economics (WINE 2008), WINE 2008 ; Conference date: 17-12-2008 Through 20-12-2008",

}

Hoefer, M, Olbrich, L & Skopalik, A 2008, Taxing subnetworks. in C Papadimitriou & S Zhang (eds), Internet and Network Economics: 4th International Workshop, WINE 2008, Proceedings. Lecture Notes in Computer Science, vol. 5385, Springer, pp. 286-294, 4th International Workshop on Internet and Network Economics, WINE 2008, Shanghai, China, 17/12/08. https://doi.org/10.1007/978-3-540-92185-1_35

Taxing subnetworks. / Hoefer, Martin; Olbrich, Lars; Skopalik, Alexander.
Internet and Network Economics: 4th International Workshop, WINE 2008, Proceedings. ed. / Christos Papadimitriou; Shuzhong Zhang. Springer, 2008. p. 286-294 (Lecture Notes in Computer Science; Vol. 5385).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Taxing subnetworks

AU - Hoefer, Martin

AU - Olbrich, Lars

AU - Skopalik, Alexander

N1 - Conference code: 4

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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.

AB - 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.

KW - n/a OA procedure

UR - https://www.scopus.com/pages/publications/58849157737

U2 - 10.1007/978-3-540-92185-1_35

DO - 10.1007/978-3-540-92185-1_35

M3 - Conference contribution

AN - SCOPUS:58849157737

SN - 978-3-540-92184-4

T3 - Lecture Notes in Computer Science

SP - 286

EP - 294

BT - Internet and Network Economics

A2 - Papadimitriou, Christos

A2 - Zhang, Shuzhong

PB - Springer

T2 - 4th International Workshop on Internet and Network Economics, WINE 2008

Y2 - 17 December 2008 through 20 December 2008

ER -

Taxing subnetworks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this