
Prophet Secretary Through Blind Strategies
Correa, José; Saona, Raimundo; Ziliotto, Bruno (2019), Prophet Secretary Through Blind Strategies, in Timothy M. Chan, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, p. 1946-1961. 10.1137/1.9781611975482.118
View/ Open
Type
Communication / ConférenceDate
2019Conference title
Thirtieth Annual ACM-SIAM Symposium on Discrete AlgorithmsConference date
2019-01Conference city
San DiegoConference country
United StatesBook title
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete AlgorithmsBook author
Timothy M. ChanPublisher
Society for Industrial and Applied Mathematics
ISBN
978-1-61197-548-2
Number of pages
IX-2972Pages
1946-1961
Publication identifier
Metadata
Show full item recordAuthor(s)
Correa, JoséSaona, Raimundo
Ziliotto, Bruno
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)
In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Gairing (1977) established that this worst case ratio is a universal constant equal to 1/2. In the last decade prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A very interesting variant is the Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms achieve a constant of 1-1/e and very recently this barrier was slightly improved. This paper analyzes strategies that set a nonincreasing sequence of thresholds to be applied at different times. The gambler stops the first time a sample surpasses the corresponding threshold. Specifically we consider a class of strategies called blind quantile strategies. They consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that they can achieve a constant of 0.665, improving upon the best known result of Azar et al. (2018), and on Beyhaghi et al. (2018) (order selection). Our proof analyzes precisely the underlying stopping time distribution, relying on Schur-convexity theory. We further prove that blind strategies cannot achieve better than 0.675. Finally we prove that no nonadaptive algorithm for the gambler can achieve better than 0.732.Subjects / Keywords
Prophet SecretaryRelated items
Showing items related by title and author.
-
Chatterjee, Krishnendu; Saona, Raimundo; Ziliotto, Bruno (2022) Article accepté pour publication ou publié
-
Chatterjee, Krishnendu; Saona, Raimundo; Ziliotto, Bruno (2022) Article accepté pour publication ou publié
-
Correa, José; Dütting, Paul; Fischer, Felix; Schewior, Kevin; Ziliotto, Bruno (2021) Communication / Conférence
-
Al-Rajhi, Ibrahim; Altman, Yochanan; Metcalfe, Beverly; Roussel, Josse (2006) Article accepté pour publication ou publié
-
Mavrotas, George; Figueira, José; Florios, Kostas (2009) Article accepté pour publication ou publié