The secretary problem is probably the purest model of decision making under
uncertainty. In this paper we ask which advice can we give the algorithm to
improve its success probability?
We propose a general model that unifies a broad range of problems: from the
classic secretary problem with no advice, to the variant where the quality of a
secretary is drawn from a known distribution and the algorithm learns each
candidate's quality on arrival, to more modern versions of advice in the form
of samples, to an ML-inspired model where a classifier gives us noisy signal
about whether or not the current secretary is the best on the market.
Our main technique is a factor revealing LP that captures all of the problems
above. We use this LP formulation to gain structural insight into the optimal
policy. Using tools from linear programming, we present a tight analysis of
optimal algorithms for secretaries with samples, optimal algorithms when
secretaries' qualities are drawn from a known distribution, and a new noisy
binary advice model.

该论文讨论求职选择问题的模型 —— 秘书问题及其改进模型，提出一种基于线性规划的技术，探索在不同模型下优化算法的结构。

具备咨询能力的秘书

Secretaries with Advice

We extend the standard online worst-case model to accommodate past experience
which is available to the online player in many practical scenarios. We do this
by revealing a random sample of the adversarial input to the online player
ahead of time. The online player competes with the expected optimal value on
the part of the input that arrives online. Our model bridges between existing
online stochastic models (e.g., items are drawn i.i.d. from a distribution) and
the online worst-case model. We also extend in a similar manner (by revealing a
sample) the online random-order model.
We study the classical secretary problem in our new models. In the worst-case
model we present a simple online algorithm with optimal competitive-ratio for
any sample size. In the random-order model, we also give a simple online
algorithm with an almost tight competitive-ratio for small sample sizes.
Interestingly, we prove that for a large enough sample, no algorithm can be
simultaneously optimal both in the worst-cast and random-order models.

本文研究了在线算法在最坏情况和随机顺序模型中的应用，探讨了秘书问题的解决方法和竞争比的优化。

带样本的竞争分析与秘书问题

Competitive Analysis with a Sample and the Secretary Problem

Optimal stopping theory is a powerful tool for analyzing scenarios such as
online auctions in which we generally require optimizing an objective function
over the space of stopping rules for an allocation process under uncertainty.
Perhaps the most classic problems of stopping theory are the prophet inequality
problem and the secretary problem. The classical prophet inequality states that
by choosing the same threshold OPT/2 for every step, one can achieve the tight
competitive ratio of 0.5. On the other hand, for the basic secretary problem,
the optimal strategy achieves the tight competitive ratio of 1/e.
In this paper, we introduce Prophet Secretary, a natural combination of the
prophet inequality and the secretary problems. An example motivation for our
problem is as follows. Consider a seller that has an item to sell on the market
to a set of arriving customers. The seller knows the types of customers that
may be interested in the item and he has a price distribution for each type:
the price offered by a customer of a type is anticipated to be drawn from the
corresponding distribution. However, the customers arrive in a random order.
Upon the arrival of a customer, the seller makes an irrevocable decision
whether to sell the item at the offered price. We address the question of
finding a strategy for selling the item at a high price.
We show that by using a uniform threshold one cannot break the 0.5 barrier.
However, we show that i) using n distinct non-adaptive thresholds one can
obtain a competitive ratio that goes to (1-1/e) as n grows; and ii) no online
algorithm can achieve a competitive ratio better than 0.75. Our results improve
the (asymptotic) approximation guarantee of single-item sequential posted
pricing mechanisms from 0.5 to (1-1/e) when the order of agents (customers) is
chosen randomly.

本文介绍一种自然结合了 prophet inequality 和 secretary problem 的问题 ——Prophet Secretary，对于一些类似拍卖的场景，研究优化一个不确定情况下的分配过程中停止规则空间内的目标函数。发现使用 $n$ 个独立的非自适应阈值可以得到比 0.5 更高的竞争比率，上限约为 $(1-1/e)$，但无在线算法可以达到更好的竞争比率。当随机选择代理（客户）的顺序时，我们将单个项目的顺序定价机制的渐近近似保证从 0.5 提高到了 $(1-1/e)$。