跳到正文
arXiv cs.CY· Antonio Ferrara, Fabio Vitale, Atsushi Miyauchi, Francesco Bonchi·· 9 小时前AI 评分26

Fair Bubble Sort:面向连续敏感属性的可证明最优公平排序

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

AI 导读

针对公平排序方法普遍要求将年龄、收入等连续敏感属性离散化分组的问题,研究者提出 Continuous Pairwise Parity(CPP)公平性概念,基于排序位置与敏感属性的 Kendall 相关性,并给出后处理算法 Fair Bubble Sort(FBS)。

正文 · 原文

View PDF HTML (experimental)

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.
Comments: 35 pages, 9 figures, 4 tables. Accepted at NeurIPS 2026. Code: this https URL
Subjects: Machine Learning (cs.LG); Computers and Society (cs.CY); Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2611.22352 [cs.LG]
  (or arXiv:2611.22352v1 [cs.LG] for this version)
  https://doi.org/10.48550/arXiv.2611.22352

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Antonio Ferrara [view email]
[v1] Tue, 17 Nov 2026 08:04:06 UTC (571 KB)

来源:arXiv cs.CY · arxiv.org