Friday, January 26, 2007
11:00 AM
CSB 209
Avrim Blum
Online Decision-Making, Routing Games, and Convergence to Equilibria
Imagine that each day you need to choose a route to drive to work without knowing what the traffic patterns will be like that day. Can you come up with a strategy so that in the long run, your performance approaches or exceeds that of the best route in hindsight? There has been substantial work in learning theory and game theory on adaptive "no-regret" algorithms for repeated decision-making problems of this form. Recently, several algorithms have been shown to achieve these guarantees efficiently even in settings such as online routing where the set of decisions (e.g., the set of all possible paths) if listed explicitly could be exponential in the natural parameters of the problem.

In this talk I will discuss new (and old) work on such no-regret algorithms, as well as algorithms with even stronger guarantees. I will also talk about recent work on game-theoretic properties of such algorithms in the context of routing. In particular, if delays on each edge are caused by congestion due to other agents in the system, and everyone is adapting their behavior to minimize their own regret, what can we say about the overall behavior of the system?