Fair Ranking under Disparate Uncertainty

Richa Rastogi, Thorsten Joachims

Abstract

Ranking is a ubiquitous method for focusing the attention of human evaluators on a manageable subset of options. Its use as part of human decision-making processes ranges from surfacing potentially relevant products on an e-commerce site to prioritizing college applications for human review. While ranking can make human evaluation more effective by focusing attention on the most promising options, we argue that it can introduce unfairness if the uncertainty of the underlying relevance model differs between groups of options. Unfortunately, such disparity in uncertainty appears widespread, often to the detriment of minority groups for which relevance estimates can have higher uncertainty due to a lack of data or appropriate features. To address this fairness issue, we propose Equal-Opportunity Ranking (EOR) as a new fairness criterion for ranking and show that it corresponds to a group-wise fair lottery among the relevant options even in the presence of disparate uncertainty. EOR optimizes for an even cost burden on all groups, unlike the conventional Probability Ranking Principle, and is fundamentally different from existing notions of fairness in rankings, such as demographic parity and proportional Rooney rule constraints that are motivated by proportional representation relative to group size. To make EOR ranking practical, we present an efficient algorithm for computing it in time $O(n \log(n))$ and prove its close approximation guarantee to the globally optimal solution. In a comprehensive empirical evaluation on synthetic data, a US Census dataset, and a real-world audit of Amazon search queries, we find that the algorithm reliably guarantees EOR fairness while providing effective rankings.

Introduction: The Problem of Disparate Uncertainty

Standard ranking algorithms, such as the Probability Ranking Principle (PRP), sort items by their estimated probability of relevance. However, this approach can be systematically unfair when the underlying model is more certain about some groups than others—a phenomenon known as disparate uncertainty.

Consider a college admissions scenario where a model has extensive data for a majority group, allowing it to assign high-confidence probabilities (e.g., 0.9). For a minority group with less data, the model might assign a flat, uncertain probability (e.g., 0.1) to all candidates. Under PRP, the majority group will dominate the top of the list, even if the minority group contains many qualified individuals who are simply "hidden" by the model's uncertainty.

Posterior distributions showing disparate uncertainty between Group A (sharp) and Group B (broad).

Equal-Opportunity Ranking (EOR)

To address this, we propose Equal-Opportunity Ranking (EOR). Unlike Demographic Parity (DP), which focuses on proportional representation, EOR aims to equalize the "cost of opportunity" across groups. A ranking satisfies EOR if, at any rank $k$, the expected fraction of relevant candidates selected from Group A is approximately equal to the fraction selected from Group B.

Comparison of ranking principles: PRP favors certain groups, DP enforces proportions, and EOR balances the fraction of relevant candidates.

As shown in the comparison above:

  • PRP ($\sigma^{PRP}$) maximizes utility but can completely exclude relevant members of uncertain groups.
  • DP ($\sigma^{DP}$) enforces group proportions but doesn't account for the actual distribution of relevance.
  • EOR ($\sigma^{EOR}$) acts as a "fair lottery," ensuring that relevant members from all groups have an equal chance of being surfaced.

The EOR Algorithm

Implementing EOR efficiently is crucial for large-scale systems. We developed a greedy merging algorithm that operates in $O(n \log n)$ time. The algorithm takes pre-sorted lists for each group and iteratively selects the candidate that minimizes the current fairness gap. We prove that this greedy approach provides a close approximation to the globally optimal solution, maximizing utility while strictly adhering to the EOR fairness constraint.

Empirical Evaluation

We evaluated EOR across three distinct domains:

  • Synthetic Data: EOR maintained near-zero unfairness even as uncertainty increased, whereas PRP and DP showed significant fairness spikes.
  • US Census (ACSIncome): In predicting high-income individuals, EOR successfully balanced opportunities across racial groups in Alabama and New York.
  • Amazon Shopping Audit: Auditing search queries revealed that EOR can identify instances where logged rankings favor specific brands (e.g., in-house brands) beyond what relevance models justify.

Conclusion and Limitations

EOR provides a robust framework for fair ranking under uncertainty. However, it relies on group-wise calibration—the assumption that while a model may be uncertain, its probabilities are honest reflections of group averages. Future work includes extending EOR to continuous relevance scores and addressing intersectional identities. By prioritizing "equal opportunity" for relevant candidates, EOR helps break negative feedback loops and ensures that "not knowing" doesn't lead to systematic exclusion.

Summary updated

Abstract

Ranking is a ubiquitous method for focusing the attention of human evaluators on a manageable subset of options. Its use as part of human decision-making processes ranges from surfacing potentially relevant products on an e-commerce site to prioritizing college applications for human review. While ranking can make human evaluation more effective by focusing attention on the most promising options, we argue that it can introduce unfairness if the uncertainty of the underlying relevance model differs between groups of options. Unfortunately, such disparity in uncertainty appears widespread, often to the detriment of minority groups for which relevance estimates can have higher uncertainty due to a lack of data or appropriate features. To address this fairness issue, we propose Equal-Opportunity Ranking (EOR) as a new fairness criterion for ranking and show that it corresponds to a group-wise fair lottery among the relevant options even in the presence of disparate uncertainty. EOR optimizes for an even cost burden on all groups, unlike the conventional Probability Ranking Principle, and is fundamentally different from existing notions of fairness in rankings, such as demographic parity and proportional Rooney rule constraints that are motivated by proportional representation relative to group size. To make EOR ranking practical, we present an efficient algorithm for computing it in time $O(n \log(n))$ and prove its close approximation guarantee to the globally optimal solution. In a comprehensive empirical evaluation on synthetic data, a US Census dataset, and a real-world audit of Amazon search queries, we find that the algorithm reliably guarantees EOR fairness while providing effective rankings.
BibTeX
@inproceedings{rastogi2024fair,
  author = {Richa Rastogi and Thorsten Joachims},
  title = {{Fair Ranking under Disparate Uncertainty}},
  booktitle = {EAAMO},
  year = {2024},
  doi = {10.1145/3689904.3694703},
}

Loading related content...

Figure