Source-linked AI summary
Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search
Sahin Cem Geyik, Stuart Ambler, Krishnaram Kenthapadi
TL;DR
Ranking systems can reproduce societal bias, motivating measures and interventions for fair ranking of individuals. The paper proposes protected-attribute-based bias measures and fairness-aware re-ranking, then evaluates them in simulations and LinkedIn Talent Search. The deployed approach nearly tripled representative search queries without impacting business metrics.
Problem
Ranking systems can learn existing societal biases and reduce disadvantaged groups’ visibility, creating a need to measure and mitigate bias when ranking individuals.
Method
The paper combines complementary protected-attribute bias measures with fairness-aware re-ranking algorithms that target desired distributions and can support equality of opportunity or demographic parity.
Results
Nearly three fold increase in search queries with representative results occurred in LinkedIn Talent Search without statistically significant change in business metrics.
Takeaways & Limitations
The framework was deployed to 100% of LinkedIn Recruiter users worldwide after improving fairness metrics without affecting business metrics.
Takeaways & Limitations
The approach assumes protected-attribute values and desired proportions are available as inputs, assumptions that may not hold in some application settings.
Abstract
from arXiv · showhide
We present a framework for quantifying and mitigating algorithmic bias in mechanisms designed for ranking individuals, typically used as part of web-scale search and recommendation systems. We first propose complementary measures to quantify bias with respect to protected attributes such as gender and age. We then present algorithms for computing fairness-aware re-ranking of results. For a given search or recommendation task, our algorithms seek to achieve a desired distribution of top ranked results with respect to one or more protected attributes. We show that such a framework can be tailored to achieve fairness criteria such as equality of opportunity and demographic parity depending on the choice of the desired distribution. We evaluate the proposed algorithms via extensive simulations over different parameter choices, and study the effect of fairness-aware ranking on both bias and utility measures. We finally present the online A/B testing results from applying our framework towards representative ranking in LinkedIn Talent Search, and discuss the lessons learned in practice. Our approach resulted in tremendous improvement in the fairness metrics (nearly three fold increase in the number of search queries with representative results) without affecting the business metrics, which paved the way for deployment to 100% of LinkedIn Recruiter users worldwide. Ours is the first large-scale deployed framework for ensuring fairness in the hiring domain, with the potential positive impact for more than 630M LinkedIn members.
1 INTRODUCTION
The paper addresses algorithmic bias in ranking systems by proposing fairness-aware measurement and re-ranking methods for ranked individuals. It evaluates the framework through simulations and LinkedIn Talent Search deployment, reporting improved fairness without statistically significant business-metric changes.
- Ranking systems used in hiring, lending, and admissions can reproduce societal biases and systematically reduce disadvantaged groups’ visibility.
- The framework quantifies and mitigates bias in systems that rank individuals using desired distributions over protected attributes such as gender and age.
- Its fairness-aware re-ranking algorithms can target equality of opportunity or demographic parity by selecting the desired protected-attribute distribution.
- The authors evaluate the algorithms through extensive simulations spanning ranking scenarios and protected attributes with different cardinalities.
- Nearly three fold increase in search queries with representative results occurred in LinkedIn Talent Search without statistically significant change in business metrics.
2 MEASURING ALGORITHMIC BIAS
The paper introduces complementary measures for evaluating bias in ranked lists, including attribute-specific skew measures and a holistic KL-divergence-based ranking measure. These measures expose different aspects of representation bias and have distinct interpretability and scope limitations.
- The framework assumes ideal top-ranked results follow a desired protected-attribute distribution, which may derive from a baseline population, legal mandate, or voluntary commitment.
- Top-k measures: Skew@k measures the logarithmic ratio between an attribute value’s top-k representation and its desired proportion.
- Top-k measures: Negative Skew@k indicates under-representation, positive Skew@k indicates favorable representation, and the logarithm makes equal opposing ratios symmetric around zero.
- Top-k measures: For 20 males among 100 results versus a desired male proportion of 0.4, Skewmale@100 = loge(0.5) ≈−0.3, indicating 50% less representation.
- Top-k measures: Skew@k depends on the cutoff k, may require separate values for each attribute value, and can require adjustment to avoid divide-by-zero or log(0).
- Top-k measures: MinSkew@k and MaxSkew@k summarize the worst disadvantage and largest advantage across attribute values.
- Ranking measure: NDKL compares prefix distributions with the desired distribution using normalized discounted cumulative KL-divergence, with zero denoting identical distributions at every position.
- Ranking measure: NDKL provides a holistic single measure over the ranked list but cannot distinguish equally sized bias against different attribute values and is harder to interpret than skew.
3 FAIRNESS-AWARE RANKING ALGORITHMS
The framework defines desired-distribution constraints for every top-k prefix, measures violations, and provides greedy and constrained-sorting re-ranking algorithms. DetConstSort is provably feasible, while DetGreedy is guaranteed feasible only when |A| ≤3.
- Desired properties: Fair rankings constrain every top-k prefix so each attribute value stays below ⌈p_ai · k⌉ and above ⌊p_ai · k⌋.The lower-bound condition is prioritized because it guarantees minimum representation; the upper bound limits disproportionate advantage.
- Fairness measures: Infeasibility occurs when some request and prefix violate count_k(a_i) ≥ ⌊p_ai · k⌋.The paper quantifies this with InfeasibleIndex, counting violating indices, and InfeasibleCount, counting violating attribute-value/index pairs.
- Greedy algorithms: DetGreedy selects the highest-scoring next candidate among values nearing minimum-representation violations, otherwise respecting maximum requirements.Its state tracks each attribute value’s top-k count and next unseen candidate score.
- Greedy algorithms: DetCons and DetRelaxed prioritize attribute values likely to violate minimum representation soon, with DetRelaxed using integrality constraints to retain higher scores.Both are designed to satisfy the lower and upper representation conditions, although universal feasibility is not proven.
- Feasibility: DetGreedy, DetCons, and DetRelaxed are feasible for |A| ≤3, while DetGreedy is not guaranteed feasible for |A| ≥4.The paper then introduces DetConstSort as a provably feasible constrained-sorting alternative.
- Constrained sorting: DetConstSort maximizes sorting quality subject to interval constraints that prevent candidates from exceeding feasible ranking positions.Candidates are swapped toward earlier positions until score ordering or a left candidate’s maximum index prevents the swap.
3.3 Mapping from Fairness Notions to Desired Attribute Distributions
The framework maps fairness notions to desired distributions over protected attributes. Choosing qualified-candidate proportions supports equal opportunity, while choosing the overall candidate distribution supports demographic parity.
- Desired distributions: Representativeness is defined by a desired distribution over one or more protected attributes, including cross-products of attribute values.This distribution determines the target composition of ranked results.
- Equal opportunity: Equal opportunity is approximated by treating query-matching candidates as qualified and top-ranked presentation as a positive prediction.The resulting requirement is that qualified candidates’ inclusion in top results not depend on the protected attribute.
- Demographic parity: Demographic parity can be met by selecting the desired distribution as the protected-attribute distribution of all candidates.Unlike equal opportunity, demographic parity does not take qualifications into account and has known limitations.
4 EVALUATION AND DEPLOYMENT IN PRACTICE
The framework was evaluated through large-scale simulations and an online LinkedIn Recruiter deployment, measuring fairness and ranking utility. Simulations compared fairness-aware algorithms across attribute cardinalities, while the A/B test assessed representative ranking in practice.
- Evaluation setup: The evaluation combines offline simulations with online deployment in LinkedIn Recruiter.The simulations study algorithm behavior across ranking scenarios, while the deployment evaluates gender-representative ranking in production.
- Simulation results: All proposed algorithms are feasible for attributes with up to 3 possible values, while DetConstSort is feasible for all tested attribute cardinalities.The feasibility result is consistent with the paper’s theoretical result for DetConstSort.
- Simulation results: DetCons, DetRelaxed, and DetConstSort outperform DetGreedy on MinSkew@100, and all fairness-aware algorithms outperform vanilla score-based ranking.For NDKL, the look-ahead algorithms DetCons and DetRelaxed perform slightly better than DetConstSort.
- Utility trade-offs: DetGreedy achieves significantly higher NDCG@100 utility than the other fairness-aware algorithms, while DetConstSort is slightly better than DetCons and DetRelaxed.Vanilla ranking has constant NDCG of 1 because it ranks purely by scores; among consistently feasible fairness-aware algorithms, DetConstSort has slightly better utility, with no considerable fairness difference among the three algorithms.
- Online deployment: In the A/B test, more than 95% of searches were representative of the qualified population’s gender distribution, a nearly 3X improvement, without affecting business metrics.The fairness-aware approach was subsequently ramped to 100% of Recruiter users worldwide.
5 RELATED WORK
The paper situates its query-dependent, group-fair ranking framework within work on individual and group fairness in rankings. It distinguishes its per-ranking desired-distribution objective from prior approaches focused on fixed candidate sets, linear models, or amortized individual fairness.
- Prior fairness research distinguishes individual fairness from group fairness for disadvantaged groups or the broader population.
- Unlike one prior method, this approach handles query-dependent candidate sets rather than assuming a fixed set of items.
- The paper’s algorithms enforce group fairness separately for each ranking by targeting a desired protected-attribute distribution.
- The framework is not restricted to linear ranking models or weight-vector modification, supporting varied model choices in practice.
- Compared with amortized individual fairness, the paper focuses on meeting specified group-fairness requirements in every ranking.
6 CONCLUSION
The paper concludes that desired-proportion re-ranking can reduce bias in ranked results while preserving utility. Its LinkedIn Talent Search deployment substantially improved representative outcomes without affecting business metrics, while empirical scope and assumptions leave directions for further study.
- The framework combines bias measures and fairness-aware re-ranking based on desired proportions over one or more protected attributes.
- The algorithms reduced bias without affecting utility across extensive simulations comparing performance over ranking scenarios and attributes.
- Nearly 3X more LinkedIn Talent Search queries had representative results without impacting business metrics.
- The empirical study used synthetic datasets, with real-dataset experiments identified as future work.
A.1 Results for InfeasibleCount and MaxSkew Measures
This appendix continuation presents results for the InfeasibleCount and MaxSkew@100 fairness measures in Figures 6 and 7.
- The appendix reports InfeasibleCount results in Figure 6.
- The appendix reports MaxSkew@100 results in Figure 7.
- Figures 6 and 7 continue the results for these two measures from the preceding experimental analysis.
A.2 Proof of Theorem 3.2
The theorem establishes feasibility for DetGreedy, DetCons, and DetRelaxed when the protected attribute has at most three possible values. A counterexample shows that DetGreedy is not guaranteed feasible with four or more values.
- Theorem 3.2: DetGreedy, DetCons, and DetRelaxed are feasible whenever |A| ≤3.The proof treats |A| = 1 as trivial and analyzes |A| ∈ {2, 3}.
- Theorem 3.2: The contradiction proof assumes feasibility through position k but simultaneous minimum-count requirements become impossible at position k + 1.Two attribute values would each require the next candidate, even though one candidate cannot possess both values.
- Theorem 3.2: For |A| = 2, the two required floor counts sum to less than k, contradicting that k selected candidates must be fully assigned.
- Theorem 3.2: For |A| = 3, the remaining attribute count must equal its ceiling bound, and the fractional-count conditions yield a contradiction.
- Theorem 3.2: DetGreedy is not guaranteed feasible for |A| ≥4, as a four-value counterexample creates incompatible requirements at the third position.The counterexample extends to larger attribute sets by assigning zero desired proportion to additional values.
A.3 Proof of Theorem 3.3
The proof establishes that DetConstSort is feasible by showing it inserts only the candidates needed for minimum representation requirements without violating the feasibility condition.
- DetConstSort is feasible under Definition 3.1.
- The algorithm includes only as many candidates as needed to satisfy each attribute value’s minimum representation count.
- At position k, the algorithm has included at most k candidates subject to these representation requirements.
- Each required insertion has sufficient empty space through position k, while swaps preserve the feasibility condition.
- Because the feasibility condition is never violated, DetConstSort is feasible.
A.4 Description of Representative Ranking System Architecture
The representative-ranking architecture uses two re-ranking stages after first-level retrieval, each guided by learned scores and desired gender distributions before presenting candidates to recruiters.
- The architecture computes the gender distribution of qualified candidates alongside first-level ranking.
- The first re-ranking stage combines first-level machine-learned scores with desired gender distributions.
- Representative top-k′ candidates are passed to the second-level ranking stage.
- The second re-ranking stage combines second-level machine-learned scores with desired gender distributions before presenting top-k′′ candidates to recruiters.
- Matching candidates are retrieved in parallel from distributed Searcher nodes indexing hundreds of millions of LinkedIn members.