betaFeedback

WorksComputer Science

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

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.

Introduction

Algorithmic ranking systems increasingly influence decisions in high-stakes domains ranging from hiring to criminal justice, from credit scoring to college admission. As a consequence, fairness aspects in algorithmic ranking have attracted growing attention [18, 28, 31, 41, 30]. Much of such literature deals with group fairness along the lines of demographic parity [9] or equal opportunity [16], i.e., requiring the same chances of a positive outcome for different demographic groups, as defined by protected attributes, such as gender or race. In the case of ranking, this is typically cast as the problem of maximizing utility under a group-fairness constraint, which requires a minimum fraction of individuals from each group to be included in the top-kk positions [3, 5, 34]. The very notion of groups implies an underlying categorical attribute. However, in many real-world scenarios, sensitive attributes are inherently continuous, such as age, income, or health scores. When dealing with such variables, the standard practice of discretizing them into groups introduces arbitrary thresholds, discards fine-grain information about the population (individuals falling into the same bucket are treated equivalently), and destroys the natural ordinality of the data (e.g., the fact that the bucket of age [20,30) comes after the bucket [13,20) and before the [30,45) one). Despite recent progress on continuous sensitive attributes in classification and regression, fair ranking with continuous attributes remains largely unexplored. The core challenge lies in the combinatorial nature of rankings: standard continuous fairness regularizers cannot be trivially applied to listwise utility metrics or discrete ranking permutations.

In this paper, we study the problem of producing a ranking that is as close as possible to a given score-based ranking while satisfying a fairness constraint defined directly on a continuous protected attribute, without any discretization. Our starting point is a pairwise view of fairness: in a fair ranking, an item with a larger protected-attribute value should be no more likely to rank above another item than below it. We capture this principle through Continuous Pairwise Parity (CPP), defined using the Kendall correlation between ranking positions and the protected attribute. CPP requires no discretization, preserves the ordinal information in the attribute, and reduces to pairwise statistical parity for binary protected attributes.

Given a score-based ranking, our objective is to find the closest ranking satisfying a prescribed CPP constraint. We measure distortion using the Kemeny distance, as it mirrors the pairwise structure of the fairness notion, decomposing the utility loss as a sum over pairs of items whose order in the produced ranking disagrees with the score-based ranking. Weighting each pair by their difference in score further captures the intuition that swapping items of near-identical merit is essentially costless, while swapping items of very different scores is expensive. This shared pairwise decomposition of cost and fairness is precisely what allows a single algorithmic primitive – the adjacent swap – to navigate both quantities, and is the structural feature on which our theoretical guarantees rest (see Appendix B for an extended discussion motivating Continuous Pairwise Parity).

Paper Contributions. The main contributions of this paper are summarised as follows:

  1. We introduce the fairness notion of Continuous Pairwise Parity (CPP), extending pairwise statistical parity [29] to continuous protected attributes.

  1. We propose Fair Bubble Sort (FBS), the first theoretically grounded post-processing algorithm that optimally navigates the utility-fairness trade-off for continuous attributes via targeted adjacent swaps.

  1. We prove that FBS is exactly optimal for the unweighted Kemeny distance (Theorem 1). For the weighted case, we prove an asymptotic ratio of (1+2)/2≈1.21(1+\sqrt{2})/2 \approx1.21 for integer scores in the all-ascending attribute case with nn a power of two (Proposition 3). Extensive empirical evidence further suggests that FBS may satisfy a general 2-approximation bound.

  1. We show that FBS is highly scalable, running in O(nlog⁡n+K∗)O(n \log n + K^*) time for the unweighted case and in O((n+K∗)log⁡n)O((n + K^*) \log n) time for the weighted case, where K∗K^* is the minimum number of adjacent swaps required to satisfy the fairness constraint (Propositions 4).

  1. We validate FBS on four real-world datasets, empirically demonstrating its scalability and its superior performance over non-trivial baseline models.

Related Work

