Selecting the Best Few with Human Evaluators: Adaptively Combining Ratings and Pairwise Comparisons

Introduction

This paper considers a decision-maker tasked with identifying the $k$ best items from a large pool of candidates. This is done using data the decision-maker sources sequentially from human evaluators, where the adaptive choice of upcoming evaluations is informed by what has been learned so far. When modeling such human judgment, a key decision is the form of the evaluation input. While one may wish for some sophisticated multidimensional input, providing it is often beyond the scope, time, and ability for evaluators, which is why inputs such as thumbs-up/thumbs-down and swiping left or right have become popular. Rather than restrict the decision-maker to soliciting one type of input, we allow for the combination of thumbs-up/thumbs-down ratings and pairwise comparisons, which, as we will discuss, can be complementary in our problem. This model can form a basis for many applications, including selecting the best few among LLMs, job applicants, university applicants, financial analysts, award nominees, promotion candidates, new product ideas, and sports draft prospects.

While problems of this type are clearly important, they also tend to be difficult in two distinct ways. One challenge is the analysis and algorithm design. The aim is a sequential evaluation allocation policy that is both close to optimal and structured enough to yield insight and earn practitioners’ trust. The other difficulty is the modeling, which connects the application to the analysis and sets the stage for how useful that analysis will be. First, we position the problem in the literature and walk through the modeling decisions involved. We then discuss how we arrived at our solution approach.

The problem of identifying the best few items by allocating evaluation resources is central to the ranking and selection and best-arm identification literatures, where what we refer to as evaluations are typically called samples. Unlike the classical work on multi-armed bandits [49], where rewards are collected while learning, here the only concern is with the quality of the terminal selection, the setting known as pure exploration [3]. Much of this literature focuses on identifying the best (top-1) item [5, 15, 10]. We consider the more general problem of top-$k$ identification [4, 57, 36].

In this literature, evaluating (sampling) an item typically means directly observing a noisy realization of its utility (quality), which we will refer to as untransformed evaluations. Such untransformed input is natural in applications such as simulation optimization and hyperparameter tuning, where the observed output is itself the object being optimized. In our setting, the utility of each item is latent, since the value of including each item in the chosen set is never evaluated directly. Instead, each item’s quality is observed indirectly through evaluations that take the form of ratings or pairwise comparisons, both of which transform the latent utilities into coarse ordinal outcomes.

To highlight why we do not rely on adapting an established algorithm, we highlight three common modeling and analysis decisions in the ranking and selection literature. We discuss how each decision relates to our problem and, when relevant, how we overcome the additional challenges posed by differences in our setting.

The first modeling decision concerns the terminal objective: how we grade an evaluation allocation policy based on the $k$ items it ultimately selects. The two most common choices are the probability of correct selection (PCS) [5, 20, 33] and the expected opportunity cost (EOC) [12, 11, 16]. PCS is the probability that the selected set is exactly the true top-$k$, so it treats every incorrect selection equally. EOC is the expected shortfall in utility between the selected set and the true top-$k$ set, making bigger selection mistakes more costly. PCS suits highly specialized or high-stakes decisions where any deviation from the best possible selection is considered a failure. For more common tasks, where a serious mistake can be far costlier than a marginal one, EOC can be the more natural fit. Since EOC is more aligned with the applications we consider, we adopt it in this work.

A second decision concerns how the allocation problem is formulated, with two common formulations at opposite ends of the spectrum. One is static allocation, where the decision variable is the total number of evaluations assigned to each item. The other is dynamic learning, where evaluations are chosen one at a time and each outcome is observed before the next evaluation is chosen. In the static formulation, writing $N = (N_1,\ldots,N_I)$ for the vector of evaluations assigned to items $i = 1,\ldots,I$ and $R$ for the total evaluation budget, the allocation problem is

This allocation problem faces two main difficulties. The objective EOC($N$), and likewise PCS($N$), generally does not have a closed form that is amenable to analysis. Additionally, the problem is an integer program, which typically makes it intractable to consider the full solution space at scale. In the fully dynamic formulation, one evaluation is chosen at a time, avoiding the combinatorial complexity of the static problem. At each decision point, the state consists of the current posterior distribution over the items’ utilities and the remaining budget, and the action is the next evaluation. The state transition updates the posterior based on the outcome and deducts the evaluation’s cost from the remaining budget. This problem is formulated as a dynamic program which is intractable because the combination of possible evaluations, outcomes, transitions, and future states grows rapidly with the horizon [15, 27, 57].

