Fairness in Ranking: Algorithms and Explainability
Abstract:
The task of ranking a set of candidates finds applications in a large swathe of fields, such as social choice theory, collaborative filtering, web search, statistics, databases, sports, and admission systems. When there exist several conflicting rankings over the candidates, a natural and important task is to combine them into a single consensus ranking which best represents the input rankings, leading to the problem of rank aggregation. Yet the optimal consensus ranking may inherit bias of the input rankings against individual candidates or groups and thus risks perpetuating or amplifying lack of representation from these groups. This practical concern has led to the recent study of fair rank aggregation, where fairness constraints are incorporated to ensure candidates from different groups are fairly represented in the top-k positions of the aggregated ranking. Another setting arising in ranking candidates is when the ranking is generated through some function of candidate attributes, which can involve sensitive attributes that are hidden yet may influence outcomes through additive bonuses designed to promote fairness.
First, we study the maximum rank aggregation problem under the Kendall tau distance. However, even for four input rankings, this problem is NP-hard and only a (folklore) polynomial-time 2-approximation algorithm is known for finding an optimal aggregate ranking. We present significant progress in solving this problem by considering the Mallows model, a classical probabilistic model. Our proposed algorithm outputs an (1+epsilon)-approximate aggregate ranking for any epsilon > 0, with high probability, as long as the input rankings come from a Mallows model, even in a streaming fashion. Furthermore, the same approximation guarantee is achieved even in the presence of outliers, presumably a more challenging task.
Next, we study the problem of fair median rank aggregation under two distance metrics: the Kendall-tau distance and the Spearman's footrule distance. Under both distance metrics, we know of a 3-approximation algorithm for this problem. We make progress under the Kendall-tau distance, by providing novel algorithm that achieves (2+epsilon)-approximation (for any epsilon > 0). Then, we design a 2.881-approximation fair rank aggregation algorithm that works irrespective of the fairness notion, given one can find a closest fair ranking. For the Spearman's footrule distance, 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, for fair (full) rank aggregation over all candidates we make progress by giving a 2-approximation algorithm. For both distance metrics, our theoretical contributions are supported by experiments on real-world datasets, which demonstrate strong empirical performance of our algorithms.
Finally, we study a variant of the ranking explanation problem where sensitive features are unobserved but may influence candidate rankings through group-specific linear boosts. We present a formal framework for modeling this problem and develop an algorithmic solution that leverages constraint satisfaction and automated reasoning techniques to jointly infer the linear scoring parameters and latent group bonuses consistent with the observed rankings. Then, we show that determining a satisfying linear function with group-specific bonuses is NP-hard in general, but the problem admits a polynomial-time solution when the feature dimension and the number of groups are constant. Our approach is the first to address this nuanced variant, which captures key real-world challenges in fair ranking and admission systems. Extensive experiments on both real-world and synthetic datasets demonstrate that our method effectively recovers hidden bonus structures and provides faithful explanations of observed ranking outcomes.