Please use this identifier to cite or link to this item:
For citation please use:
Main Title: The Impact of Stackelberg Routing in General Networks
Author(s): Bonifaci, Vincenzo
Harks, Tobias
Schäfer, Guido
Type: Research Paper
Abstract: We investigate the impact of Stackelberg routing in network routing games. In this setting, a fraction alpha of the entire demand is first routed by a central authority, called the Stackelberg leader, while the remaining demand is then routed by selfish (nonatomic) players. The aim is to devise Stackelberg strategies, i.e., strategies to route the centrally controlled demand, so as to minimize the price of anarchy of the resulting flow. Although several advances have been made recently in proving that Stackelberg routing may in fact significantly reduce the price of anarchy for certain network topologies, it is still an open question whether this holds true in general. We answer this question negatively. We prove that the price of anarchy achievable via Stackelberg routing can be unbounded even for single-commodity networks. 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-alpha)^1/2. Thus, we obtain a smooth trade-off curve that scales between the absence of centralized control (doubling the demands is sufficient) and completely centralized control (no scaling is necessary). Finally, we analyze the effectiveness of a simple Stackelberg strategy, called SCALE, for polynomial latency functions. Our analysis is based on a general technique which is simple, yet powerful enough to obtain (almost) tight bounds for SCALE in general networks. For linear latency functions, we derive an upper bound that matches the current best one and show that this bound is tight. For general polynomial latency functions, we obtain upper bounds that improve all previously known ones.
Subject(s): game theory
selfish routing
Stackelberg game
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 20
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 127.24 kB
DownloadShow Preview
Format: Unknown | Size: 95.81 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.