Nash Equilibria in Online Sequential Routing Games
Please always quote using this URN: urn:nbn:de:0297-zib-9376
- 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.
Author: | Tobias Harks |
---|---|
Document Type: | ZIB-Report |
Tag: | Congestion Game; Nash equilibria; Online Optimization |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES | |
Date of first Publication: | 2006/10/10 |
Series (Serial Number): | ZIB-Report (06-43) |
ZIB-Reportnumber: | 06-43 |
Published in: | Appeared as: Tobias Harks and Laslo Vegh: Nonadaptive Selfish Routing with Online Demands in: CAAN 2007, Combinatorial and Algorithmic Aspects of Networking Workshop, Halifax, Canada, 2007. Jeannette C. M. Janssen and Pawel Pralat (eds.) LNCS, 4852. Springer 2007, pp. 27-45 |