License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.433
URN: urn:nbn:de:0030-drops-44771
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4477/
Go to the corresponding LIPIcs Volume Portal

Jelinek, Tomas ; Klaas, Marcus ; Schäfer, Guido

Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players

pdf-format:
35.pdf (0.7 MB)

Abstract

The problem of computing optimal network tolls that induce a Nash equilibrium of minimum total cost has been studied intensively in the literature, but mostly under the assumption that these tolls are unrestricted. Here we consider this problem under the more realistic assumption that the tolls have to respect some given upper bound restrictions on the arcs. The problem of taxing subnetworks optimally constitutes an important special case of this problem. We study the restricted network toll problem for both non-atomic and atomic (unweighted and weighted) players; our studies are the first that also incorporate heterogeneous players, i.e., players with different sensitivities to tolls.

For non-atomic and heterogeneous players, we prove that the problem is NP-hard even for single-commodity networks and affine latency functions. We therefore focus on parallel-arc networks and give an algorithm for optimally taxing subnetworks with affine latency functions. For weighted atomic players, the problem is NP-hard already for parallel-arc networks and linear latency functions, even if players are homogeneous. In contrast, for unweighted atomic and homogeneous players, we develop an algorithm to compute optimal restricted tolls for parallel-arc networks and arbitrary (standard) latency functions. Similarly, for unweighted atomic and heterogeneous players, we derive an algorithm for optimally taxing subnetworks for parallel-arc networks and arbitrary (standard) latency functions.

The key to most of our results is to derive (combinatorial) characterizations of flows that are inducible by restricted tolls. These characterizations might be of independent interest.

BibTeX - Entry

@InProceedings{jelinek_et_al:LIPIcs:2014:4477,
  author =	{Tomas Jelinek and Marcus Klaas and Guido Sch{\"a}fer},
  title =	{{Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{433--444},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4477},
  URN =		{urn:nbn:de:0030-drops-44771},
  doi =		{10.4230/LIPIcs.STACS.2014.433},
  annote =	{Keywords: Network routing games, coordination mechanisms, network tolls, taxing subnetworks, heterogeneous players}
}

Keywords: Network routing games, coordination mechanisms, network tolls, taxing subnetworks, heterogeneous players
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI