Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
Source: arXiv:2605.23265 · Published 2026-05-22 · By Diptarka Chakraborty, Arya Mazumdar, Barna Saha, Alvin Hong Yao Yan
TL;DR
This paper addresses fairness-aware rank aggregation under the Spearman footrule distance metric, focusing on two key variants: (1) computing an optimal fair top-k aggregate ranking, and (2) approximating a fair full (all-candidates) aggregate ranking. In scenarios such as hiring and recommendation systems, only the top-k ranked candidates often matter, motivating a study of fairness constraints specifically for the top-k segment. Prior work had only a 3-approximation guarantee for the full fair rank aggregation, with no optimal algorithms for the top-k constrained problem. The authors provide the first polynomial-time exact algorithm for the fair top-k rank aggregation problem by formulating it as a linear program with fairness constraints and proving total unimodularity of the constraint matrix, which ensures integral LP solutions without rounding errors. For the full ranking problem, they prove NP-hardness of a natural matching subproblem and design a novel two-step algorithm: first compute a fair top-k list using their optimal top-k method, then extend it optimally to a full ranking via minimum-cost perfect matching. This yields a 2-approximation for the fair full rank aggregation problem improving over the previous 3-approximation. Extensive empirical evaluation on several real-world datasets supports their theoretical findings, demonstrating superior objective values and robustness across different group fairness parameters and to other distance metrics like Kendall-tau. The paper closes significant gaps in both theory and practice for fairness-aware consensus ranking under the widely used Spearman footrule metric.
Key findings
- A novel polynomial-time algorithm achieves an exact, optimal (α, β)-k-fair top-k aggregate ranking under the Spearman footrule metric (Theorem 3.1).
- The integer linear program modeling the fair top-k aggregation has a totally unimodular constraint matrix, ensuring integral LP solutions without rounding and fairness violations (Lemma 3.4, Theorem 3.1).
- The fair full ranking aggregation problem is NP-hard when reduced to a fair minimum cost perfect matching, even on a complete bipartite graph (Appendix D).
- They propose a two-step polynomial-time 2-approximation algorithm for the fair full rank aggregation problem: compute optimal fair top-k list, then optimally extend it to full ranking (Theorem 4.1).
- This 2-approximation improves substantially over the known 3-approximation from prior work (Wei et al. 2022, Chakraborty et al. 2022).
- Experiments on multiple real-world datasets verify the superior performance of the new algorithms compared to state-of-the-art baselines, showing near-optimal objective values consistently.
- Their method is robust to different choices of distance metric: it achieves near-best solutions even under Kendall-tau distance, where it translates to a 4-approximation (Appendix A).
Threat model
The paper assumes a benign setting where the input rankings and protected group information are given and correct. The adversarial concern is indirect: mitigating systemic biases that emerge from aggregating rankings without fairness constraints. There is no explicit adversary who manipulates inputs or tries to game the system. Instead, the focus is on designing aggregation algorithms robust to perpetuating underrepresentation of minority groups per known fairness criteria. Thus, the threat model is a fairness-aware aggregation context, not adversarial or malicious attacks.
Methodology — deep read
The authors begin by establishing the threat model and assumptions: the problem involves aggregating multiple input rankings over d candidates partitioned into g groups with fairness constraints ensuring minimum (α) and maximum (β) proportional representation of each group in the top-k positions. The adversary model is implicit — the concern is mitigating fairness disparities in outputs but no adversarial manipulations are assumed for the rankings themselves. The primary data inputs are sets S of n input rankings over d candidates (permutations), with group membership and fairness parameters specified.
For the optimal fair top-k rank aggregation, they formulate the problem as an integer linear program (ILP) minimizing the sum of Spearman footrule distances from the output ranking to all inputs, subject to:
- at most one candidate assigned to each top-k position,
- fairness constraints on group representation in top-k,
- assignment integrality (variables x_{i,j} ∈ {0,1} indicating candidate i at position j in top-k).
They relax the ILP to a linear program (LP) by allowing x_{i,j} ∈ [0,1]. Crucially, they prove the LP's constraint matrix is totally unimodular by carefully analyzing its block structure and applying known characterizations, implying all vertices of the feasible polytope are integral. Thus solving the LP directly yields an optimal integral solution without rounding errors or fairness violations. The LP is solved using the polynomial-time Ellipsoid method with objective perturbations to ensure vertex optimality (Theorem 3.5). This step-by-step proof of total unimodularity and integrality is novel in fairness-constrained optimization.
For the fair full ranking aggregation, they prove NP-hardness of a natural matching formulation derived from the unconstrained cases. To circumvent this, they propose a two-step approximation algorithm:
- Use the optimal top-k aggregation algorithm to find a fair top-k list minimizing a modified objective that only counts leftward rank displacements.
- Extend this top-k list to a full ranking by solving a minimum-cost perfect matching problem on a constructed weighted bipartite graph (mapping remaining candidates to remaining ranks), yielding a full ranking.
They rigorously analyze the approximation factor by decomposing the objective into contributions from the top-k and rest of the ranks, and comparing to the optimal fair full ranking. Using properties of displacements and matchings, they prove the output ranking's objective is at most twice that of the optimum, yielding a 2-approximation guarantee (Theorem 4.1).
Empirically, they evaluate on multiple real-world datasets (details on exact datasets are not fully provided in the truncated text). The code is implemented in Python and uses Gurobi for ILP baselines. Their algorithm is compared against previous state-of-the-art baseline methods with a 3-approximation. They report consistent improvements in the sum of distances objective, near-optimal performance, and robustness across group fairness parameters and distance metrics (e.g., Kendall-tau).
In summary, the methodology combines linear programming theory (total unimodularity), combinatorial optimization reductions (minimum cost perfect matching), careful problem decomposition, and both theoretical and empirical performance validation to push state-of-the-art on fairness-aware rank aggregation under the Spearman footrule metric.
Technical innovations
- Showing the ILP for fair top-k rank aggregation has a totally unimodular constraint matrix, yielding integral LP solutions and an exact polynomial-time algorithm.
- Designing a novel two-step 2-approximation for fair full rank aggregation combining optimal top-k fair ranking with a minimum-cost perfect matching-based completion.
- Proving NP-hardness of the natural fair minimum cost perfect matching subproblem for full rankings despite the unconstrained version being polynomial.
- Extending Spearman footrule distance to truncated top-k rankings and analyzing fairness constraints tightly within this metric framework.
Baselines vs proposed
- Previous 3-approximation algorithms (Wei et al., 2022; Chakraborty et al., 2022): fair full ranking objective value = higher than proposed algorithm's 2-approximation
- ILP solver (Gurobi) used to find exact solutions for comparison in top-k; proposed LP based approach runs faster and outputs integral solutions
- Proposed algorithm consistently achieves nearly optimal objective values in experiments versus meta-algorithms and heuristic baselines
Figures from the paper
Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2605.23265.
Fig 1: Example of the graph generated by the reduction for the
Fig 6: Illustration of the variable gadget in the reduction for a
Fig 7: Illustration of the clause gadget in the reduction for a
Limitations
- Datasets for empirical evaluation are not fully described or publicly released, limiting reproducibility in external validation.
- The proposed fair full ranking algorithm is an approximation, so exact optimal fair rankings are computationally intractable beyond small sizes.
- Evaluation focuses on Spearman footrule and Kendall-tau; robustness to other rank metrics or non-metric fairness notions is not explored.
- Assumes given group assignments and fixed fairness parameters α, β; sensitive attribute inference or noisy group labels are not addressed.
- The computational practicality of the Ellipsoid method for the LP in very large-scale ranking problems is unclear though polynomial theoretically.
- No direct adversarial robustness evaluation or discussion on strategic manipulation of input rankings by participants.
Open questions / follow-ons
- Can the 2-approximation guarantee for fair full ranking be improved further or matching hardness results be established?
- How to efficiently scale the optimal LP-based top-k aggregation to massively large candidate sets beyond the Ellipsoid method?
- Extension of fairness definitions and aggregation algorithms to settings with noisy group attributes or overlapping groups.
- Adapting these fairness-aware aggregation methods for dynamic or streaming ranking inputs where datasets evolve over time.
Why it matters for bot defense
Bot-defense and CAPTCHA systems sometimes rely on ranking or selection algorithms for candidate challenges or scoring interactions. This paper's advances in fairness-constrained rank aggregation provide foundational tools to ensure that automated ranking systems used for bot detection do not inadvertently disadvantage certain user groups or behavioral profiles. In scenarios where only top-k results (e.g., highest risk users flagged for CAPTCHA challenges) are acted on, guaranteeing representation fairness is critical to avoid biased security outcomes that frustrate or unfairly burden subsets of users.
The exact polynomial-time algorithm for fair top-k aggregation can be directly applied to selecting challenge sets or ranking suspect behaviors while maintaining parameterized proportional representation guarantees. The improved approximation for full rankings helps in broader candidate ordering scenarios, ensuring overall system behavior aligns with fairness constraints. Security engineers can adapt these novel linear programming and matching-based techniques to design and audit ranking components within their bot-defense pipelines, providing formal fairness guarantees and mitigating disparate impact risks in automated defense mechanisms.
Cite
@article{arxiv2605_23265,
title={ Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking },
author={ Diptarka Chakraborty and Arya Mazumdar and Barna Saha and Alvin Hong Yao Yan },
journal={arXiv preprint arXiv:2605.23265},
year={ 2026 },
url={https://arxiv.org/abs/2605.23265}
}