TIME: 1:30-2:20 pm, May 22, 2007 PLACE: CSE 403 SPEAKER: Adam Taumann Kalai Microsoft Research and Georgia Tech TITLE: Playing Games with Approximation Algorithms ABSTRACT: In the 1950's, Hannan gave an algorithm for playing repeated games with appealing "no regret" properties. His algorithm and more recent variants (like the weighted-majority algorithm) have also been used as a strategy for repeated decision-making in the face of uncertainty. Recent research in computer science has focused on efficient "no regret" algorithms for playing large repeated games (or repeated combinatorial optimization for large sequential decision-making problems). An example is a player, each day, deciding on a route from home to work on a graph with unknown (and changing) edge delays. The feedback each day is the total time on the chosen path. For decision-making problems that are NP-hard (like TSP), we consider approximation algorithms. In this talk, we describe the above work and our new extension to the case of approximation algorithms. We give a general conversion procedure from an efficient approximation algorithm for a problem to an efficient algorithm for repeated decision-making that has the (appropriately generalized) "no regret" property. In the previous example, any approximation algorithm for TSP would yield an algorithm for repeatedly deciding on a route to visit all nodes in a graph in the face of unknown and changing edge delays. This is joint work with Sham Kakade and Katrina Ligett.