Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

DOI10.1287/OPRE.2022.2419MaRDI QIDQ6195077zbMATH OpenOpenAlexFDO

Authors N. Arnosti, Will Ma

Publication date 12 March 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.12893

zbMATH Keywords

online algorithmsprophet inequalitiesprophet secretary problem

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

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 $gamm{a}_k=1-e^{-k}{k}^k/k!$ times the value of the offline optimal solution. Note that $gamm{a}_1=1-1/e$, and by Stirling's approximation $gamm{a}_{k}approx1-1/sqrt2pik$. 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 $kcdotgamm{a}_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 sub-optimal guarantees for $kle4$. Our proofs use a new result for optimizing sums of independent Bernoulli random variables, which extends a classical result of Hoeffding (1956) and is likely to be of independent interest. Finally, we note that our methods for setting thresholds can be implemented under limited information about agents' values.

Recommendations

• Prophet secretary
• Prophet secretary through blind strategies
• Prophet secretary
• Prophet secretary through blind strategies
• Beating \(1-\frac{1}{e}\) for ordered prophets

Cited in

(2)

• The average-value allocation problem
• Non-adaptive matroid prophet inequalities

This page was built for publication: Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195077)