This paper, presented at NeurIPS 2026, introduces Fair Bubble Sort (FBS), a post-processing algorithm designed for fair ranking when sensitive attributes (like age, income, or health scores) are continuous rather than categorical. By moving away from arbitrary discretization, the authors provide a theoretically grounded and efficient way to balance utility and fairness in high-stakes ranking scenarios.
TL;DR
Fair Bubble Sort (FBS) is a provably optimal post-processing algorithm for fair ranking with continuous sensitive attributes. It avoids the pitfalls of discretization by optimizing a new metric, Continuous Pairwise Parity (CPP), through targeted adjacent swaps, achieving a superior utility-fairness trade-off compared to existing group-based methods.
What Problem Does This Paper Address?
Algorithmic ranking systems—used in everything from hiring to college admissions—must often satisfy fairness constraints. Traditionally, this is handled via "group fairness," which requires sensitive attributes to be categorical (e.g., binary gender). When faced with continuous data like age or credit scores, the standard practice is to "bin" the data into discrete groups.
The authors argue that this discretization is fundamentally flawed:
- Arbitrary Thresholds: Deciding where one age group ends and another begins is often subjective.
- Information Loss: Individuals at the edges of a bin are treated as identical to those in the center, discarding fine-grained nuances.
- Ignoring Ordinality: Bins treat the relationship between "Age 20-30" and "Age 30-40" as purely categorical, ignoring the natural numerical ordering.
The challenge lies in the combinatorial nature of rankings; standard continuous fairness regularizers used in regression don't easily translate to discrete permutations.
Methods
The authors propose a two-part solution: a new fairness metric and an algorithm to optimize it.
Continuous Pairwise Parity (CPP)
Instead of group parity, they introduce CPP, based on the Kendall-$\tau$ correlation between an item's rank and its sensitive attribute value. A ranking is considered "fair" if this correlation is near zero—meaning a higher sensitive attribute value doesn't make an item more (or less) likely to be ranked higher.
Fair Bubble Sort (FBS)
To achieve fairness, the authors seek a ranking that satisfies a CPP constraint while staying as close as possible to the original, utility-driven ranking. They measure "closeness" using the Kemeny distance (the number of pairwise inversions).
The FBS algorithm works by performing targeted adjacent swaps. Because an adjacent swap is the "atomic unit" of both cost (it changes the Kemeny distance by exactly 1) and fairness progress (it changes the concordant/discordant pair count by exactly 2), it allows for precise navigation of the utility-fairness trade-off.
- Unweighted FBS: Treats every swap as having equal cost. The authors prove this is exactly optimal.
- Weighted FBS: Swapping items with very different original scores costs more than swapping items with similar scores. This version uses a min-heap to greedily pick the "cheapest" fairness-improving swaps.
Datasets
The authors evaluated FBS on four standard fair-ranking datasets, using continuous attributes for each:
- COMPAS: Recidivism risk scores, using age as the sensitive attribute.
- German Credit: Credit amounts, using age as the sensitive attribute.
- Law School: LSAT scores, using undergraduate GPA as the sensitive attribute.
- Communities and Crime: Violent crime rates, using poverty rate as the sensitive attribute.
They also utilized synthetic datasets to test the algorithm across varying levels of score-attribute correlation.
Key Insights and Ideas
- The Pairwise Bridge: The "aha moment" is realizing that both the fairness metric (Kendall correlation) and the utility loss metric (Kemeny distance) share a pairwise structure. This makes the adjacent swap a uniquely powerful algorithmic primitive for this problem.
- Discretization is Costly: The experiments show that discretization-based baselines consistently pay a higher utility price for the same level of fairness because they are "blind" to unfairness within their own bins.
- Output-Sensitivity: The algorithm's runtime is tied to the number of swaps ($K^*$) needed to reach the fairness target. In practice, if a ranking is already somewhat fair, FBS is extremely fast.
Key Results
- Optimality: FBS is proven to be exactly optimal for the unweighted Kemeny distance. For the weighted case, the authors prove an asymptotic approximation ratio of ~1.21 in specific settings and conjecture a general 2-approximation bound.
- Pareto Dominance: In real-world tests, FBS consistently traces a Pareto front that dominates discretization baselines like DetConstSort and FA*IR.
- Scalability: The algorithm is highly scalable, handling datasets with millions of items ($n \approx 3 \times 10^6$) in reasonable time, as shown in the empirical scalability analysis.
Limitations and Future Work
- Single Attribute: Currently, FBS handles only one continuous sensitive attribute at a time. Extending this to multiple attributes simultaneously introduces complex combinatorial constraints.
- Static Setting: The work focuses on "single-shot" static ranking. The authors note that long-term dynamics and feedback loops in ranking systems remain an open area for future research.
- Conjecture Proof: While the 2-approximation for the weighted case is strongly supported by empirical evidence (see Figure 1), a formal mathematical proof for all general cases is still pending.
Summary updated