Friday, January 19, 2007
2:00 PM
CSB 209
Robert Kleinberg
Online Markets and Optimal Stopping
The growth of online retail and advertising markets into a multi-billion dollar industry has been accompanied by an explosion of research activity studying the issues which arise from the interaction of computational and incentive constraints in these markets. This talk with focus on the theory of markets in which users arrive and depart over time, and the interplay between these problems and optimal stopping theory, a branch of probability which addresses rules for deciding when to perform given actions while observing a random sequence. (The famous "secretary problem" is one example of such a problem.) On one hand, optimal stopping theory provides a toolkit of techniques for designing approximately-optimal online market mechanisms. On the other hand, the study of online markets motivates us to formulate (and, sometimes, solve) novel questions in optimal stopping theory, including generalizations of the secretary problem.