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 $\gamma_k = 1 - e^{-k}k^k/k!$ times the value of the offline optimal solution. Note that $\gamma_1 = 1-1/e$, and by Stirling's approximation $\gamma_k \approx 1-1/\sqrt{2 \pi 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 \cdot \gamma_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 $k \le 4$. 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.

翻译：在预言秘书问题中, 美元值独立于已知的发行量之外, 以单一随机顺序显示 。 决策者必须接受或拒绝每个值, 且在显示时必须接受或拒绝每个值, 并且可以接受最多以美元计的数值。 目标是最大限度地实现所接受值的预期总和。 我们分析静态阈值政策的表现, 接受第一个K美元值超过固定阈值( 或所有这类值, 如果存在低于k美元的话 ) 。 我们显示适当的阈值保证 $gamma_ k = 1 - k} kk/k! 。 当显示显示每个值值是离线最佳解决方案值的倍数的倍。 注意 $gamma_ 1 = 1-1/ e$ 。 并且通过 Stirling 接近 $glight 的值 $glorg 值, 我们最起码的保证 4xxx