Computer Science/Discrete Mathematics Seminar I

There has been substantial work in learning theory and game theory on adaptive "no-regret" algorithms for problems of repeated decision-making. For example, one could use such an algorithm to choose a path to drive to work each day so that no matter what the sequence of traffic patterns (and even given only feedback for the route actually taken on any given day) the average time spent per day approaches that of the best fixed route in hindsight. Recently, several (simple) efficient algorithms have been shown to have this property in a wide variety of settings, including 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, and then turn to the question: suppose we are in the setting of routing, and delays on each edge are actually caused by congestion due to other players in the system (as in the work of Roughgarden-Tardos). If each is using a no-regret algorithm, under what conditions can we expect overall behavior to quickly approach an approximate Nash equilibrium? Various portions of this talk are joint work with Eyal Even-Dar, Katrina Ligett, Yishay Mansour, and Brendan McMahan.