Our work sits at the intersection of algorithmic fair ranking and the treatment of continuous sensitive attributes, bridging two traditionally separate lines of research.

Fair Ranking. The literature on fair ranking has grown significantly, driven by the need to mitigate historical biases in search, recommendation, selection, and allocation systems [18, 28, 31, 41, 30]. With a few exceptions that focus on individual fairness [9, 3, 33], or that tackle individual and group fairness jointly [12, 40], vast majority of the approaches formulate fairness as a group-level constraint, assuming that the protected attribute is categorical (e.g., binary gender or discrete race). Solutions typically enforce variants of demographic parity or proportional representation, ensuring that a minimum fraction of items from each group appears in the top-kk positions or in every prefix of the ranking [38, 5, 39, 34, 37, 2, 13]. Conceptually closest to our work is the notion of pairwise fairness [25, 29], which evaluates the probability of a protected candidate being ranked above a non-protected one. A fundamental limitation of all these approaches is their reliance on predefined protected groups, requiring either categorical protected attributes or discrete bins. When dealing with inherently continuous protected attributes, enforcing these metrics requires arbitrary thresholding, which discards fine-grained intra-group variance and destroys the ordinal nature of the data.

Continuous Sensitive Attributes. In the broader machine learning research, the flaws of discretizing continuous sensitive attributes have been recently recognized, primarily within the contexts of regression and classification. Seminal works have proposed matching continuous distributions or penalizing statistical dependence to enforce fairness. For instance, [27] introduced fairness-aware learning using the Rényi maximum correlation coefficient, while [24] formulated non-convex optimization techniques for fair regression. Another prominent line of research leverages causal inference, where continuous sensitive attributes are naturally treated as nodes in structural equation models. In this context, [26] introduced counterfactual fairness, ensuring that predicted distributions remain invariant under counterfactual changes to the continuous protected attribute, a framework later extended by [6] to isolate path-specific fair effects. Alternatively, frameworks based on individual fairness [9] accommodate continuous spaces by requiring that similar individuals receive similar predictions. While mathematically robust, these continuous regularizers, segmentation strategies, and causal frameworks are designed for differentiable loss functions and point-wise predictions, making them inapplicable to the discrete, combinatorial nature of listwise ranking systems.

Bridging the Gap. The specific intersection of fair ranking and continuous protected attributes is still largely unexplored. While recent preliminary work by Giuliani et al. [14] has highlighted the necessity of moving beyond discrete groups by exploring continuous attributes within long-term, dynamical allocation systems, the fundamental algorithmic challenge of single-shot, static fair ranking remains unresolved. To the best of our knowledge, we propose the first theoretically grounded post-processing algorithm to enforce fairness over continuous attributes in static ranking.

Preliminaries

Let U=[n]U = [n] be a set of nn items and SUS_U be the symmetric group of all permutations of UU. A ranking rr is an element of SUS_U, i.e., a bijection r:U→[n]r : U \to[n], where r(u)r(u) denotes the position of item uu in the ranking. Each item u∈Uu \in U has a continuous sensitive attribute a(u)∈R+a(u) \in\mathbb{R}_+ and a score s(u)∈R+s(u) \in\mathbb{R}_+. The score s(u)s(u) indicates the overall fitness/utility of uu for the task at hand: it might be, e.g., the results of a test in a college admission, or the output of a complex machine learning model in a hiring setting. We assume higher score ss is better. Ranking simply by ss is not considered adequate in the fairness literature, as ss might encode historical biases, which fair ranking aims to fix by producing a ranking that is as close as possible to the one induced by ss while meeting the given fairness criteria. We denote rsr_s the “unfair” score-based ranking obtained by sorting items in descending order of ss.

