# Generalizing Fair Top-k Selection: An Integrative Approach

arXiv: https://arxiv.org/abs/2603.04689 · HTML: https://mlsanity.com/paper/2603.04689/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 47 references that are in the map.
- First posted on arXiv 5 Mar 2026.

## Builds on (most cited first, 16 of 16)

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search](https://mlsanity.com/paper/1905.01989/) (2019)
- [FA*IR: A Fair Top-k Ranking Algorithm](https://mlsanity.com/paper/1706.06368/) (2017)
- [Measuring Fairness in Ranked Outputs](https://mlsanity.com/paper/1610.08559/) (2016)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges](https://mlsanity.com/paper/2305.06969/) (2023)
- [Designing Fair Ranking Schemes](https://mlsanity.com/paper/1712.09752/) (2017)
- [Selection Problems in the Presence of Implicit Bias](https://mlsanity.com/paper/1801.03533/) (2018)
- [Efficient fair PCA for fair representation learning](https://mlsanity.com/paper/2302.13319/) (2023)
- [Balanced Ranking with Diversity Constraints](https://mlsanity.com/paper/1906.01747/) (2019)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [On Obtaining Stable Rankings](https://mlsanity.com/paper/1804.10990/) (2018)
- [Query Refinement for Diverse Top-k Selection](https://mlsanity.com/paper/2403.17786/) (2024)
- [Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice](https://mlsanity.com/paper/2503.11575/) (2025)

## Abstract (arXiv)

Fair top-k selection, which ensures appropriate proportional representation of members from minority or historically disadvantaged groups among the top-k selected candidates, has drawn significant attention. We study the problem of finding a fair (linear) scoring function with multiple protected groups while also minimizing the disparity from a reference scoring function. This generalizes the prior setup, which was restricted to the single-group setting without disparity minimization. Previous studies imply that the number of protected groups may have a limited impact on the runtime efficiency. However, driven by the need for experimental exploration, we find that this implication overlooks a critical issue that may affect the fairness of the outcome. Once this issue is properly considered, our hardness analysis shows that the problem may become computationally intractable even for a two-dimensional dataset and small values of k. However, our analysis also reveals a gap in the hardness barrier, enabling us to recover the efficiency for the case of small k when the number of protected groups is sufficiently small. Furthermore, beyond measuring disparity as the "distance" between the fair and the reference scoring functions, we introduce an alternative disparity measureunicodex2014utility lossunicodex2014that may yield a more stable scoring function under small weight perturbations. Through careful engineering trade-offs that balance implementation complexity, robustness, and performance, our augmented two-pronged solution demonstrates strong empirical performance on real-world datasets, with experimental observations also informing algorithm design and implementation decisions.