Campus Event Calendar

Event Entry

New for: D3

What and Who

Stability vs. Optimality in Atomic Selfish Routing for Egalitarian Objective

Xujin Chen
Chinese Academy of Science
AG1 Mittagsseminar (own work)

Xujin is visiting us mid-October to mid-November
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI  
AG Audience

Date, Time and Location

Friday, 22 October 2010
30 Minutes
E1 4


Selfish routing models network routing from a game-theoretic perspective, in which the network users are viewed as self-interested players participating in a non-cooperative game. Each player, with his own pair of source and destination in the network, wishes to establish a communication path (between the source and the destination) along which he experiences delay or load as low as possible, given the link congestion caused by the rest of the players. In quantifying achievable outcomes of the selfish routing, the price of stability/anarchy indicates the ratio between the best/worst possible Nash equilibrium and the globally optimal solution, while the notion of approximate Nash equilibria allows tradeoffs between stability and efficiency.

This talk discusses asymmetric selfish routing in bottleneck congestion games, with a focus on atomic selfish routing in ring networks (selfish ring routing). With respect to minimizing the maximum latency, the selfish ring routing with multiple players is shown to have a price of stability at most 3.9 for linear latency, and at most 3.5 for homogenous linear latency, which is in contrast to the unbounded price of stability in general networks. Performance guarantee and fast implementation are presented for pseudo-polynomial algorithms to compute (approximate) Nash equilibria in the selfish ring routing with linear latency. With respect to minimizing the maximum link-load, the network performance in selfish ring routing is shown to benefit significantly from coordination of self-interested players within small coalitions: the price of anarchy reduces from n-1 for ordinary Nash equilibrium to 2 for 3-strong equilibrium. (Joint work with Bo Chen, Jie Hu, Xiaodong Hu, and Weidong Ma)


Benjamin Doerr
--email hidden
passcode not visible
logged in users only

Benjamin Doerr, 10/03/2010 14:58 -- Created document.