Source-linked AI summary
FA*IR: A Fair Top-k Ranking Algorithm
Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, Ricardo Baeza-Yates
TL;DR
The paper tackles systematic under-representation in ranked lists while retaining candidate utility. It defines statistically tested ranked group fairness, proposes FA*IR to produce fair top-k rankings, and reports minor utility changes relative to color-blind rankings.
Problem
The paper asks how to prevent a ranking from reducing a protected group’s representation below a minimum while keeping utility as high as possible.
Method
FA*IR post-processes a ranking using prefix-based statistical fairness tests with adjusted significance, while optimizing selection and ordering utility.
Results
FA*IR generally causes minor utility changes relative to the color-blind ranking, achieves higher or equal ordering utility in all tested conditions, and higher or equal selection utility in all but one.
Takeaways & Limitations
The method provides a statistically grounded way to implement positive-action policies in ranking while directly controlling the fairness–utility trade-off through p.
Takeaways & Limitations
The method assumes one dominant legally protected attribute and may fail to satisfy fairness in the ranking tail when protected candidates are insufficient.
Abstract
from arXiv · showhide
In this work, we define and solve the Fair Top-k Ranking problem, in which we want to determine a subset of k candidates from a large pool of n >> k candidates, maximizing utility (i.e., select the "best" candidates) subject to group fairness criteria. Our ranked group fairness definition extends group fairness using the standard notion of protected groups and is based on ensuring that the proportion of protected candidates in every prefix of the top-k ranking remains statistically above or indistinguishable from a given minimum. Utility is operationalized in two ways: (i) every candidate included in the top-$k$ should be more qualified than every candidate not included; and (ii) for every pair of candidates in the top-k, the more qualified candidate should be ranked above. An efficient algorithm is presented for producing the Fair Top-k Ranking, and tested experimentally on existing datasets as well as new datasets released with this paper, showing that our approach yields small distortions with respect to rankings that maximize utility without considering fairness criteria. To the best of our knowledge, this is the first algorithm grounded in statistical tests that can mitigate biases in the representation of an under-represented group along a ranked list.
1 INTRODUCTION
FA*IR addresses ranked-list bias by selecting and ordering a utility-maximizing top-k subject to statistically tested minimum representation of a protected group. The method adjusts significance for repeated prefix tests and aims to preserve utility while mitigating systematic under-representation.
- Motivation: Ranked search results can systematically reduce the visibility of already disadvantaged protected groups.The paper frames this as unfair when protected-group members are ranked lower or excluded from the top-k because of systematic bias in the ranking model.
- Fairness criterion: Multiple prefix tests require an adjusted significance level; using α directly could reject fair rankings more often than the nominal rate.The paper identifies this adjustment as a key contribution, while the example notes that it is nontrivial.
- Problem: The Fair Top-k Ranking problem selects k candidates from n ≫ k while maximizing utility subject to group fairness criteria.The motivating application is automatically selecting a smaller interview group from a large candidate pool.
- Utility: Utility combines selection utility, favoring qualified included candidates, and ordering utility, favoring qualified candidates ranked above less qualified peers.Both criteria allow small qualification differences rather than requiring strict separation.
- Fairness criterion: Ranked group fairness requires the protected proportion in every ranking prefix to be statistically indistinguishable from or above a specified minimum.The criterion compares each prefix with Bernoulli-trial expectations and uses significance α.
- Method and evaluation: FA*IR efficiently produces a fair top-k ranking and experiments report small utility distortions relative to color-blind rankings.The approach is intended for positive-action policies and applies when enough protected candidates exist.
2 RELATED WORK
Related work covers algorithmic discrimination, fairness-aware prediction, fairness measurement in rankings, and constrained ranking. This paper distinguishes its approach by constructing rankings with statistically derived fairness constraints rather than only auditing or evaluating them.
- 2.1 Group fairness and individual fairness: Algorithmic discrimination research includes methods for discovering, measuring, mitigating, and removing discrimination, spanning individual and group fairness frameworks.Group fairness, also called statistical parity, concerns similar treatment of protected groups and advantaged groups or the population as a whole.
- 2.2 Fair Ranking: Prior ranking work measures fairness across list prefixes using statistical parity metrics such as KL-divergence and discounted aggregation.These approaches assess distributions of protected and non-protected candidates at multiple prefix lengths.
- 2.2 Fair Ranking: Search-bias research audits whether ranking bias originates in input data or the ranking system, whereas this paper focuses on generating fair rankings.The distinction is between identifying bias sources and mitigating representation during ranking.
- 2.2 Fair Ranking: This paper connects ranking construction to its fairness metric by deriving a constraint matrix through a statistical test of ranked group fairness.Its individual-based utility measure also identifies which candidates are most affected by reranking relative to a fairness-unaware solution.
- 2.3 Diversity: Information-retrieval diversity methods often evaluate or diversify results for multiple intents, while this work constructs rankings over discrete protected and non-protected classes.The paper contrasts its construction objective with evaluation frameworks such as per-intent NDCG.
3 THE FAIR TOP-K RANKING PROBLEM
The Fair Top-k Ranking problem seeks rankings that maintain minimum protected-group representation at every prefix while preserving selection and ordering utility. Its statistical criterion uses multiple-testing correction, and the resulting method adjusts rankings using a fair-ranking generative model while measuring utility through nonmonotonicity losses.
- Fair top-k ranking criteria: The problem requires ranked group fairness, selection utility, and ordering utility simultaneously.The ranking should represent the protected group fairly, include the most qualified candidates, and order included candidates by decreasing qualification.
- Ranked group fairness: Ranked group fairness compares protected-candidate counts in every prefix with a binomial model having target proportion p.A prefix passes when its cumulative distribution value F(τp;k,p) exceeds the significance threshold α.
- Multiple-tests correction: The criterion uses corrected significance αc to account for k simultaneous prefix tests and reduce false negatives from rejecting fair rankings.Using αc = α can produce a fair-ranking rejection rate larger than α; verification is efficient in O(k) time after precomputing the required table.
- Model adjustment: The adjustment is calibrated against rankings generated by incrementally selecting the best protected candidate with probability p and the best non-protected candidate with probability 1 − p.The acceptance probability can be computed analytically using block-based dynamic programming in O(k^2), once independently of the dataset.
- Model adjustment: Figure 1 shows that uncorrected tests with αc = 0.1 generally reject the fair-ranking model more often than α = 0.1.The analysis concerns rankings generated with p = 0.5, and the plotted k scale is logarithmic.
- Utility: Ranked utility measures losses from nonmonotonicity by comparing each candidate with the least-qualified candidate ranked above it.This utility gives an element its maximum value of zero when no higher-ranked candidate is less qualified.
4 ALGORITHM
FA*IR constructs a top-k ranking by combining qualification-based priority queues with prefix-specific minimum protected-group counts. It satisfies ranked group fairness and in-group monotonicity while achieving optimal selection utility and maximizing ordering utility under the stated constraints.
- Algorithm FA*IR: FA*IR takes k, candidate qualifications, protection indicators, minimum protected proportion p, and adjusted significance αc as inputs.
- Algorithm FA*IR: The algorithm creates separate protected and non-protected priority queues, computes required protected counts for each position, and greedily builds the ranking.
- Algorithm FA*IR: FA*IR runs in O(k logk) time when the two class-specific ranked lists are already available.
- Correctness: By construction, FA*IR selects candidates in decreasing qualification order within each group and maintains at least the required protected count in every prefix.
- Correctness: FA*IR achieves optimal selection utility among rankings satisfying in-group monotonicity and ranked group fairness.
- Correctness: FA*IR maximizes ordering utility among rankings satisfying in-group monotonicity, ranked group fairness, and optimal selection utility.
5 EXPERIMENTS
Experiments evaluate significance adjustment and FA*IR on public and newly released datasets against color-blind and Feldman et al. baselines. FA*IR generally preserves utility relative to color-blind rankings and reduces ordering-related unfairness relative to the alternative fairness baseline.
- 5.1 Significance adjustment: Synthetic experiments verified that AdjustSignificance closely matches the observed probability of falsely declaring fair rankings unfair.
- 5.2 Datasets: The evaluation uses COMPAS, German Credit, SAT, and the newly released XING dataset, with varied protected-group scenarios and top-k settings.
- 5.3 Metrics and baselines: The comparison includes a qualification-only color-blind ranking and the Feldman et al. distribution-alignment method.
- 5.3 Metrics and baselines: Utility evaluation reports ranked-utility loss, maximum rank drop, and normalized discounted cumulative gain (NDCG).
- 5.4 Results: FA*IR changes utility only slightly relative to color-blind rankings, achieves higher or equal selection utility than Feldman et al. except in D7, and has higher or equal ordering utility in all conditions.
- 5.4 Results: FA*IR supports multiple target proportions directly; in German Credit, it doubled young candidates’ top-k proportion from 15% to 30% while maintaining nearly unchanged NDCG and without large ordering-utility loss.
6 CONCLUSIONS
The method guarantees ranked group fairness while keeping utility loss small and lets users control the fairness–utility trade-off through p. Its scope remains limited by simplifying assumptions and open evaluation and design challenges.
- The method guarantees ranked group fairness without introducing large utility loss.Compared with Feldman et al., it generally introduces the same or less utility loss.
- Parameter p directly controls the trade-off between fairness and utility.
- The approach does not assume similarly shaped qualification distributions for protected and non-protected groups.
- The current setting considers one protected or non-protected group, leaving multiple protected groups or combined attributes for future work.
- Open directions include in-processing ranking, synthetic-data evaluation, robustness to qualification noise, and testing impact in real applications.