Taxing Subnetworks
| dc.contributor.author | Hoefer, Martin | deu |
| dc.contributor.author | Olbrich, Lars | deu |
| dc.contributor.author | Skopalik, Alexander | deu |
| dc.date.accessioned | 2011-03-23T10:15:54Z | deu |
| dc.date.available | 2011-03-23T10:15:54Z | deu |
| dc.date.issued | 2008 | |
| dc.description.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. | eng |
| dc.description.version | published | |
| dc.identifier.citation | Publ. in: Internet and network economics : 4th International Workshop, WINE 2008, Shanghai, China, December 17 - 20, 2008; proceedings / Christos Papadimitriou ... (eds.). - Berlin ; Heidelberg [u.a.] : Springer, 2008, pp. 286-294. - (Lecture notes in computer science ; 5385) | deu |
| dc.identifier.doi | 10.1007/978-3-540-92185-1_35 | |
| dc.identifier.uri | http://kops.uni-konstanz.de/handle/123456789/3043 | |
| dc.language.iso | eng | deu |
| dc.legacy.dateIssued | 2010 | deu |
| dc.rights | terms-of-use | deu |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | deu |
| dc.subject.ddc | 004 | deu |
| dc.title | Taxing Subnetworks | eng |
| dc.type | INPROCEEDINGS | deu |
| dspace.entity.type | Publication | |
| kops.citation.bibtex | @inproceedings{Hoefer2008Taxin-3043,
year={2008},
doi={10.1007/978-3-540-92185-1_35},
title={Taxing Subnetworks},
number={5385},
isbn={978-3-540-92184-4},
issn={0302-9743},
publisher={Springer},
address={Berlin},
series={Lecture Notes in Computer Science},
booktitle={Internet and Network Economics},
pages={286--294},
editor={Papadimitriou, Christos and Zhang, Shuzhong},
author={Hoefer, Martin and Olbrich, Lars and Skopalik, Alexander}
} | |
| kops.citation.iso690 | HOEFER, Martin, Lars OLBRICH, Alexander SKOPALIK, 2008. Taxing Subnetworks. In: PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. Internet and Network Economics. Berlin: Springer, 2008, pp. 286-294. Lecture Notes in Computer Science. 5385. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-92184-4. Available under: doi: 10.1007/978-3-540-92185-1_35 | deu |
| kops.citation.iso690 | HOEFER, Martin, Lars OLBRICH, Alexander SKOPALIK, 2008. Taxing Subnetworks. In: PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. Internet and Network Economics. Berlin: Springer, 2008, pp. 286-294. Lecture Notes in Computer Science. 5385. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-92184-4. Available under: doi: 10.1007/978-3-540-92185-1_35 | eng |
| kops.citation.rdf | <rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/3043">
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/3043"/>
<dc:contributor>Skopalik, Alexander</dc:contributor>
<dc:contributor>Olbrich, Lars</dc:contributor>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:creator>Olbrich, Lars</dc:creator>
<dcterms:title>Taxing Subnetworks</dcterms:title>
<dcterms:bibliographicCitation>Publ. in: Internet and network economics : 4th International Workshop, WINE 2008, Shanghai, China, December 17 - 20, 2008; proceedings / Christos Papadimitriou ... (eds.). - Berlin ; Heidelberg [u.a.] : Springer, 2008, pp. 286-294. - (Lecture notes in computer science ; 5385)</dcterms:bibliographicCitation>
<dcterms:issued>2008</dcterms:issued>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:54Z</dcterms:available>
<dc:language>eng</dc:language>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Skopalik, Alexander</dc:creator>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:54Z</dc:date>
<dc:creator>Hoefer, Martin</dc:creator>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
<dc:rights>terms-of-use</dc:rights>
<dc:contributor>Hoefer, Martin</dc:contributor>
</rdf:Description>
</rdf:RDF> | |
| kops.identifier.nbn | urn:nbn:de:bsz:352-opus-118216 | deu |
| kops.opus.id | 11821 | deu |
| kops.sourcefield | PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. <i>Internet and Network Economics</i>. Berlin: Springer, 2008, pp. 286-294. Lecture Notes in Computer Science. 5385. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-92184-4. Available under: doi: 10.1007/978-3-540-92185-1_35 | deu |
| kops.sourcefield.plain | PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. Internet and Network Economics. Berlin: Springer, 2008, pp. 286-294. Lecture Notes in Computer Science. 5385. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-92184-4. Available under: doi: 10.1007/978-3-540-92185-1_35 | deu |
| kops.sourcefield.plain | PAPADIMITRIOU, Christos, ed., Shuzhong ZHANG, ed.. Internet and Network Economics. Berlin: Springer, 2008, pp. 286-294. Lecture Notes in Computer Science. 5385. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-92184-4. Available under: doi: 10.1007/978-3-540-92185-1_35 | eng |
| source.bibliographicInfo.fromPage | 286 | |
| source.bibliographicInfo.seriesNumber | 5385 | |
| source.bibliographicInfo.toPage | 294 | |
| source.contributor.editor | Papadimitriou, Christos | |
| source.contributor.editor | Zhang, Shuzhong | |
| source.identifier.eissn | 1611-3349 | |
| source.identifier.isbn | 978-3-540-92184-4 | |
| source.identifier.issn | 0302-9743 | |
| source.publisher | Springer | |
| source.publisher.location | Berlin | |
| source.relation.ispartofseries | Lecture Notes in Computer Science | |
| source.title | Internet and Network Economics |