Nonadaptive Selfish Routing with Online Demands Export

@incollection{citeulike:2682911, abstract = {We study the efficiency of selfish routing problems in which traffic demands are revealed online. We go beyond the common Nash equilibrium concept in which possibly all players reroute their flow and form a new equilibrium upon arrival of a new demand. In our model, demands arrive in n sequential games. In each game, the new demands form a Nash equilibrium and their routings remain unchanged afterwards. We study the problem both with nonatomic and atomic player types and with continuous and nondecreasing latency functions on the edges. For polynomial latency functions, we give constant upper and lower bounds on the competitive ratio of the resulting online routing in terms of the maximum degree, the number of games and in the atomic setting the number of players. In particular, for nonatomic players and affine latency functions we show that the competitive ratio is at most . Finally, we present improved upper bounds for the special case of two nodes connected by parallel arcs.}, author = {Harks, Tobias and V\'{e}gh, L\'{a}szl\'{o}}, citeulike-article-id = {2682911}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-77294-1_5}, doi = {10.1007/978-3-540-77294-1_5}, journal = {Combinatorial and Algorithmic Aspects of Networking}, keywords = {selfish\_routing}, pages = {27--45}, posted-at = {2008-04-17 17:41:35}, priority = {2}, title = {Nonadaptive Selfish Routing with Online Demands}, url = {http://dx.doi.org/10.1007/978-3-540-77294-1_5}, year = {2007} }

TY - CHAP ID - citeulike:2682911 L3 - citeulike-article-id:2682911 N2 - We study the efficiency of selfish routing problems in which traffic demands are revealed online. We go beyond the common Nash equilibrium concept in which possibly all players reroute their flow and form a new equilibrium upon arrival of a new demand. In our model, demands arrive in n sequential games. In each game, the new demands form a Nash equilibrium and their routings remain unchanged afterwards. We study the problem both with nonatomic and atomic player types and with continuous and nondecreasing latency functions on the edges. For polynomial latency functions, we give constant upper and lower bounds on the competitive ratio of the resulting online routing in terms of the maximum degree, the number of games and in the atomic setting the number of players. In particular, for nonatomic players and affine latency functions we show that the competitive ratio is at most . Finally, we present improved upper bounds for the special case of two nodes connected by parallel arcs. JF - Combinatorial and Algorithmic Aspects of Networking EP - 45 TI - Nonadaptive Selfish Routing with Online Demands SP - 27 KW - selfish_routing AU - Harks, Tobias AU - Végh, László PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-77294-1_5 ER -