论文标题
秘书有建议
Secretaries with Advice
论文作者
论文摘要
秘书问题可能是不确定性下决策的最纯粹模型。在本文中，我们询问我们可以提供哪些建议来提高其成功概率？ 我们提出了一个统一各种问题的通用模型：从没有建议的经典秘书问题到秘书的质量，从已知分布中得出秘书的质量，并且该算法在到达时学习了每个候选人的质量，再到以样本的形式出现的咨询形式，到当前的nois nosifier of Signal of Signal of An Noissy In Noissy In Noissy In Noissy是noisy的秘密。 我们的主要技术是揭示LP的因素，该因素捕获了上述所有问题。我们使用该LP公式来获得对最佳政策的结构洞察力。使用线性编程中的工具，我们对带有样本的秘书的最佳算法进行了严格的分析，当秘书的质量从已知分布中汲取时，以及新的嘈杂的二进制建议模型时，最佳算法。
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.
