Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 536757.0, MPI für Informatik / Algorithms and Complexity Group
Stackelberg routing in arbitrary networks
Authors:
Language:English
Date of Publication (YYYY-MM-DD):2010
Title of Journal:Mathematics of Operations Research
Volume:35
Issue / Number:2
Start Page:330
End Page:346
Review Status:Peer-review
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
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 single-commodity 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
Largest-Latency-First (LLF) strategy that only depend on the size of the
network. Besides other implications, this rules out the possibility to
construct constant-size 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 easy-to-implement 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 (YYYY-MM-DD):2011-02-10
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-9CA118DFF9513FF6C12577FF006056B0-...
URL:http://dx.doi.org/10.1287/moor.1100.0442
DOI:10.1287/moor.1100.0442v1
ISSN:0364-765X
 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]
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.