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 nonatomic 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 nonatomic and heterogeneous players, we prove that the problem is NPhard even for singlecommodity networks and affine latency functions. We therefore focus on parallelarc networks and give an algorithm for optimally taxing subnetworks with affine latency functions. For weighted atomic players, the problem is NPhard already for parallelarc 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 parallelarc networks and arbitrary (standard) latency functions. Similarly, for unweighted atomic and heterogeneous players, we derive an algorithm for optimally taxing subnetworks for parallelarc 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 = {433444},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4477},
URN = {urn:nbn:de:0030drops44771},
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 