## 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, (Formular Presented). 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1777-1788 |

Number of pages | 12 |

Journal | Operations research |

Volume | 71 |

Issue number | 5 |

DOIs | |

State | Published - Sep 1 2023 |

Externally published | Yes |

### Bibliographical note

Publisher Copyright:© 2022 INFORMS.

## Keywords

- online algorithms
- prophet inequalities
- prophet secretary problem