Thursday, March 31, 2005 



Adaptive Algorithms for PriceSetting and Overlay Routing 

Problems of sequential decisionmaking under partial information commonly arise in the design of algorithms for networked systems and the applications they support. In such tasks, a decisionmaker 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 "multiarmed 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 ecommerce, respectively. These two problems are unified by the underlying decisionmaking 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 timevarying 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 multiarmed 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 oneparameter 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 endtoend feedback, and the first nearly tight characterization of the value of knowing the demand curve in online postedprice mechanisms. Parts of this talk represent joint work with Baruch Awerbuch and with Tom Leighton. SPEAKER BIO: Robert Kleinberg is a fifthyear 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. 