Fairness in Ranking under Disparate Uncertainty

Richa Rastogi, Thorsten Joachims

TL;DR

Standard ranking algorithms systematically disadvantage groups when a model is less certain about their qualifications—a phenomenon called "disparate uncertainty." This paper introduces Equal-Opportunity Ranking (EOR), a novel framework and efficient $O(n \log n)$ algorithm that ensures groups are ranked based on an equal fraction of their relevant members, providing a "fair lottery" even when data for some groups is scarce.

What Problem Does This Paper Address?

Imagine a college admissions officer reviewing 12,000 applications for 500 spots. To save time, they use an AI to rank candidates. For the "majority" group, the AI has mountains of data and can confidently assign high probabilities (0.9) to the best students. But for a "minority" group, the AI has less data and plays it safe, assigning a flat 0.1 probability to everyone.

If you rank strictly by probability (the standard Probability Ranking Principle), the top 500 spots will be filled entirely by the majority group. Even if the minority group has 200 "hidden gems" (qualified students), none will ever be seen by a human.

The authors argue that this isn't just a data problem—it's a ranking problem. Traditional fairness metrics like Demographic Parity (ensuring group proportions match population size) don't solve this because they don't account for the fraction of qualified individuals being overlooked. The gap is "disparate uncertainty": when a model’s predictive confidence varies across groups, the group with higher uncertainty is systematically pushed to the bottom of the list.

Methods

The authors propose Equal-Opportunity Ranking (EOR). The core idea is to equalize the "cost of opportunity" across groups.

  1. The EOR Criterion: A ranking is fair if, at any point $k$ in the list, the expected fraction of relevant (qualified) candidates selected from Group A is roughly equal to the fraction selected from Group B.
  2. The Algorithm: They developed a greedy merging algorithm. It takes pre-sorted lists for each group and, at each step, selects the candidate from the group that minimizes the current fairness gap ($\delta$).
  3. Theoretical Grounding: Using linear programming duality, the authors prove that this greedy approach is near-optimal. It maximizes the total number of relevant candidates found (utility) while strictly adhering to the fairness constraint.
  4. Efficiency: The algorithm runs in $O(n \log n)$ time, making it practical for large-scale systems like search engines or massive hiring platforms.

Datasets

The researchers evaluated EOR across three distinct environments:

  • Synthetic Data: Controlled environments where they could precisely vary the "sharpness" (certainty) of relevance probabilities using Beta distributions.
  • US Census (ACSIncome): A real-world dataset used to predict whether individuals earn over $50,000. They looked at disparities across racial groups (White, Black, Asian, etc.) in Alabama and New York.
  • Amazon Shopping Audit: They used a dataset of Amazon search queries and binned products into "Amazon-owned brands" vs. "Other brands" to audit whether Amazon’s logged rankings favored their own products beyond what relevance models would suggest.

Key Insights and Ideas

  • The "Fair Lottery" Principle: EOR is philosophically grounded in the idea of a fair lottery. If we can't perfectly distinguish who is best within a group due to uncertainty, we should treat the relevant members of that group as having an equal shot at being seen compared to relevant members of other groups.
  • Calibration is Key: The method assumes "group-wise calibration." This means that while the model might be uncertain (giving everyone a 0.1), that 0.1 must be an honest reflection of the group's average relevance.
  • Beyond Representation: Unlike Demographic Parity, which just looks at raw numbers, EOR looks at opportunity. It asks: "Of the people who actually deserve to be here, what percentage did we actually show?"
  • Feedback Loops: By ranking uncertain but potentially relevant candidates higher, EOR helps collect better data for those groups, potentially reducing disparate uncertainty for future model iterations.

Key Results

  • Fairness Guarantee: In synthetic tests, EOR maintained an unfairness score near zero, while standard rankers (PRP) and even Demographic Parity rankers showed massive spikes in unfairness as uncertainty increased.
  • Utility Trade-off: EOR is surprisingly efficient. While it does slightly lower the expected number of relevant candidates in the top-$k$ (compared to the "optimal but unfair" PRP), it remains competitive with other fairness-aware baselines while providing much stronger procedural guarantees.
  • Real-World Audit: In the Amazon brand audit, the EOR criterion successfully identified prefixes where Amazon's logged rankings deviated significantly from a fair "equal opportunity" baseline, suggesting a potential bias toward in-house brands.

Limitations and Future Work

  • The Calibration Assumption: If the underlying model is not just uncertain but actively biased (e.g., it systematically underestimates a group's relevance), EOR cannot fix that. It relies on the probabilities being "honest" averages.
  • Binary Relevance: The current framework focuses on binary outcomes (relevant vs. not relevant). Extending this to continuous scores (like "star ratings") is a suggested next step.
  • Human in the Loop: The paper assumes the human reviewer is perfect and unbiased once they see a candidate. In reality, human bias at the review stage could interact with the ranking in complex ways.
  • Intersectionality: The current model handles multiple groups but does not explicitly address intersectional identities (e.g., the specific uncertainty associated with being both a minority and from a low-income zip code).

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{rastogi2024fairness,
  author = {Richa Rastogi and Thorsten Joachims},
  title = {{Fairness in Ranking under Disparate Uncertainty}},
  booktitle = {EAAMO},
  year = {2024},
  doi = {10.1145/3689904.3694703},
}

Loading related content...

Figure