Source-linked AI summary
Unpublished Draft: A Post-Processing Approach to Fairness in Tie-Aware Rankings
Somya Nigam, Johan Springael, Kenneth Sörensen
TL;DR
Fair rank aggregation has mainly studied strict permutations, leaving tie-aware input and output rankings underexplored despite their practical relevance. This paper post-processes an unfair tie-aware consensus ranking using an exact algorithm and a heuristic to obtain a closest fair ranking. The exact method computes optimal solutions efficiently for n ≤104, while the heuristic scales to larger instances but may not minimize distance.
Problem
Existing fair rank aggregation studies predominantly treat input and output rankings as permutations, leaving rankings with ties insufficiently addressed.
Method
The paper post-processes an unfair tie-aware consensus ranking with an exact algorithm and a heuristic under pairwise statistical parity.
Results
For n ≤104, the exact method computes an optimal fair ranking efficiently; for larger instances, the heuristic scales well and produces a fair ranking, though not always the lowest-distance one.
Takeaways & Limitations
Ties can satisfy fairness at every threshold, while the objective function limits unnecessary added ties to keep the fair ranking close to the original.
Takeaways & Limitations
The current approach assumes a binary protected attribute and requires extension to multiple groups and further testing with other fairness measures and multiple rankings.
Abstract
from arXiv · showhide
The problem of finding a fair consensus ranking is an active research topic in the domain of fair rank aggregation and has been well studied; however, existing studies predominantly consider both the input rankings and the output ranking to be permutations where elements are always strictly ordered. In practice, however, a ranking with ties is far more common. This study bridges this gap by presenting a post-processing approach to determine the closest fair consensus ranking when an unfair tie-aware consensus ranking is provided. It proposes an exact algorithm and a fast heuristic to achieve this.
I. INTRODUCTION
Fair rank aggregation addresses potential bias in consensus rankings, but prior work has largely restricted both inputs and outputs to strict permutations. This paper extends the setting to tie-aware rankings through a post-processing approach with an exact algorithm and a heuristic.
- Motivation: Rank aggregation combines multiple preference rankings into one consensus ranking across elections, information retrieval, sports, collaborative filtering, and bioinformatics.With at least four base rankers, the problem becomes NP-hard, motivating polynomial-time methods.
- Motivation: Fair rank aggregation seeks to mitigate bias and prevent particular groups from losing opportunities through misrepresentation in the consensus ranking.The paper situates this concern in ranking decisions involving individuals, communities, or countries and existing disparities.
- Research gap: Existing fair rank aggregation studies primarily use strict permutations for both input rankings and consensus rankings, despite ties being common in practice.The paper identifies this restriction as the central gap addressed by its tie-aware setting.
- Contributions: The paper provides an exact algorithm that accepts tie-aware rankings or permutations and optimally finds the closest fair ranking under pairwise statistical parity.It supports rankings of size ≥100, arbitrary fairness thresholds, and multiple rankings simultaneously.
- Contributions: The paper also presents a heuristic for finding a reasonable closest fair ranking.The heuristic is introduced as a faster complementary approach to the exact method.
II. RELATED WORK
Related work covers rank aggregation with and without ties, fairness constraints, and fair rank aggregation. The paper distinguishes its contribution by directly handling tie-aware input rankings without requiring strictly ordered outputs.
- Rank aggregation without ties: Classical rank aggregation includes Kemeny optimization and approximate methods such as Borda, Pick-a-Perm, KWIKSORT, Markov-chain, and Copeland methods.Kemeny aggregation uses Kendall’s distance but is NP-hard even with four base rankers.
- Rank aggregation with ties: Tie-aware rank aggregation remains NP-hard and has motivated generalized Kendall and Spearman metrics for comparing partial rankings.The generalized Kendall distance applies a penalty parameter p when one ranking ties a pair that the other strictly orders.
- Fair ranking: Fair-ranking methods address exposure allocation, prefix group representation, and selection of qualified protected candidates in top-k rankings.Examples include exposure-based fairness frameworks and FA*IR-style prefix constraints.
- Research gap: Prior fair-ranking and fair-rank-aggregation studies are described as restricting input rankings to permutations.This paper instead considers rankings with ties as algorithm inputs.
- Positioning: Related approaches differ by using in-process fairness, ratings, permutation outputs, or weighted rankings rather than the paper’s post-processing formulation.The paper notes that these structural differences make direct mathematical comparison challenging for one line of work.
III. PRELIMINARIES AND FORMALISM
The paper represents rankings with ties as ordered buckets and compares them using a generalized Kendall–Tau distance that counts pairwise disagreements.
- Ranking Representations: A strict ranking is a permutation in which every item has a distinct ordered position.
- Ranking Representations: A tie-aware ranking is a bucket order that partitions items into ordered groups, with items in the same bucket considered tied.
- Ranking Representations: Strict rankings are a special case of bucket orders in which every bucket has size one.
- Ranking Representations: The paper uses “partial ranking” to mean a ranking with ties, excluding incomplete rankings or ratings.
- Distance Metrics: Distance metrics quantify disagreement between rankings; the paper adopts the generalized Kendall–Tau metric with penalty p = 1 for ties.
- Distance Metrics: The generalized Kendall–Tau distance compares rank values assigned to item pairs across two tie-aware rankings.
- Distance Metrics: It assigns cost 1 when an ordering is reversed between rankings or when a pair is tied in one ranking but ordered in the other.
Fair Ranking
The paper defines fair ranking over protected groups using pairwise statistical parity and formulates the closest fair ranking problem, whose search space is NP-hard and explored with synthetic data.
- Items sharing a protected attribute value form a group, while the attribute itself is treated as irrelevant to the ranking task.
- The study considers binary group fairness with two groups, G1 and G2.
- Pairwise statistical parity aims to give protected and non-protected candidates equal chances of appearing in top positions.
- The closest fair ranking minimizes its distance from a given tie-aware consensus ranking while satisfying pairwise statistical parity.
- The problem is NP-hard, with possible solutions counted by a sum involving factorials and Stirling numbers of the second kind.
- The synthetic dataset randomly generates rankings with a specified tie proportion and randomly assigns items to groups G1 and G2.
VI. METHODOLOGY
The methodology formulates closest fair ranking as a binary integer linear program that extends an existing ranking formulation with pairwise statistical parity constraints.
- The BILP adapts Brancotte et al.’s formulation by adding a fairness constraint for pairwise statistical parity.
- Binary variables indicate whether one item precedes another, the reverse ordering holds, or the items are tied.
- The formulation includes ordering, transitivity, consensus-with-ties, and parity constraints.
Heuristic
The heuristic searches over ranking buckets using several metaheuristic components and three operations that alter bucket order or ties.
- The heuristic targets instances where the exact algorithm cannot produce a solution within a reasonable time.
- It combines Sequential Local Search, Tabu Search, Simulated Annealing, and an Epsilon-Greedy Policy.
- The search operates at bucket level, exploiting tie information to confine the search space.
- Swap exchanges the rank values of two ordered buckets.
- CreatingTies combines two ordered buckets into one bucket assigned the earlier rank.
- BreakingTies divides a multi-item bucket into two or more disjoint buckets with consecutive ranks.
- Bucket-level operations can modify multiple items simultaneously and reduce algorithmic overhead.
SLS & Tabu Search Phase
The heuristic searches for fair rankings through bucket-level swaps, tie creation, and tie breaking, while tracking distance from the original ranking. It then applies item-level refinements and perturbations to improve the solution.
- Bucket-level search: Bucket-level swaps are accepted when they improve the fairness constraint, with tabu lists preventing reversals and repeated operations.The procedure updates the ranking and distance tracker after accepted moves.
- Bucket-level search: The search iterates through swaps, tie creation, and tie breaking, prioritizing smaller buckets when breaking ties to limit distance increases.Breaking smaller buckets produces smaller increments in the distance metric.
- Item-level refinement: Item-level refinement swaps items within groups and restores certain original ties when doing so reduces distance without materially affecting fairness.Restored ties are considered when consecutive ranks contain only items from the same group.
- Acceptance and perturbation: Simulated annealing decides whether to accept moves that improve fairness but could enlarge distance, using a fixed cooling schedule.This prevents updating the ranking after every fairness-improving move.
- Acceptance and perturbation: After the SLS phase, epsilon-greedy perturbation uses complete resets or partial destruction and shuffling to explore alternative fair rankings.The algorithm resets fairness values and clears tabu lists during these perturbations.
VII. EXPERIMENTATION AND FINDINGS
The experiments evaluate exact and heuristic procedures on synthetic tie-aware rankings across fairness thresholds and instance sizes. Exact solutions often require substantial ranking changes for strict parity, while computational feasibility is limited for larger instances.
- Experimental setup: Synthetic datasets contain n items, an unfair ranking, and protected-attribute information, with tested sizes ranging from 5 to 113.The exact algorithm was evaluated at 10 distinct fairness-threshold points.
- Experimental setup: The heuristic algorithm applies swap, tie-creation, and tie-breaking executions iteratively, with epsilon-greedy perturbation and termination after insufficient improvement.Algorithm 2 returns the resulting fair-ranking dataset after the iteration loop.
- Exact algorithm findings: For strict parity (ε = 0), the original ranking undergoes substantial transformation, producing maximum distance; distance decreases as the parity constraint is relaxed.The relationship is illustrated in Figure 1a.
- Exact algorithm findings: The exact algorithm produced no infeasibility for any tested threshold, while its objective function kept the number of added ties minimal.The paper attributes fairness in every possible scenario to the presence of ties, which can otherwise increase distance.
- Limitations: The current implementation becomes computationally infeasible within a reasonable time for instances with more than 104 items.The algorithm can handle multiple rankings simultaneously, but the experiments used only a single ranking.
- Implementation: The implementation uses Python, Gurobi, and Cython, evaluating threshold values concurrently on a 64-core HPC node.The solver was run under a free academic license.
- Limitations: Optimal fair rankings may be non-unique, with different environments yielding different optimal solutions having the same distance value.The discrepancy is attributed to differences between Gurobi versions.
Heuristic Performance
The heuristic is tuned and evaluated against the exact algorithm across small, medium, and large synthetic instances. It agrees strongly with the exact method on smaller instances but is less accurate on large ones.
- Evaluation setup: Hyperparameters are optimized with Optuna’s TPE using 300 trials across instances, 10 epsilon values, and two random seeds.The tasks are run concurrently, while TPE itself is applied sequentially to avoid irreproducibility issues.
- Evaluation setup: The datasets are grouped into three size categories for reporting performance results.Tables III and IV provide the principal quantitative indicators.
- Performance results: 84.4-86.6% Exact Match accuracy is achieved for small instances, compared with 26.6-28.8% for medium instances.Exact Match measures the proportion of instances where the heuristic obtains the same distance as the exact algorithm.
- Performance results: For large instances, heuristic accuracy is more modest, although its result is reasonably close to the exact algorithm and tends to have a slightly higher value.Figures 2 and 3 visualize behavior at ϵ=0 across instance sizes.
- Performance results: The plots for ϵ > 0 are provided in the Appendix.
VIII. LIMITATIONS AND FUTURE WORK
The study identifies scope limitations in its binary protected-attribute setting and outlines extensions to multiple groups, alternative fairness measures, and in-process methods. It reports that the exact method is efficient for n ≤ 10^4, while the heuristic scales to larger instances without always minimizing distance.
- Limitations and Future Work: The current approach supports only binary protected attributes, motivating extension to settings with more than two groups.The authors specifically propose investigating how ties affect exact-algorithm complexity in the multi-group setting.
- Limitations and Future Work: The authors call for experimentation with additional fairness measures, particularly proportionate fairness.
- Limitations and Future Work: Further experimentation is proposed for an in-process method using multiple rankings and for assessing the exact algorithm’s limitations.
- Results: For n ≤ 10^4, the exact method computes an optimal fair ranking efficiently.
- Evaluation: Variation metrics are computed only for instances where the heuristic did not achieve an exact match.
- Results: For larger instances, the heuristic scales well and produces a fair ranking, though not always the one with the lowest distance value.
APPENDIX
The appendix presents results for small/medium instances and large instances under ϵ > 0. These are shown separately in Figures 4 and 5.
- Appendix: Figure 4 presents results for small and medium instances with ϵ > 0.
- Appendix: Figure 5 presents results for large instances with ϵ > 0.