Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Stackelberg Routing in Arbitrary Networks

Bonifaci, V., Harks, T., & Schäfer, G. (2010). Stackelberg Routing in Arbitrary Networks. Mathematics of Operations Research, 35(2), 330-346. doi:10.1287/moor.1100.0442v1.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Bonifaci2010b.pdf (beliebiger Volltext), 271KB
 
Datei-Permalink:
-
Name:
Bonifaci2010b.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
ATTCYBW3.pdf (beliebiger Volltext), 271KB
 
Datei-Permalink:
-
Name:
ATTCYBW3.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bonifaci, Vincenzo1, Autor           
Harks, Tobias2, Autor
Schäfer, Guido1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 536757
DOI: 10.1287/moor.1100.0442v1
URI: http://dx.doi.org/10.1287/moor.1100.0442
Anderer: Local-ID: C1256428004B93B8-9CA118DFF9513FF6C12577FF006056B0-Bonifaci:2009:a
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Mathematics of Operations Research
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Hanover, USA : INFORMS
Seiten: - Band / Heft: 35 (2) Artikelnummer: - Start- / Endseite: 330 - 346 Identifikator: ISSN: 0364-765X