Fair Bubble Sort: Provably Optimal Fair Ranking with Continuous Sensitive Attributes

Algorithmic ranking systems increasingly dictate high-stakes outcomes, yet most fairness interventions implicitly assume that protected attributes are categorical. When sensitive attributes are inherently continuous (e.g., age, income, or health scores), standard practices rely on arbitrary discretization, which discards crucial fine-grained information and destroys the natural ordinality of the data. In this paper, we study the problem of fair ranking with continuous protected attributes without relying on thresholding. We formalize fairness via the Kendall correlation between the ranking and the continuous attribute, and measure utility loss via the Kemeny distance from an initial score-based ranking. To solve this, we propose Fair Bubble Sort (FBS), a highly efficient adjacent-swap algorithm that minimizes utility loss subject to a strict continuous fairness constraint. We provide strong theoretical guarantees, proving that FBS is exactly optimal for the unweighted Kemeny distance. Extensive 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.