Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
复制标题
DOI：
--
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Aranyak Mehta;Alexandros Psomas
中科院分区：
文献类型：
--
作者：
Aranyak Mehta;Alexandros Psomas
我们考虑了从$n$随机变量中选择$k$以使期望的最大值或次最大值最大化的基本问题。这个问题抓住了几个应用，在这些应用中，我们对候选者的质量(例如拍卖出价、搜索结果)存在不确定性，并且由于外部约束，我们只能探索一小部分。例如，考虑第二次价格拍卖，其中系统约束(例如，昂贵的检索或模型计算)仅允许$n$投标者中的$k$参与，并且目标是优化预期效率(最高出价)或预期收益(第二高出价)。我们研究的情况是，我们得到了每个随机变量的明确描述。我们给出了极大化最大期望值问题的PTAS。对于第二个最大值，我们证明了一个困难的结果：假设种植集团假设，不存在运行在多项式时间内的恒因子近似算法。令人惊讶的是，在每个随机变量都有单调风险率(MHR)的假设下，一种简单的基于分数的算法，即选择具有最大$1/\Sqrt{k}$顶部分位数值的$k$随机变量，是预期最高值和次高值\emph{同时}的常量逼近。
We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e.g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e.g., costly retrieval or model computation) allow the participation of only $k$ out of $n$ bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid). We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the $k$ random variables with the largest $1/\sqrt{k}$ top quantile value, is a constant approximation to the expected highest and second highest value, \emph{simultaneously}.