ID:
536757.0,
MPI für Informatik / Algorithms and Complexity Group 
Stackelberg routing in arbitrary networks 
Authors:  Bonifaci, Vincenzo; Harks, Tobias; Schäfer, Guido 
Language:  English 
Date of Publication (YYYYMMDD):  2010 
Title of Journal:  Mathematics of Operations Research 
Volume:  35 
Issue / Number:  2 
Start Page:  330 
End Page:  346 
Review Status:  Peerreview 
Audience:  Experts Only 
Intended Educational Use:  No 
Abstract / Description:  We investigate the impact of \emph{Stackelberg routing} to reduce the price of anarchy in network routing games. In this setting, an $\alpha$ fraction of the entire demand is first routed centrally according to a predefined \emph{Stackelberg strategy} and the remaining demand is then routed selfishly by (nonatomic) players. Although several advances have been made recently in proving that Stackelberg routing can in fact significantly reduce the price of anarchy for certain network topologies, the central question of whether this holds true in general is still open. We answer this question negatively by constructing a family of singlecommodity instances such that every Stackelberg strategy induces a price of anarchy that grows linearly with the size of the network. Moreover, we prove upper bounds on the price of anarchy of the LargestLatencyFirst (LLF) strategy that only depend on the size of the network. Besides other implications, this rules out the possibility to construct constantsize networks to prove an unbounded price of anarchy. In light of this negative result, we consider bicriteria bounds. We develop an efficiently computable Stackelberg strategy that induces a flow whose cost is at most the cost of an optimal flow with respect to demands scaled by a factor of $1 + \sqrt{1\alpha}$. Finally, we analyze the effectiveness of an easytoimplement Stackelberg strategy, called SCALE. We prove bounds for a general class of latency functions that includes polynomial latency functions as a special case. Our analysis is based on an approach which is simple, yet powerful enough to obtain (almost) tight bounds for SCALE in general networks. 
Last Change of the Resource (YYYYMMDD):  20110210 
External Publication Status:  published 
Document Type:  Article 
Communicated by:  Kurt Mehlhorn 
Affiliations:  MPI für Informatik/Algorithms and Complexity Group

Identifiers:  LOCALID:C1256428004B93B89CA118DFF9513FF6C12577FF006056B0... URL:http://dx.doi.org/10.1287/moor.1100.0442 DOI:10.1287/moor.1100.0442v1 ISSN:0364765X 
Full Text: 
You have privileges to view the following file(s): 
Bonifaci2010b.pdf [270,00 Kb] [Comment:file from upload service] 


ATTCYBW3.pdf [270,00 Kb] [Comment:file from upload service] 