Kemeny distance. We denote by Inv⁡(rs,r):={(i,j)∣1<i<j<n, (rs(j)−rs(i))(r(i)−r(j))>0}\operatorname{Inv}(r_s,r) := \{(i,j) \mid1 < i < j < n,\ (r_s(j) - r_s(i))(r(i) - r(j)) > 0\} the inversion set of rr w.r.t. rsr_s, the item pairs whose relative order in rr differs from that in rsr_s. We denote by d(rs,r)d(r_s,r) the Kemeny distance1 between rsr_s and an alternative ranking rr, defined as

d(rs,r)=∑(i,j)∈Inv⁡(rs,r)wij,d(r_s,r) = \sum_{(i,j)\in\operatorname{Inv}(r_s,r)} w_{ij},

where wij≥0w_{ij} \ge0 is a non-negative weight assigned to each pair. While the proposed algorithm and all theoretical results hold for any weight function wij≥0w_{ij} \ge0, in this paper we consider two cases: the unweighted case with uniform weights wij=1/(n2)w_{ij} = 1/\binom{n}{2} and the score-gap weighted case with wij=∣s(i)−s(j)∣/Ww_{ij} = |s(i) - s(j)|/W, where W=∑1≤k<l≤n∣s(k)−s(l)∣W = \sum_{1 \le k<l \le n} |s(k) - s(l)| is a normalization constant. Both choices yield d∈[0,1]d \in[0,1], but in the score-gap weighted case swapping items with closer scores is cheaper than swapping items with further scores.

Continuous Pairwise Parity (CPP). Let N↗(r):=∑1≤i<j≤n1[(r(j)−r(i))(a(j)−a(i))>0]N_{\nearrow}(r) := \sum_{1 \le i<j \le n} \mathbb{1}[(r(j) - r(i))(a(j) - a(i)) > 0] and N↘(r):=∑1≤i<j≤n1[(r(j)−r(i))(a(j)−a(i))<0]N_{\searrow}(r) := \sum_{1 \le i<j \le n} \mathbb{1}[(r(j) - r(i))(a(j) - a(i)) < 0] denote the number of concordant and discordant pairs between the ranking and the attribute values, respectively. The Kendall-τ\tau correlation between a ranking rr and the attribute aa is τ(r,a)=N↗(r)−N↘(r)(n2)\tau(r,a) = \frac{N_{\nearrow}(r)-N_{\searrow}(r)}{\binom{n}{2}}. A ranking is fair when this correlation is close to zero. Since τ(r,a)∈[−1,1]\tau(r,a) \in[-1,1], we define the CPP fairness measure as ϕ(r):=1−∣τ(r,a)∣\phi(r) := 1 - |\tau(r,a)|, so that ϕ(r)=1\phi(r) = 1 indicates perfect fairness and ϕ(r)=0\phi(r) = 0 maximal unfairness. CPP needs no binning of the attribute, uses only its order, and decomposes over pairs in the same way as the Kemeny distance; when the attribute is binary, ϕ(r)=1\phi(r) = 1 is exactly the pairwise statistical parity of [25] (Appendix B).

Problem 1. Given the set of nn items UU, their sensitive attribute aa and score ss, given the weighted or unweighted Kemeny distance d(⋅,⋅)d(\cdot,\cdot) and the CPP fairness measure ϕ(⋅)\phi(\cdot), as defined above, find the ranking rr that minimizes the distance from the score-based ranking rsr_s, subject to the fairness constraint ϕ(r)≥ψ\phi(r) \ge\psi, where ψ∈[0,1]\psi\in[0,1] is a predefined fairness threshold:

arg⁡min⁡r∈SU: ϕ(r)≥ψ d(rs,r).(1)\underset{r \in S_U:\,\phi(r)\ge\psi}{\arg\min}\ d(r_s,r). \tag*{(1)}

Remark. Throughout the paper we assume that ss and aa are both injective, i.e. no two items share the same score or the same attribute value. This is without loss of generality: whenever s(u)=s(v)s(u) = s(v), the pair {u,v}\{u,v\} contributes ∣s(u)−s(v)∣=0|s(u)-s(v)| = 0 to the weighted Kemeny distance, so swapping them is free; whenever a(u)=a(v)a(u) = a(v), the pair contributes to neither N↗N_{\nearrow} nor N↘N_{\searrow}, so their ordering does not affect ϕ\phi. Ties can therefore be broken by an arbitrary total order, without losing the theoretical results presented in the paper (see detailed discussion at the end of § 4).

