Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics

Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein

Overview

When constrained to pick only $k$ candidates out of a pool of $n$—such as selecting bidders in an auction or displaying results in a search engine—how do you ensure the best possible outcome? This paper tackles the fundamental problem of maximizing expected order statistics. It provides a near-optimal algorithm (PTAS) for maximizing the expected highest value, proves that maximizing the second-highest value is computationally "hard," and demonstrates that for common "well-behaved" distributions, a simple quantile-based rule works surprisingly well for both objectives.

The Core Problem

Imagine operating a search engine. You have thousands of potential results ($n$), but screen real estate limits you to showing the user only ten ($k$). Each result has an uncertain utility, modeled as a random variable. Your goal is to pick a subset of ten such that the best result among them is as good as possible.

This is the challenge of maximizing expected order statistics. While picking the $k$ items with the highest average value seems intuitive, it is often mathematically suboptimal. A "safe" item with a consistent average might be worse for a "winner-takes-all" scenario than a "long shot" item with high variance.

The authors explore two primary objectives:

  1. Expected Maximum: Maximizing the value of the top-ranked item (highly relevant for search engines or team selection).
  2. Expected Second-Maximum: Maximizing the value of the runner-up (crucial for second-price auctions, where the second-highest bid determines the actual revenue).

Methodological Approaches

The paper approaches subset selection through three distinct lenses:

  • Algorithmic Complexity (The Max): For the Expected Maximum, the authors develop a PTAS (Polynomial Time Approximation Scheme). This involves complex pre-processing—thresholding values, rounding probabilities, and decomposing variables into "cores" and "tails"—to reduce the search space until the problem can be solved efficiently in near-linear time.
  • Hardness Proofs (The Second-Max): For the Expected Second-Maximum, the problem is proven to be fundamentally harder. By reducing it from the "densest $\kappa$-subgraph" problem, the authors show that no constant-factor approximation exists unless deep complexity assumptions (like the Planted Clique Hypothesis) are false. The second-highest value depends heavily on the interaction between variables, complicating approximations.
  • The Quantile Rule for MHR: The authors identify a specific class of distributions called MHR (Monotone Hazard Rate), which includes Normal, Exponential, and Uniform distributions. For these, a simple score-based rule—picking the $k$ variables with the largest $1/\sqrt{k}$ top quantile value—provides a constant-factor approximation for both the first and second maximum simultaneously.

Empirical Performance and Key Results

To validate their theoretical findings, the authors evaluated their algorithms using both synthetic data (independent Normal distributions) and real-world data (a Twitter dataset of 8 million tweets used to predict "likes").

Performance of selection algorithms for expected maximum (k=10)

As shown in the synthetic evaluations above, the Quantile algorithm's performance approaches that of the Greedy and KR (Kleinberg-Raghu) methods at higher quantiles, vastly outperforming a naive Expectation-based selection. For MHR distributions, the $1/\sqrt{k}$ quantile rule is theoretically proven to be a 32-approximation for the max and a 1000-approximation for the second-max, though empirical performance is much tighter.

In the real-world Twitter experiments, both the Quantile-based and KR scores significantly outperformed standard squared-loss regression in picking "high-note" tweets.

Data Scarcity Bias and Fairness

A fascinating secondary insight from the paper is how the choice of algorithm affects who gets selected, particularly concerning data scarcity.

Trade-off between true expected maximum and selection of small sample candidates

Algorithms exhibit different biases toward "small data" candidates (those with fewer historical samples). As illustrated above, while Greedy approaches achieve a high true expected maximum, they tend to pick fewer small-sample candidates compared to Expectation or KR methods. The Quantile method offers a middle ground. Because variance is a virtue in subset selection for the maximum, algorithms that properly value uncertainty can inadvertently promote fairness by giving "risky" or lesser-known candidates a chance to compete against reliable, well-documented ones.

Limitations and Future Work

  • Independence Assumption: The current model assumes all random variables are independent. In reality, candidates (like bidders in an auction) often have correlated values, which significantly complicates the underlying math.
  • Pessimistic Constants: The theoretical approximation factors for the MHR case (32 and 1000) are quite large. While the authors prioritize proving that a constant exists, future work could focus on tightening these bounds to reflect their strong empirical performance.
  • Black-Box Distributions: The PTAS requires an explicit description of the distribution. Extending these high-guarantee algorithms to settings where we only have samples or features remains an open challenge for machine learning integration.

Summary updated

Abstract

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}.
BibTeX
@inproceedings{mehta2020hitting,
  author = {Aranyak Mehta and Uri Nadav and Alexandros Psomas and Aviad Rubinstein},
  title = {{Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=MBfIq0QlVQ},
}
Figure