Our base formulation is fully dynamic with evaluations chosen sequentially. However, allocating one evaluation at a time can have logistical obstacles. There may be considerable overhead in assigning and conducting evaluations, which can favor giving an evaluator a batch of tasks at once. We therefore also consider a hybrid approach in §6, where a batch of evaluations is chosen in each round. This sits between the two formulations and inherits both difficulties. Within a round, the allocation is an integer program, each linked through the between-round dynamics.

The complexity of the problem under both formulations has given rise to a variety of solution approaches. Before turning to our own, we discuss the three most relevant well-studied families, all developed in the untransformed evaluation setting. The first is a family of algorithms known as Optimal Computing Budget Allocation (OCBA), originating with Chen et al. [6, 5] and Glynn and Juneja [20]. At a high level, the algorithm loops through three steps: (i) take the items’ current mean estimates as if they were the ground truth utilities, (ii) choose the next evaluation(s) by determining the static allocation that would maximize PCS (or minimize EOC), and (iii) update the estimates of the means based on the outcome. However, step (ii) is intractable due to the complexities of the static allocation problem discussed above. To overcome this, it is common to consider the asymptotic regime where $R \to\infty$ and find the allocation proportions that (approximately) optimize the resulting problem. Eventually, the estimated means will converge to the true means, and thus the evaluation proportions will converge to the (approximately) optimal proportions. The majority of the OCBA literature studies the top-1 setting with PCS, with extensions to top-1 EOC [24, 18], as well as to top-$k$ PCS [4, 17, 58] and top-$k$ EOC [16]. Such approaches tend to perform better in large-budget settings. In fact, for small budgets, it has been demonstrated that such allocation procedures may even perform worse than equal allocation [40, 36].

A second family of algorithms considers the dynamic formulation restricted to one-step look-ahead policies, see Powell and Ryzhov [42] for an overview. At each round, the decision-maker chooses the evaluation that (approximately) maximizes the expected value of information (EVI), the improvement in the quality of the terminal selection that results from one additional evaluation. For top-1 identification, Chick and Inoue [12], Chick et al. [11] derive policies that approximately maximize EVI for both the PCS and EOC objectives. Recently, Zhang et al. [57] developed a top-$k$ identification policy that maximizes an approximation of the EVI for PCS. Assuming evaluations follow Gaussian distributions with known variances, Frazier et al. [15] derive the exact one-step look-ahead policy that maximizes the EVI for EOC, known as the knowledge gradient (KG) policy. In our setting, however, KG’s myopia can be particularly detrimental with binary evaluations [23, 31]. We return to this point in § 2.3.

A third related family of algorithms is based on the expected improvement (EI) approach [28], which originated in the Bayesian Optimization literature. Various works have studied its application to top-1 identification [50, 44, 9]. In its simplest form, EI scores each item by how much its utility, in expectation, exceeds that of the current best candidate and evaluates the item with the highest score. EI’s simplicity is appealing, and although it does not explicitly look ahead, it still reflects future dynamics: evaluating items with high potential to improve on the current best can help inform which evaluations to conduct in future rounds. However, EI does not naturally extend to reflect alternative evaluation forms with different information contents and costs. Furthermore, it chooses which single item to evaluate next, whereas our evaluation alternatives include choosing a pair to compare.

Finally, the third modeling decision concerns the form of the evaluations themselves. In psychometrics, the field of measurement of psychological data, the two most common forms of input for human feedback are ratings, where an evaluation assigns a categorical score to a particular item, and rankings, where a set of items is ordered relative to one another [53, 35, 55]. We consider each in its parsimonious form—binary thumbs-up/thumbs-down ratings and pairwise comparisons—both among the most common input choices. Restricting to these simple versions of ordinal feedback keeps evaluators’ cognitive load low [48, 30]. The two input forms have distinct pros and cons in our setting. Ratings can be cheaper and easier to provide than pairwise comparisons [56], and a few of them can be an efficient way to establish the ballpark utility of an item. However, ratings are not efficient at distinguishing the relative order of close items, which is essential for differentiating between top-$k$ candidates. Additionally, a rating (say, a thumbs-up) can carry a different meaning to different evaluators, resulting in potential ambiguity when aggregating and interpreting them. Pairwise comparisons, in contrast, only contain relative information about item utilities, and while their interpretation is unambiguous, their usefulness depends heavily on which items are paired. The number of possible pairings is quadratic in the number of items, so starting from an uninformed prior would result in many unhelpful pairings early on. For example, we might compare the items that turn out to be the two worst. Even if that comparison provides a strong signal about which of the two is better, it does little to inform us about which items are in the top-$k$. However, once we do have a clear sense of which items are top-$k$ contenders, comparisons can be far more effective than ratings at pinning down their relative ordering [32]. It follows that the two evaluation forms can be especially useful when combined [14]. Intuitively, ratings can be used more in early rounds to get a coarse picture of which items are “good” and which are not, and then as that picture forms, comparisons can gradually take over, refining the relative ordering of the good items and narrowing in on the ultimate top-$k$ selection. Our model allows the two evaluation types to differ in accuracy and cost (effort), following the empirical findings of Pérez-Ortiz et al. [41] and White et al. [56].

The two evaluation forms can also interact in non-intuitive ways. Consider a simple example with four items, $A$, $B$, $C$, and $D$, whose utilities are independent ex-ante. With ratings alone, a rating of $B$ informs its utility relative to the other items but leaves our beliefs about their utilities unchanged. Now suppose we observe the comparisons $A \succ B$ and $C \succ D$, followed by $B \succ C$. Intuitively, the third comparison suggests that $A$ is preferred to $D$ even though neither was involved in the comparison. The mechanism by which our model reflects this is that comparisons create dependency in the joint posterior over the utilities: the third comparison raises $B$’s estimate and thereby also lifts $A$, while lowering $C$’s estimate and thereby also lowering $D$. This dependency also changes what we learn from a rating. A subsequent rating of $B$ can now influence our posterior beliefs about $A$, $C$, and $D$. In fact, with a more complex comparison history, a rating of $B$ can even reverse our estimated relative ranking of two non-evaluated items, such as $A$ and $D$. Thus, the value of an evaluation for informing the top-$k$ set may not be apparent from what it tells us about the evaluated items alone. Including such dependency in the joint posterior is an opportunity, as it leads to better discrimination between items and hence a more accurate top-$k$ choice. But this added accuracy does not come for free: reflecting the dependency in the dynamic choice of evaluations adds complexity.

Work related to top-$k$ selection tasks in which evaluations are, like ours, binary pairwise comparisons (and possibly also ratings) is scarce in the literature, especially with small budgets. In this setting, one common approach to model evaluations is to assign each possible evaluation its own parameter. For pairwise comparisons, this means a separate parameter specification for each pair of items, representing the probability that one item is preferred to the other. Although the outcomes are binary, this model is still in the untransformed evaluation setting: the outcomes remain a direct noisy realization of the underlying parameter. An alternative approach is the latent-utility model of our setting, where each item has a single value, its utility, that generates the comparisons (and ratings).

In the ranking and selection literature, Priekule and Meisel [43], Groves and Branke [23], Li et al. [31] study top-1 and top-$k$ selection with binary pairwise comparisons under the first evaluation model. Their methodology does not transfer to our problem, as their more flexible model requires learning the parameters of $I(I-1)/2$ item pairs, which is unrealistic in small-budget settings. More fundamentally, they only consider pairwise comparisons, and it is not clear how one could combine ratings and comparisons under this model.

In the crowdsourcing literature, these problems are more commonly studied under latent-utility models. Chen et al. [7] develop an approximate KG algorithm for learning the full ranking of items (as opposed to the top-$k$) from pairwise comparisons. Li et al. [32], Pérez-Ortiz et al. [41], Fageot et al. [14] develop a unified statistical model for combining pairwise comparisons and ratings. Fageot et al. [14] show empirically that combining ratings and pairwise comparisons can improve estimation of the latent utilities. More directly related to our problem, Li et al. [32] also give a heuristic approach for choosing evaluations for top-$k$ selection, a slightly modified version of which we use as a benchmark.

Finally, top-$k$ identification from pairwise comparisons is well studied in the dueling-bandit and active-ranking literature. Usually set in the fixed-confidence regime where sampling continues until a target confidence is reached (as opposed to a fixed budget $R$), these algorithms tend to require large numbers of evaluations—far beyond the budgets we consider. See, e.g., [38, 46, 8, 25, 51, 47, 52, 21] for recent developments and Bengs et al. [1] for a review.

Instead of explaining our evaluation allocation approach directly, we find it easier to lay out where it came from. Our starting point was the KG policy primarily because, among the existing methods, it is well suited for small-budget problems and can naturally accommodate the combination of evaluation types—our key initial motivation for undertaking this research. However, the KG policy allocates evaluations in each round as if the final selection would immediately follow. Except for the last evaluation, that is not the actual task. The task is to prepare for the terminal selection, and it may be that the best evaluation to do next is decided by how it may inform later evaluation choices. To illustrate how much KG misses out on future dynamics, consider that in its eyes any evaluation whose outcome cannot change the current top-$k$ set has no value at all.

Ideally, we would incorporate the full dynamics into the evaluation choices, but based on the existing literature, anything beyond solving a sequence of state-dependent, static problems seems out of reach. Our key insight leading to our approach came from flipping the perspective from the positive focus on what the decision-maker wants to achieve—choosing the best $k$ items—to a negative perspective—how to reduce errors. There are two ways to err ex-post: including an item that does not belong (inclusion error) and excluding one that does (exclusion error). Ex-ante, items have an expected mismatch loss: the expected magnitude of an inclusion error for items in the current top-$k$ and an exclusion error for those not in it. We then construct a per-round surrogate objective that values uncertainty reduction by how much it reduces the expected mismatch loss. We contrast this with the KG policy that adopts the terminal top-$k$ EOC as each round’s objective. It uses the current uncertainty to assess possible changes in the membership of the top-$k$ posterior means. Our method instead holds the current means fixed and values an evaluation by how much it is expected to reduce uncertainty. The terminal top-$k$ decision then drives the evaluation choices only implicitly by providing a measure of where uncertainty reduction is more valuable. This surrogate is naturally forward-looking. It seeks to reduce uncertainty about the items currently near the top-$k$ cutoff without requiring any direct change to the current top-$k$ set. Doing so pays off in future rounds, since the more effective we are at singling out items near the top-$k$ cutoff, the more effectively we can direct the remaining evaluations.

The difficulty is that mismatch loss does not admit an analysis-friendly expression. The magnitude of an item’s error depends on where it stands relative to the $k$th or $(k+1)$th best of the remaining items, so computing an item’s mismatch loss requires an expectation with respect to the joint utility distribution and an order statistic of the other $I-1$ items, where even the latter itself is intractable. Our resolution is to replace this random top-$k$ threshold with a simpler threshold that is recalibrated each round, such that, in expectation, $k$ items’ utilities will exceed it. With this threshold, an item’s mismatch loss depends only on the marginal distribution of its utility relative to it. This separability gives a clean and interpretable way to account for an evaluation’s effect on all items, those being directly evaluated and, via covariance, those that are not. The sum of these mismatch losses is our surrogate objective, and in each round, the policy chooses the evaluation whose reduction of this loss per evaluation cost is largest.

We also point out a potential trap that arises when combining the two evaluation types, in part because we initially fell into it. Ratings contain information about the average utility of the items, while comparisons do not. Learning about this average reduces the variance of each item’s utility but does not help distinguish the top-$k$, since shifting all utilities together leaves their ordering unchanged. A surrogate that rewards this reduction in variance would therefore unfairly favor ratings over comparisons. We discuss this issue in § 3 and show that our surrogate does not reward learning about the average utility, so ratings and comparisons are on equal footing.

As the horizon approaches its end, being forward-looking becomes less valuable, and this strength of the surrogate can become a weakness. In this regime, the myopia of the KG policy would be desirable. We therefore develop the KG policy for our problem, with a switching criterion for the endgame, the final rounds where its myopia outperforms the surrogate.

We support our method through both analysis and simulation. In the analysis, although the surrogate objective was constructed from analytical intuition rather than derived, we show that it can be obtained from an upper bound on the EOC, which rigorously justifies and refines our choice of the top-$k$ threshold. We also prove that the resulting policy that allocates by minimizing the surrogate in each round is asymptotically consistent. In simulation, we show that the allocations this policy produces are intuitive and insightful, and that it substantially outperforms existing benchmarks.

The remainder of the paper is organized as follows: § 2 presents the model and defines the objective. § 3 develops the surrogate objective, which §4 uses to construct the sequential evaluation procedure and establish its asymptotic consistency. § 5 develops the knowledge gradient policy for the endgame and the switching rule.

§6 considers the batch setting. §7 reports the results of the numerical experiments, and §8 gives concluding remarks.

Model and objective

This section defines the generative data model for pairwise comparisons and ratings, introduces the sequential evaluation process and formulates the optimization problem as a dynamic program. We then demonstrate that the KG policy is not well-suited for our setting, which motivates the surrogate objective of §3.

Generative model

We consider $I$ items with latent utilities $\boldsymbol{\theta} = (\theta_1,\ldots,\theta_I) \in\mathbb{R}^I$, which represent the values of selecting each item. We adopt a Bayesian framework and place a Gaussian prior on the utility vector, $\boldsymbol{\theta} \sim\mathcal{N}(\boldsymbol{\mu}_0,\Sigma_0)$ where $\Sigma_0$ is positive definite. When preliminary information distinguishes the items, $\boldsymbol{\mu}_0$ and $\Sigma_0$ can reflect it. When no such information is available, or when items are people and a prior that discriminates raises ethical or legal concerns, an exchangeable prior $(\boldsymbol{\mu}_0 = 0, \Sigma_0 = sI_d)$ treats all items symmetrically.

Evaluators can provide two types of feedback, pairwise comparisons and ratings. A pairwise comparison of items $i$ and $j$ produces a binary outcome: one item is preferred to the other. The event that an evaluator prefers $i$ to $j$ is denoted by $i \succ j$, and its probability is determined by $\theta_i - \theta_j + \epsilon_1$, where $\epsilon_1 \sim\mathcal{N}(0,\sigma_1^2)$. Thus, the evaluator’s ability to distinguish between the two items depends on the difference in their utilities and on $\epsilon_1$, which captures imperfections in pairwise evaluations. The subscript 1 is used because item $i$ is compared to 1 other item. A rating of item $i$ produces a binary ‘thumbs-up’ or ‘thumbs-down’ outcome, where item $i$ is implicitly compared to some utility threshold $\theta_0$. Note that $\theta_0$ is not a part of $\boldsymbol{\theta}$—we use this notation to facilitate unified expressions for pairwise comparisons and ratings. Similar to the pairwise comparison model, the event that an evaluator ranks $i$ above the threshold is denoted by $i \succ0$ and its probability is determined by $\theta_i - \theta_0 + \epsilon_0$, where $\epsilon_0 \sim\mathcal{N}(0,\sigma_0^2)$. Here $\epsilon_0$ captures two sources of noise: the evaluator’s ability to estimate item $i$’s utility and the uncertainty about where the latent threshold $\theta_0$ lies. The subscript 0 is used because item $i$ is compared to 0 items.

The set of possible evaluations is given by $\mathcal{I} := \{(i,j): 0 \le j < i \le I\}$. Define $\jmath= \min(j,1)$, which is 0 (1) when an evaluation is a rating (comparison). For an evaluation $(i,j) \in\mathcal{I}$, let $X_{ij}$ denote the outcome where

and, conditioned on the evaluator-noise term $\epsilon_j$, $\mathbb{P}(X_{ij}=1 \mid\boldsymbol{\theta},\epsilon_j)=g(\theta_i-\theta_j+\epsilon_j)$, where $g:\mathbb{R}\to(0,1)$ is some link function. For the remainder of the paper, unless specified otherwise, we consider the probit link function, commonly used to model human ordinal rating data [34], i.e., $g=\Phi$, where $\Phi$ is the standard normal CDF and $\phi$ its density. Thus,

where $\beta_j := \frac{1}{\sqrt{1+\sigma_j^2}} \in(0,1]$, for $j \in\{0,1\}$, captures the evaluator precision when providing a rating or a pairwise comparison. As shown in Pérez-Ortiz et al. [41], a single latent-utility model for ratings and pairwise comparisons can fit human data well as long as the two evaluation types are allowed to differ in signal quality, which we capture through $\beta_0$ and $\beta_1$. In addition to variation in signal quality, there may also be heterogeneity in evaluator accuracy and bias. If these differences were known, our model would capture this by using different values of $\theta_0$, $\beta_0$, and $\beta_1$ for each evaluator. Because they are generally unknown, we instead use common parameters across evaluators, effectively absorbing evaluator-level variation into the noise terms rather than learning evaluator-specific accuracy or bias from past evaluations. This is a standard simplification in the literature, and models using it have been shown to still fit human data well [41]. Learning evaluator-specific parameters could further inform the allocation, but would introduce an additional inference problem that we leave for future work. In the numerical experiments of § 7, we stress-test this assumption by using synthetic data where accuracy and bias differ across evaluators.

One may question the feasibility of calibrating these parameters in practice. Remark 1 shows that after fixing one for identification, the rest can be calibrated from three simple, interpretable quantities.