Prophets, Secretaries, and Maximizing the Probability of Choosing the Best

Hossein Esfandiari, MohammadTaghi Hajiaghayi, Brendan Lucier, Michael Mitzenmacher
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3717-3727, 2020.

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 [\textit{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.58010.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/e1/e, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of 1/e1/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.58010.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 kk 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-esfandiari20a, title = {Prophets, Secretaries, and Maximizing the Probability of Choosing the Best}, author = {Esfandiari, Hossein and Hajiaghayi, MohammadTaghi and Lucier, Brendan and Mitzenmacher, Michael}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3717--3727}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/esfandiari20a/esfandiari20a.pdf}, url = {https://proceedings.mlr.press/v108/esfandiari20a.html}, 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 [\textit{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.58010.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/e1/e, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of 1/e1/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.58010.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 kk 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.} }
Endnote
%0 Conference Paper %T Prophets, Secretaries, and Maximizing the Probability of Choosing the Best %A Hossein Esfandiari %A MohammadTaghi Hajiaghayi %A Brendan Lucier %A Michael Mitzenmacher %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-esfandiari20a %I PMLR %P 3717--3727 %U https://proceedings.mlr.press/v108/esfandiari20a.html %V 108 %X 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 [\textit{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.58010.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/e1/e, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of 1/e1/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.58010.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 kk 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.
APA
Esfandiari, H., Hajiaghayi, M., Lucier, B. & Mitzenmacher, M.. (2020). Prophets, Secretaries, and Maximizing the Probability of Choosing the Best. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3717-3727 Available from https://proceedings.mlr.press/v108/esfandiari20a.html.

Related Material