Method

Both our notions of fairness and distance from the score-based ranking are defined in terms of pairwise comparisons. This shared structure suggests a natural algorithmic primitive: the adjacent swap. Swapping two items at consecutive positions kk, k+1k+1 flips the orientation of exactly one pair – it either creates or resolves a single inversion with respect to rsr_s, and it changes the difference N↗−N↘N_{\nearrow} - N_{\searrow} by exactly ±2\pm2 (Observation 1). No other pair is affected. This locality makes adjacent swaps the atomic unit of both cost and fairness progress: each swap incurs the smallest possible perturbation to the ranking while making a discrete, predictable step toward the fairness target. In the following, for convenience, we refer to sign⁡(N↗−N↘)\operatorname{sign}(N_{\nearrow} - N_{\searrow}) as the majority sign and we work with the imbalance Δ(r):=∣N↗(r)−N↘(r)∣\Delta(r) := |N_{\nearrow}(r) - N_{\searrow}(r)|, so that the constraint ϕ(r)≥ψ\phi(r) \ge\psi is equivalent to

Δ(r)≤Δ∗:=⌈n(n−1)2(1−ψ)⌉.\Delta(r) \le\Delta^{*} := \left\lceil\frac{n(n-1)}{2}(1-\psi) \right\rceil.

The key design insight is that, when Δ(r)>Δ∗\Delta(r) > \Delta^{*}, there always exists at least one adjacent pair of the majority sign whose swap reduces Δ\Delta by 22 (Lemma 3). A greedy strategy that repeatedly picks such a swap is therefore always well defined; moreover, since each swap reduces Δ\Delta by exactly 22, the total number of swaps K∗K^{*} is determined by the initial imbalance Δ0:=Δ(rs)\Delta_0 := \Delta(r_s) and the threshold alone. Note that Δ\Delta retains the parity of Δ0\Delta_0; the algorithm therefore sets Δ∗←max⁡(Δ∗,Δ0 mod 2)\Delta^{*} \leftarrow\max(\Delta^{*}, \Delta_0 \bmod2) to guarantee feasibility. Every swap made by FBS improves fairness and increases the distance from rsr_s (see the proof of Theorem 1), so FBS never moves back towards rsr_s. One may ask whether this costs optimality, that is, whether some optimal ranking can only be reached by paths that at some point move back towards rsr_s. Lemma 2 in § 5 shows that it does not: every optimal ranking is reachable from rsr_s by adjacent swaps along which the distance from rsr_s never decreases.

The resulting algorithm, dubbed Fair Bubble Sort (FBS), is provided in Algorithm 1 for the unweighted Kemeny distance. The pseudocode for the weighted case is instead given in Algorithm 2 in Appendix § 13. Like classical bubble sort, our method operates exclusively via adjacent swaps, selecting at each step a swap that improves fairness. In the pseudocode we use uppercase arrays indexed by position: R[i]R[i] is the item at position ii and A[i]A[i] its attribute (i.e., RR stores the ranking in one-line notation, the inverse of the function r:U→[n]r: U \to[n] defined in § 3). Lines 1–6 initialise the algorithm. The arrays are initialized according to the score-based ranking rsr_s (descending order of score, line 1). The sign array σ\sigma records the orientation of each adjacent pair (line 2), and the global counts N↗,N↘N_{\nearrow}, N_{\searrow} are computed in O(nlog⁡n)O(n\log n) via a merge-sort-based count (line 3). The parity-safe threshold Δ∗\Delta^{*} is derived from ψ\psi (line 4), the majority sign μ\mu identifies which type of pair is in excess (line 5), and the linked list LL collects all positions eligible for swapping (line 6).

