Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Bonifaci, Vincenzo
Harks, Tobias
Schäfer, Guido
dblp
dblp
dblp
Not MPG Author(s):

Harks, Tobias
Schäfer, Guido

BibTeX cite key*:

Bonifaci:2009:a

Title

Title*:

Stackelberg Routing in Arbitrary Networks


Bonifaci2010b.pdf (270.74 KB); ATTCYBW3.pdf (270.74 KB)

Journal

Journal Title*:

Mathematics of Operations Research
Journal's URL:

http://mor.journal.informs.org/

Download URL
for the article:

http://dx.doi.org/10.1287/moor.1100.0442
Language:

English

Publisher

Publisher's
Name:

INFORMS
Publisher's URL:

http://www.informs.org/

Publisher's
Address:

Hanover, USA
ISSN:

0364-765X

Vol, No, pp, Date

Volume*:

35
Number:

2

Publishing Date:

May 2010

Pages*:

330 - 346
Number of
VG Pages:


Page Start:

330
Page End:

346

Sequence Number:


DOI:

10.1287/moor.1100.0442v1

Note, Abstract, ©

Note:


(LaTeX) Abstract:

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 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.

URL for the Abstract:


Categories,
Keywords:

Network Routing Games, Stackelberg Routing, Inefficiency of Equilibria

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Bonifaci:2009:a,
AUTHOR = {Bonifaci, Vincenzo and Harks, Tobias and Sch{\"a}fer, Guido},
 TITLE = {Stackelberg Routing in Arbitrary Networks},
 JOURNAL = {Mathematics of Operations Research},
 PUBLISHER = {INFORMS},
 YEAR = {2010},
 NUMBER = {2},
 VOLUME = {35},
 PAGES = {330 -- 346},
 ADDRESS = {Hanover, USA},
 MONTH = {May},
 ISBN = {0364-765X},
 DOI = {10.1287/moor.1100.0442v1},
}

Entry last modified by Vincenzo Bonifaci, 01/02/2012
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
12/20/2010 06:32:16 PM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Vincenzo Bonifaci
Vincenzo Bonifaci
Vincenzo Bonifaci
Vincenzo Bonifaci
Vincenzo Bonifaci		Edit Dates
01/02/2012 06:50:33 PM
02/10/2011 05:04:55 PM
02/10/2011 05:03:39 PM
02/10/2011 05:02:15 PM
02/10/2011 05:01:31 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:

File Attachment Icon
Bonifaci2010b.pdf		File Attachment Icon
ATTCYBW3.pdf