pdf icon
Volume 6 (2010) Article 8 pp. 179-199
Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
Received: November 10, 2009
Published: September 15, 2010
Download article from ToC site:
[PDF (299K)] [PS (972K)] [Source ZIP]
Keywords: regret minimization, Nash equilibria, routing games
ACM Classification: G.2.2, J.4
AMS Classification: 68T05, 68W40, 91A13, 91A20, 91A43

Abstract: [Plain Text Version]

There has been substantial work developing simple, efficient regret-minimizing algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strategies an individual can use that give strong guarantees on performance even in adversarially-changing environments. There has also been substantial work on analyzing properties of Nash equilibria in routing games. In this paper, we consider the question: if each player in a routing game uses a regret-minimizing strategy, will behavior converge to a Nash equilibrium? In general games the answer to this question is known to be no in a strong sense, but routing games have substantially more structure.

In this paper we show that in the Wardrop setting of multicommodity flow and infinitesimal agents, behavior will approach Nash equilibrium (on most days, the cost of the flow will be close to the cost of the cheapest paths possible given that flow) at a rate that depends polynomially on the players' regret bounds and the maximum slope of any latency function. We also show that Price of Anarchy results may be applied to these approximate equilibria, and also consider the finite-size (non-infinitesimal) load-balancing model of Azar (1998). Our nonatomic results also apply to the more general class of congestion games.