Theory of Computing
-------------------
Title     : Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games
Authors   : Avrim Blum, Eyal Even-Dar, and Katrina Ligett
Volume    : 6
Number    : 8
Pages     : 179-199
URL       : https://theoryofcomputing.org/articles/v006a008

Abstract
--------

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.