Name
Title | ||
|---|---|---|
Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games |
Abstract | ||
|---|---|---|
There has been substantial work developing simple, efficientno-regret algorithms for a wide class of repeated decision-making problems including online routing. These are adaptive strate- gies 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 no- regret 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 (formally, 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 (2). Our nonatomic results also apply to a more general class of games known as congestion games. 1. Introduction. There has been substantial work in learning theory and game theory on adaptive no-regret algorithms for problems of repeated decision-making. These algorithms have the property that in any online, repeated game setting, their average loss per time step approaches that of the best fixed strategy in hindsight (or better) over time. Moreover, the convergence rates are quite good: in Hannan's original algorithm (19), the number of time steps needed to achieve a gap of ² with respect to the best fixed strategy in hindsight—the "per time step regret"—is linear in the size of the game N. This was reduced to O(logN) in more recent exponential- weighting algorithms for this problem (23, 6, 16) (also called the problem of "combining expert advice"). Most recently, a number of algorithms have been developed for achieving such guarantees efficientlyin many settings where the number of choices N is exponential in the natural description-length of the problem (21, 30, 31). One specific setting where these efficient algorithms apply is online routing. Given a graph G = (V,E) and two distinguished nodes vstart and vend, the game for an individual player is defined as follows. At each time step t, the player's algorithm chooses a path Pt from vstart to vend, and simultaneously an adversary (or nature) chooses a set of edge costs {cte}e2E. The edge costs are then revealed and the player pays the cost of its path. Even though the number of possible paths can be exponential in the size of the graph, no-regret algorithms exist (e.g., (21, 31)) that achieve running time and convergence rates (to the cost of the best fixed path in hindsight) which are polynomial in the size of the graph and the maximum edge cost. Moreover, a number of extensions (1, 24) have shown how these algorithms can be applied even to 2A preliminary version of these results appeared in the Proceedings of the 25th Annual ACM |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1146381.1146392 | Symposium on Principles of Distributed Computing |
Keywords | Field | DocType |
network games,multicommodity flow,routing game,approximate equilibrium,behavior converge,nash equilibrium,regret-minimizing algorithm,substantial work,strong guarantee,online routing,no-regret strategy,efficient no-regret algorithm,game theory,convergence rate,load balance,nash equilibria,price of anarchy,learning theory,repeated game | Correlated equilibrium,Mathematical economics,Mathematical optimization,Epsilon-equilibrium,Risk dominance,Computer science,Best response,Algorithm,Repeated game,Equilibrium selection,Nash equilibrium,Folk theorem | Journal |
Volume | Issue | ISBN |
6 | 1 | 1-59593-384-0 |
Citations | PageRank | References |
63 | 6.52 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Avrim Blum | 1 | 7978 | 906.15 |
| Eyal Even-dar | 2 | 948 | 73.71 |
| Katrina Ligett | 3 | 923 | 66.19 |