Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking

Ensuring fairness in algorithmic ranking systems is a critical challenge with significant societal implications for hiring, recommendations, web search, and data management. Standard methods for aggregating multiple preference orders into a consensus ranking may perpetuate and even amplify the lack of representation of underrepresented groups. To address this, recent research has focused on incorporating fairness constraints to ensure the presence of different groups in the top-$k$ positions of the final aggregate ranking. We study two fairness-aware variants under the well-known Spearman footrule, which corresponds to the $L_1$ distance between rankings. First, we address the practically salient task of computing a fair aggregate top-$k$ ranking -- crucial in settings like recommendations and hiring where selection is primarily based on the top-$k$ results -- and present the first optimal algorithm for this problem. Second, we consider fair (full) rank aggregation over all candidates (not specifically on top-$k$). We already know of a $3$-approximation for this fair rank aggregation variant (Wei et al., SIGMOD’22; Chakraborty et al., NeurIPS’22), whereas an exact algorithm exists for the corresponding unconstrained (unfair) version (Dwork et al., WWW’01). Closing the computational gap between fair and unconstrained rank aggregation has remained a tantalizing open problem. We make significant progress by giving a $2$-approximation algorithm for fair (full) rank aggregation, improving substantially over the previous $3$-approximation. Further, we complement our theoretical contributions with experiments on different real-world datasets, which corroborate our theoretical results and demonstrate strong empirical performance relative to state-of-the-art baselines.

Ranking systems help determine what or who appears first in areas such as job hiring, online recommendations, search engines, and data organization. But when these systems combine many different opinions into one final list, they can sometimes leave out already underrepresented groups. Our paper explores how to make those rankings fairer. We focus on fairness rules that ensure different groups appear among the top most ranks, since the highest-ranked positions usually matter the most. We first design an algorithm that can find the best possible fair top-k ranking, which is especially useful when only the top ranks matter, such as in shortlisting job candidates or showing recommended items. Second, we design an algorithm that improves on existing methods for creating a fair ranking of all candidates, that gives stronger quality guarantees than previous work. We also test our methods on real-world datasets. The results show that the new approaches work well in practice and often outperform existing methods. Overall, our work makes progress toward ranking systems that are both effective and more inclusive.