Your 2 is My 1, Your 3 is My 9: Handling Arbitrary Miscalibrations in Ratings

Introduction

“A raw rating of 7 out of 10 in the absence of any other information is potentially useless.” [MGCV11]

“The rating scale as well as the individual ratings are often arbitrary and may not be consistent from one user to another.” [AS12]

Consider two items that need to be evaluated (for example, papers submitted to a conference) and two reviewers. Suppose each reviewer is assigned one distinct item for evaluation, and this assignment is done uniformly at random. The two reviewers provide their evaluations (say, in the range $$) for the respective item they evaluate, from which the better item must be chosen. However, the reviewers’ rating scales may be miscalibrated. It might be the case that the first reviewer is lenient and always provides scores in$[0.6,1]$whereas the second reviewer is more stringent and provides scores in the range$[0,0.4]$. Or it might be the case that one reviewer is moderate whereas the other is extreme – the first reviewer’s 0.2 is equivalent to the second reviewer’s 0.1 whereas the first reviewer’s 0.3 is equivalent to the second reviewer’s 0.9. More generally, the miscalibration of the reviewers may be arbitrary and unknown. Then is there any hope of identifying the better of the two items with any non-trivial degree of certainty?

A variety of applications involve collection of human preferences or judgments in terms of cardinal scores (numeric ratings). A perennial problem with eliciting cardinal scores is that of miscalibration – the systematic errors introduced due to incomparability of cardinal scores provided by different people (see [GB08] and references therein).

This issue of miscalibration is sometimes addressed by making simplifying assumptions about the form of miscalibration, and post-hoc corrections under these assumptions. Such models include one-parameter-per-reviewer additive biases [Pau81, BK13, GWG13, MKLP17], two-parameters-per-reviewer scale-and-shift biases [Pau81, RRS11] and others [FSG+10]. The calibration issues with human-provided scores are often significantly more complex causing significant violations to these simplified assumptions (see [GB08] and references therein). Moreover, the algorithms for post-hoc correction often try to estimate the individual parameters which may not be feasible due to low sample sizes. For instance, John Langford notes from his experience as the program chair of the ICML 2012 conference [Lan12]:

“We experimented with reviewer normalization and generally found it significantly harmful.”

This problem of low sample size is exacerbated in a number of applications such as A/B testing where every reviewer evaluates only one item, thereby making the problem underdetermined even under highly restrictive models.

It is commonly believed that when unable or unwilling to make any simplifying assumptions on the bias in cardinal scores, the only useful information is the ranking of the scores [Rok68, FISS03, HBBR+09, MGCV11, AS12, NOS12]. This perception gives rise to a second approach towards handling miscalibrations – that of using only the induced ranking or otherwise directly eliciting a ranking and not scores from the use. As noted by Freund et al. [FISS03]:

“[Using rankings instead of ratings] becomes very important when we combine the rankings of many viewers who often use completely different ranges of scores to express identical preferences.”

These motivations have spurred a long line of literature on analyzing data that takes the form of partial or total rankings of items [CGPR07, BK09, AS12, NOS12, RGLA15, SBB+16, SW18].

In this paper, we contest this widely held belief with the following two fundamental questions:

In the absence of simplifying modeling assumptions on the miscalibration, is there any estimator (based on the scores) that can outperform estimators based on the induced rankings?

If only one evaluation per reviewer is available, and if each reviewer may have an arbitrary (possibly adversarially chosen) miscalibration, is there hope of estimation better than random guessing?

We show that the answer to both questions is “Yes”. One need not make simplifying assumptions about the miscalibration and yet guarantee a performance superior to that of any estimator that uses only the induced rankings.

In more detail, we consider settings where a number of people provide cardinal scores for one or more from a collection of items. The calibration of each reviewer is represented by an unknown monotonic function that maps the space of true values to the scores given by this reviewer. These functions are arbitrary and may even be chosen adversarially. We present a class of estimators based on cardinal scores given by the reviewers which uniformly outperforms any estimator that uses only the induced rankings. A compelling feature of our estimators is that they can be used as a plug-in to improve ranking-based algorithms in a variety of applications, and we provide a proof-of-concept for two applications: A/B testing and ranking.

The techniques used in our analyses draw inspiration from the framework of Stein’s shrinkage [Ste56, JS61] and empirical Bayes [Rob56]. Moreover, our setting with $2$ reviewers and $2$ papers presented subsequently in the paper carries a close connection to the classic two-envelope problem (for a survey of the two-envelope problem, see [Gne16]), and our estimator in this setting is similar in spirit to the randomized strategy [Cov87] proposed by Thomas Cover. We discuss connections with the literature in more detail in Section 3.1.1.

Our work provides a new perspective on the eternal debate between cardinal scores and ordinal rankings. It is often believed that ordinal rankings are a panacea for the miscalibration issues with cardinal scores. Here we show that ordinal estimators are not only inadmissible, they are also strictly and uniformly beaten by our cardinal estimators. Our results thus uncover a new point on the bias-variance tradeoff for this class of problems: Estimators that rely on simplified assumptions about the miscalibration incur biases due to model mismatch, whereas the absence of such assumptions in our work eliminates the modeling bias. Moreover, in this minimal-bias regime, our cardinal estimators incur a strictly smaller variance as compared to estimators based on ordinal data alone.

Finally, a note qualifying the scope of the problem setting considered here. In applications such as crowdsourced microtasks where workers often spend very little time answering every question, the cardinal scores elicited may not necessarily be consistent with the ordinal rankings, and moreover, ordinal rankings are often easier and faster to provide. These differences cease to exist in a variety of applications such as peer-review or in-person laboratory A/B tests which require the reviewers to spend a non-trivial amount of time and effort in the review process, and these applications form the motivation of this work.

Preliminaries

Every reviewer is assigned one or more items to evaluate. We denote the assignment of items to reviewers as $A=(S_{1},\ldots,S_{m})$, where $S_{j}\subseteq[n]$ is the set of items assigned to reviewer $j\in[m]$. We use the notation $\Pi$ to represent the set of all permutations of $n$ items. We let $\pi^{*}\in\Pi$ denote the ranking of the $n$ items induced by their respective values $(x_{1},\ldots,x_{n})$, such that $x_{\pi^{*}(1)}>x_{\pi^{*}(2)}>\cdots>x_{\pi^{*}(n)}$. The goal is to estimate this ranking $\pi^{*}$ from the evaluations of the reviewers. We consider two types of settings: an ordinal setting where estimation is performed using the rankings induced by each reviewer’s reported scores, and a cardinal setting where the estimation is performed using the reviewers’ scores (which can have an arbitrary miscalibration and only need to be consistent with the rankings). Formally:

Ordinal: Each reviewer $j$ reports a total ranking among the items in $S_{j}$, that is, the ranking of the items induced by the values $\{f_{j}(x_{i})\}_{i\in S_{j}}$. An ordinal estimator observes the assignment $A$ and the rankings reported by all reviewers.

Cardinal: Each reviewer $j$ reports the scores for the items in $S_{j}$, that is, the values of $\{f_{j}(x_{i})\}_{i\in S_{j}}$. A cardinal estimator observes the assignment $A$ and the scores reported by all reviewers.

Observe that the setting described above considers “noiseless” data, where each reviewer reports either the scores $\{f_{j}(x_{i})\}$ or the induced rankings. We provide an extension to the noisy setting in Appendix A.

In order to compare the performance of different estimators, we use the notion of strict uniform dominance. Informally, we say that one estimator strictly uniformly dominates another if it incurs a strictly lower risk for all possible choices of the miscalibration functions and the item values.

In more detail, suppose that you wish to show that an estimator $\widehat{\pi}_{1}$ is superior to estimator $\widehat{\pi}_{2}$ with respect to some metric for estimating $\pi^{*}$. However, there is a clever adversary who intends to thwart your attempts. The adversary can choose the miscalibration functions of all reviewers and the values of all items, and moreover, can tailor these choices for different realizations of $\pi^{*}$. Formally, the adversary specifies a set of values $\{f^{\pi}_{1},\ldots,f^{\pi}_{m},x^{\pi}_{1},\ldots,x^{\pi}_{n}\}_{\pi\in\Pi}$. The only constraints in this choice are that the miscalibration functions $f^{\pi}_{1},\ldots,f^{\pi}_{m}$ must be strictly monotonic and that the item values $x^{\pi}_{1},\ldots,x^{\pi}_{n}$ should induce the ranking $\pi$. In the sequel, we consider two ways of choosing the true ranking $\pi^{*}$: In one setting, $\pi^{*}$ can be chosen by the adversary, and in the second setting $\pi^{*}$ is drawn uniformly at random from $\Pi$. Once this ranking $\pi^{*}$ is chosen, the actual values of the miscalibration functions and the item values are set as $f^{\pi^{*}}_{1},\ldots,f^{\pi^{*}}_{m}$ and $x^{\pi^{*}}_{1},\ldots,x^{\pi^{*}}_{n}$. The items are then assigned to reviewers according to the (possibly random) assignment $A$. The reviewers now provide their ordinal or cardinal evaluations as described earlier, and these evaluations are used to compute and evaluate the two estimators $\widehat{\pi}_{1}$ and $\widehat{\pi}_{2}$. We say that estimator $\widehat{\pi}_{1}$ strictly uniformly dominates $\widehat{\pi}_{2}$, if $\widehat{\pi}_{1}$ is always guaranteed to incur a strictly smaller (expected) error than $\widehat{\pi}_{2}$. Formally:

