1 Search Results for "Klaas, Marcus"

Document

DOI: 10.4230/LIPIcs.STACS.2014.433

Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players

Authors: Tomas Jelinek, Marcus Klaas, and Guido Schäfer

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

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.

Cite as

Tomas Jelinek, Marcus Klaas, and Guido Schäfer. Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 433-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jelinek_et_al:LIPIcs.STACS.2014.433,
  author =	{Jelinek, Tomas and Klaas, Marcus and Sch\"{a}fer, Guido},
  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 =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.433},
  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}
}

Refine by Author
1 Jelinek, Tomas
1 Klaas, Marcus
1 Schäfer, Guido

Refine by Classification

Refine by Keyword
1 Network routing games
1 coordination mechanisms
1 heterogeneous players
1 network tolls
1 taxing subnetworks

Refine by Type
1 document

Refine by Publication Year
1 2014

1 Search Results for "Klaas, Marcus"

Computing Optimal Tolls with Arc Restrictions and Heterogeneous Players

Abstract

Cite as

Thanks for your feedback!

Could not send message