PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jingyan Wang, Nihar B. Shah

arXiv:1806.05085v2stat.MLcs.AIcs.ITcs.LGmath.IT

TL;DR

Cardinal scores provided by different people can be incomparable, making human ratings difficult to compare. The paper constructs cardinal estimators for arbitrary, potentially adversarial miscalibrations, requiring only consistency with the induced rankings. The cardinal estimators strictly and uniformly outperform estimators that use only induced rankings.

  • Problem

    Cardinal scores provided by different people can be incomparable, making human ratings difficult to compare.

    Source: §1 · p. 1

  • Method

    The paper constructs cardinal estimators for arbitrary, potentially adversarial miscalibrations, requiring only consistency with the induced rankings.

    Source: §1 · p. 2

  • Results

    The cardinal estimators strictly and uniformly outperform estimators that use only induced rankings.

    Source: §1 · p. 2, §6 · p. 22

  • Takeaways & Limitations

    The estimators can be plugged into algorithms for varied applications, with proof-of-concept applications in A/B testing and ranking.

    Source: §1 · p. 2, §6 · p. 22

    Some microtasks may not fit the setting because ratings may be inconsistent with ordinal rankings and rankings can be easier and faster to provide.

    Source: §1 · p. 3

Abstract

from arXiv · show

Cardinal scores (numeric ratings) collected from people are well known to suffer from miscalibrations. A popular approach to address this issue is to assume simplistic models of miscalibration (such as linear biases) to de-bias the scores. This approach, however, often fares poorly because people's miscalibrations are typically far more complex and not well understood. In the absence of simplifying assumptions on the miscalibration, it is widely believed by the crowdsourcing community that the only useful information in the cardinal scores is the induced ranking. In this paper, inspired by the framework of Stein's shrinkage, empirical Bayes, and the classic two-envelope problem, we contest this widespread belief. Specifically, we consider cardinal scores with arbitrary (or even adversarially chosen) miscalibrations which are only required to be consistent with the induced ranking. We design estimators which despite making no assumptions on the miscalibration, strictly and uniformly outperform all possible estimators that rely on only the ranking. Our estimators are flexible in that they can be used as a plug-in for a variety of applications, and we provide a proof-of-concept for A/B testing and ranking. Our results thus provide novel insights in the eternal debate between cardinal and ordinal data.

1 Introduction

The paper challenges the belief that rankings are the only useful information when cardinal scores are arbitrarily miscalibrated. It argues that cardinal estimators can strictly and uniformly outperform ranking-only estimators, while identifying settings where the score-ranking consistency assumption may not fit.

1 Introduction

  • Miscalibration makes ratings from different people difficult to compare, while commonly used correction models may fail when errors are complex or samples are small.In A/B testing, a reviewer may evaluate only one item, making the problem underdetermined even under restrictive models.Source: §1 · pp. 1–2
  • The paper contests the belief that, without assumptions about miscalibration, only the induced ranking is useful.The paper frames this belief as a reason to use induced rankings or elicit rankings directly instead of scores.Source: §1 · p. 2
  • With no simplifying assumptions on miscalibration, cardinal estimators strictly and uniformly outperform every estimator using only induced rankings.The estimators can serve as plug-ins for ranking-based algorithms, with proof-of-concept applications in A/B testing and ranking.Source: §1 · p. 2
  • The proposed setting allows arbitrary, potentially adversarial reviewer miscalibrations represented by unknown monotonic functions.The estimator uses cardinal scores that remain consistent with their induced rankings.Source: §1 · p. 2
  • In the minimal-bias regime, cardinal estimators have strictly smaller variance than ordinal-only estimators, while avoiding modeling bias from simplified assumptions.The paper presents this as a new point on the bias-variance tradeoff.Source: §1 · pp. 2–3
  • The motivating scope is limited where ratings may not preserve ordinal rankings, as in some microtasks; peer review and in-person lab A/B tests motivate the setting instead.In those latter applications, reviewers spend non-trivial time and effort on evaluations.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the item-ranking problem and distinguish estimation from reviewers’ rankings versus their cardinal scores. They also formalize arbitrary monotonic miscalibration and compare estimators through strict uniform dominance under adversarial choices.

