Fair Bubble Sort: Provably Optimal Fair Ranking with Continuous Sensitive Attributes
Organizations: Intesa Sanpaolo AI Research, Turin, Italy · Intesa Sanpaolo Innovation Center, Turin, Italy · Intesa Sanpaolo, Turin, Italy
Abstract
Most fair-ranking methods assume categorical protected attributes, requiring continuous attributes such as age or income to be discretized into groups. This introduces arbitrary thresholds, loses fine-grained information, and ignores the natural ordering of the attribute. In this paper, we study the problem of fair ranking with continuous protected attributes without relying on thresholding. We introduce Continuous Pairwise Parity (CPP), a fairness notion based on Kendall correlation between ranking positions and the protected attribute, and seek rankings that satisfy a prescribed CPP constraint while minimizing their Kemeny distance from an initial score-based ranking. To solve this problem, we propose Fair Bubble Sort (FBS), an efficient post-processing algorithm based on targeted adjacent swaps. We prove that FBS is exactly optimal for the unweighted Kemeny distance and provide approximation guarantees for the score-weighted setting. FBS is output-sensitive, with running time determined by the number of swaps required to meet the fairness constraint. Experiments on synthetic and real-world datasets show that FBS is scalable and consistently outperforms discretization-based baselines, achieving a superior fairness-accuracy Pareto front.
Figures & tables
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| 2 | 4 | 5 | 3 | 1.667 |
| 3 | 8 | 33 | 22 | 1.500 |
| 4 | 16 | 222 | 160 | 1.387 |
| 5 | 32 | 1 580 | 1 205 | 1.311 |
| 6 | 64 | 11 800 | 9 348 | 1.262 |
| 7 | 128 | 90 928 | 73 587 | 1.236 |
| Baseline | Dataset | reached | cost vs. FBS (median) | cost vs. FBS (max) | |
|---|---|---|---|---|---|
| Wasserstein repair | COMPAS | 0.72 | 0.96 | 2.1 | 5.8 |
| German Credit | 0.98 | 1.00 | 18 | 88 | |
| Law School | 0.85 | 0.98 | 1.3 | 11 | |
| Communities | 0.56 | 0.99 | 2.0 | 2.8 | |
| Residual repair | COMPAS | 0.72 | 0.95 | 2.6 | 3.8 |
| German Credit | 0.98 | 0.99 | 70 | 70 |
| Dataset (matched ) | Metric | Random fair | Best baseline | FBS | FBS-NDCG |
|---|---|---|---|---|---|
| COMPAS ( ) | NDCG | 0.920 | 0.995 | 0.991 | 0.998 |
| NDCG@10 | 0.400 | 1.000 | 0.889 | 1.000 | |
| NDCG@100 | 0.440 | 0.997 | 0.872 | 1.000 | |
| German Credit ( ) | NDCG | 0.790 | 0.999 | 1.000 | 1.000 |
| NDCG@10 | 0.210 | 0.992 | 1.000 | 1.000 | |
| NDCG@100 | 0.290 | 0.996 | 1.000 | 1.000 |
| Dataset | Spearman | distance correlation | HSIC | positional discrepancy | |
|---|---|---|---|---|---|
| Communities | 0.56 | 0.62 0.19 | 0.57 0.36 | 0.300 0.143 | 1.26 0.40 |
| COMPAS | 0.72 | 0.42 0.13 | 0.41 0.23 | 0.131 0.042 | 0.94 0.48 |
| Law School | 0.85 | 0.22 0.06 | 0.20 0.10 | 0.032 0.003 | 0.47 0.15 |
| German Credit | 0.98 | 0.03 0.01 | 0.06 0.07 | 0.005 0.005 | 0.16 0.17 |
Algorithmic Fairness
Algorithmic fairness studies how automated decisions distribute errors, opportunities, and harms across groups, and how to measure and reduce disparities.
See all 452 papers