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-k k k 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:
We introduce the fairness notion of Continuous Pairwise Parity (CPP), extending pairwise statistical parity [29 ] to continuous protected attributes.
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.
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 ( 1 + 2 ) /2 ≈ 1.21 for integer scores in the all-ascending attribute case with n n n a power of two (Proposition 3 ). Extensive empirical evidence further suggests that FBS may satisfy a general 2-approximation bound.
We show that FBS is highly scalable, running in O ( n log n + K ∗ ) O(n \log n + K^*) O ( n log n + K ∗ ) time for the unweighted case and in O ( ( n + K ∗ ) log n ) O((n + K^*) \log n) O (( n + K ∗ ) log n ) time for the weighted case, where K ∗ K^* K ∗ is the minimum number of adjacent swaps required to satisfy the fairness constraint (Propositions 4).
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-k k k 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] U = [ n ] be a set of n n n items and S U S_U S U be the symmetric group of all permutations of U U U . A ranking r r r is an element of S U S_U S U , i.e., a bijection r : U → [ n ] r : U \to[n] r : U → [ n ] , where r ( u ) r(u) r ( u ) denotes the position of item u u u in the ranking. Each item u ∈ U u \in U u ∈ U has a continuous sensitive attribute a ( u ) ∈ R + a(u) \in\mathbb{R}_+ a ( u ) ∈ R + and a score s ( u ) ∈ R + s(u) \in\mathbb{R}_+ s ( u ) ∈ R + . The score s ( u ) s(u) s ( u ) indicates the overall fitness/utility of u u u 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 s s s is better. Ranking simply by s s s is not considered adequate in the fairness literature, as s s s 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 s s s while meeting the given fairness criteria. We denote r s r_s r s the “unfair” score-based ranking obtained by sorting items in descending order of s s s .
Kemeny distance. We denote by Inv ( r s , r ) : = { ( i , j ) ∣ 1 < i < j < n , ( r s ( j ) − r s ( 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\} Inv ( r s , r ) := {( i , j ) ∣ 1 < i < j < n , ( r s ( j ) − r s ( i )) ( r ( i ) − r ( j )) > 0 } the inversion set of r r r w.r.t. r s r_s r s , the item pairs whose relative order in r r r differs from that in r s r_s r s . We denote by d ( r s , r ) d(r_s,r) d ( r s , r ) the Kemeny distance1 between r s r_s r s and an alternative ranking r r r , defined as
d ( r s , r ) = ∑ ( i , j ) ∈ Inv ( r s , r ) w i j , d(r_s,r) = \sum_{(i,j)\in\operatorname{Inv}(r_s,r)} w_{ij}, d ( r s , r ) = ( i , j ) ∈ Inv ( r s , r ) ∑ w ij ,
where w i j ≥ 0 w_{ij} \ge0 w ij ≥ 0 is a non-negative weight assigned to each pair. While the proposed algorithm and all theoretical results hold for any weight function w i j ≥ 0 w_{ij} \ge0 w ij ≥ 0 , in this paper we consider two cases: the unweighted case with uniform weights w i j = 1 / ( n 2 ) w_{ij} = 1/\binom{n}{2} w ij = 1/ ( 2 n ) and the score-gap weighted case with w i j = ∣ s ( i ) − s ( j ) ∣ / W w_{ij} = |s(i) - s(j)|/W w 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)| W = ∑ 1 ≤ k < l ≤ n ∣ s ( k ) − s ( l ) ∣ is a normalization constant. Both choices yield d ∈ [ 0 , 1 ] d \in[0,1] d ∈ [ 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 ≤ n 1 [ ( 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] N ↗ ( r ) := ∑ 1 ≤ i < j ≤ n 1 [( r ( j ) − r ( i )) ( a ( j ) − a ( i )) > 0 ] and N ↘ ( r ) : = ∑ 1 ≤ i < j ≤ n 1 [ ( 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] N ↘ ( r ) := ∑ 1 ≤ i < j ≤ n 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 r r r and the attribute a a a is τ ( r , a ) = N ↗ ( r ) − N ↘ ( r ) ( n 2 ) \tau(r,a) = \frac{N_{\nearrow}(r)-N_{\searrow}(r)}{\binom{n}{2}} τ ( r , a ) = ( 2 n ) N ↗ ( r ) − N ↘ ( r ) . A ranking is fair when this correlation is close to zero. Since τ ( r , a ) ∈ [ − 1 , 1 ] \tau(r,a) \in[-1,1] τ ( r , a ) ∈ [ − 1 , 1 ] , we define the CPP fairness measure as ϕ ( r ) : = 1 − ∣ τ ( r , a ) ∣ \phi(r) := 1 - |\tau(r,a)| ϕ ( r ) := 1 − ∣ τ ( r , a ) ∣ , so that ϕ ( r ) = 1 \phi(r) = 1 ϕ ( r ) = 1 indicates perfect fairness and ϕ ( r ) = 0 \phi(r) = 0 ϕ ( 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 ϕ ( r ) = 1 is exactly the pairwise statistical parity of [25 ] (Appendix B).
Problem 1. Given the set of n n n items U U U , their sensitive attribute a a a and score s s s , given the weighted or unweighted Kemeny distance d ( ⋅ , ⋅ ) d(\cdot,\cdot) d ( ⋅ , ⋅ ) and the CPP fairness measure ϕ ( ⋅ ) \phi(\cdot) ϕ ( ⋅ ) , as defined above, find the ranking r r r that minimizes the distance from the score-based ranking r s r_s r s , subject to the fairness constraint ϕ ( r ) ≥ ψ \phi(r) \ge\psi ϕ ( r ) ≥ ψ , where ψ ∈ [ 0 , 1 ] \psi\in[0,1] ψ ∈ [ 0 , 1 ] is a predefined fairness threshold:
arg min r ∈ S U : ϕ ( r ) ≥ ψ d ( r s , r ) . (1) \underset{r \in S_U:\,\phi(r)\ge\psi}{\arg\min}\ d(r_s,r). \tag*{(1)} r ∈ S U : ϕ ( r ) ≥ ψ arg min d ( r s , r ) . (1)
Remark. Throughout the paper we assume that s s s and a a a 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) s ( u ) = s ( v ) , the pair { u , v } \{u,v\} { u , v } contributes ∣ s ( u ) − s ( v ) ∣ = 0 |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) a ( u ) = a ( v ) , the pair contributes to neither N ↗ N_{\nearrow} N ↗ nor N ↘ N_{\searrow} N ↘ , 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 k k k , k + 1 k+1 k + 1 flips the orientation of exactly one pair – it either creates or resolves a single inversion with respect to r s r_s r s , and it changes the difference N ↗ − N ↘ N_{\nearrow} - N_{\searrow} N ↗ − N ↘ by exactly ± 2 \pm2 ± 2 (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}) sign ( N ↗ − N ↘ ) as the majority sign and we work with the imbalance Δ ( r ) : = ∣ N ↗ ( r ) − N ↘ ( r ) ∣ \Delta(r) := |N_{\nearrow}(r) - N_{\searrow}(r)| Δ ( r ) := ∣ N ↗ ( r ) − N ↘ ( r ) ∣ , so that the constraint ϕ ( r ) ≥ ψ \phi(r) \ge\psi ϕ ( r ) ≥ ψ is equivalent to
Δ ( r ) ≤ Δ ∗ : = ⌈ n ( n − 1 ) 2 ( 1 − ψ ) ⌉ . \Delta(r) \le\Delta^{*} := \left\lceil\frac{n(n-1)}{2}(1-\psi) \right\rceil. Δ ( r ) ≤ Δ ∗ := ⌈ 2 n ( n − 1 ) ( 1 − ψ ) ⌉ .
The key design insight is that, when Δ ( r ) > Δ ∗ \Delta(r) > \Delta^{*} Δ ( r ) > Δ ∗ , there always exists at least one adjacent pair of the majority sign whose swap reduces Δ \Delta Δ by 2 2 2 (Lemma 3). A greedy strategy that repeatedly picks such a swap is therefore always well defined; moreover, since each swap reduces Δ \Delta Δ by exactly 2 2 2 , the total number of swaps K ∗ K^{*} K ∗ is determined by the initial imbalance Δ 0 : = Δ ( r s ) \Delta_0 := \Delta(r_s) Δ 0 := Δ ( r s ) and the threshold alone. Note that Δ \Delta Δ retains the parity of Δ 0 \Delta_0 Δ 0 ; the algorithm therefore sets Δ ∗ ← max ( Δ ∗ , Δ 0 m o d 2 ) \Delta^{*} \leftarrow\max(\Delta^{*}, \Delta_0 \bmod2) Δ ∗ ← max ( Δ ∗ , Δ 0 mod 2 ) to guarantee feasibility. Every swap made by FBS improves fairness and increases the distance from r s r_s r s (see the proof of Theorem 1), so FBS never moves back towards r s r_s r 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 r s r_s r s . Lemma 2 in § 5 shows that it does not: every optimal ranking is reachable from r s r_s r s by adjacent swaps along which the distance from r s r_s r 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] R [ i ] is the item at position i i i and A [ i ] A[i] A [ i ] its attribute (i.e., R R R stores the ranking in one-line notation, the inverse of the function r : U → [ n ] r: U \to[n] r : U → [ n ] defined in § 3 ). Lines 1–6 initialise the algorithm. The arrays are initialized according to the score-based ranking r s r_s r 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} N ↗ , N ↘ are computed in O ( n log n ) O(n\log 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 L L L collects all positions eligible for swapping (line 6).
The main loop (lines 7–24) iterates until the imbalance Δ ( r ) \Delta(r) Δ ( r ) falls within the threshold Δ ∗ \Delta^{*} Δ ∗ . At each iteration, an arbitrary eligible position k ∗ k^{*} k ∗ is retrieved from L L L in O ( 1 ) 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 ∗ − 1 ] , σ [ k ∗ ] \sigma[k^{*}] σ [ k ∗ ] , σ [ k ∗ + 1 ] \sigma[k^{*}+1] σ [ k ∗ + 1 ] – and updates L L L accordingly. The global counts are updated in O ( 1 ) 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^{*} 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 L L L suffices to maintain the pool of eligible positions in O ( 1 ) O(1) O ( 1 ) per swap. When the Kemeny distance is weighted by score gaps w i j = ∣ s ( i ) − s ( j ) ∣ w_{ij} = |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] 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]| c [ k ] = ∣ S [ k ] − S [ k + 1 ] ∣ , yielding an O ( ( n + K ∗ ) log n ) 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.
Adjacent signs. The sign array becomes σ [ k ] ∈ { + 1 , 0 , − 1 } \sigma[k] \in\{+1,0,-1\} σ [ k ] ∈ { + 1 , 0 , − 1 } , where σ [ k ] = 0 \sigma[k] = 0 σ [ k ] = 0 when A [ k ] = A [ k + 1 ] A[k] = A[k+1] A [ k ] = A [ k + 1 ] . Swapping a tied pair does not change the orientation of that pair—it was tied before and remains tied after—so Δ ( r ) \Delta(r) Δ ( r ) is unaffected. Positions with σ [ k ] = 0 \sigma[k] = 0 σ [ k ] = 0 are therefore never inserted into L L L (or H H H ) and are never selected for swapping.
Neighbour updates. After a swap at position k ∗ k^{*} k ∗ , the recomputed sign σ [ ℓ ] \sigma[\ell] σ [ ℓ ] for a neighbour ℓ ∈ { k ∗ − 1 , k ∗ + 1 } \ell\in\{k^{*}-1,k^{*}+1\} ℓ ∈ { k ∗ − 1 , k ∗ + 1 } may transition to or from 0 0 0 . If σ [ ℓ ] \sigma[\ell] σ [ ℓ ] was μ \mu μ and becomes 0 0 0 , the entry is removed from L L L (or H H H ); if it was 0 0 0 and becomes μ \mu μ , it is inserted. The middle entry σ [ k ∗ ] \sigma[k^{*}] σ [ k ∗ ] flips sign as before (+ 1 ↔ − 1 +1 \leftrightarrow-1 + 1 ↔ − 1 ) and cannot become 0 0 0 , since the swap reverses a strict inequality.
All remaining logic – the imbalance Δ ( r ) = ∣ N ↗ − N ↘ ∣ \Delta(r) = |N_{\nearrow} - N_{\searrow}| Δ ( r ) = ∣ N ↗ − N ↘ ∣ , the threshold Δ ∗ \Delta^{*} Δ ∗ , the majority sign μ \mu μ , and the O ( 1 ) O(1) O ( 1 ) update of N ↗ , N ↘ N_{\nearrow},N_{\searrow} N ↗ , N ↘ per swap – carries over without change.
Optimality of FBS for the Unweighted Problem
The proof of optimality builds on four results: (i) an adjacent swap changes the imbalance by exactly ± 2 \pm2 ± 2 and the number of inversions by exactly ± 1 \pm1 ± 1 (Observation 1); (ii) any ranking can be realized by adjacent swaps only, with the shortest sequence of swaps having length equal to ∣ Inv ( r s , r ) ∣ |\operatorname{Inv}(r_s,r)| ∣ Inv ( r s , r ) ∣ (Lemma 1); (iii) a valid majority-sign swap always exists when the imbalance exceeds the threshold (Lemma 3); (iv) FBS uses the minimum number of swaps among all feasible solutions (Proposition 1). A further structural result motivates the design of FBS: every optimal ranking is reachable from r s r_s r s by adjacent swaps along which the distance from r s r_s r s never decreases (Lemma 2), so the search space of algorithms that never move back towards r s r_s r s , to which FBS belongs, still contains every optimal ranking.
Throughout this subsection, an adjacent swap action τ k \tau_k τ k exchanges positions k k k and k + 1 k+1 k + 1 in a ranking r r r ; an algorithm π \pi π is an ordered sequence of adjacent swaps ( τ t 1 , … , τ t m ) (\tau_{t_1},\ldots,\tau_{t_m}) ( τ t 1 , … , τ t m ) such that their composition π = τ t m ∘ ⋯ ∘ τ t 1 \pi=\tau_{t_m}\circ\cdots\circ\tau_{t_1} π = τ t m ∘ ⋯ ∘ τ t 1 determines the output ranking π ∘ r s \pi\circ r_s π ∘ r s . The intermediate rankings produced by the sequence of swaps are denoted r ( 0 ) = r s r^{(0)}=r_s r ( 0 ) = r s , r ( 1 ) = τ t 1 ∘ r ( 0 ) , … , r ( m ) = τ t m ∘ r ( m − 1 ) r^{(1)}=\tau_{t_1}\circ r^{(0)},\ldots,r^{(m)}=\tau_{t_m}\circ r^{(m-1)} r ( 1 ) = τ t 1 ∘ r ( 0 ) , … , r ( m ) = τ t m ∘ r ( m − 1 ) . We let A s w a p A_{\mathrm{swap}} A swap denote the set of all such algorithms and A s w a p , ↗ ⊆ A s w a p A_{\mathrm{swap},\nearrow}\subseteq A_{\mathrm{swap}} A swap , ↗ ⊆ A swap the subset of algorithms such that d ( r s , r ( t ) ) d(r_s,r^{(t)}) d ( r s , r ( t ) ) is non-decreasing in t t t . A key elementary fact used repeatedly below is the following.
Observation 1 (Single-swap increment). Let r ′ r' r ′ be obtained from r r r by an adjacent swap of the items u , v u,v u , v at positions k , k + 1 k,k+1 k , k + 1 , r ′ = τ k ∘ r r'=\tau_k\circ r r ′ = τ k ∘ r . Then d ( r s , r ′ ) − d ( r s , r ) = ± w u v d(r_s,r')-d(r_s,r)=\pm w_{uv} d ( r s , r ′ ) − d ( r s , r ) = ± w uv , where the sign is + + + iff the swap creates an inversion with respect to r s r_s r s and − - − iff it resolves one. Moreover, the same swap flips the Kendall orientation of the pair { u , v } \{u,v\} { u , v } between ↗ \nearrow ↗ and ↘ \searrow ↘ and leaves all other pair orientations unchanged, so
Δ ( r ′ ) − Δ ( r ) ∈ { − 2 , + 2 } . \Delta(r')-\Delta(r)\in\{-2,+2\}. Δ ( r ′ ) − Δ ( r ) ∈ { − 2 , + 2 } .
Lemma 1 (Reduction to adjacent swaps [23 ] ). For every ranking r ∈ S U r\in S_U r ∈ S U there exists an algorithm π ∈ A s w a p \pi\in A_{\mathrm{swap}} π ∈ A swap such that π ∘ r s = r \pi\circ r_s=r π ∘ r s = r , and the shortest such algorithm has length ∣ Inv ( r s , r ) ∣ |\operatorname{Inv}(r_s,r)| ∣ Inv ( r s , r ) ∣ .
Lemma 2 (Reduction to non-decreasing swaps). Let r ∗ r^* r ∗ be an optimal solution to Problem 1, then there exists an algorithm π ∈ A s w a p , ↗ \pi\in A_{\mathrm{swap},\nearrow} π ∈ A swap , ↗ such that π ∘ r s = r ∗ \pi\circ r_s=r^* π ∘ r s = r ∗ .
Lemma 3 (Existence of a valid greedy swap). For any r ∈ S U r\in S_U r ∈ S U , consider b k : = a ( r − 1 ( k ) ) b_k:=a(r^{-1}(k)) b k := a ( r − 1 ( k )) for k = 1 , … , n k=1,\ldots,n k = 1 , … , n , where r − 1 ( k ) ∈ U r^{-1}(k)\in U r − 1 ( k ) ∈ U is the item at rank k k k . Under the injectivity assumption of a ( ⋅ ) a(\cdot) a ( ⋅ ) , the sequence b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n consists of pairwise distinct reals. Hence, a pair of ranks ( i , j ) (i,j) ( i , j ) with i < j i<j i < j is ↗ \nearrow ↗ iff b i < b j b_i<b_j b i < b j and ↘ \searrow ↘ iff b i > b j b_i>b_j b i > b j . If N ↗ ( r ) ≠ N ↘ ( r ) N_{\nearrow}(r)\ne N_{\searrow}(r) N ↗ ( r ) = N ↘ ( r ) , then r r r contains at least one adjacent pair of the majority sign, i.e. an index k ∈ { 1 , … , n − 1 } k\in\{1,\ldots,n-1\} k ∈ { 1 , … , n − 1 } whose flip strictly reduces Δ ( r ) \Delta(r) Δ ( r ) by 2 2 2 .
Proposition 1 (Minimality of the number of greedy swaps). Assume without loss of generality N ↗ ( r s ) ≥ N ↘ ( r s ) N_{\nearrow}(r_s)\ge N_{\searrow}(r_s) N ↗ ( r s ) ≥ N ↘ ( r s ) and set Δ 0 : = Δ ( r s ) \Delta_0:=\Delta(r_s) Δ 0 := Δ ( r s ) . If Δ 0 > Δ ∗ \Delta_0>\Delta^* Δ 0 > Δ ∗ , then FBS is well defined and terminates after exactly K ∗ : = [ ( Δ 0 − Δ ∗ ) / 2 ] K^*:=[(\Delta_0-\Delta^*)/2] K ∗ := [( Δ 0 − Δ ∗ ) /2 ] swaps. Moreover, any algorithm in A s w a p A_{\mathrm{swap}} A swap that outputs a feasible ranking uses at least K ∗ K^* K ∗ swaps.
Theorem 1 (Optimality of FBS for the unweighted Kemeny distance). Let r F B S r_{\mathrm{FBS}} r FBS denote the ranking returned by FBS. Then r F B S r_{\mathrm{FBS}} r FBS is an optimal solution of Problem 1 for the unweighted Kemeny distance. Moreover, d ( r F B S , r s ) = K ∗ / ( n 2 ) d(r_{\mathrm{FBS},r_s})=K^*/\binom{n}{2} d ( r FBS , r s ) = K ∗ / ( 2 n ) where K ∗ = [ ( Δ 0 − Δ ∗ ) / 2 ] K^*=[(\Delta_0-\Delta^*)/2] K ∗ = [( Δ 0 − Δ ∗ ) /2 ] as in Proposition 1.
All proofs for the results above are given in Appendix § 14 .
Approximation Bound for the Weighted Problem
When the Kemeny distance is weighted, different swaps have different costs and FBS must select the cheapest majority-sign adjacent pair at each step. Algorithm 2 (see pseudocode in Appendix § 13 ) replaces the doubly-linked list of Algorithm 1 with a min-heap keyed by the adjacent cost c [ k ] = ∣ S [ k ] − S [ k + 1 ] ∣ c[k]=|S[k]-S[k+1]| c [ k ] = ∣ S [ k ] − S [ k + 1 ] ∣ . Because FBS does not necessarily select the K ∗ K^* K ∗ feasible pairs of smallest cumulative weight, it loses the optimality property of the unweighted case. Nonetheless, for any strictly positive weight function, we can bound its sub-optimality in terms of the weight spread.
All the proofs of this section are given in Appendix § 15 .
Proposition 2 (Weight-spread approximation bound for FBS). Let w i j > 0 w_{ij}>0 w ij > 0 be an arbitrary strictly positive weight function, and let r F B S r_{\mathrm{FBS}} r FBS be the ranking produced by FBS and r ∗ r^* r ∗ an optimal solution to Problem 1 for the corresponding weighted Kemeny distance. Let w min : = min i < j w i j w_{\min}:=\min_{i<j}w_{ij} w m i n := min i < j w ij and w max : = max i < j w i j w_{\max}:=\max_{i<j}w_{ij} w m a x := max i < j w ij . Then: d ( r s , r F B S ) ≤ w max / w min d ( r s , r ∗ ) d(r_s,r_{\mathrm{FBS}})\le w_{\max}/w_{\min}\,d(r_s,r^*) d ( r s , r FBS ) ≤ w m a x / w m i n d ( r s , r ∗ ) .
In the remainder of this section, we study a natural and practically relevant setting in which the scores s s s of the n n n items are mapped to [ n ] [n] [ n ] – only the ordinal information of the score s s s is maintained – and the items are identified according to their score: the highest-score item will be identified with n n n , the second highest by n − 1 n-1 n − 1 , and so on till the smallest-score item 1. Having s ( i ) = i s(i)=i s ( i ) = i for i ∈ [ n ] i\in[n] i ∈ [ n ] , score-gap weights reduce to positional gaps w i j = ∣ i − j ∣ / W w_{ij}=|i-j|/W w ij = ∣ i − j ∣/ W , penalizing large displacements more than local rearrangements. In this setting, Proposition 2 yields w max / w min = n − 1 w_{\max}/w_{\min}=n-1 w m a x / w m i n = n − 1 , too loose to be informative. To obtain tighter bounds, we exploit the following identity, whose proof builds on a left/right inversion decomposition in the spirit of the displacement-inversion analysis of Diaconis and Graham [8 ] .
Lemma 4 (Spearman–Kendall identity). For integer scores s ( i ) = i s(i)=i s ( i ) = i , i = 1 , … , n i=1,\ldots,n i = 1 , … , n , with unnormalised pair weights w i j = ∣ i − j ∣ w_{ij}=|i-j| w ij = ∣ i − j ∣ and any ranking r r r ,
d ( r s , r ) = 1 2 W S 2 ( r ) , where S 2 ( r ) : = ∑ i = 1 n ( r ( i ) − i ) 2 . d(r_s,r)=\frac{1}{2W}S_2(r),\qquad\text{where}\qquad S_2(r):=\sum_{i=1}^{n}(r(i)-i)^2. d ( r s , r ) = 2 W 1 S 2 ( r ) , where S 2 ( r ) := i = 1 ∑ n ( r ( i ) − i ) 2 . is the Spearman squared displacement.
This identity transforms the weighted distance from a sum over O ( n 2 ) O(n^2) O ( n 2 ) pairs into a sum over n n n items, where each term depends only on how far item i i i has moved from its original position. The approximation ratio becomes a ratio of squared ℓ 2 \ell_2 ℓ 2 norms: d ( r s , r F B S ) / d ( r s , r ∗ ) = ∥ δ F B S ∥ 2 2 / ∥ δ ∗ ∥ 2 2 d(r_s,r_{\mathrm{FBS}})/d(r_s,r^*)=\|\delta_{\mathrm{FBS}}\|_2^2/\|\delta^*\|_2^2 d ( r s , r FBS ) / d ( r s , r ∗ ) = ∥ δ FBS ∥ 2 2 /∥ δ ∗ ∥ 2 2 , where δ i = r ( i ) − i \delta_i=r(i)-i δ i = r ( i ) − i . Exploiting this identity, we can derive the exact FBS cost in closed form for the worst-case attribute configuration (i.e., the all-ascending case a = s a=s a = s where all pairs are concordant and thus the initial imbalance is maximal), maximal fairness requirement ψ = 1 \psi=1 ψ = 1 , and n n n a power of two.
Proposition 3 (Tight bound for the all-ascending case). For integer scores s ( i ) = i s(i)=i s ( i ) = i with a = s a=s a = s , ψ = 1 \psi=1 ψ = 1 , and n = 2 t ≥ 4 n=2^t\geq4 n = 2 t ≥ 4 , FBS produces a ranking r F B S r_{\mathrm{FBS}} r FBS such that:
d ( r s , r F B S ) L P ⟶ 1 + 2 2 ≈ 1.207 as n → ∞ , \frac{d(r_s,r_{\mathrm{FBS}})}{\mathrm{LP}}\longrightarrow\frac{1+\sqrt{2}}{2}\approx1.207\qquad\text{as }n\to\infty, LP d ( r s , r FBS ) ⟶ 2 1 + 2 ≈ 1.207 as n → ∞ , where LP is the LP relaxation lower bound, L P = ∑ k = 1 K ∗ w ( k ) \mathrm{LP}=\sum_{k=1}^{K^*}w_{(k)} LP = ∑ k = 1 K ∗ w ( k ) , where w ( 1 ) ≤ w ( 2 ) ≤ ⋯ ≤ w ( K ∗ ) w_{(1)}\leq w_{(2)}\leq\cdots\leq w_{(K^*)} w ( 1 ) ≤ w ( 2 ) ≤ ⋯ ≤ w ( K ∗ ) are the sorted pair weights. In particular, d ( r s , r F B S ) < 2 d ( r s , r ∗ ) d(r_s,r_{\mathrm{FBS}})<2d(r_s,r^*) d ( r s , r FBS ) < 2 d ( r s , r ∗ ) for all n = 2 t n=2^t n = 2 t with t ≥ 2 t\geq2 t ≥ 2 .
The above asymptotic ratio d F B S / L P → ( 1 + 2 ) / 2 d_{\mathrm{FBS}}/\mathrm{LP}\to(1+\sqrt{2})/2 d FBS / LP → ( 1 + 2 ) /2 is independent of n n n and has been further verified computationally for all n = 2 t n=2^t n = 2 t with $t=2,\ldots,21 (Table 1 in Appendix § 15 .§ 3 ).
Table 1. FBS cost vs. LP relaxation for a = s a=s a = s , n = 2 t n=2^t n = 2 t , t = 2 , … , 21 t=2,\ldots,21 t = 2 , … , 21 . The ratio converges to ( 1 + 2 ) / 2 ≈ 1.207 (1+\sqrt{2})/2\approx1.207 ( 1 + 2 ) /2 ≈ 1.207 .
Our analysis and experiments suggest that the 2-approximation holds in general, dropping the all-ascending assumption a = s a=s a = s . That is, we conjecture that d ( r s , r F B S ) < 2 d ( r s , r ∗ ) d(r_s,r_{\mathrm{FBS}})<2d(r_s,r^*) d ( r s , r FBS ) < 2 d ( r s , r ∗ ) for integer scores s ( i ) = i s(i)=i s ( i ) = i , for any attribute array a a a , and any feasible Δ ∗ \Delta^* Δ ∗ . Indeed, combining the Spearman–Kendall identity (Lemma 4) with the classical Diaconis–Graham inequality K ≤ F ≤ 2 K K\leq F\leq2K K ≤ F ≤ 2 K [8 ] yields a natural proof target of factor 2, since the right-hand inequality F ≤ 2 K F\leq2K F ≤ 2 K is tight in general. Tightening below 2 would require arguments beyond classical norm comparisons that exploit the specific structure of FBS’s output (see Appendix § 15 .§ 4 for further discussion). We next report empirical evidence supporting the 2-approximation.
Brute-force exact computation for small instances. For n = 3 , … , 9 n=3,\ldots,9 n = 3 , … , 9 with integer scores s ( i ) = i s(i)=i s ( i ) = i , we enumerate every attribute permutation a a a and every feasible fairness threshold Δ ∗ \Delta^* Δ ∗ (all values with the correct parity). For each instance we compute the FBS cost d F B S d_{\mathrm{FBS}} d FBS and the exact optimum d ∗ d^* d ∗ by brute-force search over all n ! n! n ! permutations, recording the ratio d F B S / d ∗ d_{\mathrm{FBS}}/d^* d FBS / d ∗ . Figure 1 (a) shows a scatter plot of all 699,282 non-trivial instances across these values of n n n . Every ratio lies strictly below 2, with the worst observed value ≈ 1.46 \approx1.46 ≈ 1.46 at n = 9 n=9 n = 9 , supporting the 2-approximation conjecture.
Figure 1. Empirical approximation ratio of FBS for the weighted Kemeny distance with integer scores s ( i ) = i s(i)=i s ( i ) = i and fairness threshold Δ ∗ \Delta^* Δ ∗ set to the tightest feasible value. (a) Exact ratio d F B S / d ∗ d_{\mathrm{FBS}}/d^* d FBS / d ∗ for all attribute permutations and all feasible Δ ∗ \Delta^* Δ ∗ , n = 3 , … , 9 n=3,\ldots,9 n = 3 , … , 9 (699,282 instances). (b) For n ∈ { 20 , 50 , 100 } n\in\{20,50,100\} n ∈ { 20 , 50 , 100 } , MILP-exact ratio d F B S / d ∗ d_{\mathrm{FBS}}/d^* d FBS / d ∗ (blue: random instances, orange: correlated instances) and LP-bound upper bound d F B S / d L P ∗ d_{\mathrm{FBS}}/d^*_{\mathrm{LP}} d FBS / d LP ∗ (green: random, yellow: correlated); at each n n n , the left box summarizes the LP-bound ratios and the right box the MILP-exact ratios. The dashed red line marks the conjectured 2-approximation bound.
Exact MILP optimum for medium instances. For n ∈ { 20 , 50 , 100 } n\in\{20,50,100\} n ∈ { 20 , 50 , 100 } we generate random and correlated attribute arrays and solve the integer programme exactly via MILP (binary inversion variables with FAS-style triangle constraints, see Appendix § 19 ). We use Gurobi via scipy.optimize.milp with a 180 s solver time-limit per instance, a 0.1% relative gap tolerance, and a 300 s wall-clock sub-process cap to handle pathologically hard correlated configurations. We also report the LP-relaxation lower bound d L P ∗ ≤ d ∗ d^*_{\mathrm{LP}}\leq d^* d LP ∗ ≤ d ∗ on 612 instances, so that d F B S / d L P ∗ d_{\mathrm{FBS}}/d^*_{\mathrm{LP}} d FBS / d LP ∗ provides a complementary upper-bound on the true approximation ratio. Figure 1 (b) compares the two: the LP-bound and MILP-exact distributions coincide for the hardest correlated instances at n = 20 n=20 n = 20 and n = 50 n=50 n = 50 (the LP relaxation is tight there), but the MILP-exact ratio is strictly smaller for the random configurations at n = 100 n=100 n = 100 , where the LP bound has slack. Across all 542 MILP-solved instances the worst observed exact ratio is 1.31, well below the conjectured 2. The ratio d F B S / d L P d_{\mathrm{FBS}}/d_{\mathrm{LP}} d FBS / d LP for the all-ascending case a = s a=s a = s (up to n ≈ 2 × 10 6 n\approx2\times10^6 n ≈ 2 × 1 0 6 , including non-power-of-two values) is reported in Appendix § 20 .
Comparison with Baselines
We next compare FBS against baselines on the quality of the ranking produced: as FBS is optimal in the unweighted case, we focus these experiments on the weighted case. Given that existing fair-ranking algorithms assume discrete protected groups, we discretize the continuous attribute into G G G equal-frequency bins and apply two representative methods using their original implementations: DetConstSort [13 ] (FairRankTune library [4 ] , tested at G ∈ { 2 , 3 , 5 , 10 } G\in\{2,3,5,10\} G ∈ { 2 , 3 , 5 , 10 } ) and FAIR [39 ] (fairsearchcore library [22 ] , with G = 2 G=2 G = 2 since FA IR is inherently binary). We also include two baselines of our own: a simple median-split interleaving that splits items at the median attribute value into two groups, sorts each by descending score, and alternately picks the next highest-scored item from each group, and Blend, a continuous heuristic that sorts items by a convex combination of their score-rank and a fair-target rank. We defer detailed descriptions of all four baselines, including their parameters and implementation choices, to Appendix § 18 .
All methods are evaluated on the same axes: achieved continuous fairness ϕ \phi ϕ (computed on the original, undiscretized attribute) and weighted Kemeny distance from the score-based ranking. On synthetic instances with n ∈ { 100 , 1000 , 5000 } n\in\{100,1000,5000\} n ∈ { 100 , 1000 , 5000 } and score–attribute correlation corr ∈ { 0 , 0.5 , 1 } \operatorname{corr}\in\{0,0.5,1\} corr ∈ { 0 , 0.5 , 1 } , FBS consistently traces a Pareto front that dominates all baselines (full results in Appendix § 20 .§ 2 ).
Real-world datasets. We apply FBS to four datasets commonly used in the fair-ranking literature, reporting for each the initial fairness ϕ 0 = ϕ ( r s ) \phi_0=\phi(r_s) ϕ 0 = ϕ ( r s ) of the score-based ranking: COMPAS (n = 7 , 214 n=7,214 n = 7 , 214 , ϕ 0 = 0.72 \phi_0=0.72 ϕ 0 = 0.72 ), German Credit (n = 1 , 000 n=1,000 n = 1 , 000 , ϕ 0 = 0.98 \phi_0=0.98 ϕ 0 = 0.98 ), Law School (n = 18 , 692 n=18,692 n = 18 , 692 , ϕ 0 = 0.85 \phi_0=0.85 ϕ 0 = 0.85 ), and Communities and Crime (n = 1 , 994 n=1,994 n = 1 , 994 , ϕ 0 = 0.56 \phi_0=0.56 ϕ 0 = 0.56 ). Detailed descriptions of each dataset (score and attribute choice, source, preprocessing) are deferred to Appendix § 17 . For each dataset we sweep the fairness threshold ψ \psi ψ from 0 to 1 in steps of 0.05 and record the achieved fairness ϕ \phi ϕ , the weighted Kemeny distance from the original score-based ranking, and the number of swaps K ∗ K^* K ∗ . Results are reported in Figure 2 . On all four datasets, FBS traces a smooth Pareto front that dominates the baselines: DetConstSort with G ∈ { 2 , 3 , 5 , 10 } G \in\{2, 3, 5, 10\} G ∈ { 2 , 3 , 5 , 10 } and FA*IR (G = 2 G = 2 G = 2 ) achieve comparable fairness levels but at substantially higher cost, while median-split interleaving reaches moderate fairness at moderate cost but cannot match FBS’s efficiency. The advantage of FBS is most pronounced on COMPAS and Communities, where the initial ranking is far from fair (ϕ 0 = 0.72 \phi_0 = 0.72 ϕ 0 = 0.72 and ϕ 0 = 0.56 \phi_0 = 0.56 ϕ 0 = 0.56 , respectively) and the continuous attribute carries fine-grained information that is lost by discretization. German Credit is nearly fair to begin with (ϕ 0 = 0.98 \phi_0 = 0.98 ϕ 0 = 0.98 ), so FBS achieves ϕ ≈ 1 \phi\approx1 ϕ ≈ 1 at negligible cost.
Figure 2. FBS vs. discretization baselines on real datasets. FBS (blue line) traces a Pareto front by sweeping ψ \psi ψ ; baselines, except the continuous heuristic Blend, are shown as individual points for each G G G . FBS dominates all baselines across all four datasets.
Appendix J extends this comparison in three directions. Two repair-then-sort baselines, which first remove the dependence of the score on the attribute and then sort, reach the same fairness as FBS only at a higher cost on all four datasets (Appendix J.3). NDCG with the original score as relevance, a utility measure that weighs the top of the list, stays at or above 0.98 for FBS at the fairness of the best baseline, and a variant of FBS that uses the NDCG loss of a swap as its cost keeps NDCG at 1.00 on the top 10 and top 100 positions at the same fairness (Appendix J.4). Finally, on the three datasets whose initial ranking is far from fair, FBS also reduces the Spearman correlation, the distance correlation, the Hilbert–Schmidt independence criterion and a positional discrepancy between position and attribute as ψ \psi ψ increases (Appendix J.5).
Runtime and Scalability
We first report theoretical runtime and space complexity of FBS, then the empirical scalability.
Proposition 4 (Runtime and space complexity of FBS). Let K ∗ = ⌈ ( Δ 0 − Δ ∗ ) / 2 ⌉ K^* = \lceil(\Delta_0 - \Delta^*)/2\rceil K ∗ = ⌈( Δ 0 − Δ ∗ ) /2 ⌉ be the number of swaps performed by FBS. Both variants use O ( n ) O(n) O ( n ) auxiliary space beyond the input. The running times are O ( n log n + K ∗ ) O(n \log n + K^*) O ( n log n + K ∗ ) (for the unweighted case) and O ( ( n + K ∗ ) log n ) O((n + K^*) \log n) O (( n + K ∗ ) log n ) (for the weighted case). In both cases the worst case is K ∗ = Θ ( n 2 ) K^* = \Theta(n^2) K ∗ = Θ ( n 2 ) .
Proof. See Appendix F.
Empirical scalability analysis. We measure wall-clock time of FBS as n n n grows from 100 to 3 × 10 6 3 \times10^6 3 × 1 0 6 . The following configurations are compared:
Weighted heap (Algorithm 2) with a = s a = s a = s (perfectly correlated) and with corr ( s , a ) = 0.8 \operatorname{corr}(s,a) = 0.8 corr ( s , a ) = 0.8 , both at ψ = 1.0 \psi= 1.0 ψ = 1.0 : K ∗ = Θ ( n 2 ) K^* = \Theta(n^2) K ∗ = Θ ( n 2 ) , exercising the worst-case O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) branch.
Unweighted linked list (Algorithm 1) with a = s a = s a = s , ψ = 1.0 \psi= 1.0 ψ = 1.0 : each swap is O ( 1 ) O(1) O ( 1 ) , giving O ( K ∗ ) = O ( n 2 ) O(K^*) = O(n^2) O ( K ∗ ) = O ( n 2 ) total.
Naïve linear scan with a = s a = s a = s , ψ = 1.0 \psi= 1.0 ψ = 1.0 : O ( n ) O(n) O ( n ) per swap, giving O ( n K ∗ ) = O ( n 3 ) O(nK^*) = O(n^3) O ( n K ∗ ) = O ( n 3 ) total.
Random regime (a a a uniform random, ψ = 1.0 \psi= 1.0 ψ = 1.0 ): K ∗ K^* K ∗ is much smaller than in the correlated case, yielding sub-quadratic runtime (10 independent instances per n n n ).
Figure 3 (a) shows the results on a log-log scale with reference lines for n log n n \log n n log n , n 2 n^2 n 2 , n 2 log n n^2 \log n n 2 log n , and n 3 n^3 n 3 . The weighted heap closely tracks n 2 log n n^2 \log n n 2 log n in both correlated settings (a = s a = s a = s and corr = 0.8 \operatorname{corr} = 0.8 corr = 0.8 ), the unweighted linked-list variant tracks n 2 n^2 n 2 , and the naïve variant follows n 3 n^3 n 3 . In the random regime, K ∗ K^* K ∗ is much smaller and the runtime is sub-quadratic; error bars (one standard deviation over 10 random instances) show moderate variance that increases with n n n , reflecting the instance-dependent nature of K ∗ K^* K ∗ . A runtime comparison of FBS against the baselines is reported in Figure 3 (b).
Figure 3. (a) Wall-clock time vs. input size n n n (log-log scale). The weighted heap-based FBS scales as O ( n 2 log n ) O(n^{2}\log n) O ( n 2 log n ) in the correlated regime (a = s a=s a = s and corr = 0.8 \operatorname{corr}=0.8 corr = 0.8 ) and sub-quadratically when K ∗ K^{*} K ∗ is small (random attributes). The unweighted linked-list variant scales as O ( n 2 ) O(n^{2}) O ( n 2 ) , while the naïve linear-scan implementation scales as O ( n 3 ) O(n^{3}) O ( n 3 ) . (b) Time comparison of FBS vs. baselines (corr = 1 \operatorname{corr}=1 corr = 1 , ψ = 1.0 \psi=1.0 ψ = 1.0 ).
Conclusions
We studied the problem of producing a ranking that is as close as possible to a given score-based ranking while satisfying a fairness constraint defined on a continuous protected attribute, without resorting to discretization. To this end, we introduced the fairness notion of Continuous Pairwise Parity and proposed Fair Bubble Sort, a greedy adjacent-swap algorithm that minimises the distance from the score-based ranking under given fairness constraint. On the theoretical side, we proved that FBS is optimal for the unweighted Kemeny distance (Theorem 1) and provided a data-dependent approximation bound for the weighted case. For the case of scores congruent to [ n ] [n] [ n ] we sharpened this bound to a constant ( 1 + 2 ) / 2 ≈ 1.207 (1+\sqrt{2})/2 \approx1.207 ( 1 + 2 ) /2 ≈ 1.207 in the worst-case attribute configuration and for n n n a power of two (Proposition 3), and extensive computation suggests the ratio stays well below 2 for arbitrary attributes. On four real datasets (COMPAS, German Credit, Law School, and Communities and Crime) FBS dominates the Pareto front of fairness vs. accuracy across all tested fairness thresholds, outperforming both group-based baselines and a continuous heuristic.
Limitations. Our results have several limitations that suggest natural directions for future work. ( i ) (i) ( i ) The 2-approximation is conjectured but unproved: while d F B S < 2 d ∗ d_{\mathrm{FBS}} < 2d^{*} d FBS < 2 d ∗ is empirically validated in every tested configuration, a formal proof remains open. ( i i ) (ii) ( ii ) FBS handles a single continuous protected attribute; extending to multiple attributes simultaneously adds further combinatorial constraints and is left for future work. ( i i i ) (iii) ( iii ) Our setting is static and one-shot : long-term dynamics, repeated exposure, and feedback loops [14 ] are beyond the scope of this paper.
Acknowledgments and Disclosure of Funding
The authors received no third-party funding for this work and declare no competing interests.
Broader Impact
Fair ranking algorithms are deployed in high-stakes settings including hiring, lending, college admissions, content moderation, and criminal justice. Almost all existing algorithms require the protected attribute to be discrete, which forces practitioners to either categorise inherently continuous variables (age, income, health scores) into ad-hoc bins or to abandon fairness control entirely. Both choices are problematic: the former discards information and introduces arbitrary thresholds that can themselves be unfair (e.g., who decides where the age bins begin and end?), while the latter offers no protection at all. By providing a theoretically grounded algorithm that operates directly on continuous attributes, our work lowers the barrier to using fair-ranking methods in these settings and removes a class of arbitrary modelling choices that have historically been difficult to justify.
At the same time, we caution against treating FBS—or any post-processing fairness intervention—as a complete solution. The fairness measure ϕ \phi ϕ targets pairwise statistical parity with respect to a continuous attribute, but it does not by itself guarantee proportional top-k k k representation, equal exposure, calibration across sub-populations, or freedom from indirect discrimination through correlated features. Rankings that look fair under ϕ \phi ϕ can still encode biases inherited from the underlying score function, and a ϕ \phi ϕ -fair re-ranking may give a misleading impression of fairness when applied on top of a flawed score. Responsible use therefore requires (a) auditing the score function itself, (b) verifying that ϕ \phi ϕ is the appropriate fairness criterion for the application context, and (c) combining FBS with complementary checks (e.g., exposure or representation audits) where multiple fairness notions are simultaneously relevant. The choice of which protected attribute to enforce fairness on is itself a normative decision that should involve the affected stakeholders rather than be made unilaterally by the system designer.
Motivations for the Continuous Pairwise Parity (CPP) measure ϕ \phi ϕ
This section motivates the choice of ϕ ( r ) = 1 − ∣ τ ( r , a ) ∣ \phi(r) = 1 - \lvert\tau(r,a)\rvert ϕ ( r ) = 1 − ∣ τ ( r , a )∣ as the fairness measure for ranking with continuous sensitive attributes. We argue that (i) ϕ \phi ϕ is the natural pairwise extension of statistical parity to the continuous-attribute setting; (ii) it strictly generalises the Pairwise Statistical Parity of [25 ] from discrete groups to continuous values; and (iii) it satisfies a list of desirable properties—boundedness, symmetry, discretisation-freeness, and tractability—that the standard group-based measures cannot meet without arbitrary binning.
From group statistical parity to a pairwise principle. In classification, statistical parity [9 ] requires that the probability of a positive outcome be equal across protected groups, Pr ( y ^ = 1 ∣ g = A ) = Pr ( y ^ = 1 ∣ g = B ) \Pr(\hat{y}=1\mid g=A)=\Pr(\hat{y}=1\mid g=B) Pr ( y ^ = 1 ∣ g = A ) = Pr ( y ^ = 1 ∣ g = B ) . Adapting this principle to ranking is non-trivial: a “positive outcome” has no immediate analogue in a permutation, so the literature replaces it with proxies such as “appearing in the top-k k k ” [39 , 5 , 34 ] , which require predefined groups A A A , B B B and a discrete cut-off k k k . When the protected attribute is continuous, neither the groups nor the cut-off are defined: discretising a a a into bins forces an arbitrary choice of thresholds, discards fine-grained variation, and destroys the ordinality of the attribute (e.g. the bin [ 20 , 30 ) [20,30) [ 20 , 30 ) is treated as categorically distinct from [ 30 , 40 ) [30,40) [ 30 , 40 ) , even though their boundary is conventional).
A more natural primitive in the ranking setting is the pair : for any two items u , v u,v u , v , one is ranked above the other, and one has a larger attribute value than the other. Pairwise statistical parity [25 ] formalises fairness as the requirement that the conditional probability of one group being ranked above the other equals the converse:
Pr ( r ( u ) < r ( v ) ∣ g ( u ) = A , g ( v ) = B ) = Pr ( r ( u ) < r ( v ) ∣ g ( u ) = B , g ( v ) = A ) . \Pr(r(u)<r(v)\mid g(u)=A,g(v)=B)=\Pr(r(u)<r(v)\mid g(u)=B,g(v)=A). Pr ( r ( u ) < r ( v ) ∣ g ( u ) = A , g ( v ) = B ) = Pr ( r ( u ) < r ( v ) ∣ g ( u ) = B , g ( v ) = A ) .
The translation to a continuous attribute is direct: replace “g ( u ) = A g(u)=A g ( u ) = A , g ( v ) = B g(v)=B g ( v ) = B ” by “a ( u ) > a ( v ) a(u)>a(v) a ( u ) > a ( v ) ” (and the converse by “a ( u ) < a ( v ) a(u)<a(v) a ( u ) < a ( v ) ”), so that fairness becomes the requirement that, for a uniformly random pair ( u , v ) (u,v) ( u , v ) , the high-attribute item is equally likely to be ranked above or below the lower-attribute one. Empirically over the n n n items, this reads N ↗ ( r ) ≈ N ↘ ( r ) N_{\nearrow}(r)\approx N_{\searrow}(r) N ↗ ( r ) ≈ N ↘ ( r ) , which is precisely the condition τ ( r , a ) ≈ 0 \tau(r,a)\approx0 τ ( r , a ) ≈ 0 , equivalently ϕ ( r ) ≈ 1 \phi(r)\approx1 ϕ ( r ) ≈ 1 .
Reduction to Pairwise Statistical Parity in the binary case. The CPP measure recovers, as a special case, the Pairwise Statistical Parity of [25 ] , a notion also defined by [29 ] . Suppose a a a takes only two values, a ( u ) ∈ { 0 , 1 } a(u)\in\{0,1\} a ( u ) ∈ { 0 , 1 } , encoding membership in a low group A = { u : a ( u ) = 0 } A=\{u:a(u)=0\} A = { u : a ( u ) = 0 } and a high group B = { u : a ( u ) = 1 } B = \{u : a(u) = 1\} B = { u : a ( u ) = 1 } of sizes n A n_A n A and n B n_B n B ; this is the situation obtained by discretising a continuous attribute at a threshold, for example its median. Let
P ( r ) : = Pr ( r ( v ) < r ( u ) ∣ u ∈ A , v ∈ B ) P(r) := \Pr(r(v) < r(u) \mid u \in A,\ v \in B) P ( r ) := Pr ( r ( v ) < r ( u ) ∣ u ∈ A , v ∈ B )
be the probability that a uniformly random B B B -item is ranked above a uniformly random A A A -item. The rank-parity score of [25 ] is P ( r ) P(r) P ( r ) for group B B B and 1 − P ( r ) 1 - P(r) 1 − P ( r ) for group A A A , and their Pairwise Statistical Parity requires the two scores to be equal, i.e. P ( r ) = 1 2 P(r) = \frac{1}{2} P ( r ) = 2 1 .
Proposition 5 (Binary CPP equals Pairwise Statistical Parity). For a binary attribute as above, Δ ( r ) = n A n B ∣ 2 P ( r ) − 1 ∣ \Delta(r) = n_A n_B \lvert2P(r) - 1\rvert Δ ( r ) = n A n B ∣ 2 P ( r ) − 1 ∣ , and hence
ϕ ( r ) = 1 − n A n B ( n 2 ) ∣ 2 P ( r ) − 1 ∣ . \phi(r) = 1 - \frac{n_A n_B}{\binom{n}{2}}\lvert2P(r) - 1\rvert. ϕ ( r ) = 1 − ( 2 n ) n A n B ∣ 2 P ( r ) − 1 ∣ . In particular, ϕ ( r ) = 1 \phi(r) = 1 ϕ ( r ) = 1 if and only if P ( r ) = 1 2 P(r) = \frac{1}{2} P ( r ) = 2 1 , i.e. if and only if r r r satisfies the Pairwise Statistical Parity of [25 ] .
Proof. Two items of the same group have equal attribute values, so their pair contributes to neither N ↗ N_{\nearrow} N ↗ nor N ↘ N_{\searrow} N ↘ (tie convention of § 3 ); only the n A n B n_A n_B n A n B cross-group pairs count. Among them, n A n B P ( r ) n_A n_B P(r) n A n B P ( r ) pairs have the B B B -item ranked above the A A A -item and n A n B ( 1 − P ( r ) ) n_A n_B(1 - P(r)) n A n B ( 1 − P ( r )) have it ranked below. By the definition of § 3 , a cross-group pair is concordant when the item with the larger attribute value, the B B B -item, has the larger position index, i.e. is ranked below the A A A -item; hence N ↗ = n A n B ( 1 − P ( r ) ) N_{\nearrow} = n_A n_B(1 - P(r)) N ↗ = n A n B ( 1 − P ( r )) , N ↘ = n A n B P ( r ) N_{\searrow} = n_A n_B P(r) N ↘ = n A n B P ( r ) , and Δ ( r ) = ∣ N ↗ − N ↘ ∣ = n A n B ∣ 2 P ( r ) − 1 ∣ \Delta(r) = \lvert N_{\nearrow} - N_{\searrow}\rvert= n_A n_B\lvert2P(r) - 1\rvert Δ ( r ) = ∣ N ↗ − N ↘ ∣ = n A n B ∣ 2 P ( r ) − 1 ∣ . Dividing by ( n 2 ) \binom{n}{2} ( 2 n ) gives ∣ τ ( r , a ) ∣ \lvert\tau(r,a)\rvert ∣ τ ( r , a )∣ and the expression for ϕ ( r ) \phi(r) ϕ ( r ) .
The quantity P ( r ) P(r) P ( r ) is the cross-group AUC, i.e. the Mann–Whitney U U U statistic of the two groups’ positions divided by n A n B n_A n_B n A n B , and 2 P ( r ) − 1 2P(r)-1 2 P ( r ) − 1 is Somers’ D D D . CPP therefore subsumes the discrete-group definition without loss of expressivity, and discretising a continuous attribute recovers that metric exactly. For G > 2 G > 2 G > 2 ordered groups the same computation gives
N ↗ − N ↘ = ∑ g < h n g n h ( 1 − 2 P g h ( r ) ) , N_{\nearrow} - N_{\searrow} = \sum_{g<h} n_g n_h\left(1 - 2P_{gh}(r)\right), N ↗ − N ↘ = g < h ∑ n g n h ( 1 − 2 P g h ( r ) ) ,
where P g h ( r ) P_{gh}(r) P g h ( r ) is the probability that a random item of the higher group h h h is ranked above a random item of the lower group g g g : the signed imbalance is the size-weighted sum of the pairwise parity terms over all pairs of groups.
Statistical interpretation. At the strict-fairness threshold ψ = 1 \psi= 1 ψ = 1 (equivalently Δ ∗ = 0 \Delta^* = 0 Δ ∗ = 0 when n ( n − 1 ) / 2 n(n - 1)/2 n ( n − 1 ) /2 is even), ϕ ( r ) = 1 \phi(r) = 1 ϕ ( r ) = 1 admits a probabilistic reading: for a uniformly random ordered pair of distinct items ( u , v ) (u,v) ( u , v ) ,
Pr ( u , v ) ( r ( u ) < r ( v ) ∣ a ( u ) > a ( v ) ) = 1 2 , \Pr_{(u,v)}(r(u) < r(v) \mid a(u) > a(v)) = \frac{1}{2}, ( u , v ) Pr ( r ( u ) < r ( v ) ∣ a ( u ) > a ( v )) = 2 1 ,
i.e. the relative ranking position carries no monotonic signal about the attribute. Intermediate thresholds ψ ∈ ( 0 , 1 ) \psi\in(0,1) ψ ∈ ( 0 , 1 ) correspond to a controlled relaxation of this equality, with the maximum imbalance Δ ∗ = ⌊ n ( n − 1 ) ( 1 − ψ ) / 2 ⌋ \Delta^* = \left\lfloor n(n - 1)(1 - \psi)/2\right\rfloor Δ ∗ = ⌊ n ( n − 1 ) ( 1 − ψ ) /2 ⌋ measuring how far from the strict statistical-parity condition the practitioner is willing to deviate.
Comparison with related pairwise notions. [29 ] introduced a pairwise fairness criterion for learning-to-rank and regression, requiring equality of the probability that a relevant item from group A A A is ranked above a non-relevant item from group B B B , and vice versa. Their formulation targets the supervised-learning setting (training a scoring function under a fairness constraint) and relies on discrete groups. CPP, in contrast, is defined directly on the output ranking and on a continuous attribute, making it suitable for post-processing without retraining. The two notions agree in spirit—both anchor fairness at the pairwise level—but operate in different regimes.
Properties of ϕ \phi ϕ . The CPP measure satisfies the following desiderata, none of which are jointly achieved by the standard group-based ranking-fairness measures.
Boundedness and calibration. ϕ ( r ) ∈ [ 0 , 1 ] \phi(r) \in[0,1] ϕ ( r ) ∈ [ 0 , 1 ] for every ranking, with ϕ ( r ) = 1 \phi(r) = 1 ϕ ( r ) = 1 iff τ ( r , a ) = 0 \tau(r,a) = 0 τ ( r , a ) = 0 (perfect fairness) and ϕ ( r ) = 0 \phi(r) = 0 ϕ ( r ) = 0 iff ∣ τ ( r , a ) ∣ = 1 \lvert\tau(r,a)\rvert= 1 ∣ τ ( r , a )∣ = 1 (deterministic monotonic dependence between ranking and attribute).
Direction symmetry. ϕ \phi ϕ is invariant under reflection of the attribute, ϕ ( r ; a ) = ϕ ( r ; − a ) \phi(r;a) = \phi(r;-a) ϕ ( r ; a ) = ϕ ( r ; − a ) : the measure does not privilege “high-attribute on top” over “low-attribute on top”.
Discretisation-freeness. ϕ \phi ϕ is defined directly on the continuous values a ( u ) a(u) a ( u ) and requires neither thresholds nor groups; in particular, it is invariant under any strictly monotone transformation of a a a .
Robustness to attribute perturbations. A small perturbation of the attribute values that preserves their relative order leaves ϕ \phi ϕ exactly unchanged; an attribute swap that flips a single pair changes ϕ \phi ϕ by O ( 1 / n 2 ) O(1/n^2) O ( 1/ n 2 ) . CPP is therefore stable under measurement noise that preserves rank order.
Pairwise locality. ϕ \phi ϕ decomposes additively over pairs, mirroring the pairwise structure of the (unweighted) Kemeny distance. This shared structure is what enables FBS to optimise both quantities through a single algorithmic primitive—the adjacent swap—and underlies the optimality result of Theorem 1.
Tractability. ϕ ( r ) \phi(r) ϕ ( r ) is computable in O ( n log n ) O(n \log n) O ( n log n ) via merge-sort–based inversion counting, matching the cost of evaluating the Kemeny distance.
Comparison with alternative dependence measures. Other measures of dependence between position and attribute could replace the Kendall-τ \tau τ correlation in the definition of ϕ \phi ϕ . Spearman’s correlation is also monotone, but it measures squared rank differences rather than pairwise concordance, so it does not share the pairwise structure of the Kemeny distance that lets a single adjacent-swap primitive optimise fairness and utility together. Distance correlation [35 ] and the Hilbert–Schmidt independence criterion (HSIC) [15 ] also capture non-monotone dependence, but they are not additive over pairs, and the effect of an adjacent swap on them depends on the whole ranking, so they admit neither the exact analysis of FBS nor a tractable hard constraint. Binning the attribute and applying a group-parity measure discards its ordinal structure and introduces binning artifacts. The Kendall-based CPP is the notion that is at the same time binning-free, ordinal and pairwise-decomposable, which is what lets one adjacent-swap primitive optimise both fairness and utility; the price is that CPP captures monotone dependence only, as discussed next.
Limitations. CPP captures monotonic dependence between ranking and attribute. A ranking in which the highest- and lowest-attribute items occupy the middle positions and mid-attribute items are placed at the extremes can have τ ( r , a ) = 0 \tau(r,a)=0 τ ( r , a ) = 0 yet exhibit a clearly non-uniform attribute distribution along positions. Detecting such non-monotonic biases requires complementary measures (e.g., position-conditional moments of a a a ), which we view as orthogonal extensions rather than as substitutes for a pairwise primitive.
Pseudocode of FBS for the weighted Kemeny distance
When the Kemeny distance is weighted by score gaps w i j = ∣ s ( i ) − s ( j ) ∣ w_{ij}=|s(i)-s(j)| w ij = ∣ s ( i ) − s ( j ) ∣ , different swaps have different costs and FBS must select the cheapest majority-discordant adjacent pair at each step. We replace the doubly-linked list L L L of Algorithm 1 with a min-heap H H H keyed by the adjacent cost c [ k ] = ∣ S [ k ] − S [ k + 1 ] ∣ c[k]=|S[k]-S[k+1]| c [ k ] = ∣ S [ k ] − S [ k + 1 ] ∣ (the normalisation 1 / W 1/W 1/ W where W = ∑ k < l ∣ s ( k ) − s ( l ) ∣ W=\sum_{k<l}|s(k)-s(l)| W = ∑ k < l ∣ s ( k ) − s ( l ) ∣ is a monotone rescaling and plays no role in the arg-min), supporting extraction, insertion, deletion, and key updates in O ( log n ) O(\log n) O ( log n ) . Ties in cost are broken by picking the leftmost pair (via the secondary key k k k ).
Proofs of Section 5
Proofs of structural lemmas
Proof of Observation 1 (Single-swap increment). Let u , v ∈ U u,v\in U u , v ∈ U be the items with r ( u ) = k r(u)=k r ( u ) = k and r ( v ) = k + 1 r(v)=k+1 r ( v ) = k + 1 , so that after the adjacent swap r ′ ( u ) = k + 1 r'(u)=k+1 r ′ ( u ) = k + 1 , r ′ ( v ) = k r'(v)=k r ′ ( v ) = k , and r ′ ( w ) = r ( w ) r'(w)=r(w) r ′ ( w ) = r ( w ) for every w ∉ { u , v } w\notin\{u,v\} w ∈ / { u , v } .
Pairwise locality. Let w w w be any item distinct from u u u and v v v , with rank r ( w ) ∉ { k , k + 1 } r(w)\notin\{k,k+1\} r ( w ) ∈ / { k , k + 1 } . Since r ( w ) r(w) r ( w ) is either strictly less than both k k k and k + 1 k+1 k + 1 or strictly greater than both, its order relative to u u u (and to v v v ) is unchanged by the swap, and the rank of w w w itself is fixed. Hence for every pair of items other than { u , v } \{u,v\} { u , v } the relative order in the ranking is the same in r r r and r ′ r' r ′ ; consequently both the r s r_s r s -inversion status (which depends only on the relative orders in r r r and r s r_s r s ) and the Kendall orientation (which depends only on the relative order in r r r and the attribute values) are preserved. The only pair whose status can change is { u , v } \{u,v\} { u , v } , whose relative order is reversed by the swap.
Algorithm 2 FBS (Fair Bubble Sort) – weighted, with priority queue
Require: Items U = [ n ] U=[n] U = [ n ] , attribute a : U → R + a:U\to\mathbb{R}_{+} a : U → R + , score s : U → R + s:U\to\mathbb{R}_{+} s : U → R + , fairness threshold ψ ∈ [ 0 , 1 ] \psi\in[0,1] ψ ∈ [ 0 , 1 ]
Ensure: Ranking R R R solving Problem (1) with the weighted Kemeny distance
( R , S , A ) ← (R,S,A)\gets ( R , S , A ) ← arrays initialized according to r s r_s r s (descending order of score) ▷ initial r s r_s r s
c [ k ] ← ∣ S [ k ] − S [ k + 1 ] ∣ c[k]\gets\lvert S[k]-S[k+1]\rvert c [ k ] ← ∣ S [ k ] − S [ k + 1 ]∣ for k = 1 , … , n − 1 k=1,\ldots,n-1 k = 1 , … , n − 1
σ [ k ] ← sign ( A [ k + 1 ] − A [ k ] ) \sigma[k]\gets\operatorname{sign}(A[k+1]-A[k]) σ [ k ] ← sign ( A [ k + 1 ] − A [ k ]) for k = 1 , … , n − 1 k=1,\ldots,n-1 k = 1 , … , n − 1 ▷ adjacent-pair signs
N ↗ ← ∣ { i < j : A [ i ] < A [ j ] } ∣ N_{\nearrow}\gets\lvert\{i<j:A[i]<A[j]\}\rvert N ↗ ← ∣{ i < j : A [ i ] < A [ j ]}∣ ; N ↘ ← ∣ { i < j : A [ i ] > A [ j ] } ∣ N_{\searrow}\gets\lvert\{i<j:A[i]>A[j]\}\rvert N ↘ ← ∣{ i < j : A [ i ] > A [ j ]}∣
Δ ∗ ← max ( ⌊ ( 1 − ψ ) n ( n − 1 ) / 2 ⌋ , ∣ N ↗ − N ↘ ∣ m o d 2 ) \Delta^{*}\gets\max(\lfloor(1-\psi)n(n-1)/2\rfloor,\lvert N_{\nearrow}-N_{\searrow}\rvert\bmod2) Δ ∗ ← max (⌊( 1 − ψ ) n ( n − 1 ) /2 ⌋ , ∣ N ↗ − N ↘ ∣ mod 2 ) ▷ parity-safe threshold
μ ← sign ( N ↗ − N ↘ ) \mu\gets\operatorname{sign}(N_{\nearrow}-N_{\searrow}) μ ← sign ( N ↗ − N ↘ ) ▷ majority sign (+1 or −1)
H ← H\gets H ← min-heap keyed by ( c [ k ] , k ) (c[k],k) ( c [ k ] , k ) over { k : σ [ k ] = μ } \{k:\sigma[k]=\mu\} { k : σ [ k ] = μ } ▷ build in O ( n ) O(n) O ( n )
while ∣ N ↗ − N ↘ ∣ > Δ ∗ \lvert N_{\nearrow}-N_{\searrow}\rvert>\Delta^{*} ∣ N ↗ − N ↘ ∣ > Δ ∗ do
k ∗ ← EXTRACT-MIN ( H ) k^{*}\gets\operatorname{EXTRACT-MIN}(H) k ∗ ← EXTRACT-MIN ( H ) ▷ O ( log n ) O(\log n) O ( log n )
swap R [ k ∗ ] ↔ R [ k ∗ + 1 ] R[k^{*}]\leftrightarrow R[k^{*}+1] R [ k ∗ ] ↔ R [ k ∗ + 1 ] , S [ k ∗ ] ↔ S [ k ∗ + 1 ] S[k^{*}]\leftrightarrow S[k^{*}+1] S [ k ∗ ] ↔ S [ k ∗ + 1 ] , A [ k ∗ ] ↔ A [ k ∗ + 1 ] A[k^{*}]\leftrightarrow A[k^{*}+1] A [ k ∗ ] ↔ A [ k ∗ + 1 ]
for ℓ ∈ { k ∗ − 1 , k ∗ , k ∗ + 1 } ∩ { 1 , … , n − 1 } \ell\in\{k^{*}-1,k^{*},k^{*}+1\}\cap\{1,\ldots,n-1\} ℓ ∈ { k ∗ − 1 , k ∗ , k ∗ + 1 } ∩ { 1 , … , n − 1 } do ▷ update neighbours
c [ ℓ ] ← ∣ S [ ℓ ] − S [ ℓ + 1 ] ∣ c[\ell]\gets\lvert S[\ell]-S[\ell+1]\rvert c [ ℓ ] ← ∣ S [ ℓ ] − S [ ℓ + 1 ]∣
σ o l d ← σ [ ℓ ] \sigma_{\mathrm{old}}\gets\sigma[\ell] σ old ← σ [ ℓ ]
if ℓ = k ∗ \ell=k^{*} ℓ = k ∗ then
σ [ ℓ ] ← − σ [ ℓ ] \sigma[\ell]\gets-\sigma[\ell] σ [ ℓ ] ← − σ [ ℓ ] ▷ middle sign flips (Observation 1)
else
σ [ ℓ ] ← sign ( A [ ℓ + 1 ] − A [ ℓ ] ) \sigma[\ell]\gets\operatorname{sign}(A[\ell+1]-A[\ell]) σ [ ℓ ] ← sign ( A [ ℓ + 1 ] − A [ ℓ ]) ▷ recompute from new attributes
end if
if σ o l d = μ \sigma_{\mathrm{old}}=\mu σ old = μ and σ [ ℓ ] ≠ μ \sigma[\ell]\ne\mu σ [ ℓ ] = μ then
remove ℓ \ell ℓ from H H H ▷ O ( log n ) O(\log n) O ( log n )
else if σ o l d ≠ μ \sigma_{\mathrm{old}}\ne\mu σ old = μ and σ [ ℓ ] = μ \sigma[\ell]=\mu σ [ ℓ ] = μ then
insert ℓ \ell ℓ into H H H with key ( c [ ℓ ] , ℓ ) (c[\ell],\ell) ( c [ ℓ ] , ℓ ) ▷ O ( log n ) O(\log n) O ( log n )
else if σ [ ℓ ] = μ \sigma[\ell]=\mu σ [ ℓ ] = μ and c [ ℓ ] c[\ell] c [ ℓ ] changed then
update key of ℓ \ell ℓ in H H H to ( c [ ℓ ] , ℓ ) (c[\ell],\ell) ( c [ ℓ ] , ℓ ) ▷ O ( log n ) O(\log n) O ( log n )
end if
end for
N ↗ ← N ↗ − μ N_{\nearrow}\gets N_{\nearrow}-\mu N ↗ ← N ↗ − μ ; N ↘ ← N ↘ + μ N_{\searrow}\gets N_{\searrow}+\mu N ↘ ← N ↘ + μ
end while
return R R R
Effect on d d d . The pair { u , v } \{u,v\} { u , v } contributes w u v w_{uv} w uv to d ( r s , ⋅ ) d(r_s,\cdot) d ( r s , ⋅ ) iff it lies in Inv ( r s , ⋅ ) \operatorname{Inv}(r_s,\cdot) Inv ( r s , ⋅ ) , and the swap toggles this membership:
if { u , v } ∉ Inv ( r s , r ) \{u,v\}\notin\operatorname{Inv}(r_s,r) { u , v } ∈ / Inv ( r s , r ) (i.e. u , v u,v u , v are in the same relative order as in r s r_s r s ), then { u , v } ∈ Inv ( r s , r ′ ) \{u,v\}\in\operatorname{Inv}(r_s,r') { u , v } ∈ Inv ( r s , r ′ ) and the swap creates an inversion, so d ( r s , r ′ ) − d ( r s , r ) = + w u v d(r_s,r')-d(r_s,r)=+w_{uv} d ( r s , r ′ ) − d ( r s , r ) = + w uv ;
if { u , v } ∈ Inv ( r s , r ) \{u,v\}\in\operatorname{Inv}(r_s,r) { u , v } ∈ Inv ( r s , r ) , then { u , v } ∉ Inv ( r s , r ′ ) \{u,v\}\notin\operatorname{Inv}(r_s,r') { u , v } ∈ / Inv ( r s , r ′ ) and the swap resolves an inversion, so d ( r s , r ′ ) − d ( r s , r ) = − w u v d(r_s,r')-d(r_s,r)=-w_{uv} d ( r s , r ′ ) − d ( r s , r ) = − w uv .
By pairwise locality no other pair contributes to the change, establishing the first claim.
Effect on N ↗ − N ↘ N_{\nearrow}-N_{\searrow} N ↗ − N ↘ . Under the general-position assumption (no ties in a a a ), every pair is either ↗ \nearrow ↗ or ↘ \searrow ↘ . By pairwise locality the orientation of every pair other than { u , v } \{u,v\} { u , v } is preserved, while the orientation of { u , v } \{u,v\} { u , v } flips between ↗ \nearrow ↗ and ↘ \searrow ↘ . Hence N ↗ N_{\nearrow} N ↗ changes by exactly ± 1 \pm1 ± 1 and N ↘ N_{\searrow} N ↘ by exactly ∓ 1 \mp1 ∓ 1 , giving
( N ↗ − N ↘ ) ( r ′ ) − ( N ↗ − N ↘ ) ( r ) ∈ { − 2 , + 2 } . (N_{\nearrow}-N_{\searrow})(r')-(N_{\nearrow}-N_{\searrow})(r)\in\{-2,+2\}. ( N ↗ − N ↘ ) ( r ′ ) − ( N ↗ − N ↘ ) ( r ) ∈ { − 2 , + 2 } .
with sign + 2 +2 + 2 if { u , v } \{u,v\} { u , v } was ↘ \searrow ↘ in r r r (and becomes ↗ \nearrow ↗ in r ′ r' r ′ ) and − 2 -2 − 2 otherwise.
Proof of Lemma 1 (Reduction to adjacent swaps). Since r s r_s r s and r r r are bijections U → [ n ] U\to[n] U → [ n ] , the map π : = r ∘ r s − 1 \pi:=r\circ r_s^{-1} π := r ∘ r s − 1 is a permutation of [ n ] [n] [ n ] , and r = π ∘ r s r=\pi\circ r_s r = π ∘ r s . It is classical that S n S_n S n is generated by the adjacent transpositions τ k : = ( k , k + 1 ) \tau_k:=(k,k+1) τ k := ( k , k + 1 ) , k = 1 , … , n − 1 k=1,\ldots,n-1 k = 1 , … , n − 1 : every π ∈ S n \pi\in S_n π ∈ S n admits a finite decomposition π = τ k m ∘ ⋯ ∘ τ k 1 \pi=\tau_{k_m}\circ\cdots\circ\tau_{k_1} π = τ k m ∘ ⋯ ∘ τ k 1 , and the minimum number of factors equals ∣ Inv ( π ) ∣ = ∣ Inv ( r s , r ) ∣ \lvert\operatorname{Inv}(\pi)\rvert=\lvert\operatorname{Inv}(r_s,r)\rvert ∣ Inv ( π )∣ = ∣ Inv ( r s , r )∣ (e.g. the bound is attained by bubble sort) [23 ] . An adjacent swap at rank k k k sends a ranking r ′ r' r ′ to τ k ∘ r ′ \tau_k\circ r' τ k ∘ r ′ , so applying τ k 1 , τ k 2 , … , τ k m \tau_{k_1},\tau_{k_2},\ldots,\tau_{k_m} τ k 1 , τ k 2 , … , τ k m in order to r s r_s r s produces the trajectory
r s , τ k 1 ∘ r s , τ k 2 ∘ τ k 1 ∘ r s , … , τ k m ∘ ⋯ ∘ τ k 1 ∘ r s = π ∘ r s = r , (2) r_s,\ \tau_{k_1}\circ r_s,\ \tau_{k_2}\circ\tau_{k_1}\circ r_s,\ \ldots,\ \tau_{k_m}\circ\cdots\circ\tau_{k_1}\circ r_s=\pi\circ r_s=r, \tag*{(2)} r s , τ k 1 ∘ r s , τ k 2 ∘ τ k 1 ∘ r s , … , τ k m ∘ ⋯ ∘ τ k 1 ∘ r s = π ∘ r s = r , (2)
i.e., an algorithm in A s w a p A_{\mathrm{swap}} A swap whose output is r r r .
Proof of Lemma 2 (Reduction to non-decreasing swaps). We construct a sequence of adjacent swaps from r s r_s r s to r ∗ r^* r ∗ along which d ( r s , ⋅ ) d(r_s,\cdot) d ( r s , ⋅ ) is non-decreasing. Run bubble sort on r ∗ r^* r ∗ , sorting items toward the order prescribed by r s r_s r s : at each step, with current ranking q q q , find adjacent ranks k , k + 1 k,k+1 k , k + 1 such that the items u , v u,v u , v at those ranks in q q q (i.e., q ( u ) = k q(u)=k q ( u ) = k , q ( v ) = k + 1 q(v)=k+1 q ( v ) = k + 1 ) are in opposite r s r_s r s -order — equivalently, { u , v } \{u,v\} { u , v } contributes an inversion to Inv ( r s , q ) \operatorname{Inv}(r_s,q) Inv ( r s , q ) — and swap them. Such a pair exists whenever q ≠ r s q\ne r_s q = r s , and each swap reduces ∣ Inv ( r s , q ) ∣ |\operatorname{Inv}(r_s,q)| ∣ Inv ( r s , q ) ∣ by exactly 1, so the algorithm terminates at r s r_s r s after m = ∣ Inv ( r s , r ∗ ) ∣ m=|\operatorname{Inv}(r_s,r^*)| m = ∣ Inv ( r s , r ∗ ) ∣ swaps. By Observation 1 each swap resolves the r s r_s r s -inversion of the corresponding item pair { u , v } \{u,v\} { u , v } and decreases d ( r s , ⋅ ) d(r_s,\cdot) d ( r s , ⋅ ) by w u v ≥ 0 w_{uv}\ge0 w uv ≥ 0 ; hence the trajectory
r ∗ = q ( 0 ) → τ k 1 q ( 1 ) → τ k 2 ⋯ → τ k m q ( m ) = r s r^*=q^{(0)}\xrightarrow{\tau_{k_1}}q^{(1)}\xrightarrow{\tau_{k_2}}\cdots\xrightarrow{\tau_{k_m}}q^{(m)}=r_s r ∗ = q ( 0 ) τ k 1 q ( 1 ) τ k 2 ⋯ τ k m q ( m ) = r s
satisfies d ( r s , q ( 0 ) ) ≥ d ( r s , q ( 1 ) ) ≥ ⋯ ≥ d ( r s , q ( m ) ) = 0 d(r_s,q^{(0)})\ge d(r_s,q^{(1)})\ge\cdots\ge d(r_s,q^{(m)})=0 d ( r s , q ( 0 ) ) ≥ d ( r s , q ( 1 ) ) ≥ ⋯ ≥ d ( r s , q ( m ) ) = 0 .
Adjacent transpositions are involutions (τ k 2 = i d \tau_k^2=\mathrm{id} τ k 2 = id ), so applying τ k m , τ k m − 1 , … , τ k 1 \tau_{k_m},\tau_{k_{m-1}},\ldots,\tau_{k_1} τ k m , τ k m − 1 , … , τ k 1 in this reversed order to r s r_s r s visits the same rankings in reverse,
r s = q ( m ) → q ( m − 1 ) → ⋯ → q ( 0 ) = r ∗ , r_s=q^{(m)}\to q^{(m-1)}\to\cdots\to q^{(0)}=r^*, r s = q ( m ) → q ( m − 1 ) → ⋯ → q ( 0 ) = r ∗ ,
along which d ( r s , ⋅ ) d(r_s,\cdot) d ( r s , ⋅ ) is non-decreasing. The corresponding algorithm therefore lies in A s w a p , ↗ A_{\mathrm{swap},\nearrow} A swap , ↗ and produces r ∗ r^* r ∗ .
Proof of Lemma 3 (Existence of a valid greedy swap). We argue by contrapositive. The claim “N ↗ ( r ) > N ↘ ( r ) ⇒ N_{\nearrow}(r)>N_{\searrow}(r)\Rightarrow N ↗ ( r ) > N ↘ ( r ) ⇒ some adjacent pair is ↗ \nearrow ↗ ” is logically equivalent to
no adjacent pair of r is ↗ ⇒ N ↗ ( r ) ≤ N ↘ ( r ) . \text{no adjacent pair of }r\text{ is }\nearrow\quad\Rightarrow\quad N_{\nearrow}(r)\le N_{\searrow}(r). no adjacent pair of r is ↗ ⇒ N ↗ ( r ) ≤ N ↘ ( r ) .
Because the values b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n are pairwise distinct, every pair is either ↗ \nearrow ↗ or ↘ \searrow ↘ , so the hypothesis “no adjacent ↗ \nearrow ↗ ” is equivalent to
b k > b k + 1 for every k = 1 , … , n − 1 , ( ⋆ ) b_k>b_{k+1}\qquad\text{for every }k=1,\ldots,n-1,\qquad(\star) b k > b k + 1 for every k = 1 , … , n − 1 , ( ⋆ )
i.e. every adjacent pair is ↘ \searrow ↘ . We shall actually establish the stronger conclusion N ↗ ( r ) = 0 N_{\nearrow}(r)=0 N ↗ ( r ) = 0 from ( ⋆ ) (\star) ( ⋆ ) ; since N ↗ ( r ) = 0 ≤ N ↘ ( r ) N_{\nearrow}(r)=0\le N_{\searrow}(r) N ↗ ( r ) = 0 ≤ N ↘ ( r ) this suffices.
Assume ( ⋆ ) (\star) ( ⋆ ) . For any pair i < j i<j i < j , chaining the j − i j-i j − i adjacent strict inequalities in ( ⋆ ) (\star) ( ⋆ ) and using transitivity of > > > on the distinct reals b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n yields
b i > b i + 1 > ⋯ > b j ⇒ b i > b j , b_i>b_{i+1}>\cdots>b_j\quad\Rightarrow\quad b_i>b_j, b i > b i + 1 > ⋯ > b j ⇒ b i > b j ,
so ( i , j ) (i,j) ( i , j ) is ↘ \searrow ↘ . This holds for every i < j i<j i < j , hence N ↗ ( r ) = 0 N_{\nearrow}(r)=0 N ↗ ( r ) = 0 as announced. Returning to the original direction: if N ↗ ( r ) > N ↘ ( r ) ≥ 0 N_{\nearrow}(r)>N_{\searrow}(r)\ge0 N ↗ ( r ) > N ↘ ( r ) ≥ 0 then N ↗ ( r ) ≥ 1 N_{\nearrow}(r)\ge1 N ↗ ( r ) ≥ 1 , so ( ⋆ ) (\star) ( ⋆ ) must fail, i.e. at least one adjacent pair is ↗ \nearrow ↗ . The ↘ \searrow ↘ -majority case is obtained by exchanging > > > and < < < throughout.
The argument only invokes transitivity on the pairwise distinct values b 1 , … , b n b_1,\ldots,b_n b 1 , … , b n of the current ranking, so it applies unchanged at every greedy iteration, not only at the initial r = r s r=r_s r = r s .
Proof of Proposition 1 (Minimality of the number of greedy swaps). Lower bound. By Observation 1, any adjacent swap changes N ↗ − N ↘ N_{\nearrow}-N_{\searrow} N ↗ − N ↘ by exactly ± 2 \pm2 ± 2 . Since Δ = ∣ N ↗ − N ↘ ∣ \Delta=|N_{\nearrow}-N_{\searrow}| Δ = ∣ N ↗ − N ↘ ∣ , the reverse triangle inequality gives Δ ′ ≥ Δ − 2 \Delta'\ge\Delta-2 Δ ′ ≥ Δ − 2 after any single swap (Δ ′ \Delta' Δ ′ can equal Δ − 2 \Delta-2 Δ − 2 , Δ \Delta Δ , or Δ + 2 \Delta+2 Δ + 2 ); the middle case occurs only when Δ = 1 \Delta=1 Δ = 1 and the swap flips the sign of N ↗ − N ↘ N_{\nearrow}-N_{\searrow} N ↗ − N ↘ . Going from Δ 0 \Delta_0 Δ 0 to any value ≤ Δ ∗ \le\Delta^* ≤ Δ ∗ therefore requires at least ⌈ ( Δ 0 − Δ ∗ ) / 2 ⌉ = K ∗ \lceil(\Delta_0-\Delta^*)/2\rceil=K^* ⌈( Δ 0 − Δ ∗ ) /2 ⌉ = K ∗ swaps.
Parity remark. Each swap preserves the parity of N ↗ − N ↘ N_{\nearrow}-N_{\searrow} N ↗ − N ↘ , so Δ m o d 2 = Δ 0 m o d 2 \Delta\bmod2=\Delta_0\bmod2 Δ mod 2 = Δ 0 mod 2 throughout. If Δ ∗ < Δ 0 m o d 2 \Delta^*<\Delta_0\bmod2 Δ ∗ < Δ 0 mod 2 , the target Δ ≤ Δ ∗ \Delta\le\Delta^* Δ ≤ Δ ∗ is unreachable. This is precisely why the algorithm sets Δ ∗ ← max ( Δ ∗ , Δ 0 m o d 2 ) \Delta^*\leftarrow\max(\Delta^*,\Delta_0\bmod2) Δ ∗ ← max ( Δ ∗ , Δ 0 mod 2 ) : the adjusted threshold ensures K ∗ K^* K ∗ is a non-negative integer and Δ 0 − 2 K ∗ ≥ 0 \Delta_0-2K^*\ge0 Δ 0 − 2 K ∗ ≥ 0 .
FBS attains the bound. We assume without loss of generality N ↗ ( r s ) ≥ N ↘ ( r s ) N_{\nearrow}(r_s)\ge N_{\searrow}(r_s) N ↗ ( r s ) ≥ N ↘ ( r s ) , so the majority sign is μ = + 1 \mu=+1 μ = + 1 and N ↗ − N ↘ = Δ 0 > 0 N_{\nearrow}-N_{\searrow}=\Delta_0>0 N ↗ − N ↘ = Δ 0 > 0 (the μ = − 1 \mu=-1 μ = − 1 case is symmetric). We prove by induction on k k k the loop invariant
N ↗ − N ↘ = Δ 0 − 2 k ( 0 ≤ k ≤ K ∗ ) . N_{\nearrow}-N_{\searrow}=\Delta_0-2k\qquad(0\le k\le K^*). N ↗ − N ↘ = Δ 0 − 2 k ( 0 ≤ k ≤ K ∗ ) .
Base case (k = 0 k=0 k = 0 ): immediate from the definition of Δ 0 \Delta_0 Δ 0 . Inductive step (k → k + 1 k \to k+1 k → k + 1 , for k < K ∗ k < K^* k < K ∗ ): by the inductive hypothesis N ↗ − N ↘ = Δ 0 − 2 k N_{\nearrow} - N_{\searrow} = \Delta_0 - 2k N ↗ − N ↘ = Δ 0 − 2 k . Since k < K ∗ = ⌈ ( Δ 0 − Δ ∗ ) / 2 ⌉ k < K^* = \left\lceil(\Delta_0-\Delta^*)/2\right\rceil k < K ∗ = ⌈ ( Δ 0 − Δ ∗ ) /2 ⌉ , we have Δ 0 − 2 k > Δ ∗ ≥ 0 \Delta_0-2k > \Delta^* \ge0 Δ 0 − 2 k > Δ ∗ ≥ 0 , so in particular N ↗ > N ↘ N_{\nearrow} > N_{\searrow} N ↗ > N ↘ . Lemma 3 then guarantees the existence of an adjacent ↗ \nearrow ↗ pair, so FBS can select one. By Observation 1, swapping it decreases N ↗ N_{\nearrow} N ↗ by 1 and increases N ↘ N_{\searrow} N ↘ by 1, giving N ↗ − N ↘ = Δ 0 − 2 ( k + 1 ) N_{\nearrow} - N_{\searrow} = \Delta_0 - 2(k+1) N ↗ − N ↘ = Δ 0 − 2 ( k + 1 ) .
After K ∗ K^* K ∗ swaps, Δ = Δ 0 − 2 K ∗ ∈ { 0 , 1 } ⊆ [ 0 , Δ ∗ ] \Delta= \Delta_0 - 2K^* \in\{0,1\} \subseteq[0,\Delta^*] Δ = Δ 0 − 2 K ∗ ∈ { 0 , 1 } ⊆ [ 0 , Δ ∗ ] (using Δ ∗ ≥ Δ 0 m o d 2 \Delta^* \ge\Delta_0 \mathbin{\mathrm{mod}} 2 Δ ∗ ≥ Δ 0 mod 2 ), and the algorithm terminates. The greedy therefore uses exactly K ∗ K^* K ∗ swaps, matching the lower bound.
Proof of Theorem 1 (Optimality for the unweighted case)
Proof of Theorem 1. Unlike the weighted case, the unweighted Kemeny distance depends only on the number of inversions, not on which specific pairs are inverted:
d ( r s , r ) = ∣ Inv ( r s , r ) ∣ ( n 2 ) . d(r_s,r)=\frac{\lvert\operatorname{Inv}(r_s,r)\rvert}{\binom{n}{2}}. d ( r s , r ) = ( 2 n ) ∣ Inv ( r s , r )∣ .
If Δ 0 ≤ Δ ∗ \Delta_0 \le\Delta^* Δ 0 ≤ Δ ∗ , then r s r_s r s is already feasible and d ( r s , r s ) = 0 d(r_s,r_s)=0 d ( r s , r s ) = 0 is trivially optimal. We therefore assume Δ 0 > Δ ∗ \Delta_0 > \Delta^* Δ 0 > Δ ∗ , so that K ∗ = ⌈ ( Δ 0 − Δ ∗ ) / 2 ⌉ ≥ 1 K^*=\left\lceil(\Delta_0-\Delta^*)/2\right\rceil\ge1 K ∗ = ⌈ ( Δ 0 − Δ ∗ ) /2 ⌉ ≥ 1 . It suffices to show that ∣ Inv ( r s , r F B S ) ∣ = K ∗ \lvert\operatorname{Inv}(r_s,r_{\mathrm{FBS}})\rvert= K^* ∣ Inv ( r s , r FBS )∣ = K ∗ and that ∣ Inv ( r s , r ) ∣ ≥ K ∗ \lvert\operatorname{Inv}(r_s,r)\rvert\ge K^* ∣ Inv ( r s , r )∣ ≥ K ∗ for every feasible r r r .
Lower bound. Fix any feasible r r r , i.e. any r r r with ϕ ( r ) ≥ ψ \phi(r) \ge\psi ϕ ( r ) ≥ ψ . By Lemma 1, the minimum number of adjacent swaps taking r s r_s r s to r r r is ∣ Inv ( r s , r ) ∣ \lvert\operatorname{Inv}(r_s,r)\rvert ∣ Inv ( r s , r )∣ . This minimum-length sequence is an algorithm in A s w a p A_{\mathrm{swap}} A swap whose output is the feasible ranking r r r , so by Proposition 1 it uses at least K ∗ K^* K ∗ swaps. Therefore
∣ Inv ( r s , r ) ∣ ≥ K ∗ for every feasible r . \lvert\operatorname{Inv}(r_s,r)\rvert\ge K^* \qquad\text{for every feasible }r. ∣ Inv ( r s , r )∣ ≥ K ∗ for every feasible r .
FBS matches the bound. By Proposition 1, FBS terminates after exactly K ∗ K^* K ∗ adjacent swaps at a ranking r F B S r_{\mathrm{FBS}} r FBS with Δ ( r F B S ) ≤ Δ ∗ \Delta(r_{\mathrm{FBS}}) \le\Delta^* Δ ( r FBS ) ≤ Δ ∗ , so r F B S r_{\mathrm{FBS}} r FBS is feasible. By Observation 1, each adjacent swap creates or resolves exactly one r s r_s r s -inversion, so ∣ Inv ( r s , ⋅ ) ∣ \lvert\operatorname{Inv}(r_s,\mathord{\cdot})\rvert ∣ Inv ( r s , ⋅ )∣ changes by exactly ± 1 \pm1 ± 1 per swap. Since ∣ Inv ( r s , r s ) ∣ = 0 \lvert\operatorname{Inv}(r_s,r_s)\rvert= 0 ∣ Inv ( r s , r s )∣ = 0 , we have
∣ Inv ( r s , r F B S ) ∣ ≤ K ∗ . \lvert\operatorname{Inv}(r_s,r_{\mathrm{FBS}})\rvert\le K^*. ∣ Inv ( r s , r FBS )∣ ≤ K ∗ .
Combined with the lower bound (applied to the feasible r F B S r_{\mathrm{FBS}} r FBS ) we get ∣ Inv ( r s , r F B S ) ∣ = K ∗ \lvert\operatorname{Inv}(r_s,r_{\mathrm{FBS}})\rvert= K^* ∣ Inv ( r s , r FBS )∣ = K ∗ , and hence
d ( r s , r F B S ) = K ∗ ( n 2 ) = min r : ϕ ( r ) ≥ ψ d ( r s , r ) . d(r_s,r_{\mathrm{FBS}})=\frac{K^*}{\binom{n}{2}}
=\min_{r:\phi(r)\ge\psi}d(r_s,r). d ( r s , r FBS ) = ( 2 n ) K ∗ = r : ϕ ( r ) ≥ ψ min d ( r s , r ) .
Proofs of Section 6
Proof of Proposition 2 (Weight-spread approximation bound)
Proof of Proposition 2. If Δ 0 ≤ Δ ∗ \Delta_0 \le\Delta^* Δ 0 ≤ Δ ∗ , then r s r_s r s is already feasible, K ∗ = 0 K^*=0 K ∗ = 0 , and d ( r s , r F B S ) = d ( r s , r ∗ ) = 0 d(r_s,r_{\mathrm{FBS}})=d(r_s,r^*)=0 d ( r s , r FBS ) = d ( r s , r ∗ ) = 0 ; the bound holds trivially. We therefore assume Δ 0 > Δ ∗ \Delta_0 > \Delta^* Δ 0 > Δ ∗ , so that K ∗ ≥ 1 K^* \ge1 K ∗ ≥ 1 .
Upper bound on d ( r s , r F B S ) . ∗ B y x r e f ‘ P r o p o s i t i o n 1 ‘ , F B S p e r f o r m s e x a c t l y d(r_s,r_{\mathrm{FBS}}).* By {xref}`Proposition 1`, FBS performs exactly d ( r s , r FBS ) . ∗ B y x r e f ‘ P r o p os i t i o n 1‘ , F B S p er f or m se x a c tl y K^ $ adjacent swaps starting from r s r_s r s . By Observation 1, each swap changes ∣ Inv ( r s , ⋅ ) ∣ \lvert\operatorname{Inv}(r_s,\mathord{\cdot})\rvert ∣ Inv ( r s , ⋅ )∣ by exactly ± 1 \pm1 ± 1 . Since ∣ Inv ( r s , r s ) ∣ = 0 \lvert\operatorname{Inv}(r_s,r_s)\rvert= 0 ∣ Inv ( r s , r s )∣ = 0 and r F B S r_{\mathrm{FBS}} r FBS is feasible (hence ∣ Inv ( r s , r F B S ) ∣ ≥ K ∗ \lvert\operatorname{Inv}(r_s,r_{\mathrm{FBS}})\rvert\ge K^* ∣ Inv ( r s , r FBS )∣ ≥ K ∗ by Lemma 1 and Proposition 1), we obtain ∣ Inv ( r s , r F B S ) ∣ = K ∗ \lvert\operatorname{Inv}(r_s,r_{\mathrm{FBS}})\rvert= K^* ∣ Inv ( r s , r FBS )∣ = K ∗ (in particular, every swap creates a new r s r_s r s -inversion). Therefore
d ( r s , r F B S ) = ∑ ( i , j ) ∈ Inv ( r s , r F B S ) w i j ≤ K ∗ ⋅ w max . d(r_s,r_{\mathrm{FBS}})=\sum_{(i,j)\in\operatorname{Inv}(r_s,r_{\mathrm{FBS}})}w_{ij}\le K^*\cdot w_{\max}. d ( r s , r FBS ) = ( i , j ) ∈ Inv ( r s , r FBS ) ∑ w ij ≤ K ∗ ⋅ w m a x .
Lower bound on d ( r s , r ∗ ) d(r_s,r^*) d ( r s , r ∗ ) . By Lemma 1 and Proposition 1, every feasible ranking r r r satisfies ∣ Inv ( r s , r ) ∣ ≥ K ∗ \lvert\operatorname{Inv}(r_s,r)\rvert\ge K^* ∣ Inv ( r s , r )∣ ≥ K ∗ . Hence
d ( r s , r ∗ ) = ∑ ( i , j ) ∈ Inv ( r s , r ∗ ) w i j ≥ K ∗ ⋅ w min . d(r_s,r^*)=\sum_{(i,j)\in\operatorname{Inv}(r_s,r^*)}w_{ij}\ge K^*\cdot w_{\min}. d ( r s , r ∗ ) = ( i , j ) ∈ Inv ( r s , r ∗ ) ∑ w ij ≥ K ∗ ⋅ w m i n .
Dividing the upper by the lower bound (both positive since K ∗ ≥ 1 K^* \ge1 K ∗ ≥ 1 and w min > 0 w_{\min} > 0 w m i n > 0 ) gives the stated ratio.
Score-rank convention. Throughout this appendix we write “s ( i ) = i s(i)=i s ( i ) = i ” as shorthand for equally-spaced scores: only the score gaps enter the weights, yielding pair weights w u v = ∣ s ( u ) − s ( v ) ∣ = ∣ u − v ∣ w_{uv}=\lvert s(u)-s(v)\rvert=\lvert u-v\rvert w uv = ∣ s ( u ) − s ( v )∣ = ∣ u − v ∣ up to a global normalisation that cancels in all ratios, so the labeling r s = i d r_s=\mathrm{id} r s = id (item i i i at position i i i ) is without loss of generality. Similarly, “a = s a=s a = s ” refers to the configuration a ( i ) = i a(i)=i a ( i ) = i , which under r s = i d r_s=\mathrm{id} r s = id gives τ ( r s , a ) = + 1 \tau(r_s,a)=+1 τ ( r s , a ) = + 1 — the maximum-imbalance case in which all ( n 2 ) \binom{n}{2} ( 2 n ) pairs are concordant.
Proof of Lemma 4 (Spearman–Kendall identity)
Proof of Lemma 4. Items are labelled 1 , … , n 1,\ldots,n 1 , … , n with scores s ( i ) = i s(i)=i s ( i ) = i and unnormalised pair weights w u v = v − u w_{uv}=v-u w uv = v − u for u < v u<v u < v (the global factor 1 / W 1/W 1/ W cancels in all ratios and is omitted throughout this appendix). For a ranking r r r , we must show
∑ u < v r ( u ) > r ( v ) ( v − u ) = ∑ i i 2 − ∑ i i r ( i ) = 1 2 ∑ i ( r ( i ) − i ) 2 . (3) \sum_{\substack{u<v\\r(u)>r(v)}}(v-u)=\sum_i i^2-\sum_i ir(i)=\frac{1}{2}\sum_i(r(i)-i)^2. \tag*{(3)} u < v r ( u ) > r ( v ) ∑ ( v − u ) = i ∑ i 2 − i ∑ i r ( i ) = 2 1 i ∑ ( r ( i ) − i ) 2 . (3)
The second equality follows from ∑ i r ( i ) 2 = ∑ i i 2 \sum_i r(i)^2=\sum_i i^2 ∑ i r ( i ) 2 = ∑ i i 2 (both range over { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } ). For the first equality, define for each item i i i :
ℓ ( i ) : = # { j < i : r ( j ) > r ( i ) } (left inversions) , \ell(i):=\#\{j<i:r(j)>r(i)\}\quad\text{(left inversions)}, ℓ ( i ) := # { j < i : r ( j ) > r ( i )} (left inversions) ,
ρ ( i ) : = # { j > i : r ( j ) < r ( i ) } (right inversions) . \rho(i):=\#\{j>i:r(j)<r(i)\}\quad\text{(right inversions)}. ρ ( i ) := # { j > i : r ( j ) < r ( i )} (right inversions) .
Step 1: ℓ ( i ) − ρ ( i ) = i − r ( i ) \ell(i)-\rho(i)=i-r(i) ℓ ( i ) − ρ ( i ) = i − r ( i ) . Among items { 1 , … , i − 1 } \{1,\ldots,i-1\} { 1 , … , i − 1 } , let p p p denote how many occupy positions < r ( i ) <r(i) < r ( i ) . Then ℓ ( i ) = ( i − 1 ) − p \ell(i)=(i-1)-p ℓ ( i ) = ( i − 1 ) − p . Since exactly r ( i ) − 1 r(i)-1 r ( i ) − 1 items in total sit before position r ( i ) r(i) r ( i ) , p + ρ ( i ) = r ( i ) − 1 p+\rho(i)=r(i)-1 p + ρ ( i ) = r ( i ) − 1 , giving p = r ( i ) − 1 − ρ ( i ) p=r(i)-1-\rho(i) p = r ( i ) − 1 − ρ ( i ) . Substituting: ℓ ( i ) = ( i − 1 ) − ( r ( i ) − 1 − ρ ( i ) ) = i − r ( i ) + ρ ( i ) \ell(i)=(i-1)-(r(i)-1-\rho(i))=i-r(i)+\rho(i) ℓ ( i ) = ( i − 1 ) − ( r ( i ) − 1 − ρ ( i )) = i − r ( i ) + ρ ( i ) , hence ℓ ( i ) − ρ ( i ) = i − r ( i ) \ell(i)-\rho(i)=i-r(i) ℓ ( i ) − ρ ( i ) = i − r ( i ) .
Step 2: The right-hand side equals ∑ i ( ℓ ( i ) − ρ ( i ) ) \sum_i(\ell(i)-\rho(i)) ∑ i ( ℓ ( i ) − ρ ( i )) . Rewriting the inversion sum:
∑ u < v r ( u ) > r ( v ) ( v − u ) = ∑ v v ℓ ( v ) − ∑ u u ρ ( u ) = ∑ i i ( ℓ ( i ) − ρ ( i ) ) . \sum_{\substack{u<v\\r(u)>r(v)}}(v-u)=\sum_v v\ell(v)-\sum_u u\rho(u)=\sum_i i\bigl(\ell(i)-\rho(i)\bigr). u < v r ( u ) > r ( v ) ∑ ( v − u ) = v ∑ v ℓ ( v ) − u ∑ u ρ ( u ) = i ∑ i ( ℓ ( i ) − ρ ( i ) ) .
Conclusion. By Step 1, ∑ i i ( ℓ ( i ) − ρ ( i ) ) = ∑ i i ( i − r ( i ) ) = ∑ i i 2 − ∑ i i r ( i ) \sum_i i(\ell(i)-\rho(i))=\sum_i i(i-r(i))=\sum_i i^2-\sum_i ir(i) ∑ i i ( ℓ ( i ) − ρ ( i )) = ∑ i i ( i − r ( i )) = ∑ i i 2 − ∑ i i r ( i ) .
Remark. The identity connects two classical rank-correlation measures: the weighted Kendall distance (with weights v − u v-u v − u ) equals half the Spearman squared displacement. This is specific to equally-spaced (integer) scores and does not hold for general score arrays.
Proof of Proposition 3 (Tight bound for the all-ascending case)
The proof of Proposition 3 rests on two ingredients: (i) an exact characterisation of the FBS output and its closed-form cost for the all-ascending case a = s a=s a = s (Proposition 6), and (ii) an LP relaxation lower bound on d ∗ d^* d ∗ (Proposition 7). We develop each in turn, then combine them to prove, for this special case, the asymptotic convergence of the ratio d F B S / L P d_{\mathrm{FBS}}/\mathrm{LP} d FBS / LP to ( 1 + 2 ) / 2 (1+\sqrt{2})/2 ( 1 + 2 ) /2 and the strict 2-approximation d F B S < 2 d ∗ d_{\mathrm{FBS}}<2d^* d FBS < 2 d ∗ .
Setup. When a = s = ( 1 , 2 , … , n ) a=s=(1,2,\ldots,n) a = s = ( 1 , 2 , … , n ) , all ( n 2 ) \binom{n}{2} ( 2 n ) pairs are concordant. With ψ = 1 \psi=1 ψ = 1 , FBS performs K ∗ = ⌈ ( n 2 ) / 2 ⌉ K^*=\lceil\binom{n}{2}/2\rceil K ∗ = ⌈ ( 2 n ) /2 ⌉ swaps. We restrict to n = 2 t n=2^t n = 2 t (t ≥ 2 t\ge2 t ≥ 2 ) where ( n 2 ) \binom{n}{2} ( 2 n ) is even and K ∗ = n ( n − 1 ) / 4 K^*=n(n-1)/4 K ∗ = n ( n − 1 ) /4 . Write m : = n / 2 m:=n/2 m := n /2 .
Proposition 6 (FBS output and closed-form cost for a = s a=s a = s , n = 2 t n=2^t n = 2 t ). When a = s = ( 1 , … , n ) a=s=(1,\ldots,n) a = s = ( 1 , … , n ) and n = 2 t ≥ 4 n=2^t\ge4 n = 2 t ≥ 4 , FBS produces the ranking r F B S r_{\mathrm{FBS}} r FBS defined by the following five blocks:
(B1) Positions 1 , … , m / 2 1,\ldots,m/2 1 , … , m /2 : items m , m − 1 , … , m / 2 + 1 m,m-1,\ldots,m/2+1 m , m − 1 , … , m /2 + 1 (reversed upper-left quarter);
(B2) Position m / 2 + 1 m/2+1 m /2 + 1 : item n n n ;
(B3) Positions m / 2 + 2 , … , m + 1 m/2+2,\ldots,m+1 m /2 + 2 , … , m + 1 : items m / 2 , m / 2 − 1 , … , 1 m/2,m/2-1,\ldots,1 m /2 , m /2 − 1 , … , 1 (reversed lower-left quarter);
(B4) Position m + 2 m+2 m + 2 : item n − 1 n-1 n − 1 ;
(B5) Positions m + 3 , … , 2 m m+3,\ldots,2m m + 3 , … , 2 m : items n − 2 , n − 3 , … , m + 1 n-2,n-3,\ldots,m+1 n − 2 , n − 3 , … , m + 1 (reversed right half).
The total FBS cost is
d F B S ( n ) = m ( 8 m 2 + 21 m − 14 ) 24 , m = n / 2. (4) d_{\mathrm{FBS}}(n)=\frac{m(8m^2+21m-14)}{24},\qquad m=n/2. \tag*{(4)} d FBS ( n ) = 24 m ( 8 m 2 + 21 m − 14 ) , m = n /2. (4)
We prove the two parts of the proposition separately. We first derive the closed-form cost (3) assuming the five-block structure, and then prove the five-block structure itself by induction on t t t .
Proof of (4) . Assuming the five-block structure, we compute d F B S = 1 2 S 2 ( r F B S ) d_{\mathrm{FBS}}=\frac{1}{2}S_2(r_{\mathrm{FBS}}) d FBS = 2 1 S 2 ( r FBS ) using Lemma 4. The displacement of item i i i is δ i : = r F B S ( i ) − i \delta_i:=r_{\mathrm{FBS}}(i)-i δ i := r FBS ( i ) − i . We evaluate S 2 = ∑ i δ i 2 S_2=\sum_i\delta_i^2 S 2 = ∑ i δ i 2 block by block.
Block B1 (positions j = 1 , … , m / 2 j=1,\ldots,m/2 j = 1 , … , m /2 , item m + 1 − j m+1-j m + 1 − j ). Displacement δ j = m + 1 − 2 j \delta_j=m+1-2j δ j = m + 1 − 2 j , taking all odd values from m − 1 m-1 m − 1 down to 1. Hence S 2 ( 1 ) = m ( m 2 − 1 ) / 6 S_2^{(1)}=m(m^2-1)/6 S 2 ( 1 ) = m ( m 2 − 1 ) /6 .
Block B2 (position m / 2 + 1 m/2+1 m /2 + 1 , item 2 m 2m 2 m ). S 2 ( 2 ) = ( 3 m / 2 − 1 ) 2 S_2^{(2)}=(3m/2-1)^2 S 2 ( 2 ) = ( 3 m /2 − 1 ) 2 .
Block B3 (positions m / 2 + 2 , … , m + 1 ) . m/2+2,\ldots,m+1). m /2 + 2 , … , m + 1 ) . \delta=2k$ for k = 1 , … , m / 2 k=1,\ldots,m/2 k = 1 , … , m /2 , giving S 2 ( 3 ) = m ( m + 1 ) ( m + 2 ) / 6 S_2^{(3)}=m(m+1)(m+2)/6 S 2 ( 3 ) = m ( m + 1 ) ( m + 2 ) /6 .
Block B4 (position m + 2 m+2 m + 2 , item 2 m − 1 2m-1 2 m − 1 ). S 2 ( 4 ) = ( m − 3 ) 2 S_2^{(4)}=(m-3)^2 S 2 ( 4 ) = ( m − 3 ) 2 .
Block B5 (positions m + 3 , … , 2 m m+3,\ldots,2m m + 3 , … , 2 m , items 2 m − 2 , … , m + 1 2m-2,\ldots,m+1 2 m − 2 , … , m + 1 ). Item i = 3 m + 1 − j i=3m+1-j i = 3 m + 1 − j sits at position j j j , giving δ = 2 j − 3 m − 1 \delta=2j-3m-1 δ = 2 j − 3 m − 1 . As j j j ranges from m + 3 m+3 m + 3 to 2 m 2m 2 m , these are the m − 2 m-2 m − 2 consecutive odd values 5 − m , 7 − m , … , m − 3 , m − 1 5-m,7-m,\ldots,m-3,m-1 5 − m , 7 − m , … , m − 3 , m − 1 . The full set of odd values from − ( m − 1 ) -(m-1) − ( m − 1 ) to m − 1 m-1 m − 1 has m m m elements with sum of squares m ( m 2 − 1 ) / 3 m(m^2-1)/3 m ( m 2 − 1 ) /3 ; Block B5 omits the two largest absolute values m − 1 m-1 m − 1 and m − 3 m-3 m − 3 (which belong to the items in blocks B1 and B4 respectively). Hence S 2 ( 5 ) = m ( m 2 − 1 ) / 3 − ( m − 1 ) 2 − ( m − 3 ) 2 S_2^{(5)}=m(m^2-1)/3-(m-1)^2-(m-3)^2 S 2 ( 5 ) = m ( m 2 − 1 ) /3 − ( m − 1 ) 2 − ( m − 3 ) 2 .
Total. The ( m − 3 ) 2 (m-3)^2 ( m − 3 ) 2 terms from B4 and B5 cancel. Combining the three fractional terms:
m ( m 2 − 1 ) 6 + m ( m + 1 ) ( m + 2 ) 6 + m ( m 2 − 1 ) 3 = m ( m + 1 ) [ ( m − 1 ) + ( m + 2 ) + 2 ( m − 1 ) ] 6 = m ( m + 1 ) ( 4 m − 1 ) 6 . \frac{m(m^2-1)}{6}+\frac{m(m+1)(m+2)}{6}+\frac{m(m^2-1)}{3}
=\frac{m(m+1)[(m-1)+(m+2)+2(m-1)]}{6}
=\frac{m(m+1)(4m-1)}{6}. 6 m ( m 2 − 1 ) + 6 m ( m + 1 ) ( m + 2 ) + 3 m ( m 2 − 1 ) = 6 m ( m + 1 ) [( m − 1 ) + ( m + 2 ) + 2 ( m − 1 )] = 6 m ( m + 1 ) ( 4 m − 1 ) .
The remaining squared terms give ( 3 m / 2 − 1 ) 2 − ( m − 1 ) 2 = m ( 5 m − 4 ) / 4 (3m/2-1)^2-(m-1)^2=m(5m-4)/4 ( 3 m /2 − 1 ) 2 − ( m − 1 ) 2 = m ( 5 m − 4 ) /4 . Therefore
S 2 = m ( m + 1 ) ( 4 m − 1 ) 6 + m ( 5 m − 4 ) 4 = 2 m ( m + 1 ) ( 4 m − 1 ) + 3 m ( 5 m − 4 ) 12 = m ( 8 m 2 + 21 m − 14 ) 12 , S_2=\frac{m(m+1)(4m-1)}{6}+\frac{m(5m-4)}{4}
=\frac{2m(m+1)(4m-1)+3m(5m-4)}{12}
=\frac{m(8m^2+21m-14)}{12}, S 2 = 6 m ( m + 1 ) ( 4 m − 1 ) + 4 m ( 5 m − 4 ) = 12 2 m ( m + 1 ) ( 4 m − 1 ) + 3 m ( 5 m − 4 ) = 12 m ( 8 m 2 + 21 m − 14 ) ,
where the last step uses 2 ( m + 1 ) ( 4 m − 1 ) = 8 m 2 + 6 m − 2 2(m+1)(4m-1)=8m^2+6m-2 2 ( m + 1 ) ( 4 m − 1 ) = 8 m 2 + 6 m − 2 and 3 ( 5 m − 4 ) = 15 m − 12 3(5m-4)=15m-12 3 ( 5 m − 4 ) = 15 m − 12 , giving 8 m 2 + 21 m − 14 8m^2+21m-14 8 m 2 + 21 m − 14 . Hence d F B S = S 2 / 2 = m ( 8 m 2 + 21 m − 14 ) / 24 d_{\mathrm{FBS}}=S_2/2=m(8m^2+21m-14)/24 d FBS = S 2 /2 = m ( 8 m 2 + 21 m − 14 ) /24 . □
Proof of the five-block structure. The proof proceeds by induction on t t t , exploiting a hierarchical merge structure forced by FBS’s min-cost rule. We establish the required auxiliary definitions and lemmas, then give the main induction.
Definition 1 (Reversed block). A reversed block of size b b b at positions p , p + 1 , … , p + b − 1 p,p+1,\ldots,p+b-1 p , p + 1 , … , p + b − 1 containing items { q , q + 1 , … , q + b − 1 } \{q,q+1,\ldots,q+b-1\} { q , q + 1 , … , q + b − 1 } means that position p + j p+j p + j holds item q + b − 1 − j q+b-1-j q + b − 1 − j for j = 0 , … , b − 1 j=0,\ldots,b-1 j = 0 , … , b − 1 .
Lemma 5 (Phase 1: disjoint transpositions). The first m m m FBS swaps transpose the pairs at positions ( 1 , 2 ) , ( 3 , 4 ) , … , ( n − 1 , n ) (1,2),(3,4),\ldots,(n-1,n) ( 1 , 2 ) , ( 3 , 4 ) , … , ( n − 1 , n ) , each at cost 1. After phase 1, the state consists of m m m reversed blocks of size 2: block j j j at positions 2 j − 1 , 2 j 2j-1,2j 2 j − 1 , 2 j contains items { 2 j − 1 , 2 j } \{2j-1,2j\} { 2 j − 1 , 2 j } in reversed order, for j = 1 , … , m j=1,\ldots,m j = 1 , … , m .
Proof. Initially all n − 1 n-1 n − 1 adjacent pairs are concordant with cost 1. FBS picks position 1 (leftmost minimum-cost eligible position). After swapping positions 1 and 2: position 1 becomes discordant (σ [ 1 ] = − 1 \sigma[1]=-1 σ [ 1 ] = − 1 ); position 2 has cost ∣ s ( 1 ) − s ( 3 ) ∣ = 2 \lvert s(1)-s(3)\rvert=2 ∣ s ( 1 ) − s ( 3 )∣ = 2 ; all positions k ≥ 3 k\ge3 k ≥ 3 remain at cost 1. Hence the next FBS choice is position 3. By induction on j j j : after j j j transpositions, the first 2 j 2j 2 j positions form reversed pairs with discordant internal signs, while positions 2 j + 1 , … , n − 1 2j+1,\ldots,n-1 2 j + 1 , … , n − 1 remain concordant at cost 1. FBS next selects position 2 j + 1 2j+1 2 j + 1 . After all m m m transpositions, every position 2 j − 1 2j-1 2 j − 1 holds the pair ( 2 j , 2 j − 1 ) (2j,2j-1) ( 2 j , 2 j − 1 ) and no cost-1 eligible positions remain.
Lemma 6 (Post-phase-1 eligible positions). After phase 1, the eligible (concordant) adjacent positions are precisely the even indices k = 2 , 4 , … , n − 2 k=2,4,\ldots,n-2 k = 2 , 4 , … , n − 2 , each with cost 3. There are m − 1 m-1 m − 1 such positions.
Proof. At even position k = 2 j k=2j k = 2 j , the items are 2 j − 1 2j-1 2 j − 1 (right element of block j j j ) and 2 j + 2 2j+2 2 j + 2 (left element of block j + 1 j+1 j + 1 ). Since 2 j − 1 < 2 j + 2 2j-1<2j+2 2 j − 1 < 2 j + 2 , the pair is concordant with cost ∣ s ( 2 j − 1 ) − s ( 2 j + 2 ) ∣ = 3 \lvert s(2j-1)-s(2j+2)\rvert=3 ∣ s ( 2 j − 1 ) − s ( 2 j + 2 )∣ = 3 . At odd positions, items form a reversed pair within a block and are discordant.
Lemma 7 (Merge Lemma). Suppose the current state contains two adjacent reversed blocks of size b b b : a left block at positions p , … , p + b − 1 p,\ldots,p+b-1 p , … , p + b − 1 containing items { q , … , q + b − 1 } \{q,\ldots,q+b-1\} { q , … , q + b − 1 } reversed, and a right block at positions p + b , … , p + 2 b − 1 p+b,\ldots,p+2b-1 p + b , … , p + 2 b − 1 containing items { q + b , … , q + 2 b − 1 } \{q+b,\ldots,q+2b-1\} { q + b , … , q + 2 b − 1 } reversed. Suppose furthermore that:
the boundary position p + b − 1 p+b-1 p + b − 1 (between items q q q and q + 2 b − 1 q+2b-1 q + 2 b − 1 ) is the unique eligible position with minimum cost within these 2 b 2b 2 b positions;
no eligible position outside these 2 b 2b 2 b positions has cost less than the boundary cost 2 b − 1 2b-1 2 b − 1 .
Then FBS performs exactly b 2 b^2 b 2 swaps within these 2 b 2b 2 b positions, merging them into a single reversed block of size 2 b 2b 2 b containing items { q , … , q + 2 b − 1 } \{q,\ldots,q+2b-1\} { q , … , q + 2 b − 1 } in decreasing order. The total cost of these b 2 b^2 b 2 swaps is b 3 b^3 b 3 . The merge proceeds in b b b rounds, where round r r r (r = 0 , … , b − 1 r=0,\ldots,b-1 r = 0 , … , b − 1 ) consists of b b b swaps with costs 2 b − 1 − r 2b-1-r 2 b − 1 − r , 2 b − 2 − r , … , b − r 2b-2-r,\ldots,b-r 2 b − 2 − r , … , b − r .
Proof. We prove by induction on r r r (r = − 1 , 0 , … , b − 1 r=-1,0,\ldots,b-1 r = − 1 , 0 , … , b − 1 , where r = − 1 r=-1 r = − 1 denotes the initial state) the following invariant.
**Invariant after round r : ∗ ∗ r e l a t i v e t o l o c a l p o s i t i o n s $ 0 , … , 2 b − 1 r:** relative to local positions \$0,\ldots,2b-1 r : ∗ ∗ r e l a t i v e t o l oc a l p os i t i o n s $0 , … , 2 b − 1 (offset by p p p ), the state consists of three segments:
Segment 1 (positions 0 , … , r 0,\ldots,r 0 , … , r ): items q + 2 b − 1 q+2b-1 q + 2 b − 1 , q + 2 b − 2 q+2b-2 q + 2 b − 2 ,… \ldots … , q + 2 b − 1 − r q+2b-1-r q + 2 b − 1 − r in decreasing order.
Segment 2 (positions r + 1 , … , b + r r+1,\ldots,b+r r + 1 , … , b + r ): items q + b − 1 q+b-1 q + b − 1 , q + b − 2 q+b-2 q + b − 2 ,… , q \ldots,q … , q in decreasing order (the original left-block items, shifted right by r + 1 r+1 r + 1 ).
Segment 3 (positions b + r + 1 , … , 2 b − 1 b+r+1,\ldots,2b-1 b + r + 1 , … , 2 b − 1 ): items q + 2 b − 2 − r q+2b-2-r q + 2 b − 2 − r ,… , q + b \ldots,q+b … , q + b in decreasing order (the remaining right-block items).
All adjacent pairs within each segment are discordant. The unique eligible position with minimum cost (within these 2 b 2b 2 b positions) is the boundary between segments 2 and 3 at position b + r b+r b + r , with cost 2 b − 2 − r 2b-2-r 2 b − 2 − r .
Base case (r = − 1 r=-1 r = − 1 ): Segment 1 is empty, segment 2 is the left block, segment 3 is the right block. The only eligible position is the boundary at position b − 1 b-1 b − 1 , with cost 2 b − 1 2b-1 2 b − 1 .
Round r + 1 r+1 r + 1 execution: The boundary between segments 2 and 3 is at position b + r b+r b + r , where item q q q sits at position b + r b+r b + r and item q + 2 b − 2 − r q+2b-2-r q + 2 b − 2 − r sits at position b + r + 1 b+r+1 b + r + 1 . FBS swaps these two items at cost 2 b − 2 − r 2b-2-r 2 b − 2 − r .
After this initial swap, item q + 2 b − 2 − r q+2b-2-r q + 2 b − 2 − r at position b + r b+r b + r propagates leftward through segment 2. At each step the leftward swap is the cheapest eligible move: the propagation front has strictly decreasing cost ( 2 b − 3 − r , 2 b − 4 − r , … ) (2b-3-r,2b-4-r,\ldots) ( 2 b − 3 − r , 2 b − 4 − r , … ) , while the only other eligible position—item q q q adjacent to segment 3’s leftmost item at position b + r + 1 b+r+1 b + r + 1 —has fixed cost 2 b − 3 − r 2b-3-r 2 b − 3 − r . At the first step both costs are equal and leftmost tie-breaking selects the propagation; at every subsequent step the leftward cost is strictly smaller.
After b − 1 b-1 b − 1 leftward swaps, item q + 2 b − 2 − r q+2b-2-r q + 2 b − 2 − r reaches position r + 1 r+1 r + 1 , adjacent to item q + 2 b − 1 − r q+2b-1-r q + 2 b − 1 − r in segment 1; since q + 2 b − 2 − r < q + 2 b − 1 − r q+2b-2-r<q+2b-1-r q + 2 b − 2 − r < q + 2 b − 1 − r , this pair is discordant. The state matches the invariant with r r r replaced by r + 1 r+1 r + 1 . Total swaps in round r + 1 r+1 r + 1 : 1 + ( b − 1 ) = b 1+(b-1)=b 1 + ( b − 1 ) = b , with costs 2 b − 1 − ( r + 1 ) 2b-1-(r+1) 2 b − 1 − ( r + 1 ) , 2 b − 2 − ( r + 1 ) 2b-2-(r+1) 2 b − 2 − ( r + 1 ) , … \ldots … , b − ( r + 1 ) b-(r+1) b − ( r + 1 ) .
After round b − 1 b-1 b − 1 : Segment 1 spans all 2 b 2b 2 b positions with items q + 2 b − 1 , … , q q+2b-1,\ldots,q q + 2 b − 1 , … , q in decreasing order; segments 2 and 3 are empty. The merge is complete.
Cost calculation: Each round r r r sums an arithmetic series of b b b terms from b − r b-r b − r to 2 b − 1 − r 2b-1-r 2 b − 1 − r , giving per-round total b ( 3 b − 1 − 2 r ) / 2 b(3b-1-2r)/2 b ( 3 b − 1 − 2 r ) /2 . Summing over r = 0 , … , b − 1 r=0,\ldots,b-1 r = 0 , … , b − 1 yields another arithmetic series from b ( 3 b − 1 ) / 2 b(3b-1)/2 b ( 3 b − 1 ) /2 to b ( b + 1 ) / 2 b(b+1)/2 b ( b + 1 ) /2 , so the total cost is b ⋅ b ( 3 b − 1 ) / 2 + b ( b + 1 ) / 2 2 = b 3 b\cdot\frac{b(3b-1)/2+b(b+1)/2}{2}=b^3 b ⋅ 2 b ( 3 b − 1 ) /2 + b ( b + 1 ) /2 = b 3 . The swap count is b ⋅ b = b 2 b\cdot b=b^2 b ⋅ b = b 2 .
Lemma 8 (Level separation). At the start of level ℓ \ell ℓ (ℓ = 1 , … , t − 2 \ell=1,\ldots,t-2 ℓ = 1 , … , t − 2 ), the state consists of n / b = 2 t − ℓ n/b=2^{t-\ell} n / b = 2 t − ℓ reversed blocks of size b = 2 ℓ b=2^\ell b = 2 ℓ , where block j j j contains items { ( j − 1 ) b + 1 , … , j b } \{(j-1)b+1,\ldots,jb\} {( j − 1 ) b + 1 , … , j b } . All boundary costs between adjacent blocks equal 2 b − 1 2b-1 2 b − 1 . Consequently, FBS completes all merges at level ℓ \ell ℓ before touching any boundary at a higher level, and merges proceed left to right within each level.
Proof. At the start of level ℓ \ell ℓ , the boundary between any two adjacent blocks has cost 2 b − 1 2b-1 2 b − 1 : the right end of each block holds its smallest item and the left end holds its largest, separated by 2 b − 1 2b-1 2 b − 1 .
After the leftmost merge (blocks 1, 2) completes, the merged block of size 2 b 2b 2 b is fully reversed: all internal pairs are discordant and ineligible. The boundary between the merged block and the next unmerged block 3 has cost 3 b − 1 3b-1 3 b − 1 : the merged block’s smallest item is 1 (at its right end) and block 3’s largest item is 3 b 3b 3 b (at its left end), giving 3 b − 1 3b-1 3 b − 1 . Since 3 b − 1 > 2 b − 1 3b-1>2b-1 3 b − 1 > 2 b − 1 (for b ≥ 1 b\ge1 b ≥ 1 ), FBS proceeds to the next intra-pair boundary (blocks 3, 4, still at cost 2 b − 1 2b-1 2 b − 1 ). The argument generalises: after any merge pair completes, the inter-pair boundary has cost 3 b − 1 > 2 b − 1 3b-1>2b-1 3 b − 1 > 2 b − 1 , so merges proceed left to right.
After all merges at level ℓ \ell ℓ complete, the state consists of n / ( 2 b ) n/(2b) n / ( 2 b ) reversed blocks of size 2 b 2b 2 b , each with boundary cost 4 b − 1 = 2 ( 2 b ) − 1 4b-1=2(2b)-1 4 b − 1 = 2 ( 2 b ) − 1 —precisely the starting configuration for level ℓ + 1 \ell+1 ℓ + 1 .
Proof of Proposition 6 (five-block structure). We proceed by induction on t t t .
Base case (t = 2 t=2 t = 2 , n = 4 n=4 n = 4 ). K ∗ = 3 K^*=3 K ∗ = 3 . The FBS trace is: swap positions (1, 2) at cost 1, then (3, 4) at cost 1, then (2, 3) at cost 3, producing (2, 4, 1, 3). This matches: B1 = { 2 } \{2\} { 2 } , B2 = { 4 } \{4\} { 4 } , B3 = { 1 } \{1\} { 1 } , B4 = { 3 } \{3\} { 3 } , B5 empty.
Inductive step (t ≥ 3 t\ge3 t ≥ 3 ).
Phase 1. By Lemma 5, the first m m m swaps produce m m m reversed blocks of size 2.
Levels 1 through t − 2 t-2 t − 2 (full merges). By Lemma 6, after phase 1 the eligible positions are the m − 1 m-1 m − 1 even indices, all at cost 3 = 2 ⋅ 2 − 1 3=2\cdot2-1 3 = 2 ⋅ 2 − 1 . These are the intra-pair boundaries for level-1 merges. By Lemma 8, FBS processes merges left to right at each level. By the Merge Lemma 7, each level-ℓ \ell ℓ merge of two blocks of size b = 2 ℓ b=2^\ell b = 2 ℓ uses b 2 b^2 b 2 swaps at cost b 3 b^3 b 3 . At level ℓ \ell ℓ there are n / ( 2 b ) n/(2b) n / ( 2 b ) merges, giving 2 t − ℓ − 1 ⋅ b 2 = 2 t + ℓ − 1 2^{t-\ell-1}\cdot b^2=2^{t+\ell-1} 2 t − ℓ − 1 ⋅ b 2 = 2 t + ℓ − 1 swaps per level.
After level t − 2 t-2 t − 2 , the state consists of two reversed blocks of size m m m : the left block at positions 1 , … , m 1,\ldots,m 1 , … , m with items m , … , 1 m,\ldots,1 m , … , 1 , and the right block at positions m + 1 , … , 2 m m+1,\ldots,2m m + 1 , … , 2 m with items 2 m , … , m + 1 2m,\ldots,m+1 2 m , … , m + 1 .
Swap budget. Total swaps through level t − 2 t-2 t − 2 : ∑ k = t − 1 t − 3 2 k = 2 t − 1 ( 2 t − 1 − 1 ) = m ( m − 1 ) \sum_{k=t-1}^{t-3}2^k=2^{t-1}(2^{t-1}-1)=m(m-1) ∑ k = t − 1 t − 3 2 k = 2 t − 1 ( 2 t − 1 − 1 ) = m ( m − 1 ) . Since K ∗ = m ( 2 m − 1 ) / 2 K^*=m(2m-1)/2 K ∗ = m ( 2 m − 1 ) /2 , exactly K ∗ − m ( m − 1 ) = m / 2 K^*-m(m-1)=m/2 K ∗ − m ( m − 1 ) = m /2 swaps remain.
Top level (partial merge). The boundary at position m m m has cost 2 m − 1 2m-1 2 m − 1 . By the Merge Lemma’s round-0 structure, item n = 2 m n=2m n = 2 m (leftmost element of the right block) propagates leftward from position m + 1 m+1 m + 1 through positions m , m − 1 , … , m / 2 + 1 m,m-1,\ldots,m/2+1 m , m − 1 , … , m /2 + 1 , displacing items 1 , 2 , … , m / 2 1,2,\ldots,m/2 1 , 2 , … , m /2 one position to the right. This uses exactly m / 2 m/2 m /2 swaps (the remaining budget) at costs 2 m − 1 , 2 m − 2 , … , 3 m / 2 2m-1,2m-2,\ldots,3m/2 2 m − 1 , 2 m − 2 , … , 3 m /2 . The algorithm terminates because after K ∗ K^* K ∗ total swaps, Δ = ( n 2 ) − 2 K ∗ = 0 ≤ Δ ∗ \Delta=\binom{n}{2}-2K^*=0\le\Delta^* Δ = ( 2 n ) − 2 K ∗ = 0 ≤ Δ ∗ .
Final state. After the partial merge:
Positions 1 , … , m / 2 1,\ldots,m/2 1 , … , m /2 : items m , m − 1 , … , m / 2 + 1 m,m-1,\ldots,m/2+1 m , m − 1 , … , m /2 + 1 (undisturbed upper portion of the left block). This is B1 .
Positions m / 2 + 2 , … , m + 1 m/2+2,\ldots,m+1 m /2 + 2 , … , m + 1 : items m / 2 , m / 2 − 1 , … , 1 m/2,m/2-1,\ldots,1 m /2 , m /2 − 1 , … , 1 (lower portion of the left block, shifted right by one). This is B3 .
Position m + 2 m+2 m + 2 : item 2 m − 1 2m-1 2 m − 1 (second element of the right block, unmoved since only item 2 m 2m 2 m propagated left). This is B4 .
Positions m + 3 , … , 2 m m+3,\ldots,2m m + 3 , … , 2 m : items 2 m − 2 , … , m + 1 2m-2,\ldots,m+1 2 m − 2 , … , m + 1 (remainder of the right block). This is B5 .
This matches the five-block structure of Proposition 6.
LP relaxation lower bound. To compare the FBS cost against a lower bound, we relax the constraint that the inverted pairs form a valid inversion set (i.e., arise from a permutation). Let P ↗ : = { ( i , j ) : i < j , α i j = + 1 } P^{\nearrow}:=\{(i,j):i<j,\ \alpha_{ij}=+1\} P ↗ := {( i , j ) : i < j , α ij = + 1 } denote the set of concordant pairs in r s r_s r s . Introducing indicators x i j ∈ [ 0 , 1 ] x_{ij}\in[0,1] x ij ∈ [ 0 , 1 ] for each concordant pair and dropping the transitivity constraint gives the fractional knapsack relaxation :
LP : = min ∑ ( i , j ) ∈ P ↗ w i j x i j s.t. ∑ ( i , j ) ∈ P ↗ x i j = K ∗ , 0 ≤ x i j ≤ 1. \operatorname{LP}:=\min\sum_{(i,j)\in P^{\nearrow}}w_{ij}x_{ij}
\quad\text{s.t.}\quad
\sum_{(i,j)\in P^{\nearrow}}x_{ij}=K^*,\quad0\le x_{ij}\le1. LP := min ( i , j ) ∈ P ↗ ∑ w ij x ij s.t. ( i , j ) ∈ P ↗ ∑ x ij = K ∗ , 0 ≤ x ij ≤ 1.
The solution is immediate: set x i j = 1 x_{ij}=1 x ij = 1 for the K ∗ K^* K ∗ pairs with smallest weight. Hence LP = ∑ k = 1 K ∗ w ( k ) \operatorname{LP}=\sum_{k=1}^{K^*}w_{(k)} LP = ∑ k = 1 K ∗ w ( k ) , where w ( 1 ) ≤ w ( 2 ) ≤ ⋯ w_{(1)}\le w_{(2)}\le\cdots w ( 1 ) ≤ w ( 2 ) ≤ ⋯ are the sorted pair weights. Since LP relaxes constraints present in the true optimisation, LP ≤ d ∗ \operatorname{LP}\le d^* LP ≤ d ∗ .
Proposition 7 (LP closed form for a = s a=s a = s ). For integer scores s ( i ) = i s(i)=i s ( i ) = i with all pairs concordant, there are exactly ( n − d ) (n-d) ( n − d ) pairs of weight d d d for each d = 1 , … , n − 1 d=1,\ldots,n-1 d = 1 , … , n − 1 . The LP selects pairs greedily from cheapest to most expensive:
LP ( n ) = ∑ d = 1 D − 1 d ( n − d ) + D ⋅ R , \operatorname{LP}(n)=\sum_{d=1}^{D-1}d(n-d)+D\cdot R, LP ( n ) = d = 1 ∑ D − 1 d ( n − d ) + D ⋅ R , where D D D is the smallest integer with ∑ d = 1 D ( n − d ) ≥ K ∗ \sum_{d=1}^{D}(n-d)\ge K^* ∑ d = 1 D ( n − d ) ≥ K ∗ and R : = K ∗ − ∑ d = 1 D − 1 ( n − d ) R:=K^*-\sum_{d=1}^{D-1}(n-d) R := K ∗ − ∑ d = 1 D − 1 ( n − d ) .
Proof of Proposition 7. For s ( i ) = i s(i)=i s ( i ) = i , each pair ( i , j ) (i,j) ( i , j ) with i < j i<j i < j has weight w i j = j − i = : d w_{ij}=j-i=:d w ij = j − i =: d . For each d ∈ { 1 , … , n − 1 } d\in\{1,\ldots,n-1\} d ∈ { 1 , … , n − 1 } there are exactly n − d n-d n − d pairs at distance d d d (namely ( i , i + d ) (i,i+d) ( i , i + d ) for i = 1 , … , n − d i=1,\ldots,n-d i = 1 , … , n − d ). The LP selects the K ∗ K^* K ∗ cheapest pairs, so it fills all n − 1 n-1 n − 1 pairs of weight 1, then all n − 2 n-2 n − 2 pairs of weight 2, and so on through weight D − 1 D-1 D − 1 , consuming ∑ d = 1 D − 1 ( n − d ) \sum_{d=1}^{D-1}(n-d) ∑ d = 1 D − 1 ( n − d ) pairs at total cost ∑ d = 1 D − 1 d ( n − d ) \sum_{d=1}^{D-1}d(n-d) ∑ d = 1 D − 1 d ( n − d ) . The remaining R = K ∗ − ∑ d = 1 D − 1 ( n − d ) R=K^*-\sum_{d=1}^{D-1}(n-d) R = K ∗ − ∑ d = 1 D − 1 ( n − d ) pairs are taken from the n − D n-D n − D available pairs of weight D D D (note R ≤ n − D R\le n-D R ≤ n − D by minimality of D D D ), contributing $D\cdot R.
The critical weight satisfies D = ( 2 − 2 ) m + O ( 1 ) D=(2-\sqrt{2})m+O(1) D = ( 2 − 2 ) m + O ( 1 ) as m → ∞ m\to\infty m → ∞ : solving ∑ d = 1 D ( n − d ) = K ∗ \sum_{d=1}^{D}(n-d)=K^* ∑ d = 1 D ( n − d ) = K ∗ , i.e. D n − D ( D + 1 ) / 2 = m ( 2 m − 1 ) / 2 Dn-D(D+1)/2=m(2m-1)/2 D n − D ( D + 1 ) /2 = m ( 2 m − 1 ) /2 , gives D 2 − 2 ( 2 m − 1 ) D + m ( 2 m − 1 ) = 0 D^2-2(2m-1)D+m(2m-1)=0 D 2 − 2 ( 2 m − 1 ) D + m ( 2 m − 1 ) = 0 , whose positive root is ( 2 − 2 ) m + O ( 1 ) (2-\sqrt{2})m+O(1) ( 2 − 2 ) m + O ( 1 ) . Despite being called “LP”, the value requires no solver and is computed in O ( n ) O(n) O ( n ) time.
Proof of Proposition 3 (Tight bound for the all-ascending case). Write m = n / 2 m=n/2 m = n /2 and c = 2 − 2 c=2-\sqrt{2} c = 2 − 2 .
FBS cost. By Proposition 6, d F B S = m ( 8 m 2 + 21 m − 14 ) / 24 = m 3 / 3 + O ( m 2 ) d_{\mathrm{FBS}}=m(8m^2+21m-14)/24=m^3/3+O(m^2) d FBS = m ( 8 m 2 + 21 m − 14 ) /24 = m 3 /3 + O ( m 2 ) .
LP lower bound. By Proposition 7, LP = ∑ d = 1 D − 1 d ( n − d ) + D ⋅ R \operatorname{LP}=\sum_{d=1}^{D-1}d(n-d)+D\cdot R LP = ∑ d = 1 D − 1 d ( n − d ) + D ⋅ R with D = c m + O ( 1 ) D=cm+O(1) D = c m + O ( 1 ) . Expanding: ∑ d = 1 D − 1 d ( 2 m − d ) = c 2 ( 1 − c / 3 ) m 3 + O ( m 2 ) \sum_{d=1}^{D-1}d(2m-d)=c^2(1-c/3)m^3+O(m^2) ∑ d = 1 D − 1 d ( 2 m − d ) = c 2 ( 1 − c /3 ) m 3 + O ( m 2 ) . The remainder term D ⋅ R D\cdot R D ⋅ R contributes O ( m 2 ) O(m^2) O ( m 2 ) , so LP = c 2 ( 1 − c / 3 ) m 3 + O ( m 2 ) \operatorname{LP}=c^2(1-c/3)m^3+O(m^2) LP = c 2 ( 1 − c /3 ) m 3 + O ( m 2 ) .
Convergence. The ratio satisfies
d F B S LP = m 3 / 3 + O ( m 2 ) c 2 ( 1 − c / 3 ) m 3 + O ( m 2 ) ⟶ 1 3 c 2 ( 1 − c / 3 ) . \frac{d_{\mathrm{FBS}}}{\operatorname{LP}}
=
\frac{m^3/3+O(m^2)}{c^2(1-c/3)m^3+O(m^2)}
\longrightarrow
\frac{1}{3c^2(1-c/3)}. LP d FBS = c 2 ( 1 − c /3 ) m 3 + O ( m 2 ) m 3 /3 + O ( m 2 ) ⟶ 3 c 2 ( 1 − c /3 ) 1 .
Substituting c = 2 − 2 c=2-\sqrt{2} c = 2 − 2 : c 2 = 6 − 4 2 c^2=6-4\sqrt{2} c 2 = 6 − 4 2 , 1 − c / 3 = ( 1 + 2 ) / 3 1-c/3=(1+\sqrt{2})/3 1 − c /3 = ( 1 + 2 ) /3 , so 3 c 2 ( 1 − c / 3 ) = ( 6 − 4 2 ) ( 1 + 2 ) = 6 + 6 2 − 4 2 − 8 = 2 ( 2 − 1 ) 3c^2(1-c/3)=(6-4\sqrt{2})(1+\sqrt{2})=6+6\sqrt{2}-4\sqrt{2}-8=2(\sqrt{2}-1) 3 c 2 ( 1 − c /3 ) = ( 6 − 4 2 ) ( 1 + 2 ) = 6 + 6 2 − 4 2 − 8 = 2 ( 2 − 1 ) . Hence the limit is 1 / [ 2 ( 2 − 1 ) ] = ( 1 + 2 ) / 2 ≈ 1.207 1/[2(\sqrt{2}-1)]=(1+\sqrt{2})/2\approx1.207 1/ [ 2 ( 2 − 1 )] = ( 1 + 2 ) /2 ≈ 1.207 .
Strict 2-approximation. Since L P ≤ d ∗ \mathrm{LP} \le d^* LP ≤ d ∗ , it suffices to show d F B S < 2 L P d_{\mathrm{FBS}} < 2\mathrm{LP} d FBS < 2 LP for all t ≥ 2 t \ge2 t ≥ 2 . For even m ≥ 2 m \ge2 m ≥ 2 , the m / 2 m/2 m /2 cheapest weight classes contain ∑ d = 1 m / 2 ( 2 m − d ) = m ( 7 m − 2 ) / 8 ≤ m ( 2 m − 1 ) / 2 = K ∗ \sum_{d=1}^{m/2}(2m-d)=m(7m-2)/8 \le m(2m-1)/2=K^* ∑ d = 1 m /2 ( 2 m − d ) = m ( 7 m − 2 ) /8 ≤ m ( 2 m − 1 ) /2 = K ∗ pairs (the inequality reduces to m ≥ 2 m \ge2 m ≥ 2 ), so
L P ≥ ∑ d = 1 m / 2 d ( 2 m − d ) = m ( m + 2 ) ( 5 m − 1 ) 24 . \mathrm{LP} \ge\sum_{d=1}^{m/2}d(2m-d)=\frac{m(m+2)(5m-1)}{24}. LP ≥ d = 1 ∑ m /2 d ( 2 m − d ) = 24 m ( m + 2 ) ( 5 m − 1 ) .
The condition d F B S < 2 L P d_{\mathrm{FBS}} < 2\mathrm{LP} d FBS < 2 LP then becomes
m ( 8 m 2 + 21 m − 14 ) 24 < m ( m + 2 ) ( 5 m − 1 ) 12 , \frac{m(8m^2+21m-14)}{24}<\frac{m(m+2)(5m-1)}{12}, 24 m ( 8 m 2 + 21 m − 14 ) < 12 m ( m + 2 ) ( 5 m − 1 ) ,
which simplifies to 2 m 2 − 3 m + 10 > 0 2m^2-3m+10>0 2 m 2 − 3 m + 10 > 0 . Since the discriminant 9 − 80 = − 71 < 0 9-80=-71<0 9 − 80 = − 71 < 0 and the leading coefficient is positive, this holds for all real m m m .
Towards a proof of the 2-approximation
This appendix explains why the constant 2 in the 2-approximation conjecture is structurally motivated, outlines the proof path it suggests, and identifies the remaining open step.
Step 1: FBS and optimum live in the same Kendall ball. By Theorem 1, every feasible ranking has at least K ∗ K^* K ∗ inversions, and FBS achieves exactly K ∗ K^* K ∗ . Hence
K ( r F B S ) = K ( r ∗ ) = K ∗ , K(r_{\mathrm{FBS}})=K(r^*)=K^*, K ( r FBS ) = K ( r ∗ ) = K ∗ ,
i.e. both rankings sit on the sphere { r : ∣ Inv ( r s , r ) ∣ = K ∗ } \{r:|\operatorname{Inv}(r_s,r)|=K^*\} { r : ∣ Inv ( r s , r ) ∣ = K ∗ } . The two solutions therefore differ only in which K ∗ K^* K ∗ pairs are inverted, not in their cardinality.
Step 2: Diaconis–Graham yields a factor-2 ratio on the Spearman footrule. The classical Diaconis–Graham inequality [8 ] states that for every ranking r r r ,
K ( r ) ≤ F ( r ) ≤ 2 K ( r ) , F ( r ) : = ∑ i ∣ r ( i ) − i ∣ = ∥ δ ∥ 1 . K(r)\le F(r)\le2K(r),\qquad F(r):=\sum_i|r(i)-i|=\lVert\delta\rVert_1. K ( r ) ≤ F ( r ) ≤ 2 K ( r ) , F ( r ) := i ∑ ∣ r ( i ) − i ∣ = ∥ δ ∥ 1 .
Applying this to both rankings (which have K = K ∗ K=K^* K = K ∗ by Step 1):
∥ δ F B S ∥ 1 = F ( r F B S ) ≤ 2 K ∗ , ∥ δ ∗ ∥ 1 = F ( r ∗ ) ≥ K ∗ . \lVert\delta_{\mathrm{FBS}}\rVert_1=F(r_{\mathrm{FBS}})\le2K^*,\qquad\lVert\delta^*\rVert_1=F(r^*)\ge K^*. ∥ δ FBS ∥ 1 = F ( r FBS ) ≤ 2 K ∗ , ∥ δ ∗ ∥ 1 = F ( r ∗ ) ≥ K ∗ .
Dividing gives the footrule-ratio bound
∥ δ F B S ∥ 1 ∥ δ ∗ ∥ 1 ≤ 2. \frac{\lVert\delta_{\mathrm{FBS}}\rVert_1}{\lVert\delta^*\rVert_1}\le2. ∥ δ ∗ ∥ 1 ∥ δ FBS ∥ 1 ≤ 2.
Step 3: The Spearman–Kendall identity propagates the ratio to d d d . By Lemma 4, d ( r s , r ) = 1 2 ∥ δ ∥ 2 2 d(r_s,r)=\frac{1}{2}\lVert\delta\rVert_2^2 d ( r s , r ) = 2 1 ∥ δ ∥ 2 2 , so
d ( r s , r F B S ) d ( r s , r ∗ ) = ∥ δ F B S ∥ 2 2 ∥ δ ∗ ∥ 2 2 . \frac{d(r_s,r_{\mathrm{FBS}})}{d(r_s,r^*)}=\frac{\lVert\delta_{\mathrm{FBS}}\rVert_2^2}{\lVert\delta^*\rVert_2^2}. d ( r s , r ∗ ) d ( r s , r FBS ) = ∥ δ ∗ ∥ 2 2 ∥ δ FBS ∥ 2 2 .
Converting the footrule ratio of Step 2 into a squared-displacement ratio is straightforward when the two displacement profiles are comparably spread. A standard tool is Hölder’s inequality
∥ δ ∥ 2 2 ≤ ∥ δ ∥ ∞ ⋅ ∥ δ ∥ 1 , \lVert\delta\rVert_2^2\leq\lVert\delta\rVert_\infty\cdot\lVert\delta\rVert_1, ∥ δ ∥ 2 2 ≤ ∥ δ ∥ ∞ ⋅ ∥ δ ∥ 1 ,
which combined with Step 2 gives
d ( r s , r F B S ) ≤ 1 2 ∥ δ F B S ∥ ∞ ⋅ ∥ δ F B S ∥ 1 ≤ ∥ δ F B S ∥ ∞ ⋅ K ∗ . d(r_s,r_{\mathrm{FBS}})\leq\frac{1}{2}\lVert\delta_{\mathrm{FBS}}\rVert_\infty\cdot\lVert\delta_{\mathrm{FBS}}\rVert_1\leq\lVert\delta_{\mathrm{FBS}}\rVert_\infty\cdot K^*. d ( r s , r FBS ) ≤ 2 1 ∥ δ FBS ∥ ∞ ⋅ ∥ δ FBS ∥ 1 ≤ ∥ δ FBS ∥ ∞ ⋅ K ∗ .
A factor-2 bound on d d d then follows whenever ∥ δ F B S ∥ ∞ / ∥ δ ∗ ∥ ∞ \lVert\delta_{\mathrm{FBS}}\rVert_\infty/\lVert\delta^*\rVert_\infty ∥ δ FBS ∥ ∞ / ∥ δ ∗ ∥ ∞ is bounded, i.e. whenever FBS does not concentrate its displacement on a single item disproportionately more than the optimum does.
Why the constant cannot be lowered through this route. The right-hand side F ≤ 2 K F\leq2K F ≤ 2 K in the Diaconis–Graham inequality is tight : it is saturated, for example, by the long shift r = ( 2 , 3 , … , n , 1 ) r=(2,3,\ldots,n,1) r = ( 2 , 3 , … , n , 1 ) , which has K = n − 1 K=n-1 K = n − 1 inversions and F = 2 ( n − 1 ) F=2(n-1) F = 2 ( n − 1 ) . Consequently, no proof going through Diaconis–Graham can yield a constant below 2. Tightening the conjecture would require an inequality that exploits the specific structure of r F B S r_{\mathrm{FBS}} r FBS —in particular, the fact that FBS’s min-cost selection rule produces spread-out displacement profiles, while the optimum may concentrate displacement on a few items.
The remaining open step: anti-concentration of FBS. The structural property still to be formalised is that FBS’s min-cost rule prevents displacement concentration: an item that has already been displaced far creates expensive adjacent pairs, which FBS avoids in favour of cheaper swaps elsewhere. Concretely, we conjecture an injective charging argument : every swap that contributes a large term to ∥ δ F B S ∥ 2 2 \lVert\delta_{\mathrm{FBS}}\rVert_2^2 ∥ δ FBS ∥ 2 2 can be paired with at least one earlier swap of comparable cost in r ∗ r^* r ∗ . Combined with Steps 1–3 this would close the proof.
Empirical support. For the all-ascending case a = s a=s a = s with ψ = 1 \psi=1 ψ = 1 , the strict 2-approximation is proved analytically (Proposition 3), with the ratio converging to ( 1 + 2 ) / 2 ≈ 1.207 (1+\sqrt{2})/2\approx1.207 ( 1 + 2 ) /2 ≈ 1.207 . For arbitrary attribute arrays, the exhaustive verification at n ≤ 9 n\leq9 n ≤ 9 (worst ratio 1.46) together with MILP-exact computation up to n = 100 n=100 n = 100 (d F B S / d ∗ ≤ 1.31 d_{\mathrm{FBS}}/d^*\leq1.31 d FBS / d ∗ ≤ 1.31 across 542 instances; LP-bound ≤ 1.32 \leq1.32 ≤ 1.32 across 612 instances, Appendix I) strongly supports the conjecture, and indeed suggests that the sharp constant may be substantially below 2.
Proof of Section 8
Proof of Proposition 4 (unweighted case). Initialisation (lines 1–6). Sorting by score costs O ( n log n ) O(n\log n) O ( n log n ) . Computing the sign array σ \sigma σ costs O ( n ) O(n) O ( n ) . The Kendall counts N ↗ N_{\nearrow} N ↗ and N ↘ N_{\searrow} N ↘ are each computed by merge-sort–based counting in O ( n log n ) O(n\log n) O ( n log n ) . Building the linked list L L L is a single pass over σ \sigma σ : O ( n ) O(n) O ( n ) . Total initialisation: O ( n log n ) O(n\log n) O ( n log n ) .
Main loop (lines 7–24). The loop executes exactly K ∗ K^* K ∗ iterations (Proposition 1). In each iteration: retrieving an element from L L L is O ( 1 ) O(1) O ( 1 ) ; the swap itself is O ( 1 ) O(1) O ( 1 ) ; updating σ \sigma σ for three neighbours and maintaining L L L (at most 3 insertions/deletions in a doubly-linked list) is O ( 1 ) O(1) O ( 1 ) ; updating N ↗ , N ↘ N_{\nearrow},N_{\searrow} N ↗ , N ↘ is O ( 1 ) O(1) O ( 1 ) . Total per iteration: O ( 1 ) O(1) O ( 1 ) . Total for the loop: O ( K ∗ ) O(K^*) O ( K ∗ ) .
Overall time (part (i)). O ( n log n ) + O ( K ∗ ) = O ( n log n + K ∗ ) O(n\log n)+O(K^*)=O(n\log n+K^*) O ( n log n ) + O ( K ∗ ) = O ( n log n + K ∗ ) . In the worst case K ∗ = Θ ( n 2 ) K^*=\Theta(n^2) K ∗ = Θ ( n 2 ) and the n log n n\log n n log n term is absorbed, giving O ( n 2 ) O(n^2) O ( n 2 ) .
Space (part (ii)). The algorithm stores: the arrays R [ ] R[\,] R [ ] , A [ ] A[\,] A [ ] (O ( n ) O(n) O ( n ) ); the sign array σ [ 1.. n − 1 ] \sigma[1..n-1] σ [ 1.. n − 1 ] (O ( n ) O(n) O ( n ) ); the doubly-linked list L L L with at most n − 1 n-1 n − 1 entries (O ( n ) O(n) O ( n ) ); and O ( 1 ) O(1) O ( 1 ) scalars. Total: O ( n ) O(n) O ( n ) .
Proof of Proposition 4 (weighted case). Initialisation (lines 1–7).
Line 4 (Kendall counts). Computing N ↗ = ∣ { i < j : A [ i ] < A [ j ] } ∣ N_{\nearrow} = |\{i < j : A[i] < A[j]\}| N ↗ = ∣ { i < j : A [ i ] < A [ j ]} ∣ and N ↘ = ∣ { i < j : A [ i ] > A [ j ] } ∣ N_{\searrow} = |\{i < j : A[i] > A[j]\}| N ↘ = ∣ { i < j : A [ i ] > A [ j ]} ∣ independently, each by a merge-sort-based count, costs O ( n log n ) O(n \log n) O ( n log n ) .
Line 7 (heap construction). Build a min-heap H H H over the ≤ n − 1 \le n-1 ≤ n − 1 entries k k k with σ [ k ] = μ \sigma[k] = \mu σ [ k ] = μ , keyed by ( c [ k ] , k ) (c[k], k) ( c [ k ] , k ) . Bottom-up heap construction costs O ( n ) O(n) O ( n ) .
Total initialisation: O ( n log n ) O(n \log n) O ( n log n ) .
Main loop (lines 8–28). By Proposition 1 the loop executes exactly K ∗ K^* K ∗ iterations. In each iteration:
Lines 11–26 (neighbour updates and heap maintenance). Exactly 3 entries ℓ ∈ { k ∗ − 1 , k ∗ , k ∗ + 1 } \ell\in\{k^*-1, k^*, k^*+1\} ℓ ∈ { k ∗ − 1 , k ∗ , k ∗ + 1 } are inspected (fewer at the boundaries). For each:
Recompute c [ ℓ ] c[\ell] c [ ℓ ] and σ [ ℓ ] \sigma[\ell] σ [ ℓ ] in O ( 1 ) O(1) O ( 1 ) .
Perform at most one heap operation (insert, delete, or decrease-key), each costing O ( log n ) O(\log n) O ( log n ) .
Total per iteration: at most 3 heap operations, costing O ( log n ) O(\log n) O ( log n ) .
Line 27 (Kendall counts). The global counters N ↗ , N ↘ N_{\nearrow}, N_{\searrow} N ↗ , N ↘ are updated in O ( 1 ) O(1) O ( 1 ) .
Total for the loop: O ( log n ) × K ∗ = O ( K ∗ log n ) O(\log n) \times K^* = O(K^* \log n) O ( log n ) × K ∗ = O ( K ∗ log n ) .
Overall time (part (i)). O ( n log n ) + O ( K ∗ log n ) = O ( ( n + K ∗ ) log n ) O(n \log n) + O(K^* \log n) = O((n + K^*) \log n) O ( n log n ) + O ( K ∗ log n ) = O (( n + K ∗ ) log n ) .
Worst case. The maximum value of K ∗ K^* K ∗ occurs when Δ 0 = ( n 2 ) \Delta_0 = \binom{n}{2} Δ 0 = ( 2 n ) (all pairs concordant, e.g. a ≡ r s a \equiv r_s a ≡ r s ) and Δ ∗ = 0 \Delta^* = 0 Δ ∗ = 0 (or 1), giving K ∗ = ⌊ ( n 2 ) / 2 ⌋ = Θ ( n 2 ) K^* = \lfloor\binom{n}{2}/2 \rfloor= \Theta(n^2) K ∗ = ⌊ ( 2 n ) /2 ⌋ = Θ ( n 2 ) . The overall time is then O ( n 2 log n ) O(n^2 \log n) O ( n 2 log n ) .
Space (part (ii)). The algorithm stores: the arrays R [ ⋅ ] R[\cdot] R [ ⋅ ] , S [ ⋅ ] S[\cdot] S [ ⋅ ] , A [ ⋅ ] A[\cdot] A [ ⋅ ] (input, O ( n ) O(n) O ( n ) ); the auxiliary arrays c [ 1.. n − 1 ] c[1..n-1] c [ 1.. n − 1 ] and σ [ 1.. n − 1 ] \sigma[1..n-1] σ [ 1.. n − 1 ] (O ( n ) O(n) O ( n ) each); the min-heap H H H with at most n − 1 n-1 n − 1 entries (O ( n ) O(n) O ( n ) ); the scalars N ↗ N_{\nearrow} N ↗ , N ↘ N_{\searrow} N ↘ , Δ ∗ \Delta^* Δ ∗ , k ∗ k^* k ∗ , μ \mu μ (O ( 1 ) O(1) O ( 1 ) ). Total auxiliary space: O ( n ) O(n) O ( n ) .
Datasets
For the real-world experiments we use four datasets commonly adopted in the fair-ranking literature. For each, we report the chosen score, the chosen continuous protected attribute, the size n n n after removing missing entries, and the initial fairness ϕ 0 \phi_0 ϕ 0 (the value of ϕ \phi ϕ on the score-sorted ranking). All datasets are publicly available; preprocessing is intentionally minimal to keep results reproducible.
COMPAS [1 ] . The ProPublica COMPAS dataset of recidivism risk assessments. Score: decile_score (integer 1–10, higher = higher predicted risk). Continuous attribute: age (years). After dropping rows with missing values, n = 7,214 n = 7{,}214 n = 7 , 214 and ϕ 0 = 0.72 \phi_0 = 0.72 ϕ 0 = 0.72 .
German Credit [17 ] . The Statlog (German Credit) dataset from the UCI repository. Score: credit_amount (Deutschmark, continuous). Continuous attribute: age (years). n = 1,000 n = 1{,}000 n = 1 , 000 (no missing values), ϕ 0 = 0.98 \phi_0 = 0.98 ϕ 0 = 0.98 .
Law School [36 ] . The LSAC National Longitudinal Bar Passage Study. Score: lsat (LSAT score, continuous). Continuous attribute: ugpa (undergraduate GPA, continuous). After dropping rows with missing values, n = 18,692 n = 18{,}692 n = 18 , 692 and ϕ 0 = 0.85 \phi_0 = 0.85 ϕ 0 = 0.85 .
Communities and Crime [32 ] . A community-level dataset from the UCI repository combining socio-economic data from the 1990 US Census, 1995 FBI Uniform Crime Report, and 1990 Law Enforcement Management and Administrative Statistics survey. All variables are normalized to [ 0 , 1 ] [0, 1] [ 0 , 1 ] . Score: ViolentCrimesPerPop (continuous, normalized violent-crime rate per population). Continuous attribute: PctPopUnderPov (continuous, fraction of the population below the poverty line). n = 1,994 n = 1{,}994 n = 1 , 994 , ϕ 0 = 0.56 \phi_0 = 0.56 ϕ 0 = 0.56 .
Score and attribute choice. For COMPAS and German Credit we follow the standard fair-ranking convention of using the dataset’s primary risk/utility score and treating age as the continuous protected attribute. For Law School we follow the same convention used for predicting bar passage, with LSAT as the score and undergraduate GPA as the continuous attribute on which the ranking should remain balanced. For Communities and Crime, all numerical variables are continuous and pre-normalized; we choose the violent-crime rate as the score (the natural ranking target in this dataset) and the poverty rate as the protected attribute, motivated by the well-documented correlation between poverty and reported crime rates [20 ] . This choice yields the lowest initial fairness among the four datasets (ϕ 0 = 0.56 \phi_0 = 0.56 ϕ 0 = 0.56 ) and therefore exhibits the richest fairness–cost trade-off curve.
Baselines
We compare FBS against four baselines. Three are existing group-fair re-ranking algorithms that require a discrete protected group; we adapt them to the continuous setting by quantile-binning the attribute a a a into G G G equal-frequency bins. The fourth, Blend , is a continuous heuristic of our own that interpolates between the score order and a perfectly-fair target order. All baselines are evaluated on the same axes as FBS: achieved continuous fairness ϕ \phi ϕ (computed on the original undiscretized attribute) and weighted Kemeny distance d ( r s , r ) d(r_s, r) d ( r s , r ) from the score-based ranking.
DetConstSort [13 ] . A deterministic constrained-sorting algorithm that enforces proportional representation of each protected group within every prefix of the output ranking. Given group proportions p g = ∣ { i : g ( i ) = g } ∣ / n p_g = |\{i : g(i) = g\}|/n p g = ∣ { i : g ( i ) = g } ∣/ n , it iteratively appends the highest-scoring remaining item subject to the constraint that, for every group g g g , the count in the current prefix is at least ⌊ p g ⋅ k ⌋ \lfloor p_g \cdot k \rfloor ⌊ p g ⋅ k ⌋ for prefix length k k k . We use the implementation provided by FairRankTune [4 ] . We report results for G ∈ { 2 , 3 , 5 , 10 } G \in\{2, 3, 5, 10\} G ∈ { 2 , 3 , 5 , 10 } .
FA*IR [39 ] . A re-ranking algorithm that guarantees the protected group meets a minimum representation in every prefix, certified by a statistical test with significance α = 0.1 \alpha= 0.1 α = 0.1 . FA*IR is intrinsically binary: a single “protected” group versus the rest. We restrict it to G = 2 G = 2 G = 2 (median split on a a a ), assigning as protected the group most under-represented in the top half of the score-sorted ranking. Since the mtable computation is exponential in k k k , in the Pareto experiments, we use k = 400 k = 400 k = 400 , as suggested by the authors. Furthermore, we use the implementation provided by fairsearchcore [22 ] .
Median-split interleaving (ours). A simple binary baseline that splits items at the median attribute value into two groups, sorts each group by descending score, and builds the output ranking by alternately picking the next highest-scored item from each group. When one group is exhausted, the remainder of the other is appended. This serves as a sanity-check baseline: it always achieves close-to-perfect attribute balance on the binary partition but ignores both score gaps and the continuous nature of a a a .
Blend (continuous heuristic, ours). Unlike the above, Blend does not discretize a a a . It computes, for each item i i i : (a) its score-position ρ s ( i ) \rho_s(i) ρ s ( i ) , the rank of i i i in the score-sorted order; (b) a fair-position ρ f ( i ) \rho_f(i) ρ f ( i ) , obtained by sorting items by a a a and interleaving the high-attribute and low-attribute halves to produce a permutation with ϕ ≈ 1 \phi\approx1 ϕ ≈ 1 . The output ranking is then obtained by sorting items by the convex combination
ρ β ( i ) = β ρ s ( i ) + ( 1 − β ) ρ f ( i ) , β ∈ [ 0 , 1 ] . \rho_\beta(i) = \beta\rho_s(i) + (1 - \beta)\rho_f(i), \qquad\beta\in[0, 1]. ρ β ( i ) = β ρ s ( i ) + ( 1 − β ) ρ f ( i ) , β ∈ [ 0 , 1 ] .
At β = 1 \beta= 1 β = 1 this reduces to the original score order (ϕ = ϕ 0 \phi= \phi_0 ϕ = ϕ 0 , d = 0 d = 0 d = 0 ); at β = 0 \beta= 0 β = 0 it returns the perfectly-fair target order (ϕ ≈ 1 \phi\approx1 ϕ ≈ 1 , d d d potentially very large). Sweeping β \beta β traces a curve in the fairness–cost plane. Because the blend is between integer ranks rather than scores, Blend is cost-blind: a swap between two items with very different scores costs the same in the blend space as a swap between two near-equal-score items. This is the main reason Blend underperforms FBS on real data with skewed score distributions, where greedy minimum-cost swapping (FBS) keeps the cumulative cost much smaller for the same fairness gain.
Discretization information loss. The first three baselines depend on a discretization parameter G G G . Increasing G G G allows finer fairness control but also increases the number of constraints and hence the cost of satisfying them. Crucially, even at G = 10 G = 10 G = 10 the algorithm is blind to within-bin variation of a a a , while FBS optimises the continuous fairness measure ϕ \phi ϕ at the pairwise level.
MILP formulation for the exact optimum
§ 6 (Exact MILP optimum for medium n n n ) reports the empirical approximation ratio d F B S / d ∗ d_{\mathrm{FBS}}/d^* d FBS / d ∗ obtained by solving the weighted Kemeny problem with fairness constraint exactly. Here we describe the MILP formulation used.
For each unordered pair ( i , j ) (i,j) ( i , j ) with i < j i < j i < j we introduce a binary variable x i j ∈ { 0 , 1 } x_{ij} \in\{0,1\} x ij ∈ { 0 , 1 } that equals 1 if and only if the pair is inverted in the output ranking with respect to the score-sorted ranking r s r_s r s . Writing α i j = sgn ( a ( j ) − a ( i ) ) ∈ { − 1 , + 1 } \alpha_{ij} = \operatorname{sgn}(a(j) - a(i)) \in\{-1,+1\} α ij = sgn ( a ( j ) − a ( i )) ∈ { − 1 , + 1 } and D 0 = ∑ i < j α i j D_0 = \sum_{i<j}\alpha_{ij} D 0 = ∑ i < j α ij , the problem reads:
min x ∈ { 0 , 1 } ( n 2 ) ∑ i < j ∣ s ( i ) − s ( j ) ∣ x i j s.t. ∣ D 0 − 2 ∑ i < j α i j x i j ∣ ≤ Δ ∗ \min_{x\in\{0,1\}^{\binom{n}{2}}} \sum_{i<j} \lvert s(i)-s(j)\rvert x_{ij}
\quad\text{s.t.}\quad
\left\lvert D_0 - 2\sum_{i<j}\alpha_{ij}x_{ij}\right\rvert\le\Delta^* x ∈ { 0 , 1 } ( 2 n ) min i < j ∑ ∣ s ( i ) − s ( j )∣ x ij s.t. D 0 − 2 i < j ∑ α ij x ij ≤ Δ ∗
together with the standard FAS-style triangle (transitivity) constraints
x i j + x j k − x i k ≤ 1 , − x i j − x j k + x i k ≤ 0 ∀ i < j < k x_{ij}+x_{jk}-x_{ik}\le1,\qquad-x_{ij}-x_{jk}+x_{ik}\le0\qquad\forall i<j<k x ij + x j k − x ik ≤ 1 , − x ij − x j k + x ik ≤ 0 ∀ i < j < k
which together rule out the only two binary inversion patterns inconsistent with a permutation. The fairness constraint is encoded as the pair of linear inequalities α ⊤ x ≤ ( D 0 + Δ ∗ ) / 2 \alpha^\top x \le(D_0+\Delta^*)/2 α ⊤ x ≤ ( D 0 + Δ ∗ ) /2 and α ⊤ x ≥ ( D 0 − Δ ∗ ) / 2 \alpha^\top x \ge(D_0-\Delta^*)/2 α ⊤ x ≥ ( D 0 − Δ ∗ ) /2 .
For n ∈ { 20 , 50 , 100 } n \in\{20,50,100\} n ∈ { 20 , 50 , 100 } this yields a MILP with ( n 2 ) \binom{n}{2} ( 2 n ) binary variables and 2 + 2 ( n 3 ) 2+2\binom{n}{3} 2 + 2 ( 3 n ) linear constraints (e.g., 190 binaries and 2,282 constraints at n = 20 n=20 n = 20 ; 1,225 binaries and 39,202 constraints at n = 100 n=100 n = 100 ). We solve each instance with HiGHS via scipy.optimize.milp, capping the solver at 180 s with a 0.1% relative-gap tolerance, and additionally wrapping every solve in a 300 s subprocess wall-clock cap. We generate 155 instances per n n n (100 random, 50 correlated, 5 reversed). Across the 542 instances solved within the limits, the worst observed exact ratio is 1.31, attained on a correlated configuration at n = 50 n=50 n = 50 , and the LP relaxation upper-bounds the ratio by 1.32 across 612 instances. Together with the exhaustive enumeration up to n = 9 n=9 n = 9 (worst ratio 1.46 over 699,282 instances), this provides strong empirical evidence for the 2-approximation conjecture.
Additional experimental results
Approximation ratio for the all-ascending case
Proposition 3 predicts that, for the all-ascending configuration a = s a=s a = s and n = 2 t n=2^t n = 2 t , the ratio d F B S / L P d_{\mathrm{FBS}}/\mathrm{LP} d FBS / LP converges to ( 1 + 2 ) / 2 ≈ 1.207 (1+\sqrt{2})/2 \approx1.207 ( 1 + 2 ) /2 ≈ 1.207 . We compute the closed-form FBS cost (Proposition 6) and the LP relaxation bound for each n = 2 t n=2^t n = 2 t with t = 2 , … , 21 t=2,\ldots,21 t = 2 , … , 21 (up to n ≈ 2 × 10 6 n\approx2\times10^6 n ≈ 2 × 1 0 6 ). Figure 4 shows the convergence: the ratio decreases monotonically from 1.67 (n = 4 n=4 n = 4 ) and stabilises at 1.207 for t ≥ 10 t\ge10 t ≥ 10 .
Figure 4. Ratio d F B S / L P d_{\mathrm{FBS}}/\mathrm{LP} d FBS / LP for the all-ascending case a = s a=s a = s with n = 2 t n=2^t n = 2 t , t = 2 , … , 21 t=2,\ldots,21 t = 2 , … , 21 . The dashed red line marks the theoretical limit ( 1 + 2 ) / 2 ≈ 1.207 (1+\sqrt{2})/2\approx1.207 ( 1 + 2 ) /2 ≈ 1.207 from Proposition 3 .
For general (non-power-of-two) n n n , the five-block structure of Proposition 6 does not apply, and the ratio exhibits a persistent oscillation. Figure 5 shows d F B S / L P d_{\mathrm{FBS}}/\mathrm{LP} d FBS / LP for n = 4 , … , 200 n=4,\ldots,200 n = 4 , … , 200 (every integer) and selected values up to n = 75 , 000 n=75,000 n = 75 , 000 , all with a = s a=s a = s and Δ ∗ \Delta^* Δ ∗ set to the tightest feasible value. The local minima, occurring near powers of two, approach the ( 1 + 2 ) / 2 (1+\sqrt{2})/2 ( 1 + 2 ) /2 limit, while the local maxima reach ≈ 1.42 \approx1.42 ≈ 1.42 but remain well below 2.
Figure 5. Ratio d F B S / L P d_{\mathrm{FBS}}/\mathrm{LP} d FBS / LP for the all-ascending case a = s a=s a = s with arbitrary n n n (dense for n ≤ 200 n\leq200 n ≤ 200 , sparse up to n = 75,000 n=75{,}000 n = 75 , 000 ). The ratio oscillates but stays bounded; local minima near powers of two approach the ( 1 + 2 ) / 2 (1+\sqrt{2})/2 ( 1 + 2 ) /2 limit (dashed red line).
Synthetic baseline comparisons
We generate synthetic instances with n ∈ { 100 , 1000 , 5000 } n \in\{100,1000,5000\} n ∈ { 100 , 1000 , 5000 } and score–attribute correlation corr ∈ { 0 , 0.5 , 1 } \operatorname{corr}\in\{0,0.5,1\} corr ∈ { 0 , 0.5 , 1 } , averaging over 5 repetitions. FBS consistently traces a Pareto front that dominates all baselines: it achieves the same fairness at lower cost, or higher fairness at the same cost. The gap is most pronounced at high correlation (corr = 1), where the discretization baselines pay a substantial cost to reach even moderate ϕ \phi ϕ values, while FBS reaches ϕ = 1 \phi=1 ϕ = 1 along a smooth, efficient trade-off curve. DetConstSort with more groups (G = 5 , 10 G=5,10 G = 5 , 10 ) reaches higher ϕ \phi ϕ than with fewer groups, but at a cost that exceeds FBS for the same fairness level. FA*IR’s one-sided minimum-representation constraint provides only a modest fairness improvement, as it addresses group underrepresentation but not the symmetric balance that ϕ \phi ϕ measures. These results confirm that discretizing a continuous attribute incurs an inherent information loss: group-fair methods can only balance across bin boundaries, while FBS directly optimises the continuous fairness measure at the pairwise level.
Figure 6. FBS vs. discretization baselines on synthetic data with corr = 0.5, n ∈ { 100 , 1000 , 5000 } n \in\{100, 1000, 5000\} n ∈ { 100 , 1000 , 5000 } . Each panel shows achieved fairness ϕ \phi ϕ (x x x -axis) vs. weighted Kemeny distance (y y y -axis). FBS (blue line) traces a Pareto front by sweeping ψ \psi ψ ; baselines are shown as individual points for each number of groups G G G . FBS dominates all baselines.
Figure 7. FBS vs. discretization baselines on synthetic data with corr = 0 (uncorrelated scores and attributes), n ∈ { 100 , 1000 , 5000 } n \in\{100, 1000, 5000\} n ∈ { 100 , 1000 , 5000 } .
Figure 8. FBS vs. discretization baselines on synthetic data with corr = 1 (perfectly correlated scores and attributes), n ∈ { 100 , 1000 , 5000 } n \in\{100, 1000, 5000\} n ∈ { 100 , 1000 , 5000 } .
Continuous-fairness repair baselines
The discretization baselines of Figure 2 enforce group constraints on a binned attribute. A different route to a fair ranking is to repair the score itself so that it no longer depends on the attribute, and then sort by the repaired score. We evaluate two such repair-then-sort baselines on the same data and axes as Figure 2 : achieved fairness ϕ \phi ϕ on the original continuous attribute, and weighted Kemeny distance from r s r_s r s .
Wasserstein repair. Following the geometric repair of [11 ] , we bin the attribute into G ∈ { 2 , 3 , 5 , 10 } G \in\{2, 3, 5, 10\} G ∈ { 2 , 3 , 5 , 10 } equal-frequency groups and move the score distribution of each group towards a common target, the pointwise median of the groups’ quantile functions: an item at quantile q q q of its group receives the score ( 1 − λ ) s + λ F − 1 ( q ) (1-\lambda)s+\lambda F^{-1}(q) ( 1 − λ ) s + λ F − 1 ( q ) , where F − 1 F^{-1} F − 1 is the target quantile function and λ ∈ { 0.25 , 0.5 , 0.75 , 1 } \lambda\in\{0.25, 0.5, 0.75, 1\} λ ∈ { 0.25 , 0.5 , 0.75 , 1 } is the repair strength (λ = 0 \lambda=0 λ = 0 leaves r s r_s r s unchanged, λ = 1 \lambda=1 λ = 1 gives every group the same score distribution). Items are then sorted by the repaired score.
Residual repair. In the spirit of [19 ] , this variant works on the continuous attribute directly. We estimate the conditional mean of the score given the attribute, f ^ ( a ) \hat{f}(a) f ^ ( a ) , by a centred moving average of the scores over the items sorted by attribute (window of max ( 11 , ⌊ n / 50 ⌋ ) \max(11,\lfloor n/50\rfloor) max ( 11 , ⌊ n /50 ⌋) items), and compute the residual s − f ^ ( a ) s-\hat{f}(a) s − f ^ ( a ) . Items are sorted by ( 1 − λ ) s ~ + λ e ~ (1-\lambda)\tilde{s}+\lambda\tilde{e} ( 1 − λ ) s ~ + λ e ~ , where s ~ \tilde{s} s ~ and e ~ \tilde{e} e ~ are the standardized score and residual and λ \lambda λ takes the same values as above; λ = 1 \lambda=1 λ = 1 ranks by the residual alone, i.e. removes the local influence of the attribute on the score.
Figure 9 overlays the two families on the curves of Figure 2 . For each repair ranking whose fairness lies within the range spanned by FBS, we compute the ratio between its cost and the cost of FBS at the same fairness, obtained by linear interpolation of the FBS curve; a ratio above one means that FBS reaches the same fairness at lower cost. Table 2 reports, for each family and dataset, the fairest ranking it produces and the median and maximum ratio. FBS is cheaper at every matched point on all four datasets. The Wasserstein repair comes closest (smallest ratio 1.05, on Law School; median ratios between 1.3 and 2.1 outside German Credit); the residual repair pays 1.4 to 2.6 times the FBS cost on COMPAS and Communities and far more on Law School, where removing the influence of the attribute reorders a large part of the list. The large ratios on German Credit reflect its near-fair starting point (ϕ 0 = 0.98 \phi_0=0.98 ϕ 0 = 0.98 ), where FBS reaches ϕ = 1 \phi=1 ϕ = 1 at a cost of about 10 − 4 10^{-4} 1 0 − 4 .
Figure 9. FBS vs. repair-then-sort baselines on the real datasets; axes as in Figure 2. Dashed lines: Wasserstein repair for G ∈ { 2 , 3 , 5 , 10 } G \in\{2, 3, 5, 10\} G ∈ { 2 , 3 , 5 , 10 } , sweeping the strength λ \lambda λ ; dotted line with crosses: residual repair, sweeping λ \lambda λ ; the discretization baselines of Figure 2 are shown as points for reference. Each panel shows the rankings at least as fair as r s r_s r s ; on German Credit, three of the four residual-repair rankings are less fair than r s r_s r s , since the repair removes the influence of the attribute on the score rather than targeting ϕ \phi ϕ , and are omitted. On Law School the y y y -axis is cut at three times the largest cost of the other methods; the residual repair continues beyond it, up to a cost of 0.20 at ϕ = 1 \phi=1 ϕ = 1 (Table 2 ).
Table 2. Repair-then-sort baselines vs. FBS at matched fairness. “ϕ \phi ϕ reached” is the fairest ranking the family produces; the cost ratio is the repair cost divided by the FBS cost at the same ϕ \phi ϕ , with median and maximum taken over the family’s rankings within the fairness range of FBS.
Ranking quality beyond the Kemeny distance: NDCG and FBS-NDCG
The weighted Kemeny distance charges every inverted pair by its score gap, wherever the pair sits in the list. NDCG with the original score as relevance is a second utility measure that weighs the top of the list more heavily: r s r_s r s is the ideal ranking and has NDCG equal to one, the relevance of an item is its score (linear gain), and position p p p is discounted by d p = 1 / log 2 ( p + 1 ) d_p=1/\log_2(p+1) d p = 1/ log 2 ( p + 1 ) . We report NDCG over the full list and truncated at the top 10 and top 100 positions.
FBS as a cost-agnostic framework. At each step, FBS performs the cheapest fairness-improving adjacent swap under a per-swap cost, and any utility whose change under one adjacent swap is cheap to evaluate can serve as this cost. Algorithm 2 uses the score gap ∣ S [ k ] − S [ k + 1 ] ∣ \lvert S[k] - S[k + 1]\rvert ∣ S [ k ] − S [ k + 1 ]∣ of the two items as the cost and minimizes the weighted Kemeny distance, with the guarantees of Theorem 1 and Proposition 2. Replacing the key of the heap by the decrease of DCG caused by the swap, ( S [ k ] − S [ k + 1 ] ) ( δ k − δ k + 1 ) (S[k] - S[k + 1])(\delta_k - \delta_{k+1}) ( S [ k ] − S [ k + 1 ]) ( δ k − δ k + 1 ) , makes swaps near the top of the list expensive, so the greedy protects the head of the list; we call this variant FBS-NDCG. Both variants perform exactly K ∗ K^* K ∗ majority-sign swaps and reach the same fairness; they differ only in which swaps they choose, that is, in where the displacement is spent. FBS-NDCG is a greedy heuristic for NDCG.
Table 3 reports NDCG at matched fairness. For each dataset we take the discretization baseline of Figure 2 with the highest achieved fairness (DetConstSort with G = 10 G = 10 G = 10 ; G = 3 G = 3 G = 3 on German Credit) and evaluate FBS and FBS-NDCG at the same ϕ \phi ϕ by linear interpolation along their ψ \psi ψ -sweeps (ψ \psi ψ from 0 to 1 in steps of 0.1). As a reference we also report a uniformly random permutation, averaged over 10 draws: it has ϕ ≈ 1 \phi\approx1 ϕ ≈ 1 but is otherwise arbitrary, so its NDCG calibrates the scale. Two observations follow. First, fair rankings remain practical: the random fair ranking loses most of its top-heavy utility (NDCG@10 between 0.18 and 0.78), while FBS keeps NDCG@10 between 0.82 and 1.00 and full-list NDCG at or above 0.98 on every dataset. Second, FBS keeps the full-list displacement small but gives up some top-k k k utility, most visibly on the datasets with coarse scores (COMPAS, Law School), where it falls below the best baseline on NDCG@10 and NDCG@100. This is exactly the regime where FBS-NDCG, by pricing swaps near the top higher, recovers NDCG@10 and NDCG@100 of 1.00 at the same fairness, matching or exceeding the best baseline on every dataset and metric. Targeting top-k k k utility therefore requires only the NDCG cost inside the same routine.
Table 3. NDCG at matched fairness, with the original score as relevance (NDCG = 1 for r s r_s r s ). For each dataset, the matched ϕ \phi ϕ is the highest fairness reached by a discretization baseline (DetConstSort with G = 10 G = 10 G = 10 , or G = 3 G = 3 G = 3 on German Credit); “Best baseline” is that baseline, FBS and FBS-NDCG are evaluated at the same ϕ \phi ϕ , and “Random fair” is a uniformly random permutation (ϕ ≈ 1 \phi\approx1 ϕ ≈ 1 ), averaged over 10 draws.
Other measures of dependence between position and attribute
CPP measures monotone dependence between position and attribute (Appendix B). To check whether FBS also reduces dependence as measured by other statistics, we evaluate four measures between the position of an item in the ranking and its attribute value, all of which are zero under independence: the absolute Spearman correlation; distance correlation [35 ] ; the Hilbert–Schmidt independence criterion (HSIC) [15 ] with Gaussian kernels whose bandwidth is the median pairwise distance, normalised by the geometric mean of the two self-HSIC terms so that it lies in [ 0 , 1 ] [0, 1] [ 0 , 1 ] ; and a positional discrepancy, the largest one-dimensional Wasserstein distance between the attribute distributions of the top, middle and bottom thirds of the ranking, divided by the standard deviation of the attribute. The last three also detect non-monotone dependence. Distance correlation and HSIC are quadratic in n n n , so on Law School (n = 18,692 n = 18{,}692 n = 18 , 692 ) they are computed on one fixed random subsample of 8,000 items, the same for every ranking of that dataset; the other two measures use all items.
Table 4 reports the four measures for the score ranking r s r_s r s and for the FBS ranking at full fairness (ψ = 1 \psi= 1 ψ = 1 ). On the three datasets whose initial ranking is far from fair (Communities, COMPAS, Law School), FBS reduces all four measures substantially, by factors between 1.6 and 11; on German Credit the four measures are already near zero at r s r_s r s and change only negligibly. FBS therefore improves fairness as measured by these statistics as well. Some non-monotone dependence remains at ψ = 1 \psi= 1 ψ = 1 (distance correlation and HSIC stay above zero), consistent with CPP measuring monotone dependence.
Table 4. Dependence between rank position and attribute for the score ranking r s r_s r s (left of each arrow) and for the FBS ranking at ψ = 1 \psi= 1 ψ = 1 (right); lower means less dependence. Distance correlation and HSIC on Law School are computed on a fixed subsample of 8,000 items.
Hardware, Software and Code
All experiments were run on a single machine with the following specifications:
Hardware: Apple MacBook Pro with Apple M1 Pro chip, 8-core CPU, 16 GB unified memory.
OS: macOS 15.6.1 (Sequoia).
Code: The source code to run FBS and to reproduce the experiments is publicly available at https://github.com/Ambress92/FairBubbleSort.