2 Preliminaries

  • Each of n items has a distinct unknown value, and reviewer j reports f_j(x_i) under an arbitrary strictly increasing calibration function.The setup assumes finite numbers of items and reviewers.Source: §2 · p. 3
  • Ordinal estimators observe reviewers’ induced rankings, whereas cardinal estimators observe their reported scores.Both settings use the reviewer-item assignment and aim to estimate the ranking induced by the true item values.Source: §2 · p. 3
  • The main-text setting is noiseless, with an extension to noisy data provided in the appendix.The noiseless observations are either scores f_j(x_i) or the rankings those scores induce.Source: §2 · p. 3
  • The adversary may choose miscalibration functions and item values subject only to inducing the specified ranking; the true ranking may be adversarially chosen or uniform at random.The framework also permits choices tailored to different realizations of the true ranking.Source: §2 · p. 3
  • Strict uniform dominance requires an estimator to incur strictly lower expected error across the allowed choices, a stronger comparison than minimax or average-case risk.The expectation can include randomness in assignment and estimators, and, for a random true ranking, its distribution.Source: §2 · p. 4
  • The main text focuses on 0-1 loss, with extensions to Kendall-tau and Spearman’s footrule distances in the appendix.Source: §2 · p. 4

3 Main results

The paper develops randomized cardinal-score estimators that outperform random guessing in a canonical two-item setting and extend as plug-ins to A/B testing. It also connects the canonical construction to the two-envelope problem and describes an algorithm for ranking multiple items.

3.1 A canonical setting

  • The canonical randomized estimator strictly uniformly dominates random guessing, and its guarantee also holds with noisy observations.The setting assigns each of two reviewers one distinct item at random, so the ordinal data is vacuous.Source: §3.1 · pp. 4–5

3.1.1 Connections to the literature

  • The canonical setting reduces to the two-envelope problem: one of two values is observed uniformly at random, and their ordering matches the items’ true ordering.The paper also relates its increasing weighting function to the two-envelope estimator’s switching function.Source: §3.1.1 · p. 5

3.2 A/B testing

  • For any even number of reviewers, sign, mean, and median estimators cannot strictly uniformly dominate random guessing, even with arbitrarily many scores.The theorem concerns A/B testing under arbitrary miscalibrations.Source: §3.2 · p. 7
  • For any even number of reviewers, the randomized A/B-testing estimator strictly uniformly dominates random guessing.The estimator applies the canonical rule to score pairs and takes a majority vote.Source: §3.2 · p. 7

3.3 Ranking

  • For multiple items, the ranking procedure starts from a topological ordering of ordinal comparisons and uses randomized cardinal comparisons to decide which adjacent items to flip.The setting has reviewers evaluate randomly selected pairs of items.Source: §3.3 · p. 7

16 end

The ranking estimator strictly uniformly dominates any ordinal estimator when the true ranking is drawn uniformly at random. The paper presents it as a plug-in component and notes that its operations can be implemented in polynomial time.

16 end

  • The algorithm starts from a topological ordering and uses the canonical randomized estimator on eligible adjacent pairs to revise the ranking.Finding a topological ordering and checking whether a ranking respects the comparison graph can be implemented in polynomial time.Source: §16 · p. 8
  • When the true ranking is drawn uniformly at random, the cardinal ranking estimator strictly uniformly dominates any ordinal estimator.The paper also notes an extension to adversarially chosen true rankings in Appendix C.Source: §16 · p. 8

4 Simulations

The simulations test proposed estimators for A/B testing and ranking, then examine the accuracy tradeoff between perfect calibration and one biased reviewer. They report gains over random or ordinal baselines alongside a robustness–accuracy cost.

4 Simulations

  • The simulations measure relative improvement over a baseline, where positive values indicate better performance, and set w(x)=x/(1+x) in the proposed estimators.Relative improvement is computed from the difference in expected losses, divided by baseline expected loss.Source: §4 · p. 8

4.1 A/B testing

  • In A/B testing, eπour consistently beats the random-guessing ordinal estimator bπab; every other estimator fails, and eπour has zero bias with variance strictly smaller than the ordinal estimators.Figure 1 averages results over 10,000 trials.Source: §4.1 · p. 9, Figure 1 · p. 9

4.2 Ranking

  • For Kendall-tau ranking, eπour_rank consistently improves on the optimal ordinal estimator, though gains shrink at large n because pair-flips alter only a neighborhood of the initial ranking.The simulations use 100 trials, with expected losses approximated over 1,000 samples.Source: §4.2 · pp. 9–10, Figure 2 · p. 10

