2019/10/09 by Hossein Esfandiari, Esfandiari, Hossein, MohammadTaghi Hajiaghayi +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1910.03798
openalex publication_date 2019/10/09 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Suppose a customer is faced with a sequence of fluctuating prices, such as\nfor airfare or a product sold by a large online retailer. Given distributional\ninformation about what price they might face each day, how should they choose\nwhen to purchase in order to maximize the likelihood of getting the best price\nin retrospect? This is related to the classical secretary problem, but with\nvalues drawn from known distributions. In their pioneering work, Gilbert and\nMosteller [\J. Amer. Statist. Assoc. 1966] showed that when the values\nare drawn i.i.d., there is a thresholding algorithm that selects the best value\nwith probability approximately 0.5801. However, the more general problem with\nnon-identical distributions has remained unsolved.\n In this paper we provide an algorithm for the case of non-identical\ndistributions that selects the maximum element with probability 1/e, and we\nshow that this is tight. We further show that if the observations arrive in a\nrandom order, this barrier of 1/e can be broken using a static threshold\nalgorithm, and we show that our success probability is the best possible for\nany single-threshold algorithm under random observation order. Moreover, we\nprove that one can achieve a strictly better success probability using more\ngeneral multi-threshold algorithms, unlike the non-random-order case. Along the\nway, we show that the best achievable success probability for the random-order\ncase matches that of the i.i.d. case, which is approximately 0.5801, under a\n"no-superstars" condition that no single distribution is very likely ex ante to\ngenerate the maximum value. We also extend our results to the problem of\nselecting one of the k best values.\n