Timezone: »
Spotlight
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
Aranyak Mehta · Uri Nadav · Alexandros Psomas · Aviad Rubinstein
Tue Dec 08 07:10 AM  07:20 AM (PST) @ Orals & Spotlights: Learning Theory
We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or secondhighest 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 secondhighest 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 scorebased 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}.
Author Information
Aranyak Mehta (Google Research)
Uri Nadav (Google)
Alexandros Psomas (Purdue University)
Aviad Rubinstein (Stanford)
Related Events (a corresponding poster, oral, or spotlight)

2020 Poster: Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics »
Tue. Dec 8th 05:00  07:00 PM Room Poster Session 1 #521
More from the Same Authors

2022 Poster: Fair and Efficient Allocations Without Obvious Manipulations »
Alexandros Psomas · Paritosh Verma 
2022 Poster: On Infinite Separations Between Simple and Optimal Mechanisms »
Alexandros Psomas · Ariel Schvartzman Cohenca · S. Weinberg 
2022 Poster: Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions »
Gagan Aggarwal · Kshipra Bhawalkar · Aranyak Mehta · Divyarthi Mohan · Alexandros Psomas 
2022 Poster: Dynamic Fair Division with Partial Information »
Gerdus Benade · Daniel Halpern · Alexandros Psomas 
2021 Poster: Cardinality constrained submodular maximization for random streams »
Paul Liu · Aviad Rubinstein · Jan Vondrak · Junyao Zhao 
2020 Poster: Explainable Voting »
Dominik Peters · Ariel Procaccia · Alexandros Psomas · Zixin Zhou