4.3 Tradeoff between estimation under perfect calibration vs. miscalibration

  • With perfect calibration versus one biased reviewer, increasing γ trades miscalibration robustness against perfect-calibration accuracy; the maximum is about (25%, 9%) at γ=1, and points left of it are not Pareto-efficient.The experiment averages 5 × 10^5 trials; formalizing the tradeoff and designing provably Pareto-efficient estimators remain open problems.Source: §4.3 · pp. 10–11

5 Proofs

The proofs establish limits for deterministic estimators and the proposed estimator’s advantage under arbitrary item values and calibration functions, extending the pairwise argument to multi-reviewer majority voting and exact recovery. They also give an equivalent joint procedure for reviewer assignment and cardinal ranking estimation, based on sampling comparisons and identifying flippable adjacent positions.

5.1 Proof of Theorem 1

  • No deterministic estimator strictly uniformly dominates random guessing: a constructed input makes any estimator differing from the sign estimator err with probability at least 0.5.The sign estimator itself has error probability 0.5 when reviewer calibration ranges are disjoint.Source: §5.1 · pp. 11–12

5.2 Proof of Theorem 2

  • The canonical estimator has success probability strictly greater than 0.5 under arbitrary item values and arbitrary calibration functions.The proof rewrites the estimator equivalently and uses monotonicity of the calibration functions and weight function.Source: §5.2 · pp. 12–13

5.3 Proof of Theorem 3

  • The proof constructs cases where the mean estimator errs with probability 0.5, so it does not strictly uniformly beat random guessing.A reviewer with substantially greater bias determines which item has the greater score sum; the reviewer is assigned to either item with equal probability.Source: §5.3 · pp. 13–14
  • The proof constructs cases where the median and sign estimators each err with probability 0.5, so neither strictly uniformly beats random guessing.For the median defined as the mean of the two middle values, the proof also gives a counterexample with error probability 0.5.Source: §5.3 · pp. 14–15

5.4 Proof of Theorem 4

  • The estimator’s probability of success is strictly greater than 0.5 uniformly over any item values x1 and x2 and any permissible calibration functions.Source: §5.4 · p. 16

5.5 Proof of Theorem 5

  • For flippable item pairs, the proof applies the canonical estimator’s pairwise advantage and shows that it improves the probability of exact recovery.An equivalent algorithm orders the random steps so that the two reviewers evaluating a flippable pair are assigned to its items uniformly at random.Source: §5.5 · p. 16
  • The proof represents the assignment as m item pairs while leaving the reviewer assigned to each pair unspecified in its equivalent joint procedure.The procedure stores flippable positions and the associated reviewer indices.Source: §5.5 · pp. 16–17
  • The procedure samples m item pairs uniformly at random without replacement, records their ordinal comparisons, and computes an initial ranking by topologically ordering the comparison graph.Ties are broken by item indices.Source: §5.5 · pp. 16–17
  • It identifies adjacent positions as flippable when swapping their items preserves a topological ordering and both items occur in available sampled comparisons.For each such pair, the procedure randomly selects one available comparison involving each item, records the match, and removes both comparisons from the available set.Source: §5.5 · pp. 16–17

18 end

The procedure samples reviewer pairs for adjacent item pairs, assigns one reviewer to each pair, collects scores, and defines a ranking obtained by flipping adjacent positions.

18 end

  • For each adjacent pair [eS_t, eS_t+1] in reviewer_indices, sample a pair of reviewers uniformly at random without replacement.Source: §18 · p. 17
  • Assign the two sampled reviewers uniformly at random to the two pairs, one reviewer per pair, and obtain their corresponding scores.Source: §18 · p. 17
  • Denote the scores for the tth and (t+1)th items in eS_t as y_bπ(t) and y_bπ(t+1), respectively.Source: §18 · p. 17
  • Define bπ_flip as the ranking obtained by swapping the tth and (t+1)th positions in bπ.Source: §18 · p. 17

27 end

The cardinal estimator matches the best ordinal estimators when no pairs can be flipped and strictly improves on them for some observations with flippable pairs. The proof also characterizes the ordinal posterior and the conditions for ordinal optimality.

