Many online problems are studied in stochastic settings for which inputs are samples from a known distribution, given in advance, or from an unknown distribution. Such distributions model both beyond-worst-case inputs and, when given, partial foreknowledge for the online algorithm. But how robust can such algorithms be to misspecification of the given distribution? When is this detectable, and when does it matter? When can algorithms give good competitive ratios both when the input distribution is as specified, and when it is not? We consider these questions in the setting of optimal stopping, where the cases of known and unknown distributions correspond to the well-known prophet inequality and to the secretary problem, respectively. Here we ask: Can a stopping rule be competitive for the i.i.d. prophet inequality problem and the secretary problem at the same time? We constrain the Pareto frontier of simultaneous approximation ratios $(α, β)$ that a stopping rule can attain. We introduce a family of algorithms that give nontrivial joint guarantees and are optimal for the extremal i.i.d. prophet and secretary problems. We also prove impossibilities, identifying $(α, β)$ unattainable by any adaptive stopping rule. Our results hold for both $n$ fixed arrivals and for arrivals from a Poisson process with rate $n$. We work primarily in the Poisson setting, and provide reductions between the Poisson and $n$-arrival settings that may be of broader interest.

翻译：许多在线问题在随机设定下进行研究，其中输入要么来自预先给定的已知分布，要么来自未知分布。这类分布既可用于建模超越最坏情况的输入，也可在已知时为在线算法提供部分先验信息。但此类算法对给定分布的误设具有多强的鲁棒性？何时可检测到误设？误设何时会产生影响？算法何时能在输入分布符合设定与不符合设定时均保持良好竞争比？我们在最优停止问题框架下探讨这些问题，其中已知分布与未知分布的情形分别对应经典先知不等式与秘书问题。本文核心研究：是否存在一个停止规则能同时适用于独立同分布先知不等式问题与秘书问题？我们约束了停止规则可实现的同步逼近比帕累托前沿$(α, β)$。我们提出一类能提供非平凡联合保证的算法族，该算法在极端独立同分布先知问题与秘书问题上达到最优。同时我们证明了不可能性结果，确定了任何自适应停止规则均无法实现的$(α, β)$对。我们的结论同时适用于固定到达次数$n$的场景与泊松到达过程（速率为$n$）的场景。研究主要在泊松设定下展开，并提供了泊松过程与$n$次到达设定间的归约方法，该方法可能具有更广泛的学术价值。