|
Thursday, March 31, 2005 |
|
|
|
|
Adaptive Algorithms for Price-Setting and Overlay Routing |
|
|
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. SPEAKER 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. |
|