The main loop (lines 7–24) iterates until the imbalance Δ(r)\Delta(r) falls within the threshold Δ∗\Delta^{*}. At each iteration, an arbitrary eligible position k∗k^{*} is retrieved from LL in O(1)O(1) (line 8) and the corresponding adjacent pair is swapped (line 9). The for-loop (lines 10–22) performs the local update: it examines the three sign entries that may have changed – σ[k∗−1]\sigma[k^{*}-1], σ[k∗]\sigma[k^{*}], σ[k∗+1]\sigma[k^{*}+1] – and updates LL accordingly. The global counts are updated in O(1)O(1) (line 23).

Algorithm 1 Fair Bubble Sort (FBS) – unweighted Kemeny distance
Require: Items $U = [n]$, attribute $a : U \to \mathbb{R}_{+}$, score $s : U \to \mathbb{R}_{+}$, fairness threshold $\psi \in [0,1]$
Ensure: Ranking $R$ solving Problem 1 with the unweighted Kemeny distance
1: $(R,A) \gets$ arrays initialized according to $r_s$ (descending order of score) ▷ initial $r_s$
2: $\sigma[k] \gets \operatorname{sign}(A[k+1] - A[k])$ for $k = 1,\ldots,n-1$ ▷ adjacent-pair signs
3: $N_{\nearrow} \gets |\{i < j : A[i] < A[j]\}|$; $N_{\searrow} \gets |\{i < j : A[i] > A[j]\}|$
4: $\Delta^{*} \gets \max\{\lfloor(1-\psi)n(n-1)/2\rfloor, |N_{\nearrow} - N_{\searrow}| \bmod 2\}$ ▷ parity-safe threshold
5: $\mu \gets \operatorname{sign}(N_{\nearrow} - N_{\searrow})$ ▷ majority sign
6: $L \gets$ doubly-linked list of $\{k : \sigma[k] = \mu\}$ ▷ build in $O(n)$
7: while $|N_{\nearrow} - N_{\searrow}| > \Delta^{*}$ do
8: $k^{*} \gets$ any element of $L$ ▷ $O(1)$
9: swap $R[k^{*}] \leftrightarrow R[k^{*}+1]$, $A[k^{*}] \leftrightarrow A[k^{*}+1]$
10: for $\ell \in \{k^{*}-1,k^{*},k^{*}+1\} \cap \{1,\ldots,n-1\}$ do
11: $\sigma_{\mathrm{old}} \gets \sigma[\ell]$
12: if $\ell = k^{*}$ then
13: $\sigma[\ell] \gets -\sigma[\ell]$ ▷ middle sign flips
14: else
15: $\sigma[\ell] \gets \operatorname{sign}(A[\ell+1] - A[\ell])$
16: end if
17: if $\sigma_{\mathrm{old}} = \mu$ and $\sigma[\ell] \ne \mu$ then
18: remove $\ell$ from $L$ ▷ $O(1)$
19: else if $\sigma_{\mathrm{old}} \ne \mu$ and $\sigma[\ell] = \mu$ then
20: insert $\ell$ into $L$ ▷ $O(1)$
21: end if
22: end for
23: $N_{\nearrow} \gets N_{\nearrow} - \mu$; $N_{\searrow} \gets N_{\searrow} + \mu$
24: end while
25: return $R$

Unweighted vs. weighted Kemeny distance. Algorithm 1 presents FBS for the unweighted Kemeny distance, where every swap has unit cost. Since the total cost depends only on the number of swaps K∗K^{*} and not on which majority-sign pairs are selected (Theorem 1), any majority-sign adjacent pair is equally good, and a doubly-linked list LL suffices to maintain the pool of eligible positions in O(1)O(1) per swap. When the Kemeny distance is weighted by score gaps wij=∣s(i)−s(j)∣w_{ij} = |s(i)-s(j)|, different swaps have different costs and FBS must select the cheapest one at each step. The algorithm additionally maintains a score array S[i]S[i]; the linked list is replaced by a min-heap keyed by the adjacent cost c[k]=∣S[k]−S[k+1]∣c[k] = |S[k]-S[k+1]|, yielding an O((n+K∗)log⁡n)O((n+K^{*}) \log n) algorithm (the full pseudocode is given in Algorithm 2 in Appendix § 13).

