We investigate the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, an a fraction of the entire demand is first routed centrally according to a predefined 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 + √1 - α. 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 that is simple yet powerful enough to obtain (almost) tight bounds for SCALE in general networks. © 2010 INFORMS.

Bonifaci, V., Harks, T., Schafer, G. (2010). Stackelberg routing in arbitrary networks. MATHEMATICS OF OPERATIONS RESEARCH, 35(2), 330-346 [10.1287/moor.1100.0442].

Stackelberg routing in arbitrary networks

Bonifaci V.;
2010-01-01

Abstract

We investigate the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, an a fraction of the entire demand is first routed centrally according to a predefined 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 + √1 - α. 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 that is simple yet powerful enough to obtain (almost) tight bounds for SCALE in general networks. © 2010 INFORMS.
Bonifaci, V., Harks, T., Schafer, G. (2010). Stackelberg routing in arbitrary networks. MATHEMATICS OF OPERATIONS RESEARCH, 35(2), 330-346 [10.1287/moor.1100.0442].
File in questo prodotto:
File Dimensione Formato  
stackelberg-MOR-final.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 325.26 kB
Formato Adobe PDF
325.26 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/381232
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 24
social impact