摘要：There has been substantial work developing simple, efficientregret-minimizingalgorithms for a wide class of repeated decision-makingproblems including online routing. These are adaptive strategies anindividual can use that give strong guarantees on performanceeven in adversarially-changing environments. There has also beensubstantial work on analyzing properties of Nash equilibria in routinggames. In this paper, we consider the question: if each player in arouting 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 flowand infinitesimal agents, behavior will approach Nash equilibrium(on most days, the cost of the flow will be close to the costof the cheapest paths possible given that flow) at a rate that dependspolynomially on the players' regret bounds and the maximum slope of anylatency function. We also show that Price of Anarchy results may beapplied to these approximate equilibria, and also consider thefinite-size (non-infinitesimal) load-balancing model of Azar (1998).Our nonatomic results also apply to the more general classof congestion games.
关键词：regret minimization; Nash equilibria; routing games
