@misc{Harks, author = {Harks, Tobias}, title = {Nash Equilibria in Online Sequential Routing Games}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9376}, number = {06-43}, abstract = {In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game \$i\$, future games \$i+1,\dots,n\$ are not known, and, once players of game \$i\$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm \$\sl {SeqNash}\$ consisting of the sequence of Nash equilibria is \$\frac{4n}{2+n}\$-competitive for affine linear latency functions. For \$n=1\$, this result contains the bound on the price of anarchy of \$\frac{4}{3}\$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of \$\frac{4n}{2+n}\$ on the competitive ratio of \$\sl {SeqNash}\$. We further prove a lower bound of \$\frac{3n-2}{n}\$ of \$\sl {SeqNash}\$ showing that for \$n=2\$ our upper bound is tight.}, language = {en} }