Xujin is visiting us mid-October to mid-November

AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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