Prophet Secretary
Prophet Secretary
复制标题
DOI：
10.1007/978-3-662-48350-3_42
复制
发表时间：
2015-07
期刊：
影响因子：
--
通讯作者：
H. Esfandiari;M. Hajiaghayi;Vahid Liaghat;M. Monemizadeh
中科院分区：
文献类型：
--
作者：
H. Esfandiari;M. Hajiaghayi;Vahid Liaghat;M. Monemizadeh
最优停止理论是分析在线拍卖等场景的有力工具，在这样的场景中，我们通常需要在不确定情况下的分配过程的停止规则空间上优化目标函数。也许停止理论最经典的问题是先知不平等问题和秘书问题。经典的先知不等式指出，通过为每一步选择相同的阈值opt/2，可以获得的紧密竞争比。另一方面，对于基本的秘书问题，最优策略达到了紧竞争比。在本文中，我们引入了预言者秘书，它是预言者不等式和秘书问题的自然结合。在先知秘书问题中，我们得到了一组(不一定相同的)分布。从每个分布中抽取一个数字，然后，在应用随机排列之后，这些数字以在线方式给我们，即在步骤中被揭示。我们只能选择一个号码，只有在收到该号码后才能这样做。与预先知道绘制的值的最佳离线解决方案的期望相比，目标是最大化对所选值的期望。特别地，我们证明了通过使用单一的统一阈值，我们不能打破先知秘书问题的先知不等式的0.5障碍。然而，我们表明，使用不同的非自适应阈值可以获得随增长的竞争比，并且没有任何在线算法可以获得好于0.75的竞争比。我们的结果将单项序贯发布定价机制的(渐近)近似保证从0.5提高到了随机选择代理人(客户)订单时的(渐近)保证。我们还考虑了停止理论问题的最小化变体，特别是先知秘书问题。有趣的是，我们证明了，即使对于输入元素取自相同且独立的分布的简单情况，对于先知秘书问题的最小化变量，也不存在恒定的竞争在线算法。我们把这个困难的结果推广到预言者不等式和秘书问题的最小化变体上。
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. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio ofIn this paper, we introduceprophet secretary, a natural combination of the prophet inequality and the secretary problems. In the prophet secretary problem we are given a setof (not necessarily identical) distributions. A numberis drawn from each distributionand then, after applying a random permutation, the numbers are given to us in an online fashion, i.e., at step,is revealed. We are allowed to choose only one number, which can be done only upon receiving that number. The goal is to maximize the expectation of the chosen value, compared to the expectation of the optimum offline solution that knows the drawn values in advance. In particular, we show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show thatusingdistinct nonadaptive thresholds one can obtain a competitive ratio that goes toasgrows, andno 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 towhen the order of agents (customers) is chosen randomly. We also consider the minimization variants of stopping theory problems and, in particular, the prophet secretary problem. Interestingly, we show that, even for the simple case in which the input elements are drawn from identical and independent distributions, there is no constant competitive online algorithm for the minimization variant of the prophet secretary problems. We extend this hardness result to the minimization variants of both the prophet inequality and the secretary problem as well.