Prophets, Secretaries, and Maximizing the Probability of Choosing the Best
Abstract
Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what price they might face each day, how should they choose when to purchase in order to maximize the likelihood of getting the best price in retrospect? This is related to the classical secretary problem, but with values drawn from known distributions. In their pioneering work, Gilbert and Mosteller [J. Amer. Statist. Assoc. 1966] showed that when the values are drawn i.i.d., there is a thresholding algorithm that selects the best value with probability approximately 0.5801. However, the more general problem with non-identical distributions has remained unsolved.
In this paper, we provide an algorithm for the case of non-identical distributions that selects the maximum element with probability 1/e, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of 1/e can be broken using a static threshold algorithm, and we show that our success probability is the best possible for any single-threshold algorithm under random observation order. Moreover, we prove that one can achieve a strictly better success probability using more general multi-threshold algorithms, unlike the non-random-order case. Along the way, we show that the best achievable success probability for the random-order case matches that of the i.i.d. case, which is approximately 0.5801, under a ``no-superstars'' condition that no single distribution is very likely ex ante to generate the maximum value. We also extend our results to the problem of selecting one of the k best values.
One of the main tools in our analysis is a suitable ``Poissonization'' of random order distributions, which uses Le Cam's theorem to connect the Poisson binomial distribution with the discrete Poisson distribution. This approach may be of independent interest.
In this paper, we provide an algorithm for the case of non-identical distributions that selects the maximum element with probability 1/e, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of 1/e can be broken using a static threshold algorithm, and we show that our success probability is the best possible for any single-threshold algorithm under random observation order. Moreover, we prove that one can achieve a strictly better success probability using more general multi-threshold algorithms, unlike the non-random-order case. Along the way, we show that the best achievable success probability for the random-order case matches that of the i.i.d. case, which is approximately 0.5801, under a ``no-superstars'' condition that no single distribution is very likely ex ante to generate the maximum value. We also extend our results to the problem of selecting one of the k best values.
One of the main tools in our analysis is a suitable ``Poissonization'' of random order distributions, which uses Le Cam's theorem to connect the Poisson binomial distribution with the discrete Poisson distribution. This approach may be of independent interest.
Research Areas
