Campus Event Calendar
Event Entry
What and Who
Routing in a partially selfish network
Vincenzo Bonifaci
Università di Roma "La Sapienza"
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 5 May 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the impact of Stackelberg routing to reduce the price of anarchy in network routing games. In this setting, a constant fraction of the entire demand is routed centrally according to a predefined Stackelberg strategy and the remaining demand is routed selfishly by nonatomic players. We exhibit a family of single-commodity networks for which every Stackelberg strategy has price of anarchy at least proportional to the size of the network, and we exhibit a Stackelberg strategy with price of anarchy bounded by a function of the size of the network. We also give improved bounds on the price of anarchy induced by specific Stackelberg strategies in other cases, such as when the latency functions are polynomials of bounded degree.
This is joint work with Tobias Harks and Guido Schäfer.
Contact
Nicole Megow
--email hidden
passcode not visible
logged in users only
Nicole Megow, 04/26/2009 18:47 -- Created document.