[Colloq] Hiring Talk - Tuesday, March 15, Robert Kleinberg- MIT

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Robert Kleinberg
MIT

Who will speak on:
Adaptive Algorithms for Price-setting and Overlay Routing

Tuesday, March 15, 2005
11:00am
366 West Village H
Northeastern University

Abstract:
Problems of sequential decision-making under partial information 
commonly arise in the design of algorithms for networked systems and the 
applications they support.  In such tasks, a decision-maker must 
repeatedly choose from a set of alternatives, given only partial 
knowledge of the past costs or benefits of these alternatives and no 
knowledge of the future.  Classically, such problems have been modeled 
as "multi-armed bandit problems," and they have been extensively studied 
and applied in a broad range of contexts including machine learning 
theory, economics, game theory, and the design of experiments.

We consider two such problems, motivated by applications to routing in 
overlay networks and pricing in e-commerce, respectively. These two 
problems are unified by the underlying decision-making model, and each 
requires the development of new techniques within this framework. The 
first problem involves choosing a series of routes between two nodes in 
a network with time-varying edge delays, so as to minimize the average 
delay.  The second involves adaptively pricing a commodity through a 
sequence of transactions with different buyers.  A major limitation of 
existing approaches based on the multi-armed bandit problem is their 
dependence on the number of available alternatives, which renders them 
inefficient if this number is exponential (e.g. the number of routing 
paths between two nodes in a network) or infinite (e.g. a one-parameter 
interval of prices).  In this talk we introduce new algorithms and lower 
bound techniques which overcome this limitation, using ideas from linear 
algebra, probability, and statistics.  This leads to the first provably 
efficient algorithm for adaptive routing with end-to-end feedback, and 
the first nearly tight characterization of the value of knowing the 
demand curve in online posted-price mechanisms.

Parts of this talk represent joint work with Baruch Awerbuch and with 
Tom Leighton.

BIO: Robert Kleinberg is a fifth-year Ph.D. student in the Computer 
Science and Artificial Intelligence Laboratory at M.I.T., working under 
the advisorship of Tom Leighton.  He is a recipient of the Fannie and 
John Hertz Foundation Fellowship.  His research interests include 
economic aspects of algorithms, online learning and its applications, 
and optimization problems in network routing.  From 1999 to 2002, he 
worked for Akamai Technologies, developing technologies for Internet 
mapping and streaming media content delivery.

HOST: Rajmohan Rajaraman