Fair Rank Aggregation
Authors: Diptarka Chakraborty
Syamantak Das
Arindam Khan
Aditya Subramanian
Venue: NeurIPS 2022 Accept (2022)
Keywords: Fairness
Ranking
Rank Aggregation
Kendall-Tau Metric
Algorithms and Theory
Approximation Algorithms
Combinatorial Optimization

Abstract: Ranking algorithms find extensive usage in diverse areas such as web search, employment, college
    admission, voting, etc.  The related rank aggregation problem deals with combining multiple
    rankings into a single aggregate ranking.  However, algorithms for both these problems might be
    biased against some individuals or groups due to implicit prejudice or marginalization in the
    historical data.  We study ranking and rank aggregation problems from a fairness or diversity
    perspective, where the candidates (to be ranked) may belong to different groups and each group
    should have a fair representation in the final ranking. We allow the designer to set the
    parameters that define fair representation. These parameters specify the allowed range of the
    number of candidates from a particular group in the top-$k$ positions of the ranking.  Given any
    ranking, we provide a fast and exact algorithm for finding the closest fair ranking for the
    Kendall tau metric under {\em strong fairness}, i.e., when the final ranking is fair for all
    values of $k$. We also provide an exact algorithm for finding the closest fair ranking for the
    Ulam metric under strong fairness when there are only $O(1)$ number of groups.  Our
    algorithms are simple, fast, and might be extendable to other relevant metrics. We also give a
    novel  meta-algorithm for the general rank aggregation problem under the fairness framework.
    Surprisingly, this meta-algorithm works for any generalized mean objective (including center and
    median problems) and any fairness criteria. As a byproduct, we obtain 3-approximation algorithms
    for both center and median problems, under both Kendall tau and Ulam metrics. Furthermore, using
    sophisticated techniques we obtain a $(3-\varepsilon)$-approximation algorithm, for a constant
    $\varepsilon>0$,  for the Ulam metric under strong fairness.

Fair Rank Aggregation
Diptarka Chakraborty
Syamantak Das
School of Computing
Department Computer Science and Engineering Indraprastha Institute of Information Technology, Delhi syamantak@iiit.co
National University of Singapore diptarka@comp... nus edu edu.sg
Arindam Khan
Department of Computer Science and Automation
Indian Institute of Science, Bengaluru
i indakhan@iiscc.ae
Aditya Subramanian
Department of Computer Science and Automation Indian Institute of Science, Bengaluru adi adityasubram@1 iisciiiscc........ ac. in
Abstract
Ranking algorithms find extensive usage in diverse areas such web search, employment, college admission, voting, etc. The related rank aggregation problem deals with combining multiple rankings into single aggregate ranking. However, algorithms for both these problems might be biased against some individuals or groups due to implicit prejudice marginalization in the historical data. We study ranking and rank aggregation problems from a fairness or diversity perspective, where the candidates (to be ranked) may belong different groups and each group should have a fair representation in the final ranking. We allow the designer to set the parameters that define fair representation. These parameters specify the allowed range of the number of candidates from particular group in the top-k positions of the ranking. Given any ranking, we provide fast and exact algorithm for finding the closest fair ranking for the Kendall tau metric under strong fairness, i.e., when the final ranking is fair for all values of We also provide an exact algorithm for finding the closest fair ranking for the Ulam metric under strong faimesss when there are only O(1) number of groups. Our algorithms are simple, fast, and might be extendable to other relevant metrics. We also give novel meta-algorithm for the general rank aggregation problem under the faimesss framework. Surprisingly, this meta-algorithm works for any generalized mean objective (including center and median problems) and any fairness criteria. As a byproduct, we obtain 3- approximation algorithms for both center and median problems, under both Kendall tau and Ulam metrics. Furthermore, using sophisticated techniques we obtain a (3 -)aaprroximation algorithm, for constant 0, for the Ulam metric under strong faimess.
Introduction
Ranking a set of candidates or items is ubiquitous problem arising in diverse areas ranging from social choice theory (BCE+1 16) to information retrieval (Har92). Given a set of d candidates and set of different, potentially conflicting, rankings of these candidates, one fundamental task is to
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

