Fairness in Aggregation: Optimal Top- k k and Improved Full Ranking
Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan · 2026
Read Fairness in Aggregation: Optimal Top- k k and Improved Full Ranking by Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23265.txt.
Introduction
Chakraborty and three coauthors study fairness in rank merging under the Spearman footrule, the L1 distance. Standard methods merging preference orders toward a consensus ranking may perpetuate underrepresentation. They address first computing a fair merged top-k ranking, presenting the first optimal method. Second, they consider fair full rank merging over all candidates. A 3-approximation is known, while an exact algorithm exists. They give a 2-approximation method for fair full rank merging, improving on the previous 3-approximation. Tests back their theoretical results.
Catalog record
| CREATOR | Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66555 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.23265
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fairness in Aggregation: Optimal Top- k k and Improved Full Ranking Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan Abstract 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 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 L_{1} distance between rankings. First, we address the practically salient task of computing a fair aggregate top- k k ranking – crucial in settings like recommendations and hiring where selection is primarily based on the top- k 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 k ). We already know of a 3 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 2 -approximation algorithm for fair (full) rank aggregation, improving substantially over the previous 3 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. † † affiliationnotice: The author order is alphabetical. 1 Introduction The problem of aggregating multiple, often conflicting, preference orderings or rankings over a set of alternatives or candidates into a single consensus ordering, known as rank aggregation , is one of the most fundamental challenges, dating back to as early as the 18th century ( 14 ; 27 ) . This task is prevalent in numerous real-world scenarios, including hiring, recommendation systems, web searches, scholarship selections, and many more. The problem is often formulated as an optimization task over permutation/ranking metric space: given a set of rankings, find a ranking that minimizes the sum of distances to the input rankings. The ubiquity of this problem in scenarios requiring a selection or the generation of ranked suggestions has elicited considerable attention from the computational perspective ( 32 ; 35 ; 36 ; 6 ; 44 ) . One of the classical distance metrics defined over a set of rankings is the Spearman footrule distance – it quantifies how far two rankings differ by summing absolute rank shifts across all candidates ( 50 ; 51 ) , i.e., the rank-wise L_{1} distance (see Section 2 for a formal definition). As an L_{1} -type measure, it emphasizes absolute positional disagreements and tends to be more responsive to large movements than counts of pairwise inversions. It is widely used in databases ( 35 ) , clustering and analysis of ranked data ( 46 ) , meta searches and learning to rank in information retrieval ( 5 ; 45 ) , web searches ( 32 ) , bioinformatics and genomics ( 48 ) and social choice ( 7 ) . Computationally, it is straightforward to evaluate. It also makes the rank aggregation problems tractable ( 31 ) ; in fact, aggregation under the footrule closely aligns with median-based aggregation, enabling simple heuristics that are effective in database settings ( 35 ) . Computational tractability is a major advantage compared to some other relevant metrics on rankings, such as Kendall–tau – yet another classical distance metric. Despite its simplicity, the footrule is tightly related to Kendall–tau being equivalent up to a factor of two ( 29 ) . Finally, in many practical contexts, such as hiring, the top- k positions of a ranking are only (the most) relevant; unlike several other metrics, the footrule naturally extends to truncated lists and accommodates missing ranks, further enhancing its utility in real-world scenarios ( 34 ) . This paper extends the classical rank aggregation task by incorporating additional constraints in the final output to ensure fair representations. The high-stakes nature of decisions made with ranking algorithms – such as offering employment, granting admissions to educational institutions, allocating loans, or prioritizing medical care during crises – underscores the need for proportional outcomes. Without explicit fairness considerations, these systems risk perpetuating systemic biases and harmful stereotypes against underrepresented groups, which are often defined by sensitive attributes like race, gender, or caste ( 39 ; 28 ; 13 ) . In many countries, fairness constraints are enforced by legal norms to counteract historical discrimination, such as reservation systems for jobs and education in India ( 15 ) , affirmative actions in employment in South Africa ( 16 ; 52 ) , and candidate selection by political parties in Spain ( 54 ) . To address the concerns on fairness and diversity in ranking algorithms, ( 55 ; 24 ) initiated the study of the rank aggregation problem considering the notion of proportional fairness ( 10 ) . This fairness criterion mandates that the representation of each protected group within the top- k – often the most relevant – segment of the final ranking is appropriately balanced; more specifically, it satisfies (i) minority protection : each group has at least a certain (input specified) fraction of representative in the top- k positions, and (ii) restricted dominance : none of the groups has more than a certain (input specified) fraction of representative in the top- k positions (see Section 2 for a formal definition). In the fair rank aggregation problem, given a set of input rankings over d candidates, the objective is to find a fair ranking that minimizes the sum of distances to the input rankings. In this paper, we focus on the Spearman footrule distance. This problem was first explored by ( 55 ; 24 ) , who proposed a simple baseline meta-algorithm. Their approach is to compute a closest fair ranking for each input permutation, then select the one with the minimum sum of distances to all inputs. Since a polynomial time algorithm for finding a closest fair ranking is already known ( 17 ) , through a direct application of the triangle inequality, this meta-algorithm yields a 3 -approximation. There is no better bound known for this fair variant until now, which is in stark contrast with the classical (unconstrained) rank aggregation problem that is solvable in polynomial time ( 31 ) . Closing this complexity gap between the unconstrained and fair versions remains an important open problem, as also explicitly mentioned in ( 55 ) . For many real-world applications, such as hiring, where open positions are limited, the primary interest lies only in the top- k portion of the final ranking. Furthermore, the requirements of many information retrieval applications necessitate a focus solely on the top- k ranked items. Such applications motivate the introduction of generalized Spearman footrule to study top- k lists ( 34 ) . While the best current algorithm achieves a 3 -approximation for