Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem

• 成果类型: Article
• 署名作者: Arnosti, Nick; Ma, Will
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2419
• 发表日期: 2023
• 页码: 1777-1788
• 关键词: selection; inequalities; maximum; ORDER

摘要

In the prophet secretary problem, n values are drawn independently from known distributions and presented in a uniformly random order. A decision maker must accept or reject each value when it is presented and may accept at most k values in total. The objective is to maximize the expected sum of accepted values. We analyze the performance of static threshold policies, which accept the first k values exceeding a fixed threshold (or all such values, if fewer than k exist). We show that an appropriate threshold guarantees gamma k = 1- e-kkk/k! times the value of the offline optimal solution. Note that gamma 1= 1 1/e, and by root ffiffiffiffiffiffififfi Stirling's approximation, gamma k approximate to 1 1/ 2 pi k. This represents the best-known guarantee for the prophet secretary problem for all k > 1 and is tight for all k for the class of static threshold policies. We provide two simple methods for setting the threshold. Our first method sets a threshold such that k center dot gamma k values are accepted in expectation, and offers an optimal guarantee for all k. Our second sets a threshold such that the expected number of values exceeding the threshold is equal to k. This approach gives an optimal guarantee if k > 4 but gives suboptimal guarantees for k < 4. Our proofs use a new result for optimizing sums of independent Bernoulli random variables, which extends a result of Hoeffding from 1956 and could be of independent interest.