27 end

  • The proof establishes that Algorithm 2’s reordered reviewer assignment and identification of flippable pairs are equivalent to Algorithm 1’s procedure.Algorithm 2 identifies pairs before using reviewer assignments and scores to decide whether to flip them.Source: §27 · p. 18
  • Given ordinal observations β, the true ranking is uniformly distributed over the topological orderings consistent with β.This posterior characterization underlies the analysis of ordinal estimators.Source: §27 · p. 18, §5.5.1 · p. 21
  • An ordinal estimator is optimal exactly when it always outputs a topological ordering consistent with the observed comparisons.The condition applies to every possible observation set β with positive probability.Source: §27 · p. 18, §5.5.1 · p. 22
  • The cardinal ranking estimator’s success probability is at least that of any optimal ordinal estimator for every case, and strictly greater for some cases.The proof establishes this for the equivalent Algorithm 2 and Algorithm 1 estimators.Source: §27 · pp. 19–20
  • For ℓ flippable pairs, independent random reviewer assignments let the canonical estimator recover all pair orderings with probability greater than 1/2^ℓ.The algorithm uses those pairwise decisions to determine its final ranking.Source: §27 · pp. 17, 19

6 Discussion

The discussion argues that cardinal scores can strictly and uniformly improve on rankings despite arbitrary or adversarial miscalibration, and that the estimator can be plugged into other algorithms. It identifies open questions about estimator design, error bounds, and handling additional practical complications.

6 Discussion

  • Cardinal scores can yield strict, uniform improvements over rankings under arbitrary or adversarial miscalibrations, and the estimator can plug into other algorithms.The discussion presents this as a new point on the tradeoff between cardinal scores and ordinal rankings.Source: §6 · p. 22
  • Open questions include improving estimator design, bounding relative errors, and adapting to simpler calibration models while retaining guarantees under arbitrary miscalibration.The discussion gives choosing the canonical estimator’s function w as one design example.Source: §6 · p. 22
  • The results extend to discrete rating scales, sometimes with non-strict rather than strict improvement to account for ties; jointly handling noise, subjectivity, and strategic behavior remains open.The discussion also identifies choosing an elicitation scale as an open problem.Source: §6 · p. 22

A Noisy data

In the canonical setting, the appendix considers noisy reviewer scores and establishes that the cardinal estimator strictly uniformly dominates random guessing. The result allows arbitrary unknown noise distributions, with noise terms assumed i.i.d.

A Noisy data

  • With i.i.d. noise drawn from an arbitrary unknown distribution, the canonical cardinal estimator strictly uniformly dominates random guessing.The result concerns the canonical setting and modifies the expectation in the dominance definition to include noise randomness.Source: A Noisy data · p. 25

A.1 Proof of Theorem 6

The proof adapts the noiseless argument by replacing reviewer scores with noisy scores and taking expectations over the noise. Its key ordering comparison remains valid because the same noise difference is added to both sides.

A.1 Proof of Theorem 6

  • The proof replaces each noiseless score term with its noisy counterpart and takes expectations over the noise terms, which are i.i.d.The expectation is simplified by linearity and renaming variables.Source: §A.1 · p. 25
  • Adding the same noise difference to both sides preserves the score ordering, so monotonicity of the estimator’s weighting function can be applied.The proof first establishes the deterministic ordering for any two noise values.Source: §A.1 · p. 25

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

The paper extends its cardinal-over-ordinal dominance result beyond exact recovery to Kendall-tau distance and Spearman’s footrule. Theorem 7 establishes strict uniform dominance under both metrics.

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

  • For consistency with standard metric definitions, this section represents a ranking by σ, which maps each item to its rank, rather than by π, which maps rank positions to items.The two representations are inverses: σ = π^-1.Source: B Ranking under Kendall-tau and… · p. 26
  • Theorem 7 gives a cardinal estimator that strictly uniformly dominates any ordinal estimator under Kendall-tau distance and Spearman’s footrule.It uses one call to the ordinal estimator; its additional computation is polynomial in the number of items.Source: B Ranking under Kendall-tau and… · p. 26
  • The result extends the paper’s dominance findings beyond the 0-1 exact-recovery loss to other ranking metrics.The section identifies Kendall-tau distance and Spearman’s footrule distance as the metrics considered.Source: B Ranking under Kendall-tau and… · p. 26