The expectation is taken over any randomness in the assignment $A$ and the estimators. If the true ranking $\pi^{*}$ is drawn at random from a fixed distribution, then the expectation is also taken over this distribution; otherwise, inequality (1) must hold for all values of $\pi^{*}$.

Note that strict uniform dominance is a stronger notion than comparing estimators in terms of their minimax (worst-case) or average-case risks. Moreover, if an estimator $\widehat{\pi}_{2}$ is strictly uniformly dominated by some estimator $\widehat{\pi}_{1}$, then the estimator $\widehat{\pi}_{2}$ is inadmissible.

Finally, for ease of exposition, we focus on the 0-1 loss in the main text:

Main results

In this section we present our main theoretical results. All proofs are provided in Section 5.

We begin with a canonical setting that involves two items and two reviewers (that is, $n=2$, $m=2$), where each reviewer evaluates one of the two items. Our analysis for this setting conveys the key ideas underlying our general results. These ideas are directly applicable towards designing uniformly superior estimators for a variety of applications, and we subsequently demonstrate this general utility with two applications.

In this canonical setting, each of the two reviewers evaluates one of the two items chosen uniformly at random without replacement, that is, the assignment $A$ is chosen uniformly at random from the two possibilities $(S_{1}=1,S_{2}=2)$ and $(S_{1}=2,S_{2}=1)$. Since each reviewer is assigned only one item, the ordinal data is vacuous. Then the natural ordinal baseline is an estimator which makes a guess uniformly at random:

In the cardinal setting, let $y_{1}$ denote the score reported for item $1$ by its respective reviewer, and let $y_{2}$ denote the score for item $2$ reported by its respective reviewer. Since the calibration functions are arbitrary (and may be adversarial), it appears hopeless to obtain information about the relative values of $x_{1}$ and $x_{2}$ from just this data. Indeed, as we show below, standard estimators such as the sign test — ranking the items in terms of their reviewer-provided scores — provably fail to achieve this goal. More generally, the following theorem holds for the class of all deterministic estimators, that is, estimators given by deterministic mappings from $\{A,y_{1},y_{2}\}$ to the set $\{1\succ 2,2\succ 1\}$.

No deterministic (cardinal or ordinal) estimator can strictly uniformly dominate the random-guessing estimator $\widehat{\pi}_{\text{can}}$.

This theorem demonstrates the difficulty of this problem by ruling out all deterministic estimators. Our original question then still remains: is there any estimator that can strictly uniformly outperform the random-guessing ordinal baseline?

We show that the answer is yes, with the construction of a randomized estimator for this canonical setting, denoted as $\widetilde{\pi}_{\text{can}}^{\text{our}}$. This estimator is based on a function $w:[0,\infty)\rightarrow[0,1)$ which may be chosen as any arbitrary strictly-increasing function. For instance, one could choose $w(x)=\frac{x}{1+x}$ or $w$ as the sigmoid function. Given the scores $y_{1},y_{2}$ reported for the two items, let $\widehat{i}^{(1)}\in\argmax_{i\in\{1,2\}}y_{i}$ denote the item which receives the higher score, and let $\widehat{i}^{(2)}$ denote the remaining item (with ties broken uniformly). Then our randomized estimator outputs:

Note that the the output of this estimator is independent of the assignment $A$, so in the remainder of this paper we also denote this estimator as $\widetilde{\pi}_{\text{can}}^{\text{our}}(y_{1},y_{2})$.

The following theorem now proves that our proposed estimator indeed achieves the stated goal.

The randomized estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ strictly uniformly dominates the random-guessing baseline $\widehat{\pi}_{\text{can}}$.

While this result considers a setting with “noiseless” observations (that is, where $y=f(x)$), in Appendix A we show that the guarantee for $\widetilde{\pi}_{\text{can}}^{\text{our}}$ continues to hold when the observations are noisy.

Having established the positive result for this canonical setting, we now discuss some connections and inspirations in the literature.

Our canonical setting can be reduced to the two-envelope problem as follows. Consider the two values $f_{1}(x_{1})-f_{2}(x_{2})$ and $f_{1}(x_{2})-f_{2}(x_{1})$. Since the two items are assigned to the two reviewers uniformly at random, we observe one of these two values uniformly at random. By the assumption that $f_{1}$ and $f_{2}$ are monotonically increasing, we know that these two values are distinct, and furthermore, $f_{1}(x_{1})-f_{2}(x_{2})>f_{1}(x_{2})-f_{2}(x_{1})$ if and only if $x_{1}>x_{2}$. Hence, the relative ordering of these two values is identical to the relative ordering of $x_{1}$ and $x_{2}$, reducing our canonical setting to the two-envelope problem. Our estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ also carries a close connection to Cover’s estimator to the two-envelope problem. Specifically, Cover’s estimator can be equivalently viewed as being designated by a “switching function” [MA09]. This switching function specifies the probability to “switch” (that is, to guess that the unobserved value is larger), and is a monotonically-decreasing function in the observed value. The use of the monotonic function $w$ in our estimator in (2) is similar in spirit.

The two-envelope problem can also be alternatively viewed as a secretary problem with two candidates. Negative results have been shown regarding the effect of cardinal vs. ordinal data when there are more than two candidates [SN92, Gne94], and positive result has been shown on extensions of the secretary problem to different losses [GK96].

Our original inspiration for our proposed estimator arose from Stein’s phenomenon [Ste56] and empirical Bayes [Rob56]. This inspiration stems for the fact that the two items are not to be estimated in isolation, but in a joint manner. That said, a significant fraction of the work (e.g., [Rob56, Ste56, JS61, Bar70, Boc75, TKV17]) in these areas is based on deterministic estimators. In comparison, our negative result for all deterministic estimators (Theorem 1) and the positive result for our randomized estimator (Theorem 2) provide interesting insights in this space.

2 A/B testing

We now demonstrate how to use the result in the canonical setting as a plug-in for more general scenarios. Specifically, we construct simple extensions to our canonical estimator, as a proof-of-concept for the superiority of cardinal data over ordinal data in A/B testing (this section) and ranking (Section 3.3). A/B testing is concerned with the problem of choosing the better of two given items, based on multiple evaluations of each item, and is used widely for the web and e-commerce (e.g. [KLSH09]). In many applications of A/B testing, the two items are rated by disjoint sets of individuals (for example, when comparing two web designs, each user sees one and only one design). It is therefore important to take into account the different calibrations of different individuals, and this problem fits in our setting with $n=2$ items and $m$ reviewers. For simplicity, we assume that $m$ is even. We consider the assignment obtained by assigning item $1$ to some $m/2$ reviewers chosen uniformly at random (without replacement) from the set of $m$ reviewers, and assigning item $2$ to the remaining $m/2$ reviewers. Our results also hold in the following settings: (a) Each reviewer is assigned one of the two items independently and uniformly at random. (b) Reviewers are grouped (in any arbitrary manner) into $m/2$ pairs, and within each pair, the two reviewers are assigned one distinct item each uniformly at random.

As in the canonical setting we studied earlier, in the absence of any direct comparison between the two items, a natural ordinal estimator in the A/B testing setting is a random guess:

For concreteness, we consider the following method of performing the random assignment of the two items to the $m$ reviewers. We first perform a uniformly random permutation of the $m$ reviewers, and then assign the first $m/2$ reviewers in this permutation to item $1$; we assign the last $m/2$ reviewers in this permutation to item $2$. We let $y_{1}^{(1)},\ldots,y_{1}^{(m/2)}$ denote the scores given by the $m/2$ reviewers to item $1$, and let $y_{2}^{(1)},\ldots,y_{2}^{(m/2)}$ denote the scores given by the $m/2$ reviewers assigned to item $2$. Namely, the reviewers (in the permuted order) provide the scores $[y_{1}^{(1)},\ldots,y_{1}^{(m/2)},y_{2}^{(1)},\ldots,y_{2}^{(m/2)}]$. Now consider the following standard (deterministic) estimators:

Mean estimator: The mean estimator outputs the item with the higher mean score: $\mean(y_{1}^{(1)},\ldots,y_{1}^{(m/2)})\mathrel{\mathop{\gtrless}\limits^{1\succ 2}_{2\succ 1}}\mean(y_{2}^{(1)},\ldots,y_{2}^{(m/2)})$.

Median estimator: The median estimator outputs the item with the higher median score (upper median if there are multiple medians) For values $a_{1}\geq\cdots\geq a_{n}$, we define the median function as the upper median, $\median(a_{1},\ldots,a_{n})=a_{\lfloor(n+1)/2\rfloor}$. Theorem 3 also holds instead for the lower median $a_{\lfloor(n+2)/2\rfloor}$, and the median defined as the mean of the two middle values, $(a_{\lfloor(n+1)/2\rfloor}+a_{\lfloor(n+2)/2\rfloor})/2$.: $\median(y_{1}^{(1)},\ldots,y_{1}^{(m/2)})\mathrel{\mathop{\gtrless}\limits^{1\succ 2}_{2\succ 1}}\median(y_{2}^{(1)},\ldots,y_{2}^{(m/2)})$.

In each estimator, ties are assumed to be broken uniformly at random.

We now show that despite using the scores given by all $m$ reviewers, where $m$ can be arbitrarily large, these natural estimators fail to uniformly dominate the naïve random-guessing ordinal estimator.

For any (even) number of reviewers, none of the sign, mean, and median estimators can strictly uniformly dominate the random-guessing estimator $\widehat{\pi}_{\text{ab}}$.

The negative result of Theorem 3 demonstrates the challenges even when one is allowed to collect an arbitrarily large number of scores for each item. Intuitively, the more reviewers there are, the more miscalibration functions they introduce. Even if the statistics used by these estimators converge as the number of the reviewers $m$ grows large, these values are not guaranteed to be informative towards comparing the values of the items due to the miscalibrations.

The failure of these standard estimators suggests the need of a novel approach towards this problem of A/B testing under arbitrary miscalibrations. To this end, we build on top of our canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ from Section 3.1, and present a simple randomized estimator $\widetilde{\pi}^{\text{our}}_{\text{ab}}$ as follows:

For every $j\in[m/2]$, use the canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ on the $j^{th}$ pair of scores $(y_{1}^{(j)},y_{2}^{(j)})$ and obtain the estimate $r_{j}:=\widetilde{\pi}_{\text{can}}^{\text{our}}(y_{1}^{(j)},y_{2}^{(j)})\in\{1\succ 2,2\succ 1\}$.

Set the output $\widetilde{\pi}^{\text{our}}_{\text{ab}}$ as the outcome of the majority vote among the estimates $\{r_{j}\}_{j\in[m/2]}$ with ties broken uniformly at random.

The following theorem now shows that the results for the canonical setting from Section 3.1 translate to this A/B testing application.

For any (even) number of reviewers, the estimator $\widetilde{\pi}^{\text{our}}_{\text{ab}}$ strictly uniformly dominates the random guessing estimator $\widehat{\pi}_{\text{ab}}$.

This result thus illustrates the use of our canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ as a plug-in for A/B testing. So far we have considered settings where there are only two items and where each reviewer is assigned only one item, thereby making the ordinal information vacuous. We now turn to an application that is free of these restrictions.

3 Ranking

It is common in practice to estimate the partial or total ranking for a list of items by soliciting ordinal or cardinal responses from individuals. In conference reviews or peer-grading, each reviewer is asked to rank [Dou09, SBP+13, STM+17] or rate [GWG13, PHC+13, STM+17] a small subset of the papers, and this information is subsequently used to estimate a partial or total ranking of the papers (or student homework). Other applications for aggregating rankings include voting [You88, PSZ16], crowdsourcing [SBB+16, SW18], recommendation systems [FISS03] and meta-search [DKNS01].

Formally, we let $n>2$ denote the number of items and $m$ denote the number of reviewers. For simplicity, we focus on a setting where each reviewer reports noiseless evaluations of some pair of items, and the goal is to estimate the total ranking of all items. We consider a random design setup where the pairs compared are randomly chosen and randomly assigned to reviewers. We assume $1<m<\binom{n}{2}$ so that the problem does not degenerate. Each reviewer evaluates a pair of items, and these pairs are drawn uniformly without replacement from the ${n\choose 2}$ possible pairs of items. We let $A=(S_{1},\ldots,S_{m})$ denote these $m$ pairs of items to be evaluated by the $m$ respective reviewers, where $S_{j}\in[n]\times[n]$ denotes the pair of items evaluated by reviewer $j\in[m]$. For each pair $S_{j}=(i,i^{\prime})$, denote the cardinal evaluation as $y(S_{j})=(f_{j}(x_{i}),f_{j}(x_{i^{\prime}}))$, and the ordinal evaluation as the induced ranking $b(S_{j})\in\{i\succ i^{\prime},i^{\prime}\succ i\}$. Denote the set of ordinal observations as $\mathcal{B}=\{b(S_{j})\}_{j=1}^{m}$, and the set of cardinal observations as $\mathcal{Y}=\{y(S_{j})\}_{j=1}^{m}$. The input to an ordinal estimator is the ordinal information $\mathcal{B}$. The input to a cardinal estimator is the reviewer assignment $A$ and the set of cardinal observations $\mathcal{Y}$. Finally, let $\mathcal{G}(\mathcal{B})$ denote a directed acyclic graph (DAG) with nodes comprising the $n$ items and with an edge from any node $i$ to any other node $i^{\prime}$ if and only if $\{i\succ i^{\prime}\}\in\mathcal{B}$. A topological ordering on $\mathcal{G}$ is any total ranking of its vertices which does not violate any pairwise comparisons indicated by $\mathcal{B}$.

We now present our (randomized) cardinal estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}(A,\mathcal{Y})$ in Algorithm 1. In words, this algorithm start from any topological ordering of the items as the initial estimate of the true ranking. Then the algorithm scans one-by-one over the pairs with adjacent items in the initial estimated ranking. If a pair can be flipped (that is, if the ranking after flipping this pair is also a topological ordering), we uniformly sample a pair of scores for these two items from the cardinal observations $\mathcal{Y}$, and use the randomized estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ to determine the relative order of the pair. After $\widetilde{\pi}_{\text{can}}^{\text{our}}$ is called, the positions of this pair are finalized. We remove all scores of these two reviewers from future use, and jump to the next pair that does not contain these two items.

The following theorem now presents the main result of this section.

Suppose that the true ranking $\pi^{*}$ is drawn uniformly at random from the collection of all possible rankings, and consider any ordinal estimator $\widehat{\pi}_{\text{rank}}$ for $\pi^{*}$. Then the cardinal estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}$ strictly uniformly dominates the ordinal estimator $\widehat{\pi}_{\text{rank}}$.

We note that Algorithm 1 runs in polynomial time (in the number of items $n$) because the two major operations of this estimator – finding a topological ordering, and checking if a ranking is a topological ordering on the DAG – can be implemented in polynomial time [DPV08]. Theorem 5 thus demonstrates again the power of the canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ as a plug-in component to be used in a variety of applications. An extension of our results to the setting where $\pi^{*}$ can be arbitrary (adversarially chosen) is presented in Appendix C.

Simulations

We now present simulations to evaluate various points on the bias-variance tradeoff. For A/B testing, we compare our estimator $\widetilde{\pi}^{\text{our}}_{\text{ab}}$ with other standard estimators — the sign, mean and median estimators introduced in Section 3.2. The item values $x_{1}$ and $x_{2}$ are chosen independently and uniformly at random from the interval $$. The calibration functions are linear and given by:

One biased reviewer: One reviewer gives an abnormally (high or low) score. Formally, $f_{j}(x)=x$ for $j\in[m-1]$, and $f_{m}(x)=x+m$.

Incremental biases: Calibration functions of reviewers are shifted from each other. Formally, $f_{j}(x)=x+j$ for $j\in[m]$.

Incremental biases with one biased reviewer: A combination of setting 1 and setting 2. Formally, $f_{j}(x)=x+(j-1)$ for $j\in[m-1]$, and $f_{m}(x)=x+\frac{m(m-1)}{2}$.

We simulate and compute the relative improvement of the different estimators as compared to the random-guessing estimator $\widehat{\pi}_{\text{ab}}$. The results are shown in Figure 1. While the performance of the estimators vary with respect to each other, our estimator consistently beats the baseline whereas every other estimator fails. Our estimator thus indeed operates at a unique point on the bias-variance tradeoff with a low (zero) bias and a variance strictly smaller than the ordinal estimators, whereas all other estimators incur a non-zero error due to bias.

2 Ranking

