Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

Nick Arnosti () and Will Ma ()
Additional contact information
Nick Arnosti: Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455
Will Ma: Graduate School of Business, Columbia University, New York, New York 10027

Operations Research, 2023, vol. 71, issue 5, 1777-1788

Abstract: In the prophet secretary problem, n values are drawn independently from known distributions and presented in a uniformly random order. A decision maker must accept or reject each value when it is presented and may accept at most k values in total. The objective is to maximize the expected sum of accepted values. We analyze the performance of static threshold policies , which accept the first k values exceeding a fixed threshold (or all such values, if fewer than k exist). We show that an appropriate threshold guarantees γ k = 1 − e − k k k / k ! times the value of the offline optimal solution. Note that γ 1 = 1 − 1 / e , and by Stirling’s approximation, γ k ≈ 1 − 1 / 2 π k . This represents the best-known guarantee for the prophet secretary problem for all k > 1 and is tight for all k for the class of static threshold policies. We provide two simple methods for setting the threshold. Our first method sets a threshold such that k · γ k values are accepted in expectation, and offers an optimal guarantee for all k . Our second sets a threshold such that the expected number of values exceeding the threshold is equal to k . This approach gives an optimal guarantee if k > 4 but gives suboptimal guarantees for k ≤ 4 . Our proofs use a new result for optimizing sums of independent Bernoulli random variables, which extends a result of Hoeffding from 1956 and could be of independent interest.

Keywords: Market Analytics and Revenue Management; online algorithms; prophet inequalities; prophet secretary problem (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2419 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:5:p:1777-1788

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().