B.1 Proof of Theorem 7

The proof constructs a cardinal estimator around an initial ordinal estimate. It uses cardinal scores to refine the ordering of a pair that the ordinal observations treat identically.

B.1 Proof of Theorem 7

  • A topologically-identical pair has no direct comparison, and each item has the same comparisons and outcomes against every other item.The pair therefore shares the same sets of items ranked above and below it by the ordinal observations.Source: §B.1 · p. 26
  • Algorithm 3 starts from one call to the ordinal estimator, then searches for a topologically-identical item pair to refine using cardinal scores.The algorithm derives ordinal observations from the cardinal observations before obtaining the initial ranking.Source: §B.1 · pp. 26–27
  • For a qualifying pair with scores, the estimator samples one score for each item and flips their relative order when the sampled scores indicate a different ordering.The algorithm rearranges the pair and related items while preserving their occupied positions.Source: §B.1 · p. 27

22 end

The section analyzes the cardinal estimator and its rearrangement step under Kendall-tau distance and Spearman’s footrule, proving strict improvement over the ordinal estimator and that correcting inconsistently ordered pairs cannot increase either loss.

22 end

  • For a topologically-identical pair, the estimator samples scores and applies the canonical estimator to decide whether to retain or flip their ordering.Only the selected pair’s relative order is changed by this step.Source: §22 · pp. 27, 29
  • Algorithm 3 runs in polynomial time in the number of items, in addition to one call to the ordinal estimator.Pair identification uses pairwise comparisons, and the affected sets are found by graph traversals.Source: §22 · pp. 27–28
  • The cardinal estimator strictly improves on the ordinal estimator in expected Kendall-tau distance and Spearman’s footrule.The proof concludes strict improvement for both metrics after combining the topologically-identical-pair step with the rearrangement step.Source: §22 · pp. 28, 30, 32
  • Rearranging items using ordinal observations yields a ranking with no greater Kendall-tau or Spearman’s footrule loss than the initial ranking.The rearrangement preserves positions outside the affected sets and orders V+ above the selected pair and V− below it.Source: §22 · pp. 27–28

B.2 Proof of Lemma 2

  • When a pair is ordered inconsistently with the true ranking, flipping it does not increase Kendall-tau or Spearman’s footrule loss.This is the first part of the appendix proof of Lemma 2.Source: §B.2 · pp. 32–33
  • For each flip, the reversed pair’s Kendall-tau contribution falls from 1 to 0; contributions involving intervening items either stay equal or fall from 2 to 0.The proof considers intervening items ranked outside the flipped pair in the true ranking, or between them in the true ranking.Source: §B.2 · p. 33
  • For Spearman’s footrule, flipping changes only the contribution of the two swapped items, which the proof analyzes using the rearrangement inequality.The flip condition is that the pair’s estimated ordering is opposite to its ordering in the true ranking.Source: §B.2 · p. 33
  • The rearranging step in Algorithm 3 is equivalent to repeatedly flipping eligible pairs until none remain, and each pair can be swapped at most once.The procedure preserves the within-set ordering of V1, V2, and V3 and terminates at the ranking specified by Algorithm 3.Source: §B.2 · pp. 33–34

C Ranking under arbitrary true ranking

For an arbitrary true ranking, the paper builds a cardinal estimator on the minimax-optimal ordinal estimator and proves strict uniform dominance. The proof treats cases with zero and positive numbers of flippable pairs.

C Ranking under arbitrary true ranking

  • The construction replaces the initial-ranking step with the minimax-optimal ordinal estimator’s output.The paper states that the resulting cardinal estimator is obtained by this substitution in Algorithm 1.Source: C Ranking under arbitrary true ranking · p. 34
  • For an arbitrary true ranking, the cardinal estimator strictly uniformly dominates the minimax-optimal ordinal estimator.It can be viewed as a polynomial-time post-processing step requiring one call to that ordinal estimator.Source: C Ranking under arbitrary true ranking · p. 34

C.1 Proof of Theorem 8

  • When there are no flippable pairs, the cardinal estimator matches the ordinal estimator; with positive counts, the proof considers rankings differing only in those pairs.Those alternative rankings are all topological orderings consistent with the ordinal observations.Source: §C.1 · p. 35
Loading 1806.05085v2…