Next, we evaluate the performance of our ranking estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}$ when the true ranking $\pi^{*}$ is drawn from a uniform prior. We compare this estimator with an optimal ordinal estimator $\widehat{\pi}_{\text{rank}}$ which outputs a topological ordering with ties broken in order of the indices of the items (this ordinal estimator is optimal regardless of the tie-breaking strategy).

For any number of items $n$, we generate the values $x_{1},\ldots,x_{n}$ of the items i.i.d. uniformly from the interval $[0,n]$. We set $m=\lfloor\frac{1}{2}{n\choose 2}\rfloor$. We assume that the $j^{th}$ reviewer has a linear calibration function $f_{j}(x)=k_{j}x+b_{j}$, where we sample $k_{j}$ and $b_{j}$ i.i.d. uniformly from the interval $$.

We have previously proved that our estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}$ based on cardinal data can strictly uniformly outperform the optimal ordinal estimator for the 0-1 loss. We use these simulations to evaluate the efficacy of our approach for a different loss function – Kendall-tau distance. Specifically, Figure 2 compares these two estimators in terms of Kendall-tau distance (Appendix B provides a formal definition of this distance and associated theoretical results). We observe that our estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}$ is able to consistently yield improvements even for this loss. The reason that the improvement becomes smaller when the number of items is large is that by flipping pairs, our estimator only modifies the ranking in the neighborhood of the initial estimate. We strongly believe that it should be possible to design better estimators for the large $n$ regime using the tools developed in this paper. Having met our stated goal of outperforming ordinal estimators to handle arbitrary miscalibrations, we leave this interesting problem for future work.

3 Tradeoff between estimation under perfect calibration vs. miscalibration

Figure 3 shows the relative improvement of our estimator over the random-guessing baseline under perfect calibration and under miscalibration, where $\gamma$ increases from left to right. Let us focus on a few regimes in this plot. First, on the left end of the curve, when $\gamma$ is close to $0$, we have $w(x)$ close to $0$. The estimator is close to random-guessing. At the other extreme, on the right end of the curve, when $\gamma$ goes to infinity, we have $w(x)$ close to $1$. The estimator always outputs the item with the higher score, and hence gives perfect estimation under perfect calibration. Under miscalibration, this estimator always chooses the biased reviewer giving the higher score and hence performs the same as random guess. Past the maximum point of the function at approximately $(25\%,9\%)$ when $\gamma=1$, the value of the curve starts decreasing, suggesting a tradeoff of estimation accuracy under perfect calibration and under miscalibration. It is clear that points to the left of the maximum point are not Pareto-efficient, since there exist other points with the same accuracy under miscalibration but improved accuracy under perfect calibration.

We thus see that robustness under arbitrary miscalibration comes at a cost of lower accuracy under perfect calibration. Establishing a formal understanding of this tradeoff and designing estimators that are provably Pareto-efficient are important open problems.

Proofs

In this section, we present the proofs of our theoretical results.

We prove that no deterministic cardinal estimator can strictly uniformly dominate the random-guessing estimator $\widehat{\pi}_{\text{can}}$, which implies the negative result for any deterministic ordinal estimator.

Recall the notation $\widehat{i}^{(1)}=\argmax_{i\in\{1,2\}}y_{i}$ as the item receiving the higher score (with ties broken uniformly at random), and the notation $\widehat{i}^{(2)}$ as the remaining item. First, we consider a deterministic estimator that always outputs $\widehat{i}^{(1)}$ as the item whose value is greater. We call this estimator the “sign estimator”, denoted $\widehat{\pi}_{\text{sign}}$:

The proof consists of two steps. (1) We show that the sign estimator does not strictly uniformly dominate random guess. (2) Building on top of (1), we show that more generally, no deterministic estimator strictly uniformly dominates random guess.

Step 1: The sign estimator does not strictly uniformly dominate random guess.

We construct the following counterexample such that the probability of error of the sign estimator is $0.5$. We construct reviewer calibration functions such that their ranges are disjoint, that is, one reviewer always gives a higher score than the other reviewer, regardless of the items they are assigned. Then the relative ordering of the two scores does not convey any information about the relative ordering of the two items, and we show that in this case, the sign estimator has a probability of error of $0.5$. Concretely, let the item values be bounded as $x_{1},x_{2}\in(0,1)$, and let the calibration functions be $f_{1}(x)=x$ and $f_{2}(x)=x+1$. Then the score given by reviewer $2$ is higher than the score given by reviewer $1$ regardless of the item values they are assigned. The sign estimator always observes $y_{1}<y_{2}$, and outputs the item assigned to reviewer $2$ as the larger item. The assignment is either $A=(S_{1}=1,S_{2}=2)$ or $(S_{1}=2,S_{2}=1)$ with probability $0.5$ each. Under assignment $(S_{1}=1,S_{2}=2)$, the sign estimator outputs $1\prec 2$. Under assignment $(S_{1}=2,S_{2}=1)$, the sign estimator outputs $1\succ 2$. Under one (and exactly one) of the two assignments, the output of the sign estimator is correct. Hence, the probability of error of the sign estimator is $0.5$.

Step 2: No deterministic estimator strictly uniformly dominates random guess.

The two steps above complete the proof that there exists no deterministic estimator that strictly uniformly dominates random guess.

2 Proof of Theorem 2

In what follows, we prove that the probability of success of our estimator is strictly greater than $0.5$ under arbitrary item values $x_{1},x_{2}$ and arbitrary calibration functions $f_{1},f_{2}$. We start with re-writing our estimator in (2) into an alternative and equivalent expression, and then prove the result on this new expression of our estimator.

Recall that $\widehat{i}^{(1)}=\argmax_{i\in\{1,2\}}y_{i}$ denotes the item receiving the higher score, and $\widehat{i}^{(2)}$ denotes the remaining item (with ties broken uniformly). Depending on the relative ordering of $y_{1}$ and $y_{2}$, we can split (2) into the following three cases:

Without loss of generality, assume $x_{1}>x_{2}$. The assignment is either $a:=(S_{1}=1,S_{2}=2)$ or $a^{\prime}:=(S_{1}=2,S_{2}=1)$ with probability $0.5$ each. Thus, the estimator observes $\{y_{1}=f_{1}(x_{1}),y_{2}=f_{2}(x_{2})\}$ under assignment $a$, or $\{y_{1}=f_{2}(x_{1}),y_{2}=f_{1}(x_{2})\}$ under assignment $a^{\prime}$. The probability of success of our estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ is:

where step (i) is true by plugging in (5), and step (ii) is true because $\widetilde{w}(x)+\widetilde{w}(-x)=1$ by the definition of the function $\widetilde{w}$ in (4).

3 Proof of Theorem 3

We construct a counterexample on which the mean, median and sign estimators have a probability of error of $0.5$. In this counterexample, let the item values be bounded as $x_{1},x_{2}\in(0,1)$, and let the $m$ reviewer calibration functions be as follows:

In these calibration functions, the score provided by each reviewer is the sum of the true value of the item assigned to this reviewer, and a bias term specific to this reviewer. The analysis is performed separately for the three estimators. At a high level, the analysis for the mean estimator uses the fact that one reviewer (specifically, reviewer $m)$ has a significantly greater bias than the rest of the reviewers. The analysis for the median and the sign estimators uses the fact that the ranges of these calibration functions are disjoint.

Mean estimator: Recall that each reviewer is assigned one of the two items. Given any assignment, consider the item assigned to reviewer $m$. Trivially, the sum of the scores for this item must be strictly greater than $f_{m}(0)=\frac{m(m-1)}{2}$. Now consider the remaining item (not assigned to reviewer $m$). The sum of the scores for the remaining item can be at most $\sum_{j=1}^{m-1}f_{j}(1)=\sum_{j=1}^{m-1}j=\frac{m(m-1)}{2}$.

From these two bounds on the sum of the scores, an item has a greater sum of scores if and only if reviewer $m$ is assigned to this item. By symmetry of the assignment, reviewer $m$ is assigned to either item with probability $0.5$. With the true ranking being either $1\succ 2$ or $1\prec 2$, the mean estimator makes an error in one of the two assignments, and this assignment happens with probability $0.5$. Hence, the mean estimator makes an error with probability $0.5$.

Median estimator and sign estimator: For the median estimator and the sign estimator, we first present an alternative view on the assignment, which is used for the analysis of both estimators. Recall that the assignment specifies $m/2$ reviewers to evaluate item $1$, drawn uniformly at random without replacement, and the remaining $m/2$ reviewers to item $2$. Equivalently, we can view this assignment as comprising the following two steps. (1) We sample uniformly at random a permutation of the $m$ reviewers, denoted as a list $(j_{1},\ldots,j_{m})$. Define $R$ and $R^{\prime}$ as the first half and second half of the reviewers in the list, $R=(j_{1},\ldots,j_{\frac{m}{2}})$ and $R^{\prime}=(j_{\frac{m}{2}+1},\ldots,j_{m})$. (2) We draw uniformly at random one of the two items, and assign the list $R$ of reviewers to this item. Then assign the list $R^{\prime}$ of reviewers to the remaining item. For each $k\in[m/2]$ , call reviewers $\{j_{k},j_{\frac{m}{2}+k}\}$ as the $k^{th}$ pair of reviewers.

For the median estimator and the sign estimator, we prove that given any arbitrary lists of reviewers $R$ and $R^{\prime}$ in Step (1) of the assignment, the randomness in Step (2) yields the probability of error of the two estimators as $0.5$.

Recall that the item values are bounded as $x_{1},x_{2}\in(0,1)$. Since the biases of any two reviewers differ by at least $1$ in Eq. (8), any reviewer $j$ gives a higher score than any other reviewer $j^{\prime}$ if and only if $j<j^{\prime}$, independent of the item values and the assignment. Formally, for any $x,x^{\prime}\in(0,1)$, and any $j,j^{\prime}\in[m]$, we have

The remaining analysis is performed separately for the median estimator and the sign estimator.

Median estimator: Denote $j_{1}^{\text{med}}$ and $j_{2}^{\text{med}}$ as the indices of the reviewers providing the (upper) median scores in the set $R_{1}$ and $R_{2}$, respectively. From (9), we have

Also from (9), the higher score in the two scores given by reviewer $j_{1}^{\text{med}}$ and $j_{2}^{\text{med}}$ is the reviewer with the larger index, $\max\{j_{1}^{\text{med}},j_{2}^{\text{med}}\}$. In Step (2) of the assignment, reviewer $j_{1}^{\text{med}}$ is assigned to item $1$ or item $2$ with equal probability. Hence, the probability of error of the median estimator is $0.5$. This proves the claim that the (upper) median estimator does not strictly uniformly dominates random guess.

We now comment on using the median function defined as the lower median, or as the mean of the two middle values. For the lower median, the same argument as above applies. Now consider the median defined as the mean of the two middle values. When $m/2$ is odd, Eq. (10) still holds, and the argument as above still applies. When $m/2$ is even, the median value may not be equal to any scores from the reviewers. We construct a counterexample where the item values are still bounded as $x_{1},x_{2}\in(0,1)$, and the calibration functions as follows:

With these calibration functions, for any $x,x^{\prime},x^{\prime\prime},x^{\prime\prime\prime}\in(0,1)$, and any $j,j^{\prime},j^{\prime\prime},j^{\prime\prime\prime}\in[m]$, we have

Using this fact, we can show that the output of this median estimator only depends on reviewer indices and the realization of Step (2), independent of the item values. The probability of error of this median estimator is also $0.5$.

Sign estimator: Denote $a$ as the assignment that reviewers in $R$ are assigned to item $1$, and denote $a^{\prime}$ as the assignment that reviewers in $R$ are assigned to item $2$. For each $k\in[m/2]$, define $v_{k}\in\{0,1\}$ as the binary value of whether the higher score in the $k^{th}$ pair of scores comes from item $1$, under assignment $a$. Set $v_{k}=1$ if the higher score comes from item $1$ and $v_{k}=0$ otherwise. Define $v^{\prime}_{k}\in\{0,1\}$ similarly under assignment $a^{\prime}$. Set $v^{\prime}_{k}=1$ if the higher score comes from item $1$, and $v^{\prime}_{k}=0$ otherwise. Inequality (9) implies that $v_{k}+v^{\prime}_{k}=1$ for any $k\in[m/2]$. Define $v=\sum_{k=1}^{m/2}v_{k}$ as the count of pairwise wins for item $1$ under assignment $a$, and define $v^{\prime}$ similarly. Then we have

The sign estimator outputs the item with more pairwise wins. That is, the sign estimator outputs item 1 under assignment $a$ if $v>m/4$, outputs item 1 under assignment $a^{\prime}$ if $v^{\prime}>m/4$, and outputs one of the two items uniformly at random if $v=m/4$ or $v^{\prime}=m/4$. When $v=v^{\prime}=m/4$, then under either assignment, the sign estimator has a tie, and hence outputs one of the two items uniformly at random. The probability of error of the sign estimator is $0.5$. Otherwise, we have $v\neq m/4$. By (11), we have either $v>m/4>v^{\prime}$ or $v^{\prime}>m/4>v$. The sign estimator gives different outputs under the two assignments, out of which one and only one output is correct. The probability of error of the sign estimator is $0.5$.

4 Proof of Theorem 4

Recall that a subset of $m/2$ reviewers, drawn uniformly at random without replacement, are assigned to item $1$, and the remaining $m/2$ reviewers are assigned to item $2$. We provide an alternative and equivalent view of the assignment as the following two steps:

We sample two reviewers, uniformly at random without replacement, as the first pair of reviewers for the two items, and call them $\{j_{1},j_{1}^{\prime}\}$. Then sample two reviewers, uniformly at random without replacement, from the remaining $(m-2)$ reviewers as the second pair of reviewers for the two items, and call them $\{j_{2},j^{\prime}_{2}\}$. Continue until all $m$ reviewers are exhausted, and call the subsequent pairs of reviewers $\{j_{3},j^{\prime}_{3}\},\ldots,\{j_{m/2},j^{\prime}_{m/2}\}$.

Within each pair, assign the pair of reviewers to the two items uniformly at random. That is, for each $k\in[m/2]$, assign reviewer $j_{k}$ to one of the two items uniformly at random, and assign reviewer $j_{k}^{\prime}$ to the remaining item. The assignments are independent across pairs.

Denote $\lambda(x_{1},x_{2},\{f,f^{\prime}\})$ as the probability that our canonical estimator in Eq. (2) gives the correct output comparing items of values $x_{1},x_{2}$ under reviewer calibration functions $f,f^{\prime}$. In Step (2) of the assignment procedure described above, for any $k\in[m/2]$, consider the $k^{th}$ pair of reviewers, $\{j_{k},j_{k}^{\prime}\}$. Suppose that the calibration functions of these two reviewers are denoted as $\{f,f^{\prime}\}$. By Theorem 2, since the two reviewers are assigned to the two items uniformly at random, we have

Let $\lambda_{\text{min}}$ denote the probability of success of our canonical estimator when run on the worst pair of calibration functions among all pairs of reviewers

where inequality (i) is true because of Eq. (12), and because the number of reviewers $m$ is finite.

Now assume that we are given any arbitrary realization of Step (1) of the assignment. For each $k\in[m/2]$, define $V_{k}\in\{0,1\}$ as the indicator variable of the correctness of our canonical estimator on the $k^{th}$ pair of scores. We set $V_{k}=1$ if the canonical estimator gives the correct output on the $k^{th}$ pair, and $0$ otherwise. Then $V_{k}$ is a Bernoulli random variable with mean $\lambda(x_{1},x_{2},\{f_{j_{k}},f_{j_{k}^{\prime}}\})\geq\lambda_{\text{min}}$. Moreover, since Step (2) of the assignment is performed independently across all pairs, the variables $\{V_{j}\}_{j=1}^{k}$ are independent given the item values and Step (1) of the assignment.

Let $V=\sum_{j=1}^{m/2}V_{j}$ be the number of pairs for which the canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ gives the correct output. Define a binomial random variable $B$ with $k$ trials and the success probability parameter $\lambda_{\text{min}}$. Then the random variable $V$ stochastically dominates the random variable $B$. Recall that our estimator breaks ties uniformly at random. The probability of success of our estimator with the majority-voting procedure is then bounded as

where inequality (i) is true because the success probability parameter $\lambda_{\text{min}}$ of the binomial variable is strictly greater than $\frac{1}{2}$.

We complete the proof that the probability of success of our estimator is strictly greater than $0.5$ uniformly on any item values $x_{1},x_{2}$ and any permissible calibration functions $\{f_{j}\}_{j=1}^{m}$.

5 Proof of Theorem 5

We first provide a high-level description of the proof. We call a pair of items “flippable”, if Algorithm 1 uses the canonical estimator to decide the relative ordering of this pair (that is, the if-condition in Line 1 in Algorithm 1 is true). Note that a “flippable” pair may or may not be flipped by the algorithm, as the outcome depends on the output of the canonical estimator. In Theorem 2, we show that our canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ predicts the relative ordering of a pair of items correctly with probability strictly greater than $0.5$. The main idea of the proof is to apply Theorem 2 to each flippable pair. Then we show that an improvement on the probability of correctness on these flippable pairs translates to an improvement on the probability of success of exact recovery.

Theorem 2 requires that within each pair, the two reviewers are assigned the two items uniformly at random. To be able to apply this theorem, we separate the different sources of randomness in the joint procedure of the assignment and the algorithm. We derive an equivalent algorithm by re-ordering the steps of Algorithm 1, so that in this equivalent algorithm, given any flippable pair of items and two reviewers evaluating this pair, the last sources of randomness comes from the random assignment of the two reviewers to the two items within this pair.

We introduce some additional notation for our re-ordered algorithm. Recall the notation of $A=(S_{1},\ldots,S_{m})$ for the reviewer assignment, where $S_{j}$ is a pair of items assigned to reviewer $j$ for each $j\in[m]$. Denote $\mathcal{Q}=\{\widetilde{S}_{j}\}_{j=1}^{m}$ as the same $m$ pairs of items, but the reviewer assigned to each pair $\widetilde{S}_{j}$ is unspecified. Now we present an equivalent joint procedure of the assignment and the cardinal estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}$ in Algorithm 2. In what follows, we provide a high-level summary of Algorithm 2:

Line 2-2: We sample $m$ pairwise comparisons of the items, drawn uniformly at random without replacement from the ${n\choose 2}$ pairs. Obtain an initial estimate $\widehat{\pi}$ of the ranking, by computing a topological ordering on the graph $\mathcal{G}(\mathcal{B})$.

Line 2-2: Store the positions of all flippable pairs (if any) determined by Algorithm 1. If an item is included in some flippable pair, then this item is matched to a distinct pairwise comparison in $\mathcal{Q}$. Store the matching between the items in flippable pairs and the pairwise comparisons.

Line 2: For the two pairwise comparisons associated with each pair of flippable items, sample two reviewers uniformly at random without replacement to evaluate the two comparisons.

Line 2-2: Within each flippable pair, assign the two reviewers to the two items uniformly at random.

Line 2-2: Run the canonical estimator on each flippable pair, and flip the pair if the canonical estimator decides to do so (Line 2-2). After all flippable pairs are examined, output the final ranking $\widehat{\pi}$.

We now briefly discuss the equivalence of Algorithm 2 to Algorithm 1. We first discuss the equivalence of the assignment procedures in the two algorithms, and then the estimation aspect in the next paragraph. The assignment consists of Steps 1, 3 and 4a. Recall that the assignment in Algorithm 1 samples $m$ pairwise comparisons, uniformly at random without replacement, to assign to the $m$ reviewers. In Algorithm 2, this assignment is decomposed into the choice of pairwise comparisons, the choice of a pair of reviewers to two pairwise comparisons in each flippable pair, and the assignment within each flippable pair, corresponding to Steps 1, 3 and 4a, respectively. Note that only the selected pairwise comparison for each item within some flippable pair is used for Algorithm 2, so we do not need to specify the assignment of the reviewers for the rest of the comparisons. This re-ordering of the assignment is equivalent to Algorithm 1.

The cardinal ranking estimator consists of the rest of the steps, namely Steps 2 and 4b. In the original presentation of the estimator in Algorithm 1, the estimator scans through the items, identifies flippable pairs, calls the canonical estimator on each flippable pair, and flips the pairs accordingly. Note that the identification of flippable pairs does not need the assignment of reviewers or the scores from the reviewers, so Algorithm 2 first scans through the items and identifies all flippable pairs, without using the choice of the reviewers in the assignment or using the scores from the reviewers. Then Algorithm 2 calls the canonical estimator on each flippable pair once the choice of the reviewers and the scores are determined, and flips each pair based on the corresponding output from the canonical estimator. Note that when checking for a flippable pair (the if-condition in Line 1 in Algorithm 1 and Line 2 in Algorithm 2), Algorithm 1 checks whether the flipped ranking $\widehat{\pi}_{\text{flip}}$ is a topological ordering, where the previous flippable pairs in $\widehat{\pi}_{\text{flip}}$ may have already been flipped. In Algorithm 2, the previous flippable pairs are identified but are not flipped. However, whether the flipped ranking $\widehat{\pi}_{\text{flip}}$ is a topological ordering is independent of whether the previous flippable pairs in $\widehat{\pi}_{\text{flip}}$ are flipped. Hence, the identification of the flippalbe pairs is equivalent in the two algorithms. The re-ordering of the steps of the cardinal estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{our}}$ is valid.

Having now established the equivalence of Algorithm 2 to Algorithm 1, we now prove Theorem 5 with respect to Algorithm 2. Let us denote ${\widetilde{\pi}}_{\text{rank}}^{\text{eq}}$ as the cardinal estimator in Algorithm 2. Denote $\topo(\mathcal{B})$ as the set of all topological orderings on the directed graph $\mathcal{G}(\mathcal{B})$ induced by the set of ordinal observations $\mathcal{B}$. We denote a random variable $T(\mathcal{B}):=\lvert\topo(\mathcal{B})\rvert$ as the number of such topological orderings. Note that the definition of flippable pairs carries over from Algorithm 1 to Algorithm 2. We denote a random variable $L$ as the number of flippable pairs in Algorithm 2.

Let us first consider the probability of success of the ordinal estimator. The following lemma describes the posterior distribution of the true ranking conditioned on the set of ordinal observations $\mathcal{B}$. Using this posterior distribution, the optimal ordinal estimators and their probability of success are derived.

(a) Given any possible set of ordinal observations $\beta$, the posterior distribution of the true ranking $\pi^{*}$ is uniformly distributed over the $T(\beta)$ topological orderings:

(b) Any ordinal estimator $\widehat{\pi}_{\text{rank}}^{\text{opt}}$ is optimal for the 0-1 loss, if and only if given any set of ordinal observations $\beta$, the output of this ordinal estimator belongs to the $T(\beta)$ topological orderings with probability $1$, that is, if and only if

Moreover, conditioned on the set of ordinal observations $\beta$, the probability of success of any optimal ordinal estimator $\widehat{\pi}_{\text{rank}}^{\text{opt}}$ is

See Section 5.5.1 for the proof of the lemma.

Now consider the probability of success of our cardinal estimator ${\widetilde{\pi}}_{\text{rank}}^{\text{eq}}$ from Algorithm 2. We write the probability of success of our cardinal estimator as

We have the number of flippable pairs $L=0$ either if there is a unique topological ordering on the graph $\mathcal{G}(\mathcal{B})$, or if in each pair of adjacent items that can be flipped without violating pairwise comparisons, at least one item in this pair does not have any score. Note that these two conditions are fully determined by the set of ordinal observations. Hence, conditioned on the set of ordinal observations $\mathcal{B}=\beta$, the event of $L=0$ is fully determined, and is independent of everything else given $\mathcal{B}$.

where $\widehat{\pi}_{\text{rank}}^{\text{opt}}$ denotes any optimal ordinal estimator. Here in (17), equality (i) is true because the event $L=0$ is fully determined by $\mathcal{B}$, and equality (ii) is true because this cardinal estimator that simply outputs a topological ordering is equivalent to an ordinal estimator that outputs the same topological ordering. From (14), this ordinal estimator is one optimal ordinal estimator.

In this case, Algorithm 2 identifies at least one flippable pair. The probability of success of our cardinal estimator is

where equality (i) is true because $L$ is independent of $\pi^{*}$ conditioned on $\mathcal{B}$. Equality (ii) is true by plugging in (13).

where $\widehat{\pi}_{\text{rank}}^{\text{opt}}$ denotes any optimal ordinal estimator. Equality (i) is true because of (15) in Lemma 1.

Plugging (17) and (19) into (16), we have

We first prove part (a) of the lemma. By Bayes rule, for any ranking $\pi\in\Pi$ and any possible set of ordinal observations $\beta$, we have

where $q$ is summed over all possible sets of $m$ pairwise comparisons. Equality (i) is true because the sampling of the set of pairwise comparisons $\mathcal{Q}$ is independent of the true ranking $\pi^{*}$.

Recall that the set of ordinal observations $\beta$ includes the pairwise comparisons and results of the relative orderings of these pairwise comparisons, whereas $q$ only includes the pairwise comparisons themselves, so $\beta$ fully determines $q$. For this term to be non-zero, the set of pairwise comparisons indicated by $\beta$ and the set of pairwise comparisons indicated by $q$ need to be identical. Hence, there is only one $q$ in the summation of (23) consistent with $\beta$, and we denote $\widetilde{q}$ as the set of pairs consistent with $\beta$. Then (23) reduces to

Combining the law of total probability with (22), (24) and (25), the posterior distribution of the true ranking is

Conditioned on the set of ordinal observations $\beta$, the posterior distribution of the true ranking is uniform over all topological ordering on the graph $\mathcal{G}(\beta)$. This completes the proof for part (a) of the lemma.

For part (b) of the lemma, we condition on any possible set of ordinal observations $\beta$. On the input $\beta$, the probability of success of any (possibly-randomized) ordinal estimator $\widehat{\pi}_{\text{rank}}$ is:

where equality (i) is true by plugging in (26). Equality (ii) is true because the output of the ordinal estimator $\widehat{\pi}_{\text{rank}}(\beta)$ on the input $\beta$ only depends on its internal randomness, and hence independent of the $\pi^{*}$ and $\mathcal{B}$. Inequality (iii) is true by the law of total probability. In particular, the equality sign in (iii) holds if and only if the output of the ordinal estimator is always a topological ordering consistent with $\beta$, that is, if and only if

Taking an expectation over all possible ordinal observations $\beta$, we have

Discussion

Breaking the barrier of using only ranking data in the presence of arbitrary (and potentially adversarial) miscalibrations, we show that cardinal scores can yield strict and uniform improvements over rankings. This result uncovers a novel, strictly-superior point on the tradeoff between cardinal scores and ordinal rankings, and provides a new perspective on this eternally-debated tradeoff. Our estimator allows for easily plugging into a variety of algorithms, thereby yielding it a wide applicability.

The results of this paper lead to several useful open problems. First, while our estimators indeed uniformly outperform ordinal estimators, in the future, a more careful design in our estimators (e.g. how to choose the function $w$ in the canonical estimator, and how to design better estimators for A/B testing and ranking) may yield even better results. Second, it is of interest to obtain statistical bounds on the relative errors of the cardinal and ordinal estimators in terms of the unknown miscalibration functions. Third, a promising direction of future research is to design estimators that achieve the guarantees of our proposed estimator under arbitrary/adversarial miscalibrations while simultaneously being able to adapt and yield stronger guarantees when the calibration functions follow one of the popular simpler models of miscalibration (à la “win-win” models and estimators in prior work [Sha17, Part I] [HSRW16, SBW16, SBGW17, SBW18, SW18]). Fourth, although we consider the rating scales as continuous intervals, it is not hard to see that our results extend to discrete scales (but with the strict inequality in Equation (1) sometimes replaced by a non-strict inequality to account for ties). Using our results to guide the choice of the scale used for elicitation is an open problem of interest. And finally, practical applications such as peer-review do not suffer from the problem of miscalibration in isolation. It is a useful and challenging open problem to address miscalibration simultaneously with other issues such as noise [SSS18], subjectivity [NSP18], strategic behavior [XZSS18] and others.

Acknowledgments

This work was supported in parts by NSF grants CRII: CIF: 1755656 and CCF: 1763734. The authors thank Bryan Parno for very useful discussions on biases in conference peer review. The authors thank Pieter Abbeel for pointing out the related work on the two-envelope problem.

References

Appendix A Noisy data

In this section, we show that even when the scores given by the reviewers are noisy, our estimator in (2) continues to strictly uniformly dominate random guessing in the canonical setting (Section 3.1). We focus on the canonical estimator.

In the noisy setting, when reviewer $j\in[m]$ evaluates item $i\in[n]$, the reported score is

where $\epsilon_{ij}$ is a noise term. We assume that the noise terms $\{\epsilon_{ij}\}_{i\in[n],j\in[m]}$ are drawn i.i.d. from an unknown distribution. In this setting of noisy reported scores, we modify Definition 1 of strict uniform dominance, and let the expectation include the randomness in the noise.

The following theorem establishes the strict uniform dominance in the noisy setting for the cardinal estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ in (2) (cf. Theorem 2 for the noiseless setting).

The canonical estimator $\widetilde{\pi}_{\text{can}}^{\text{our}}$ strictly uniformly dominates the random-guessing estimator $\widehat{\pi}_{\text{can}}$ in the presence of noise.

Observe that this result is quite general, since the noise distribution can be arbitrary and unknown. The remainder of this section is devoted to the proof of Theorem 6.

The proof is a slight modification to the proof of Theorem 2, so we only highlight the difference.

Recall that $\epsilon_{ij}$ denotes the noise in the reported score of reviewer $j\in\{1,2\}$ for item $i\in\{1,2\}$. In Eq. (6) from the proof of Theorem 2, we replace all the noiseless terms $f_{j}(x_{i})$ by the noisy terms $f_{j}(x_{i})+\epsilon_{ij}$ for each $i\in\{1,2\}$ and $j\in\{1,2\}$. Using the fact that the noise terms are independent of everything else, and taking an expectation over all the noise terms, we have

where step (i) uses linearity of expectation with a change of variable names, as the noise terms $\epsilon_{ij}$ are i.i.d.

Without loss of generality, assume $x_{1}>x_{2}$. Recall from the proof of Theorem 2 that $f_{1}(x_{1})-f_{2}(x_{2})>f_{1}(x_{2})-f_{2}(x_{1})$, and therefore we have the deterministic inequality

Using the monotonicity of $\widetilde{w}$, we have

Taking an expectation over $\epsilon_{1}$ and $\epsilon_{2}$ in (31) and combining with (30) gives

Appendix B Ranking under Kendall-tau and Spearman’s footrule distance

In addition to the 0-1 exact recovery loss considered in Theorem 5, Kendall-tau distance and Spearman’s footrule distance are also common metrics for ranking. Recall that a ranking of $n$ items is defined by a function $\pi:[n]\rightarrow[n]$, such that $\pi(t)$ is the index of the $t^{th}$ ranked item for each $t\in[n]$. Equivalently, we can define a ranking by the function $\sigma:[n]\rightarrow[n]$, such that $\sigma(i)$ is the rank of each item $i\in[n]$. With this notation, we have the relation $\sigma=\pi^{-1}$.

The Kendall-tau distance and the Spearman’s footrule distance are usually defined in terms of the ranking $\sigma$. Hence for consistency with these definitions, throughout this section we focus on the rankings as defined by $\sigma$ (instead of $\pi$ as done throughout the remainder of the paper). Kendall-tau distance and Spearman’s footrule distance between any two rankings $\sigma_{1}$ and $\sigma_{2}$ of $n$ items are defined as:

The following theorem states that given any arbitrary ordinal estimator, there exists a cardinal estimator that performs strictly uniformly better than this ordinal estimator, simultaneously on Kendall-tau distance and Spearman’s footrule distance (cf. Theorem 5 for 0-1 loss).

Suppose that the true ranking $\sigma^{*}$ is drawn uniformly at random from the collection of all possible rankings. For any arbitrary ordinal estimator $\widehat{\sigma}_{\text{rank}}$, there exists a cardinal estimator with access to one call to the ordinal estimator $\widehat{\sigma}_{\text{rank}}$ that strictly uniformly dominates the ordinal estimator $\widehat{\sigma}_{\text{rank}}$ with respect to Kendall-tau distance and Spearman’s footrule distance. The computatinal complexity of this cardinal estimator is polynomial in the number of items $n$, in addition to the time taken by one call to the ordinal estimator $\widehat{\sigma}_{\text{rank}}$.

This result demonstrates the generality of our results in the main text with respect to various (not only 0-1) loss functions. The remainder of this section is devoted to the proof of Theorem 7.

For any item $i\in[n]$ and any possible set of ordinal observations $\mathcal{B}$, we define the following sets:

In words, $V^{+}(i,\mathcal{B})$ is the set of items that are ranked higher than item $i$ according to the set of ordinal observations $\mathcal{B}$, and $V^{-}(i,\mathcal{B})$ is the set of items that are ranked lower than item $i$. For any topologically-identical pair $(i,i^{\prime})$, we have $V^{+}(i,\mathcal{B})=V^{+}(i^{\prime},\mathcal{B})$ and $V^{-}(i,\mathcal{B})=V^{-}(i^{\prime},\mathcal{B})$, so we denote $V^{+}(i,i^{\prime},\mathcal{B}):=V^{+}(i,\mathcal{B})$ and $V^{-}(i,i^{\prime},\mathcal{B}):=V^{-}(i,\mathcal{B})$. Now we present a cardinal estimator ${\widetilde{\sigma}}_{\text{rank}\text{-metric}}^{\text{our}}$ in Algorithm 3.

In words, Algorithm 3 obtains an initial estimated ranking $\widehat{\sigma}_{\text{init}}$ by making one call to the given ordinal estimator $\widehat{\sigma}_{\text{rank}}$. Then Algorithm 3 identifies two items that are topologically-identical. If such a topologically-identical pair $(i,i^{\prime})$ exists, we perform the following two steps on this topologically-identical pair:

Line 3-3: We sample uniformly at random a score for each item in the topologically-identical pair $(i,i^{\prime})$. Based on this pair of scores, we call the canonical estimator to decide the relative ordering of these two items. Depending on the outcome of the canonical estimator, we keep the relative ordering of these two items unchanged, or flip the two items accordingly.

This completes the description of the cardinal estimator ${\widetilde{\sigma}}_{\text{rank}\text{-metric}}^{\text{our}}$.

We now show that the cardinal estimator ${\widetilde{\sigma}}_{\text{rank}\text{-metric}}^{\text{our}}$ takes polynomial time in the number of items $n$, in addition to the time taken by one call to the given ordinal estimator $\widehat{\sigma}_{\text{rank}}$. To check if a pair of items $(i,i^{\prime})$ is topologically-identical, it takes polynomial time to go through the pairwise comparisons in $\mathcal{B}$. Hence, it takes polynomial time to identify a topologically-identical pair (or determine that such a pair does not exist). For any topologically-identical pair, in the re-arranging step, the set $V^{-}(i,i^{\prime},\mathcal{B})$ can be found by a graph traversal from node $i$. The set $V^{+}(i,i^{\prime},\mathcal{B})$ can be found by a graph traversal from node $i$ on the graph $\mathcal{G}(\mathcal{B})$ but with all edges reversed. Both traversals take polynomial time. Hence, Algorithm 3 takes polynomial time, in addition to one call to the ordinal estimator $\widehat{\sigma}_{\text{rank}}$.

For Spearman’s footrule dsitance, for each item $i\in[n]$, we call the term $\lvert\sigma_{1}(i)-\sigma_{2}(i)\rvert$ as Spearman’s footrule distance between $\sigma_{1}$ and $\sigma_{2}$ contributed by item $i$.

We first analyze the re-arranging step in Line 3-3 of Algorithm 3. We denote the random variable $\widehat{\sigma}_{\text{re}}$ as the estimated ranking after the re-arranging step (that is, the value of the quantity $\widehat{\sigma}$ after Line 3 of Algorithm 3). The re-arranged ranking $\widehat{\sigma}_{\text{re}}$ is a deterministic function of the initial ranking $\widehat{\sigma}_{\text{init}}$. The following lemma proves a deterministic result about this re-arranging step.

For any true ranking $\sigma^{*}$, any set of ordinal observations $\mathcal{B}$ consistent with the true ranking, and any initial estimated ranking $\widehat{\sigma}_{\text{init}}$, the re-arranged ranking $\widehat{\sigma}_{\text{re}}$ yields smaller or equal loss compared to the initial ranking $\widehat{\sigma}_{\text{init}}$, regarding Kendall-tau distance and Spearman’s footrule distance. That is,

The lemma is proved at the end of this section.

Now we turn to analyze the second step of calling the canonical estimator on the topologically-identical pair. This step starts from the re-arranged ranking $\widehat{\sigma}_{\text{re}}$. Denote $E$ as the event that Algorithm 3 identifies some topologically-identical pair (that is, Line 3-3 of Algorithm 3 is executed). Then $E^{c}$ denotes the event that no topologically-identical pair is found. If there exists no topologically-identical pairs, then the second step in Line 3-3 of Algorithm 3 is never executed. Trivially, the final output ${\widetilde{\sigma}}_{\text{rank}\text{-metric}}^{\text{our}}$ is identical to the re-arranged ranking $\widehat{\sigma}_{\text{re}}$. We have

It remains to consider the case when the event $E$ is true. We start by showing that the event $E$ happens with non-zero probability. Consider any arbitrary true ranking $\sigma^{*}$. Under this true ranking, denote the top item as $i^{(1)}$, and denote the second-ranked item as $i^{(2)}$. Conditioned on this true ranking, consider the set of pairwise comparisons $\mathcal{Q}$ such that the set $\mathcal{Q}$ includes comparisons between item $i^{(1)}$ and a subset of $\min\{\lfloor m/2\rfloor,n-2\}$ items from $[n]\setminus\{i^{(1)},i^{(2)}\}$. Assume that $\mathcal{Q}$ also includes comparisons between item $i^{(2)}$ and the identical subset of items from $[n]\setminus\{i^{(1)},i^{(2)}\}$. The rest of the comparisons can be arbitrary between the $(n-2)$ items in $[n]\setminus\{i^{(1)},i^{(2)}\}$. Recall that $1<m<{n\choose 2}$, so such a set $\mathcal{Q}$ arises with non-zero probability. Hence, the event $E$ happens with non-zero probability.

Consider the ranking $\widehat{\sigma}_{\text{re}}$ from the re-arranging step. We have

where equality (i) is true because $\sigma^{*}$ is independent of $E$ conditioned on $\mathcal{B}$. Equality (ii) is true because of (13) in Lemma 1.

Recall that the initial ranking $\widehat{\sigma}_{\text{init}}$ is obtained by calling the (possibly randomized) ordinal estimator $\widehat{\sigma}_{\text{rank}}$ taking input $\mathcal{B}$, and the re-arranged ranking $\widehat{\sigma}_{\text{re}}$ is fully determined by $\widehat{\sigma}_{\text{init}}$. Hence, we further write (36) as

where equality (i) is true, because $\widehat{\sigma}_{\text{rank}}$ is independent of the true ranking $\sigma^{*}$ and the event $E$ conditioned on $\mathcal{B}$. Hence, $\widehat{\sigma}_{\text{re}}$ is independent of the true ranking $\pi^{*}$ and the event $E$ conditioned on $\mathcal{B}$.

Define the set $\Omega_{i\succ i^{\prime}}\subseteq\topo(\beta)$ as the collection of topological orderings where $i$ is ranked higher than $i^{\prime}$. Define the set $\Omega_{i\prec i^{\prime}}\subseteq\topo(\beta)$ as the collection of topological orderings where $i$ is ranked lower than $i$. Then $\{\Omega_{i\succ i^{\prime}},\Omega_{i\prec i^{\prime}}\}$ is a partition of the collection of all topological orderings, $\topo(\beta)$. Given that the pair $(i,i^{\prime})$ is topologically-identical, for any ranking $\sigma\in\topo(\beta)$, we can flip items $(i,i^{\prime})$, and the flipped ranking is still a topological ordering. Flipping the items $(i,i^{\prime})$ defines a bijection between the set $\Omega_{i\succ i^{\prime}},\Omega_{i\prec i^{\prime}}$, so we have $\lvert\Omega_{i\prec i^{\prime}}\rvert=\lvert\Omega_{i\prec i^{\prime}}\rvert$. Any ranking $\widehat{\sigma}_{\text{re}}$ is correct on one and only one of the sets $\Omega_{i\succ i^{\prime}}$ and $\Omega_{i\prec i^{\prime}}$, and hence the re-arranged ranking $\widehat{\sigma}_{\text{re}}$ is correct on exactly half of the topological orderings. For any $\widehat{\sigma}$, we have

Now consider the cardinal estimator. Similar to the proof of Theorem 5, we have

Finally, combining (43) with inequality (34a) for the re-arranging step completes the proof for Kendall-tau distance.

Now we analyze the Spearman’s footrule distance conditioned on the event $\sigma^{*}\in\{\sigma_{i\succ i^{\prime}},\sigma_{i\prec i^{\prime}}\}$. Using the argument deriving (39), we can further derive

By the rearrangement inequality (33), if the relative ordering of the pair $(i,i^{\prime})$ is correct, then Spearman’s footrule distance does not increase compared to the ranking with the relative ordering of $(i,i^{\prime})$ incorrect. Eq. (46) implies that conditioned on $\beta$, the event $E$ and the event of $\sigma^{*}\in\{\sigma_{i\succ i^{\prime}},\sigma_{i\prec i^{\prime}}\}$, the probability that the cardinal estimator ${\widetilde{\sigma}}_{\text{rank}\text{-metric}}^{\text{our}}$ gives the correct relative ordering of the pair $(i,i^{\prime})$ is higher than the probability that $\widehat{\sigma}_{\text{re}}$ gives the correct relative ordering. Hence, for any set of ordinal observations $\beta$ and any pair $\{\sigma_{i\succ i^{\prime}},\sigma_{i\prec i^{\prime}}\}$ of the true rankings, we have

Note that directly applying the re-arrangement inequality does not translate the strict inequality from (39) to (47). The reason is that correctly ordering a topologically-identical pair does not guarantee strictly smaller Spearman’s footrule distance. For example, if item $i$ and item $i^{\prime}$ are the top-$2$ items in the true ranking, but are the bottom-$2$ items in $\widehat{\sigma}_{\text{re}}$. Then the relative ordering of the pair $(i,i^{\prime})$ does not change the Spearman’s footrule distance. In the rearrangement inequality (33), strictly inequality holds if $a_{1}\leq\{b_{1},b_{2}\}\leq a_{2}$. Hence, we find one pair of true rankings $\{\sigma^{*}_{i\succ i^{\prime}},\sigma^{*}_{i\prec i^{\prime}}\}$ such that one of the following is true:

Then strictly inequality in (46) holds on the pair $\{\sigma^{*}_{i\succ i^{\prime}},\sigma^{*}_{i\prec i^{\prime}}\}$. Now we provide the construction of this pair $\{\sigma^{*}_{i\succ i^{\prime}},\sigma^{*}_{i\prec i^{\prime}}\}$.