determine single ranking that best summarizes the preference orders in the individual rankings. This summarizing task, popularly termed rank aggregation. has been widely studied from a computational viewpoint over the last two decades [DKNSO] FKS03 GL ASCPX13] Most well- rank aggregation paradigms are median rank aggregation (or simply rank aggregation) [Kem59] You88 YL.78, DKNSOT] and maximum rank aggregation [BBGHT5 BBD09 Pop07], which are based on finding the median and center of the given set of rankings, respectively.
Recently, fairness and diversity have become a natural prerequisite for ranking algorithms where individuals are rated for access to goods and services or ranked for seeking facilities in education (e.g.. obtaining scholarship or admission), employment (e.g.. hiring or promotion in a job), medical (e.g.. triage during pandemic). or economic opportunities (e.g. loan lending). Some concrete examples include university admissions through affirmative action in the USA [Des05] or the reservation system in jobs in India [Bor10], where we want rankings to be fair to mitigate the prevalent disparities due to historical marginalization. Rankings not being fair may risk promoting extreme ideology [CHRGI6] or certain stereotypes about doninnttingmarrgnnalizedd communities based on sensitive attributes like gender or race [KMM13 BCZ 16). There has been a series of works on fair ranking algorithms, see [ZBC 17 AJSDI9 C9s
GSB21 GDL21 PPM 22 ZYS21] and the references therein.
A substantial literature on algorithmic faimess focuses on group fairness to facilitate demographic parity [DHP* 12) or equal opportunity [HPSI6]: typically this is done by imposing fairesss con- straints which require that top-k positions in the ranking contain enough candidates from protected groups that are typically underrepresented due to prevalent discrimination (c.g., due to gender, caste, age, race, sex, etc.). In many countries, group fairness constraints are being enforced by legal norms [Eur USD]. For example, in Spain 40% of candidates for elections in large voting districts must be women [Ver10), in India 10% of the total recruitment for civil posts and services in government are reserved for people from Economically Weaker Society (EWS) [Sin etc.
In this paper, we study group fairness, more specifically proportional faimess (sometimes also referred to as p-fairness (BCPV96). Inspired by the Disparate Impact doctrine, this notion of fairness mandates that the output of an algorithm must contain a fair representation of each of the "protected classes' in the population. In the context of ranking, the set of candidates is considered to be partitioned into groups G1. Gg...., Gg. For each group G,, i E [g], we have two parameters og E [0, 11,83 3: E 1]. A ranking क of the set of items is called proportionally fair if for every position k E (1,2..... n) and for every group G, the following two properties are satisfied: (a) Minority Protection: The number of items from group G., which are in the top-k positions T (1), T m())..... T (k)), is at least (a: kJ. and (b) Restricted Dominance: The number of items from group G., which are in the top-k positions π ((), =(k), is at most [3,- k].
To compare different rankings several distance functions have been considered defined on the set of permutations/rankingss. such as Kendall tau distance [Ken38] DG77 Kem59 You88 YL78
DKNSOI ACNO8 KMS07 KV10) (also called Kemeny distance in case of rank aggregation), Ulam
distance AD99 CMSO1 CK06 AK1O ANTO NSS17 BS19 CDK2T CGI2T] Spearman footrule
distance Spee04] Spe06, DG77 DKNSO1
KV10 BBGH15), etc. Among these, Kendall tau dis- tance perhaps the most common measure used ranking as it is the only known measure to simultaneously satisfy several required properties such as neutrality, consistency, and the extended Condorcet property (Kem59, You88). The Ulam metric is another widely-used measure in practice as it is also simpler variant of the general edit distance metric which finds numerous applica- tions in computational biology, DNA storage system, speech recognition, classification, etc. (e.g.. see (CMSOT CDK21] CGJ2T)).
One natural computational question related to fairness in ranking is, given a ranking, how find its closest fair ranking under p-fairness. Celis et al. [CSVI8] considered this problem and gave exact and approximation algorithms under several ranking metrics such as discounted cumulative gain (DCG), Spearman footrule, and Bradley-Terry. However, their algorithms do not extend to Kendall tau and Ulam metric, two of the most commonly used ranking metrics.
Fair rank aggregation is relatively less studied. Recently, Kulman et al. [KR20] initiated the study of fair rank aggregation under Kendall tau metric. However, their fairness notion is based on top-k statistical parity and pairwise statistical parity. These notions are quite restricted. For example, their results only hold for binary protected attributes (i.e.. g 2) and and does not satisfy p-faimesss. Informally, pairwise statistical parity considers pairs of items from different groups in an aggregated manner and does not take into account the actual rank of the items in the final ranking. See (WSR222
2

---

for an example on why the fairness notion in [KR20] does not satisfy p-fairness. In fact, as p-faimesss satisfies statistical parity for all top k-positions in the ranking. it is much stronger notion compared to statistical parity. Thus achieving paiiiesss is significantly more challenging problem.
1.1 Our Contributions.
Our first main contribution an exact algorithm for the closest fair ranking (CFR) problem under proportional fairness (see Definition 2.4 for Kendall tau and Ulam metrics. For the Kendall tau metric, we give the first exuct algorithm for the closest fair ranking problem (Theorem 3.4). Our algorithm is simple and based on a greedy strategy; however, the analysis is delicate. It exploits the following interesting and perhaps surprising fact. Under the Kendall tau metric, given a fixed (possibly unfair) ranking n, there exists closest fair ranking n to such that for every group & E [g]. the relative ordering of elements in G, remains unaltered in n' compared to π (Claim 3.3). Then, for the Ulam metric, we give a polynomial time dynamic programming algorithm for the closest fair ranking problem when the number of groups g is a constant (Theorem 3. 3.10p. In practice, the number of protected classes is relatively few, and hence result gives an efficient algorithm for such cases.
Our second significant contribution is the study of rank aggregation problem under generalized notion of proportional fairness. One of our main contributions is to develop novel algorithmic framework for the fair rank aggregation that solves wide variety of rank aggregation objectives satisfying such generic fairness constraints. An essential takeaway of our work is that a set of potentially biased rankings can be aggregated into a fair ranking with only small loss in the 'quality' of the ranking. We study q-mean Fair Rank Aggregation (FRA), where given a set of rankings T1, ........ Tu. (dis)similarity measure (or distance function) p between two rankings, and any q 2 1, the task is to determine a fair ranking a that minimizes the generalized mean objective: (Ei= p(T;; 0)))// We would like to emphasize that in general, g-mean objective captures two classical data aggregation tasks: One is median which asks to minimize the sum of distances (i.e., q 1) and another is center which asks to minimize the maximum distance to the input points (i.e., x.).
We show generic reductions of the g-mean Fair Rank Aggregation (FRA) to the problem of de- termining the closest fair ranking (CFR) to a given ranking. More specifically, we show that any c-approximation algorithm for the closest fair ranking problem can be utilized as a blackbox to give a (c + 2)-approximation to the FRA for any q 2 (Theorem 4.3). This result is oblivious to the specifics of the (dis)similarity measure and only requires the measure to be metric. Using the exact algorithms for the CFR for the Kendall tau, Spearman footrule, and Ulam metrics (for constantly many groups), thus obtain 3-approximation algorithms for the FRA problem under these three (dis)similarity measures, respectively. Further, we provide yet another simple algorithm that even breaks below 3-factor for the Ulam metric. For q 1, by combining the above-stated 3-approximation algorithm with an additional procedure, we achieve a (3 - -aaaprooximttoon factor (for some & > 0) for the FRA under the Ulam, for constantly many groups (Theorem 4.1 We also provide another reduction from FRA to one rank aggregation computation (without fairness) and a CFR computation (Theormm 4.8p, and a corollary get an Odd log d + ni-de-time algorithm for Spearman footrule when q = I (Corollary 4.10). We summarize our main results in Table
Problem
Metric
#Grropss
Approx Ratio
Runtime O
Reference
CFR
Kendall tau
Arbitrary
Exact
Theorem 3.4
Ulam
Constant
Exact
Old
Theorem 3.10
Spearman footrule
Arbitrary
Exact
Old log d)
[CSVI8
FRA
Kendall tau
Arbitrary
3
O'nd' + n n'dlog d)
Corollary 4.5
Ulam
Constant
3
O(nd + n² d' d)
Corollary 4.7
Ulam (q = 1)
Constant
3 - E
poly(n, d)
Theorem 4.
Spearman footrule
Arbitrary
3
O(d' log d + n²d + +nd
Corollary 4. 110
Comparison with concurrent work. Independently and concurrently to our work, Wei et al. [WISR22] considers the fair ranking problem under a setting that is closely related to ours. However, the fairness criteria in their work are much more restrictive compared to ours as follows.
3

---

Their algorithms for CFR are only designed for a special case of our formulation where for each group G; and any position k in the output ranking, a, = 3, = p(t). where p(i) denotes the proportion of group G; in the entire population. Further, under the Kendall tau metric, they give a polynomial time exact algorithm for CFR only for the special case of binary groups (g = 2). They also give additional algorithms for multiple groups an exact algorithm that works in time exponential in the number of groups and a polynomial time 2-approximation. In contrast, we fully resolve the CFR problem under the Kendall tau metric by giving simple polynomial time algorithm for the case of multiple groups and any arbitrary bounds on a and B, for each group G.. Further, we give the first results for CFR and FRA under the Ulam metric as well.
1.2 Other related work
Recent years have witnessed growing concern over ML algorithms or, more broadly, automated decision- decision-making processes being biased [BHNI7 MMS 21]. This bias or unfairmess might stem both from implicit bias in the historical dataset or from prejudices of human agents who are responsible for generating part of the input. Thus fair algorithms have received recent attention in machine learning and related communities. In partieular, the notion of group fairness have been studied in classifica- tion [HV19)] clustering [CKLV17), correlation clustering [AFKM20], resource allocation [PKL21]] online learning [PGNN20], matroids and matchings [CKLVI9]. Specially, fair clustering problem is closely related to our problem. Fair rank aggregation can be considered as the fair I-clustering BIO 19 for
problem where the input set is a set of rankings. See [HVV]9 CFLM19 BCFNI9
more related work on fair clustering.
2 Preliminaries
Notations. For any n E N. let [n] denote the set (1, We refer to the set of all permu- tations/rankings over [d] by Sa. Throughout this paper we consider any permutation π E Sa as a sequence of numbers 01, a2....,. dd such that (i)
For any two x, y E [d] and a permutation π E Sz. we use the notation I <x y to denote that the rank of x is less than that of y in æT For any subset / = {ir < i2 <.... i S [d]. let (() be the sequence T(1)). (12)....... ..... π (ēz-) (which is essentially subsequence of the sequence represented by σ). When clear from the context, we use (I] also to denote the set of elements in the sequence ((1),, aT (12)..... (tr)). For any k E [d] and a permutation E Sa. we refer to π ([k) as the k-length prefix of T.. For any prefix P. let Pl denote the length of that prefix. For any two prefixes P1, P2 of a given string, we use Pi S P2 to denote |P| < PP2|-
a, and we say that the rank of a,
Distance measures on rankings. There are different distance functions being considered to measure the dissimilarity between any two rankings/permuaaionn. Among them, perhaps the most commonly used one is the Kendall tau distance.
Definition 2.1 (Kendall tau distance). Given two permutations T1, E Sa, the Kendall tau distance between them, denoted by K((Ti, n2), is the number of pairwise disagreements between कı and T2, i.e.,
K(T11 22) ((a, b) E [d] x [d] a <x, b but b <x, at|.
Another important distance measure is the aeearman (aka Spearman' rho) which is essen- tially the ( f--rrrm between two permutations.
Definition 2.2 (Spearman footrule distance). Given two permutations æT, n2 E Sd, the Spearman footrule distance between them is defined as F(m1, T2) == Evejd (1) (1))
Another interesting distance measure is the Ulam distance which counts the minimum number of character move operations between two permutations (AD99). This definition is motivated by the classical edit distance that is used to measure the dissimilarity between two strings. A character move operation in permutation can be thought of as "picking up" a character from its position and then "inserting" that character into a different position
'One may also consider one deletion and one insertion operation instead of a character move, and define the Ulam distance accordingly in [CS01].

---

Definition 2.3 (Ulam distance). Given two permutations N1, E Sg, the Ulam distance between them, denoted by ((11,TT2) .T2) is the minimum number of character move operations that is needed to transform #i into 72.
Alternately, the Ulam distance between Ti n2 can be defined as d LLCS( ( T2)l where [LCS(M; mT)] denotes the length of longest common subsequence between the sequences m and 12.
Fair rankings. We are given a set C' of d candidates, which are partitioned into g groups. We call ranking (of these candidates) fair all sufficiently large prefixes of have certain proportion of representatives from each group. Formally.
Definition 2.4 (( fair ranking). Consider a set C candidates partitioned into g groups G Gg. and (a1,..... ag) [0. 1| B = ($1..... (gy) [0, 1|" k [d]. A ranking π E Sa is said to be (ā, 33-k-fairr if for any prefix P of length least k. of π and each group [g]. there are at least [a |P]] and at most [3 P|] elements from the group G₁ in P. icc.
pprefix PIPplkk:
VeE(a)- la,
|P]] < |PnG - [3, [P]].
We also define weak fairness notion that preserves the proportionate representation only for fixed k-length prefix.
Definition 2.5 ((ā, 3)- k-fair ranking). Consider a set C of d candidates partitioned into groups Gi...., . G. and ā (a1...., ag) E [0, 1|9, 3 ($1..... ..,) E [0, 1]9, [d]. A ranking
Sy is said to be (a, 3)-weak k-fair if for the k-length prefix P of i and each group E [g]. there are at least [ay &- and most [3, k) elements from the group G, in i.c.,
Las kl S P S [B k]. ViEls
Note, an (ā, fair- ranking is also (a, 3e-k k-fair, but the converse need not be true. We would like to emphasize that all the results presented in this paper hold for both (a, f)-k-fasssssss and (ar -wekk k-faireess
3 Closest Fair Ranking
In this section, we consider the problem of computing the closest fair ranking of a given input ranking. Below formally define the problem.
Definition 3.1 (Closest fair ranking problem). Consider a metric space (Sa, p) for a d E N. Given ranking æ Sa and ā, f [o, 1 for some E N, E [d], the objective of the closest fair ranking problem (resp. closest weak fair ranking problem) is to find (ā, f ranking (resp. (a. -eek f-irir ranking) x² E Sa that minimizes the distance p(π,
Unless stated explicitly, we consider the notion of (ā. -3-k-fairmess (as opposed to the weak notion) in all the results presented in this section. The following algorithm assumes that fair ranking exists, and finds one in this case. If such ranking does not exist, then the procedure might return an arbitrary ranking. However,
possible to check in linear time whether a given ranking fair or not. Hence, we can correctly output a solution if one exists, and return 'no solution' otherwise.
3.1 Closest fair ranking under Kendall tau metric
Closest weak fair ranking. We first show that we can compute closest weak fair ranking under the Kendall tau metric exactly in linear time.
Theorem 3.2. There exists a linear time algorithm that, given a ranking π E Sa. a partition of [d into g groups Gt,... for some g E M. and ā = (a1,...., ..))))))))))).... E 0,1 3 == (B,...,, E [0, 1J9, l E [d]. oulputs closest (ā, 3))- k-fair ranking under the Kendall tau distance.
Let us first describe the algorithm. Our algorithm follows simple greedy strategy. For each group Ge it picks the top [a,k] elements according to the input ranking т, and add them in set P. If P contains i elements, then we are done. Otherwise, we iterate over the remaining elements (in the increasing order of rank by π) and add them in P as long for each group G., [ G. < [3,
5

---

(each group has at most [[8,k] elements in P) until the size of P becomes exactly k. Then we use the relative ordering of the elements P as in the imput ranking π and make it the k-length prefix of the output ranking a. Fill the last d - k positions of by the remaining elements ([d) \ P) by following their relative ordering as in the input x. See Algorithm iin the appendix for the pseudocode of the algorithm.
By the construction of set P. the end, for each group Gū, La,k] < | < [3, Since we use the elements of P in the k-length prefix of the output ranking 0, a is an (ā, 3weak k-fair ranking. For the running time, a straightforward implementation our algorithms takes ((d) time. only remains to argue that is a closest (ā. 3)-weak k--air ranking to the input æT. To show that, we use the following key observation.
Claim 3.3. Under the Kendall tau distance, there always exists a closest (ūx, B)- ---fir ranking ni such that, for each group G2 (i E (g)). for any two elements a + b Go a Sx- b if and only if a < b.
We say that a ranking n" satisfying the above property (i.c., for each group G., E [g]. for any two elements a * b G., a <x b if and only if a <a 6), preserves intra-group orderings. This is because for elements of any group, their ordering in π is the same as their ordering in æ.
We want to highlight that the above claim holds for both the notions of fairness we consider. We defer the proof of the above claim and how we use to conclude the proof of Theorem 3.2 to the appendix.
Extension to general fairness notion. Previously, we provide an algorithm that outputs a weak fair ranking (see Definition 2.3 for the definition of weak fairness) closest to the input. Now, present an algorithm that outputs a closest fair ranking (according to Definition 2.4
Theorem 3.4. There exists an (dP) time algorithm that, given ranking т E Sa. a partition of [d] into g groups Gi...., for some g E N, and ā (ai...., ag)) E [0, 1|s, B = (BI..... 3g) E [0, 119, k E [d], outputs a closest (ä. B-k--fiir ranking under the Kendall tau distance.
The main challenge with this stronger fairness notion is that now we need satisfy the fairness criteria for all the prefixes not just fixed k-length prefix as in case of weak fairness. Surprisingly, we show that under the Kendall tau metrie, by iteratively applying the algorithm for the closest weak fair ranking (Algorithm I as a black-box, over the prefixes of decreasing length, we can construct a closest fair ranking (not just closest weak fair ranking). Here, it is worth noting that at any iteration the input to Algorithm i prefix of π which may not be permutation. However, Algorithm [ only treats the input as a sequence of numbers (not really as a permutation). See Algorithm in the appendix for formal description of the algorithm.
Note that, since we iteratively apply Algorithm a prefix of æ (not the whole sequence represented by T), it is not even clear whether the algorithm finally outputs a fair ranking (assuming it exists). Below we first argue that if there exists fair ranking, then the output must be fair ranking. Next, we establish that a is indeed a closest fair ranking to π.
Let T- be a closest fair ranking closest fair ranking). We show that the output a = T², We start the argument by considering any two prefixes of length kı and k2, where 22- < k1. We argue that k and ke-length prefixes of a and 'T" are the same. Since this holds for any k1 and l2 (with K1, 22 2 k), where k < k1, by using induction we can show that argument for the k and legllngthh prefixes (which is a key to prove the correctness of Theorem 3.4).
that preserves intra-group orderings (Claim 3.3 guarantees such
x². We defer the induction argument to the appendix and below provide the
For the sake of analysis, let us consider the following three permutations. Let ạ be the (ā, -eekk -farr ranking closest to n, output by Algorithm | Let के be the ranking output by Algorithm I when given the ke-length prefix of ạ (i.e., the sequence Tı (Ax)) [)) as input and is asked to output an (ā, ()) weak f ranking closest to Ty. Further, let n/. be the (ā, 3eekk k ranking closest to n, output by Algorithm[| In other words, T2 is the ranking produced by first applying Algorithm [] on x to make its k -lngthh prefix fair and then apply Algorithm D again on that output to make its ly-length prefix fair. Whereas, T2 is the ranking produced by directly applying Algorithm I on n to make its lengthh prefix fair.
From the definition it is not at all clear whether such a T2 even exists. The next claim argues about the existence of ranking 22.

---

Claim 3.5. there is a ranking n' such that its ky-length prefix P1 and ky-length prefix Pa satisfies that for each group G; (i E (g)), [acki] $ (P P G. [3, and [acka] S |P2 G. $ [3,,k]] then #2 exists.
It can further be shown that, Claim 3.6. The set of elements in T2 (k]l) is the same as that in I ((ka))
Claim 3.7. The set of elements in m2 (k2)) the same as that in ((2())
Claim 3.8. The set of elements in x (K1]) is the same as that in π2 (k1])-
Claim 3.9. The set of elements in x ([=2)) the same as that in T2 (k2]))
The proof of the above claims is in the appendix. We apply Claim 3.8 and Claim 3.9 complete the correctness of Agorithm@ which we defer to the appendix.
iteratively to
only remains to argue that the algorithm runs in time ((d). This is easy to see since the algorithm invokes at most d calls to the (dd) subroutine Algorithm
3.2 Closest fair ranking under Ulam metric
Theorem 3.10. There exists polynomial time dynamic programmiing based algorithm that finds (a, f)-k-fair ranking under Ulam metric when there are constant number of groups.
The proof of the lemma uses intricate dynamic program exploiting the connection between the Ulam distance with the Longest Common Subsequence problem. We defer the proof to the appendix.
Fair Rank Aggregation
We start this section by formally defining the fair rank aggregation problem. Then we will provide two meta-algorithms that approximate the fair aggregated ranking.
Definition 4.1 (q-mean Rank Aggregation). Consider metric space (Sa, p) for a d E N. Given an exponent parameter 9 E R. and a set S C Sy of n input rankings, the q-mean rank aggregation problem asks to find ranking Sa (not necessarily from S) that minimizes the objective function 1/9
Obj,(S,o) == (Eres P(T,, o)T)
Generalized mean g-mean objective functions are well-studied in the context of clustering (CMV. and division of goods [BKM22] We study it for the first time the context of rank aggregation. For q 1, the above problem is also referred to the median ranking problem or simply rank aggregation problem Kem59, You88 YL78) DKNSOI]. On the other hand, for oo, the problem also referred to as the center ranking problem maximum rank aggregation problem (BBGHI5] BBD09 Pop07]. Both these special cases are studied extensively in the literature with different distance measures, e.g., Kendall tau distance [DKNSO1] ACNO8 KMS07 Sch12 BBD09. Ulam distance (CDK21 BBGHT5 CGJ2T. Spearman footrule distance DKNSS1 BBGHT5)
In the fair rank aggregation problem, we want the output aggregated rank to satisfy certain fairness constraints. Throughout this section, for brevity, we use the term (weak) fair ranking instead of (a, (weak) k-fair ranking.
Definition 4.2 (q-mean Fair Rank Aggregation). Consider a metric space (Sa, p) for a d E N. Given an exponent parameter q R, and set S Sa of input rankings/permutations,, the q-mean (weak) fair rank aggregation problem asks to find a (weak) fair ranking a E Sa (not necessarily from S) that minimizes the objective function Obj, (S, o) (Enes p(T,, ()))////
is worth noting that in the above definition, the minimization is over the set of all the (weak) fair rankings in Sg. When clear from the context, drop weak and refer to it as the q-mean fair rank aggregation problem. Let o² be a (weak) fair ranking that minimizes Obj (S, then we call o* a q-mean fair aggregated rank of S. We refer to Obj, (S, o²) ) as OPT,
When q we refer the problem the fair median ranking problem or simply fair rank aggregation problem. When g = no, the objective function becomes Obj (S, a) max p(z, r), and we refer the problem as the fair center ranking problem.
7

---

Next, we present two meta algorithms that work for any values of and irrespective of weak or strong (i.e., general) fairness constraint. We will also assume q to be a constant.
4.1 First Meta Algorithm
Theorem 4.3. Consider any 2 1. Suppose there is a t(d))-imme c-approximation algorithm A.
for some e 2 1, for the closest fair ranking problem over the metric space (Sa. Then there exists a (c + 2)appproximation algorithm for the q-mean fair rank aggregation problem, that runs in O(n ((d) + n²² [(d) time where [(d) the time to compute ((T1, T22 for any 71, 52 Sa-
We devote this subsection to proving the above theorem. Let us start by describing the algorithm. It works follows: Given set S S Sa of rankings, it first computes e-approximate closest fair ranking a (for some с 2 1) for each π E S. Next, among these |S] fair rankings output the ranking o that minimizes Obj, (S, Let us denote the output ranking by a. See Algorithm 4 in the appendix for a more formal description.
It is straightforward where f(d) is the time to compute p( T2) ) for any T1, T2 E Sa and t(d) denotes the running time of the algorithm A. So it only remains to argue about the approximation factor of Algorithm 4 The following simple observation plays a pivotal role in establishing the approximation factor of Algorithm 4
verify that the running time of the above algorithm is O(n +(d) + n² n2 f(d).
Lemma 4.4. Given a set S C of rankings, let a² be an optimal q-mean fair aggregated rank S under a distance function p. Further, let ā be nearest neighbor (closest ranking) of a in S, and be a c-approximate closest fair ranking to n. for some c 2 1. Then VIT E ((T,ō) S (c+2) p(TT, o²).
We defer the proof of the above claim the appendix. Now,
the above lemma to show that the approximation factor of Algorithm 4 is c + 2. Let o² be an (arbitrary) optimal fair aggregate rank of S and be the output of Algorithm + The optimal value of the objective function is )9) Next, we show that Obj, S (c+ OPT.
OPT = =b), = (ETes p(T,,
1/9
1/9
Ep(m,orya)
(S,,(
Σ ((c+2) -(T = 2c
= (cc+2) OPT.
EE
TES
where the first inequality follows from Lemma 4.4
This concludes the proof of Theorem 4.3
Applications of Theorem 4.3 We have shown in Theorem 3.4 that the closest fair ranking problem for Kendall tau can be solved exactly in (dd²) time, i.e., the approximation ratio is 1. We also know from Kni66], that the Kendall tau distance between two permutations can be computed in Od d) time. This gives us that,
Corollary 4.5. For any 2 1. there exists an O(nd² + no d) time meta meta-algorithm that finds 3-approximate solution to the q-mean fair rank aggregation problem under the Kendall tau metric.
It is shown in (CSV18] that the closest fair ranking problem for Spearman footrule can be solved exactly in O(d log d) time, i.e., the approximation ratio is c 1. Since distance under Spearman footrule can be trivially computed in (dd we have that,
Corollary 4.6. For any 2 1, there exists an O(nd log d + n²d) time meta-algorithm that finds a 3-approximate solution to the q-mean fair rank aggregation problem under the Spearman footrule metric.
We have shown in Theorem 3.10 that for constant number of groups, the closest fair ranking problem for Ulam metric can be solved exactly in (2)+ time, i.e., the approximation ratio From (AD99 we know that Ulam distance between two permutations can be computed in O log d) time. This gives us that,
Corollary 4.7. For any q 2 1, there exists O(nd+ + n² log d) time aeta-algorithm, that finds a 3-approximate solution to the q-mean fair rank aggregation problem, under the Ulam metric.
We would like to emphasize that all the above results hold for any values of q 2 1. Hence, they are also true for the special case of the fair median problem (i.e., for q = 1) and the fair center problem (i.c., for q oo).
8

---

4.2 Second Meta Algorithm
Theorem 4.8. Consider any q 2 1. Suppose there is a t1 (n) time e₁ approoximatio algorithm A
for some 2 1 for q-mean rank aggregation problem: and a t2 (d) (im- cy-approximation algorithm for some C2 2 for the closest fair ranking problem over the metric space (Sa.P) p). Then there exists (c102 + + -2papproxiimation algorithm for the q-mean fair rank aggregation problem, that runs in (((1(n) + 12(d) + n² {(d) time where [(d) the time compute f(TT1 w2 for any R1, T2
Sa.
The algorithm works as follows: Given a S Sa of rankings, it first computes e1 -paproxxiatee aggregate rank n² Next, output ca-approximate closest fair ranking o, to n². See Algorithm 5 in the appendix for a more formal description.
is easy to see that the running time of the algorithm is (nt + (2 + n² f(d)), where f(d) the time compute p( σ)) for any म, Sa. i (n) denotes the running time of the algorithm Ai, and (2(d) denotes the running time of the algorithm A2. It now remains to argue about the approximation ratio of the above algorithm. We again make simple but crucial observation towards establishing the approximation ratio for Algorithm
Lemma 4.9. Given a set S S Sa of n rankings, let a* be an optimal q-mean fair aggregated rank of S under distance function p. Further, let x² be the ei -upproxximaee aggregate rank of S and ā be 02 c2-upproximate closest fair ranking to n², for some C 2 1. Then
Vx E S. S (c101 +1 02) p(T,
We defer the proof of this lemma to the appendix. Once we have this key lemma in place, the remaining proof Theorem 4.8 follows exactly as the proof of Theooee 4.3
The above algorithm can give similar approximation guarantees as Algorithm 4 but with potentially better running times depending on whether the rank aggregation problem is solved in faster way for the particular problem in consideration. For instance consider the case for Spearman footrule. It is known that the rank aggregation problem for Spearman footrule can be solved in (cd)) time ydBLN' 20). So, using this in conjunction with Algorithm we obtain the following result.
Corollary 4.10. For == there exists on (d3 log + n²d + nd?) time meta-algorithm, that finds a 3--aprrozimate solution the q-mean fair rank aggregation problem (i.e., the fair median problem) under Spearman footrule metric.
4.3 Breaking below 3-factor for Ulam
Theorem 4.11. For q 1, there exists a constant & O and a polynomial time algorithm that finds a (3 -ppproxmmaaee solution to the q-mean fair rank aggregation problem (i.e., the fair median problem), under the Ulam metric for constantly many groups.
We show the above result by designing an algorithm based on the relative ordering of the elements (as in the majority of the input rankings). Then the final output is the best of that output by this new algorithm and that produced by our first meta-algorithm. We argue that when the whole optimal objective value is distributed among only few elements, then the first meta-algorithm already achieves (3 50 -pparooxximaoonn. Otherwise, this relative ordering-basee approach will provide - --aaprroximttion The argument used is quite similar that used in [CDK2I] obtain better than 2- factor approximate median under the Ulam metric. We describe our algorithm along with the complete analysis in the appendix.
Conclusion
In this paper, we lay the theoretical framework for studying the closest fair ranking and fair rank aggregation problems while ensuring minority protection and restricted dominance. We first give a simple, practical, and exact algorithm for CFR under the Kendall tau metric; and polynomial time exact algorithm for CFR under the Ulam metric when there are constantly many groups. We then use such black box solution to CFR to design two novel meta-algorithms for FRA for general q-mean objective, which are valid under any metric. The approximation ratios of these meta algorithms depend on the approximation ratio of the CFR subroutine used by them. Lastly,

---

give (3 - -p)-oxiipo algorithm for FRA under the Ulam metric. which improves over our meta algorithm's approximation ratio for the same case. Achieving a similar (better than 3-factor) approximation bound for the Kendall tau or other metrics is an interesting open problem. Another set of intriguing open problems arise when there is overlap between the groups, i.e., when an element can belong to multiple groups.
It is still open whether exact algorithms exist for the the case when an element can belong (at most) two groups.
Acknowledgments. Diptarka Chakraborty was supported in part by MoE AcRF Tier 2 grant (WBS No. A-8000416-00-000 and an NUS ODPRT grant (WBS No. A-0008078-000000 Arindam Khan gratefully acknowledges the generous support due Pratiksha Trust Young Investigator Award, Google India Research Award, and Google ExploreCS Award.
References
[ACN08] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent informa- tion: Ranking and clustering. J. ACM, 55(5):23:1-23:27, 2008.
[AD99] David Aldous and Persi Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deif-Johansson theorem. Bulletin of the American Mathematical Society, 36(4):413-432 1999.
[AEKM20] Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Fair correlation clustering. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108, pages 4195-4205, 2020.
[AJSD19] Abolfazl Asudeh, HV Jagadish, Julia Stoyanovich, and Gautam Das. Designing fair ranking schemes. In SIGMOD International Conference on Management of Data, pages 1259-1276, 2019.
[AK10] Alexandr Andoni and Robert Krauthgamer. The computational hardness of estimating edit distance. SIAM J. Comput., 396)):33882229, 2010.
[AN10] Alexandr Andoni and Huy Nguyen. Near-optimal sublinear time algorithms for Ulam distance. In ACM-SIAM Symposium Discrete Algorithms (SODA), pages 76-86, 2010.
[ASCPX13] Hossein Azari Soufiani, William Chen, David Parkes, and Lirong Xia. Generalized method-or of-moments for rank aggregation. Advances in Neural Information Processing Systems (NewrIPS), pages 2706-27 2714, 2013.
[BBD09] Therese Biedl, Franz Brandenburg, and Xiaotie Deng. On the complexity of crossings in permutations. Discrete Mathematics, 309(7): 1813-12883 2009.
[BBGHI5]
Christian Bachmaier, Franz Brandenburg, Andreas Gleißner, and Andreas Hofmeier. On the hardness of maximum rank aggregation problems. Journal of Discrete Algo- rithms, 31:2-13, 2015.
|BCE* 16] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
[BCFN19] Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Advances in Neural Information Processing Systems (NeurIPS), pages 4955-4966, 2019.
[BCPV96] Sanjoy K Baruah, Neil K Cohen, Greg Plaxton, and Donald A Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600-625, 1996.
[BCZ+16] Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam Kalai. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. Advances in Neural Information Processing Systems (NeurIPS), 29, 2016.
10

---

[BHN17]
Moritz Hardt, and Arvind Narayanan. Fairness in machine leamning NeurIPS tutorial, 1:2, 2017.
Solon Barocas,
[BIO+ 19] Arturs Backurs. Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference on Machine Learning (ICML), volume 97, pages 405-413, 2019.
[BKM22] Siddharth Barman, Arindam Khan, and Amnb Maiti. Universal and tight online algorithms for generalized-meat welfare. In AAAI, pages 4793-4800, 2022.
[Bor10] Vani K Borooah. Social exclusion and jobs reservation in india. Economic and Political Weekly, pages 31-35, 2010.
[BS19] Mahdi Boroujeni and Saeed Seddighin. Improved MPC algorithms for edit distance and Ulam distance. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 31-40, 2019.
[Cas19] Carlos Castillo. Fairness and transparency in ranking. In ACM SIGIR Forum, vol- ume 52, pages 64-71, 2019.
[CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Approximating the median under the ulam metric. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 761-775, 2021.
[CFLM19] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In International Conference on Machine Learning (ICML), pages 1032-1041, 2019.
[CGJ21] Diptarka Chakraborty, Kshitij Gajjar, and Agastya Vibhuti Jha. Approximating the center ranking under ulam. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2021.
[CHRG16] Matthew Costello, James Hawdon, Thomas Ratliff, and Tyler Grantham. Who views online extremism? individual attributes leading to exposure. Computers in Human Behavior, 63:311-3200 2016.
[CK06] Moses Charikar and Robert Krauthgamer. Embedding the Ulam metric into 4 Theory of Computing, 2(1 1):207-224, 2006.
[CKLV17] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair cluster- ing through fairlets. In Advances in Neural Information Processing Systems (NeurIPS), pages 5029-5037, 2017.
[CKLV19] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvtiskii. Matroids, matchings, and fairness. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89, pages 2212-2220, 2019.
[CMS01] Graham Cormode, Shan Muthukrishnan, and Süleyman Cenk Sahinalp. Permutation editing and matching via embeddings. International Colloquium on Automata, Languages, and Programming (ICALP), pages
Springer, 2001.
[CMV] Eden Chlamtáe, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Joseph (Seffi Naor and Niv Buchbinder, editors, ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 2664-2683.
[CSV18] L Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. Ranking with fairness constraints. In International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pages 28:1 1-2815,, 2018
[Des05] Ashwini Deshpande. Affirmative action in india and the united states. 2005.
[DG77] Persi Diaconis and Graham. Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological), 39(2):262-28 1977.

---

[DHP* 12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairnsss through awareness. In Innovations in Theoretical Computer Science, pages 214-226, 2012.
[DKNSOI] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In International conference on World Wide Web, pages 613-622, 2001.
[Bur] Eu platform of diversity charters.
http::///e...urrr..//aaa//o//oop heccll/gdsccmaaattoo/vvvveeeaaad hrsifommdiiverssttychaattrsssss Accessed: May, 2022.
[FKS03] Ronald Fagin, Ravi Kumar, and Dandapani Sivakumar. Efficient similarity search and classification via rank aggregation. In SIGMOD International Conference on Management of Data, pages 301-312, 2003.
[GDL21] Sruthi Gorantla, Amit Deshpande, and Anand Louis. On the problem of underranking group-fair ranking. In International Conference on Machine Learning (ICML), pages 3777-3787, 2021.
[GL11] David F Gleich and Lek-heng Lim. Rank aggregation via nuclear norm minimization. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 60-68, 2011.
[GSB21] David Porcia-Soriano and Francesco Bonchi. Maxmin-fair ranking: individual fair- ness under group-fairness constraints. In ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 436 446, 2021.
[Hr92]] Donna Harman. Ranking algorithms. In William Frakes and Ricardo A Bacza- Yates, editors, Information Retrieval: Data Structures & &Algorithms, pages 363-392. Prentice-Hall, 1992.
[HJV19] Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. Coresets for cluster- ing with fairness constraints. In Advances in Neural Information Processing Systems (NeurIPS), pages 7587-7598, 2019.
[HPS16] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances Neural Information Processing Systems (NeurIPS), pages 3315-3323, 2016.
[HV19] Lingxiao Huang and Nisheeth Vishnoi. Stable and fair classification. In International Conference on Machine Learning (ICML), pages 2879-2890, 2019.
[Kem59] John G Kemeny. Mathematics without numbers. Daedalus, 88(4):577-591, 1959.
[Ken38] Maurice G Kendall, A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
[KMM15] Matthew Kay, Cynthia Matuszek, and Sean A Munson. Unequal representation and gender stereotypes in image search results for occupations. In ACM conference human factors computing systems, pages 3819-3828. 2015.
[KMS07] Claire Kenyon-Matts Mathieu and Warren Schudy. How to rank with few errors. In ACM Symposium Theory of Computing (STOC), pages 153103, 2007.
[Kni66] William R Knight. A computer method for calculating kendall's tau with ungrouped data. Journal of the American Statistical Association, 61(314):436433 1966.
[KR20] Caitlin Kuhlman and Elke Rundensteiner, Rank aggregation algorithms for fair con- sensus. Proceedings of the VLDB Endowment, 13(12), 2020.
[KV10] Ravi Kumar and Sergei Vassilvitskii. Generalized distances between rankings. In International Conference on World Wide Web, pages 57 571-580, 2010.
12

---

21] Ninarch Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. survey on bias and faimess in machine learning, ACM Computing Surveys (CSUR), (4(): 54(6):1-35, 2021.
[NSS17] Timothy Naumovitz, Michael E Saks, and C Seshadhri. Accurate and nearly optimal sublinear approximations to Ulam distance. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2012-2031, 2017.
[PGNN20] Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Yadati Narahari, Achieving fairness in the stochastic multi-armed bandit problem. In AAAL, pages 5379-5386, 2020.
[PKL21] Deval Patel, Arindam Khan, and Anand Louis. Group faimess for knapsack problems. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1001-1009, 2021.
[Pop07] V Yu Popov. Multiple genome rearrangement by swaps and by element duplications. Theoretical computer science. 385(1-3):115-122 2007.
22) Gourab K. Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg. Fair ranking: critical review, challenges, and future directions. In ACM Conference on Fairness, Accountability, and Transparency (FAceT), pages 1929-1942, 2022.
[Sch12] Warren Schudy. Approximation schemes for inferring rankings and clusterings from pairwise data. Ph.D. Thesis, 2012.
[Sin19] Simrandeep Singh. An analysis of the constitutionality of the economically weaker sections (ews) reservation. Available at SSRN 35433 2019.
[Spe04] C Spearman. The proof and measurement of association between two things. The American Journal of Psychology, 15(1):72-101, 1904.
[Spe06] C Spearman. Footrule for measuring correlation. British Journal of Psychology. 2(1):89, 1906.
[USD] Us equal employment opportunity commission. May, 2022.
gov
Accessed:
20] Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng. Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching nearly- linear time moderately dense graphs. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 919-930, 2020.
[Ver10] Tània Verge. Gendering representation in spain: Opportunities and limits of gender quotas. Journal of Women, Politics & Policy, 196, 2010.
[WISR22] Dong Wei, Md Mouinul Islam, Baruch Schieber, and Senjuti Basu Roy. Rank ag- gregation with proportionate fairesss. In SIGMOD International Conference on Management of Data pages 262-275, 2022.
[YL78] H Peyton Young and Arthur Levenglick. A consistent extension of condorcet's election principle. SIAM Journal on Applied Mathematics, 35(2):285-300, 1978.
[You88] Peyton Young. Condorcet's theory of voting. American Political science review, 82(4):123--124, 1988.
[ZBC+ 17] Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza- Yates. Fa ir: A fair top-k ranking algorithm. In ACM Conference on Information and Knowledge Management (CIKM), pages 1569-1578. 2017.
[ZYS21] Meike Zehlike, Ke Yang, and Julia Stoyanovich. Faimess in ranking: A survey. arXiv preprint 2000 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [No] The current work is theoretical.
The setting and models under study are clearly described in the paper.
(c) Did you discuss any potential negative societal impacts of your work? [No] Given the theoretical nature of the work, we do not envision any potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] complete proofs are given the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "wmJVJ5gDq5C", "reviewer": "Reviewer_3bHj", "summary": "The authors propose algorithms for closest fair ranking and fair rank aggregation problems.  Specifically, they consider two notions of fairness - weak : (a, b)-fair up to a prefix k of the ranking and strong : fair for all prefixes.  They provide an exact algorithm for the CFR problem for two metrics - Kendall Tau and Ulam.  Their results hold when the number of groups are a constant in the case of the Ulam metric.", "questions": "Do the algorithms extend to multi-dimensional spaces when a fairness criterion for each group can be represented as a d-dimensional vector.  The current algorithms are fairly straightforward because of the assumption of no 'overlap' between different groups.", "limitations": "While the problem of fair ranking is an important problem to consider, fair rank aggregation is not well motivated. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Fair ranking is an important problem. \n2. All the details are presented.  The paper is however a bit hard to read in some places.\n3. The algorithms are fairly intuitive.\n\nWeaknesses:\n1. The algorithms are fairly simple to analyze.\n2.  While fair ranking is an important problem, the same might not be the case for rank aggregation - one of the primary goals for aggregation is to overcome biases from any individual ranking.\n3. Comparison to related work especially in fair group formation and fair clustering/partitioning is missing.  The latter problems are especially related under the weak notion of fairness when k is set to the size of each parition/cluster/group.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jS4V_QVn31i", "reviewer": "Reviewer_VkxL", "summary": "From a fairness or diversity perspective, this paper examines ranking problems in which candidates belonging to different groups have a fair representation in the final rankings. Using a linear time exact algorithm, the algorithm will find the closest fair ranking for Kendall tau metric under strong fairness (where the final ranking is fair for all values of k) given the parameters for defining fair representation (number of candidates from a particular group in the top-k positions of the ranking).\nThe authors also provide an exact algorithm for finding the closest fair ranking for the Ulam metric under strong fairness when there are a few number of groups. Additionally, the authors propose a novel meta-algorithm for the general rank aggregation problem under the fairness framework.\nIn a nutshell, the main contribution is to develop a novel algorithmic toolbox for the fair rank aggregation that solves a variety of rank aggregation objectives satisfying such generic fairness constraints. An essential takeaway of this work is that a set of potentially biased rankings can be aggregated into a fair ranking with only a small loss in the quality of the ranking.", "questions": "See above. Have you implemented your algorithm to experiment on a real-world data?", "limitations": "I don't if they have discussed the limitations of their approach.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper throughly studies the fair rank aggregation problem under different fairness constraints. It provides two meta-algorithms to approximate the fair aggregated ranking. There are a lot of Theorems, Claims, Lemmas and Definitions in the paper which is good in a sense because it adds details but overall makes the paper not easy to follow. I suggest moving some of them to appendix. One of the main sections of the paper (Fair Rank Aggregation) starts in page 7! While the paper looks interesting and novel, it is pure theoretical paper which I'm not sure is a good choice for this venue. The paper introduces a generic approach and argues it is a novel algorithm but it does not test this method on a simulated or real-world data. It would be interesting to see some experiments and comparisons with the methods discussed in [1] or [2] as these papers mentioned in the paper as closest approaches and they provide experiments to show the effectiveness of their method. \n\nMissing related work: In line 43, Besides mentioned papers, [1] is also a new related work that outputs a fair ranking robust to label noise that maximizes the ranking utility subject to group fairness constraints based on exposure such as demographic parity. It is an in-processing method which presents a preferable trade-off between fairness and utility.\n\n[1] Caitlin Kuhlman and Elke Rundensteiner. Rank aggregation algorithms for fair con- sensus. Proceedings of the VLDB Endowment, 13(12), 2020.\n\n[2] David Wei, Md Moinul Islam, Baruch Schieber, and Senjuti Basu Roy. Rank aggrega- tion with proportional fairness. In SIGMOD, page To appear, 2022.\n\n[3] Memarrast, Omid, Ashkan Rezaei, Rizal Fathony, and Brian Ziebart. \"Fairness for Robust Learning to Rank.\" arXiv preprint arXiv:2112.06288 (2021).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IrPvQAnP94Z", "reviewer": "Reviewer_2yve", "summary": "The authors study fair rank aggregation, where candidates may belong to different groups and each group must be represented fairly in the final ranking (in a way that the designer can specify). They provide a linear time algorithm for finding the closest fair ranking under proportional fairness for the Kendall tau distance metric, and a poly-time dynamic programming algorithm for the Ulam metric for a constant number of groups (which is the case in practice). They then study the fair rank aggregation problem, and show that many biased rankings can be aggregated into a fair ranking with only a small loss in quality for a variety of distance metrics.\n", "questions": "1. Have you considered fair rank aggregation algorithms that do not use closest fair ranking as a subroutine?\n", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n+ The definition of proportional fairness is general and flexible, and nicely generalizes previous results.\n+ The fair rank aggregation problem is also an interesting line of inquiry, where the goal is to find a fair ranking that minimizes the generalized mean distance to the input profile.\n\nStrength/weakness: \n+ The meta-algorithms for fair rank aggregation are also simple (which could be a weakness, but as a first foray into the field seems like a plus), where the ideas are either to (1) find fair approximations of each input ranking and then choose the most central one, or (2) find a fair approximation of the (unfair) ranking that minimizes the generalized mean objective. However, there is perhaps more room for more sophisticated algorithms that don't involve the CFR subproblem.\n\nWeaknesses:\n- The algorithms described in the paper are all relatively simple (even if the analysis is nontrivial). This is only a minor critique, however: as an early paper in this area, that is to be expected.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-kya_7MWte", "reviewer": "Reviewer_YYph", "summary": "This paper focused on the rank aggregation problem under a very general notion of proportional fairness. Authors propose a linear time exact algorithm to find the closest fair ranking (CFR) by a greedy strategy for Kendall tau and Ulam metrics and propose a novel algorithmic toolbox to solve a wide variety of rank aggregation objectives satisfying such generic fairness constraints. They provide rigorous mathematical derivation to prove that the there exists a linear time ranking algorithm.", "questions": "* This paper discusses the different cases by leveraging different distance function, Kendall tau and Ulam. But there is no comparison between these two different distance functions. Which one is more suitable for the fair rank aggregation task?\n\n*This paper provides some mathematical derivation to compute the time complexity of the proposed algorithms. How about the performance of ranking by the proposed algorithms? Can you deliver some experiments to show the performance of your ranking, such as precision?  \n", "limitations": "*This paper focuses on the mathematical derivation for the fair rank aggregation and illustrates that the proposed algorithms are better than concurrent work [WISR22] in line 132. Maybe authors can add more comparisons and give more detailed explanation for proving the superiority of the proposed algorithms.\n\n*This paper studies group fairness, as well as proportional fairness. The assumption of this problem seems to be that each candidate only belongs to one group. I wonder if the algorithms in this paper still works if each candidate can belong to multiple groups at the same time.\n", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* This paper gives a novel meta-algorithm for the general rank aggregation problem under the fairness framework, which works for any generalized mean objective and any fairness criteria.\n* This paper proves that the there exists a linear time ranking algorithm through rigorous mathematical derivation.\nWeaknesses:\n* The structure of this paper is incomplete, which makes the paper poor readable. This paper misses Sections of Related Works and Conclusion. Authors can refer to previous paper published in NeurIPS for revision. \n* In this paper, authors only use one paragraph in Section 1.1 to introduce the comparison with only one concurrent work. It is difficult to convince me that the algorithm proposed in this paper is superior to the state-of-the-art algorithms.\n* Some formulations are not correct. For example, in Section 1, the generalized mean objective in Section 1.1 $\\sum_{i=1}^n (\\rho(\\pi_i, \\sigma)^q)^{1/q}$ should be $(\\sum_{i=1}^n \\rho(\\pi_i, \\sigma)^q)^{1/q}$ in line 105.\n* I think the contribution of the proposed algorithm is that authors design a novel objection function of greedy strategy for fair ranking and prove the algorithm is a linear time ranking algorithm. However, the greedy strategy for ranking is lack of innovation\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept