Secretaries with Advice
Secretaries with Advice
复制标题
DOI：
10.1145/3465456.3467623
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Paul Dütting;Silvio Lattanzi;R. Leme;Sergei Vassilvitskii
中科院分区：
文献类型：
--
作者：
Paul Dütting;Silvio Lattanzi;R. Leme;Sergei Vassilvitskii
秘书问题可能是不确定性下最纯粹的决策模型。在本文中，我们问哪些意见，我们可以给算法，以提高其成功概率？我们提出了一个统一了广泛问题的通用模型：从没有建议的经典秘书问题，到秘书的质量来自已知分布并且算法在到达时学习每个候选人的质量的变体，到以样本形式的更现代版本的建议，到ML启发的模型，其中分类器为我们提供关于当前秘书是否是市场上最好的噪声信号。我们的主要技术是揭示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.