Handling ties in the attribute. Both algorithms (Algorithms 1 and 2) are presented, for simplicity sake, under the general-position assumption that attribute values are pairwise distinct. In practice, real-valued attributes may contain ties (e.g. integer-valued age or discretised scores). Two modifications suffice to handle ties correctly; the algorithm structure, the greedy optimality proof, and the complexity bounds are otherwise unchanged.

References

  1. [1]Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There’s software used across the country to predict future criminals. and it’s biased against blacks. ProPublica, May 2016.
  2. [2]Abolfazl Asudeh, H. V. Jagadish, Julia Stoyanovich, and Gautam Das. Designing fair ranking schemes. In SIGMOD, pages 1259–1276, 2019.DOI
  3. [3]Asia J Biega, Krishna P Gummadi, and Gerhard Weikum. Equity of attention: Amortizing individual fairness in rankings. In The 41st international acm sigir conference on research & development in information retrieval, pages 405–414, 2018.
  4. [4]Kathleen Cachel and Elke Rundensteiner. Fairranktune: A python toolkit for fair ranking tasks. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pages 5195–5199, 2024.
  5. [5]L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. In ICALP, 2018.arxiv.org/abs/1704.06840
  6. [6]Silvia Chiappa. Path-specific counterfactual fairness. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019.
  7. [7]Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam. Improved bounds for computing kemeny rankings. In AAAI, volume 6, pages 620–626, 2006.
  8. [8]Persi Diaconis and Ronald L Graham. Spearman’s footrule as a measure of disarray. Journal of the Royal Statistical Society Series B: Statistical Methodology, 39(2):262–268, 1977.DOI
  9. [9]Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 214–226, 2012.
  10. [10]Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D Sivakumar, and Erik Vee. Comparing and aggregating rankings with ties. In Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 47–58, 2004.DOI
  11. [11]Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, page 259–268, 2015.arxiv.org/abs/1412.3756
  12. [12]David García-Soriano and Francesco Bonchi. Maxmin-fair ranking: Individual fairness under group-fairness constraints. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’21, page 436–446, 2021.
  13. [13]Sahin Cem Geyik, Stuart Ambler, and Krishnaram Kenthapadi. Fairness-aware ranking in search & recommendation systems with application to linkedin talent search. In Proceedings of the 25th acm sigkdd international conference on knowledge discovery & data mining, pages 2221–2231, 2019.DOI
  14. [14]Luca Giuliani, Eleonora Misino, Roberta Calegari, and Michele Lombardi. Long-term fairness strategies in ranking with continuous sensitive attributes. In Roberta Calegari, Virginia Dignum, and Barry O’Sullivan, editors, Proceedings of the 2nd Workshop on Fairness and Bias in AI co-located with 27th European Conference on Artificial Intelligence (ECAI 2024), Santiago de Compostela, Spain, October 20th, 2024, CEUR Workshop Proceedings. CEUR-WS.org, 2024.
  15. [15]Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. In International conference on algorithmic learning theory, pages 63–77. Springer, 2005.
  16. [16]Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In NeurIPS, pages 3315–3323, 2016.arxiv.org/abs/1610.02413
  17. [17]Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOI: https://doi.org/10.24432/C5NC77.
  18. [18]H. V. Jagadish, Francesco Bonchi, Tina Eliassi-Rad, Lise Getoor, Krishna Gummadi, and Julia Stoyanovich. The responsibility challenge for data. In Proceedings of the 2019 International Conference on Management of Data, SIGMOD ’19, page 412–414, 2019.DOI
  19. [19]James E Johndrow and Kristian Lum. An algorithm for removing sensitive information. The Annals of Applied Statistics, 13(1):189–220, 2019.arxiv.org/abs/1703.04957
  20. [20]Morgan Kelly. Inequality and crime. Review of economics and Statistics, 82(4):530–539, 2000.DOI
  21. [21]John G. Kemeny and J. Laurie Snell. Preference ranking: An axiomatic approach. In Mathematical Models in the Social Sciences, pages 9–23. Ginn, Boston, MA, USA, 1962.
  22. [22]Ivan Kitanovski. fairsearchcore: A Python library with the core algorithms used to do fair search. Python package, version 1.0.4, 2019. https://pypi.org/project/fairsearchcore/.
  23. [23]Donald E Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley Professional, 1998.
  24. [24]Junpei Komiyama, Akiko Takeda, Junya Honda, and Hajime Shimao. Nonconvex optimization for regression with fairness constraints. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2737–2746. PMLR, 10–15 Jul 2018.
  25. [25]Caitlin Kuhlman and Elke Rundensteiner. Rank aggregation algorithms for fair consensus. Proceedings of the VLDB Endowment, 13(12), 2020.DOI
  26. [26]Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.arxiv.org/abs/1703.06856
  27. [27]Jeremie Mary, Clément Calauzènes, and Noureddine El Karoui. Fairness-aware learning for continuous attributes and treatments. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4382–4391. PMLR, 09–15 Jun 2019.
  28. [28]Shira Mitchell, Eric Potash, Solon Barocas, Alexander D’Amour, and Kristian Lum. Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application, 8(1):141–163, 2021.DOI
  29. [29]Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Serena Wang. Pairwise fairness for ranking and regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5248–5255, 2020.arxiv.org/abs/1906.05330
  30. [30]Gourab K. Patro, Lorenzo Porcaro, Laura Mitchell, Qiyue Zhang, Meike Zehlike, and Nikhil Garg. Fair ranking: A critical review, challenges, and future directions. In 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 1929–1942, 2022.arxiv.org/abs/2201.12662
  31. [31]Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutika. Fairness in rankings and recommendations: an overview. The VLDB Journal, 31(3):431–458, 2022.arxiv.org/abs/2104.05994
  32. [32]Michael Redmond. Communities and Crime. UCI Machine Learning Repository, 2002. DOI: https://doi.org/10.24432/C53W3X.
  33. [33]Yuta Saito and Thorsten Joachims. Fair ranking as fair division: Impact-based individual fairness in ranking. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1514–1524, 2022.DOI
  34. [34]Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In KDD, pages 2219–2228, 2018.DOI
  35. [35]Gábor J Székely, Maria L Rizzo, and Nail K Bakirov. Measuring and testing dependence by correlation of distances. Annals of Statistics, 35(6):2769–2794, 2007.DOI
  36. [36]Linda F. Wightman. LSAC national longitudinal bar passage study. LSAC research report series, Law School Admission Council, 1998.
  37. [37]Ke Yang, Vasilis Gkatzelis, and Julia Stoyanovich. Balanced ranking with diversity constraints. In IJCAI, pages 6035–6042, 2019.arxiv.org/abs/1906.01747
  38. [38]Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In SSDBM, pages 22:1–22:6, 2017.arxiv.org/abs/1610.08559
  39. [39]Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yates. Fa*ir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM Conference on Information and Knowledge Management (CIKM), pages 1569–1578, 2017.
  40. [40]Meike Zehlike, Philipp Hacker, and Emil Wiedemann. Matching code and law: achieving algorithmic fairness with optimal transport. Data Mining and Knowledge Discovery, 34(1):163–200, 2020.arxiv.org/abs/1712.07924
  41. [41]Meike Zehlike, Ke Yang, and Julia Stoyanovich. Fairness in ranking, part i: Score-based ranking. ACM Computing Surveys, 55(6):1–36, 2022.DOI

Paper details

vlnc:W_fvwsb3am
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents