TIME: 1:30-2:20 pm,  May 22, 2007


SPEAKER: Adam Taumann Kalai
         Microsoft Research and Georgia Tech

TITLE:  Playing Games with Approximation Algorithms

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.