| Title | : | Optimal Stopping: Prophet Problems and Posted Prices |
| Speaker | : | Ashish Chiplunkar (EPFL, Switzerland) |
| Details | : | Fri, 1 Mar, 2019 11:00 AM @ A M Turing Hall |
| Abstract: | : | Online problems involve computations where the input is received over time in pieces, and we need to take irrevocable decisions in response to every piece of input. Such problems are ubiquitous, and often the knowledge of the distribution of their input through statistical data enables a formulation that models real-world more accurately. In this talk, I will focus on two closely related stochastic online problems: the prophet problem and the prophet secretary problem. The prophet problem is one of the central problems in optimal stopping theory. This problem and its related problems model the task of selling items to an online sequence of buyers. In the prophet problem, we are given the distributions of a sequence of independent random variables. We are then presented the realizations of the random variables in an online manner, and we must select one of them as soon as it is presented. When the sequence of random variables is adversarial, a celebrated result called the prophet inequality states that an algorithm can get, in expectation, at least half the expected maximum of the random variables. In the prophet secretary problem, the arrival sequence is uniformly random (but the distributions are adversarial). I will present an algorithm for prophet secretary which, in expectation, obtains at least (1-1/e+1/400) times the expected maximum. This improves the previously known (1-1/e) factor, which was believed to be optimal for natural reasons. This is joint work with Yossi Azar and Haim Kaplan. I will conclude the talk with a discussion on other closely related problems and my future research plans. |
