On Decision-Making Without Regret, Routing Games, and Convergence to Equilibria
Speaker: Avrim Blum , Carnegie Mellon University
Date: March 14 2006
Time: 4:15PM to 5:15PM
Location: 32-155 (refreshments in RSA G5 Lounge)
Host: Silvio Micali, Massachusetts Institute of Technology
Contact: Kevin Matulef, 3-5883, matulef@mit.edu
Relevant URL: http://theory.csail.mit.edu/toc-seminars/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 is not much worse than the best route in hindsight? Suppose you also want that on snowy days, your performance was comparable to the best route for snowy days, and likewise this was true for Fridays and for days with road construction (subsets of days that may overlap).
In this talk I will describe new and old work on such regret-minimizing algorithms for general problems of repeated decision-making, as well as connections of these to various game-theoretic equilibria. In addition to general results, I will also discuss recent work on the case of routing where delays on each edge are actually caused by congestion due to other players in the system (as in the work of Roughgarden-Tardos). Here, one can show that no-regret algorithms will in fact produce flows at approximate Nash equilibrium, further motivating price-of-anarchy results.
Portions of this talk are based on joint work with Eyal Even-Dar, Katrina Ligett, Yishay Mansour, and Brendan McMahan.
See other events that are part of Theory Colloquium Spring 2006
See other events happening in March 2006
