Individually Fair Rankings
Authors: Amanda Bower
Hamid Eftekhari
Mikhail Yurochkin
Yuekai Sun
Venue: ICLR 2021 Poster (2021)
Keywords: algorithmic fairness
learning to rank
optimal transport

Abstract: We develop an algorithm to train individually fair learning-to-rank (LTR) models. The proposed approach ensures items from minority groups appear alongside similar items from majority groups. This notion of fair ranking is based on the definition of individual fairness from supervised learning and is more nuanced than prior fair LTR approaches that simply ensure the ranking model provides underrepresented items with a basic level of exposure. The crux of our method is an optimal transport-based regularizer that enforces individual fairness and an efficient algorithm for optimizing the regularizer. We show that our approach leads to certifiably individually fair LTR models and demonstrate the efficacy of our method on ranking tasks subject to demographic biases.

Published as a conference paper at ICLR 2021
INDIVIDUALLY FAIR RANKING
Amanda Bower
Hamid Eftekhari
Department of Mathematics
Department of Statistics
University of Michigan
University of Michigan
amandarge umi ch. edu
hami de @umi ch edu
Mikhail Yurochkin
Yuekai Sun
IBM Research
Department of Statistics University of Michigan yueka @umi ch, edu
MIT-IBM Watson Al Lab
mi chail, yurochkiii in@ hemiimmcoo com
ABSTRACT
We develop an algorithm train individually fair saaming-to-rante (LTR) models. The proposed approach ensures items from minority groups appear alongside similar items from majority groups. This notion of fair ranking is based on the definition of individual faimess from supervised learning and is more nuanced than prior fair LTR approaches that simply ensure the ranking model provides underrepresented items with a basic level of exposure. The crux of our method is an optimal transport-base based regularizer that enforees individual fairness and an efficient algorithm for optimizing the regularizer. We show that our approach leads to certifiably individually fair LTR models and demonstrate the efficacy of our method ranking tasks subject demographic biases.
INTRODUCTION
Information retrieval (IR) systems are everywhere today's 's digital world, and ranking models are integral parts of many IR systems. In light of their ubiquity, issues of algorithmic bias and unfairness in ranking models have come to the fore of the public's 's attention. In many applications, the items to be ranked are individuals, people's lives. For example, gender bias in job search engines directly affect the career success of job applicants (Dastin, 2018).
algorithmic biases in the output of ranking models directly affect
There a rapidly growing literature on detecting and mitigating algorithmic bias machine learning (ML). The ML community has developed many formal definitions of algorithmic faimess along with algorithms to enforce these definitions (Dwork et al., 2012; Hardt et al., 2016; Berk et al., 2018; Kusner al., 2018; Ritov et al., 2017; Yurochkin et al., 2020). Unfortunately, these issues have received less attention in the IR community. In particular, compared to the myriad of mathematical definitions of algorithmic fairness the MI community, there are only few definitions of algorithmic fairness for ranking. A recent review of fair ranking (Castillo, 2019) identifies two characteristics of fair rankings:
1. sufficient exposure of items from disadvantaged groups in rankings: Rankings should display diversity of items. particular, rankings should take care to display items from disadvantaged groups avoid allocative harms items from such groups. consistent treatment of similar items in rankings: Items with similar relevant attributes should be ranked similarly.
There is line of work on fair ranking by Singh & Joachims (2018; 2019) that focuses on the first characteristic. In this paper, we complement this line of work by focusing on the second characteristic. In particular, we (i) specialize the notion of individual fairness ML to rankings and (ii) devise an efficient algorithm for enforcing this notion in practice. We focus the second characteristic since, in some sense, consistent treatment of similar items implies adequate exposure: if there are items from disadvantaged groups that are similar to relevant items from advantaged groups, then ranking model that treats similar items consistently will provide adequate exposure to the items from disadvantaged groups

---

Published as a conference paper at ICLR 2021
1.1 RELATED WORK
Our work addresses the faimess of learning-to-rant (LTR) system with respect the items being ranked. The majority of work in this area requires a fair ranking to fairly allocate exposure (measured by the rank of an item in ranking) to items. One line of work (Yang & Stoyanovich, 2017; Zehlike et al., 2017; Celis et al., 2018; Geyik et al., 2019; Celis et al., 2020; Yang et al., 2019b) requires a fair ranking to place minimum number of minority group items in the top k ranks. Another line of work models the exposure items receive based on rank position and allocates exposure based on these exposure models and item relevance (Singh & Joachims, 2018; Zehlike& & Castillo, 2020; Biega et al., 2018; 8; Singh & Joachims, 2019; Sapiezynski et al., 2019). There is some work that consider other fairness notions. The work of Kuhlman et al. (2019) proposes error-based fairness criteria, and the framework of Asudeh et al. (2019) can handle arbitrary fairness constraints given by an oracle. In contrast, we propose a fundamentally new definition: an individually fair ranking is invariant to sensitive perturbations of the features of the items. For example, consider ranking set of job candidates, and consider the hypothetical set of candidates obtained from the original set by flipping each candidate's 's gender. We require that fair LTR model produces the same ranking for both the original and hypothetical set.
The work in Zehlike al. (2017); Celis et al. (2018); Singh & Joachims (2018); Biega al. (2018); Geyik et al. (2019); Celis et al. (2020); Yang et al. (2019h); Wu et al. (2018); Asudeh et al. (2019) propose post-procsssing algorithms to obtain a fair ranking. i.c., algorithms that fairly re-rank items based on estimated relevance scores or rankings from potentially biased LTR models. However, post-processing techniques are insufficient since they can be mislead by biased estimated relevance scores (Zehlike & Castillo, 2020; Singh & Joachims, 2019) with the exception of the work in Celis et al. (2020) which assumes a specific bias model and provably counteracts this bias. In contrast, like Zehlike& & Castillo (2020); Singh & Joachims (2019), we propose an in-processing algorithm. We also note that there is some work on
We consider individual fairness as opposed to group fairness (Yang & Stoyanovich, 2017; Zehlike et al., 2017; Celis et al., 2018; Singh & Joachims, 2018; Zehlike & Castillo, 2020; Geyik et al., 2019; Sapiezynski et al., 2019; Kuhlman et al., 2019; Celis et al., 2020; Yang et al., 2019b; Wu et al., 2018; Asudeh et al., 2019). The merits of individual fairness over group fairness have been well established, e.g., group fair models can be blatantly unfair to individuals (Dwork et al., 2012). In fact, we show empirically that individual fairness is adequate for group fairness but not vice versa. The work in Biega et al. (2018); Singh & Joachims (2019) also considers individually fair LTR models. However, our notion of individual fairness is fundamentally different since we utilize a fair metric on queries like in the seminal work that introduced individual fairness (Dwork al., 2012) instead of measuring the similarity of items through relevance alone. To see the benefit of our approach, consider the job applicant example. If the training data does not contain highly ranked minority candidates, then at test time our LTR model will be able to correctly rank a minority candidate who should be highly ranked, which not necessarily true for the work in Biega et al. (2018); Singh & Joachims (2019).
2 PROBLEM FORMULATION
A query g E Q to a ranker consists of a candidate set of n items that needs to be ranked de A (d'...., d%) and a set of relevance scores rel4 & (d) E Jede Each item is represented by feature vector p(d) E X' that describes the match between item d and query where X' is the feature space of the item representations. We consider stochastic ranking policies T(- q) that are distributions over rankings (i.e. permutations) of the candidate set. Our notation for rankings r(d): the rank of item d in ranking (and r r=)(s) is the j-ranked item). A policy generally consists of two components: a scoring model and sampling method. The scoring model is smooth ML model he parameterized by (e.g.a neural network) that outputs a vector of scores: hd))) & (ho())(d))),. (..d))).... ho((p(d)))) )). The sampling method defines a distribution on rankings of the candidate set from the scores. For example, the Plackett-Luce (Plackett, 1975) model defines the probability of the ranking r = (di,..., dn) as
exp(ho((p(d)))) no (r q)) exp(ho(vp(d))) + ..... + exp(he (((()))))
(2.1)
2

---

Published as a conference paper at ICLR 2021
To sample ranking from the Baccket-Luce model, items from query chosen without replacement where the probability of selecting items is given by the softmax the scores of remaining items. The order in which the items are sampled defines the order of the ranking from best to worst. The goal of the LTR problem is finding a policy that has maximum expected utility:
π arg max, mag, (U(T g)] where UTT q) - E,--((lo) rel))
(2.2)
where Q is the distribution of queries, (sr g) is the utility of a policy for query and A is ranking metric (e.g. normalized discounted cumulative gain). In practice, we solve the empirical version of (2.2):
N Σ (Tr [.)]:
$ arg max
(2.3)
N
where {4 J training set. If the policy parameterized by 0, it is not hard evaluate the gradient of the utility with respect to 0 with the log-derivative trick:
(To q)) Op 2) (er))
(rr, q)dr
= / ree 0o
(log (r ( me g)dr En-ma(tle) [Arr rel a log (o(r) lg]
In practice, we (approximately) evaluate (mo () by sampling from no(- | g). This set-up is mostly adopted from Yadav et al. (2019).
2.1 FAIR RANKING VIA INVARIANCE REGULARIZATION
We cast the fair ranking problem as training ranking policies that are invariant under certain sensitive perturbations the queries. Let dg be fair metric on queries that encode which queries should be treated similarly by the LTR model. For example, LTR model should similarly rank set of job candidates and the hypothetical set of job candidates obtained from the original set via flipping the gender of each candidate. Hence, these two queries should be close according to dg. We propose Sensitive Set Transport Invariant Ranking (SenSTIR) enforce individual fairness in ranking via the following optimization problem:
n" arg max, (U(T [)] pR((),
(SenSTIR)
such that > 0 is regularization parameter and
En ( 1)) T(. (1)]
R(T) subject to
E )n - (d ) Sc
(2.4)
11(, Q) =
is invariance regularizer where dR is a metric ranking policies, A A Q) is the set of probability distributions on Q x Q where Q is the set of queries, and é 0. At a high-level, individual fairness requires ML models have similar outputs for similar inputs. This property is exactly what the regularizer encourages: the LTR model is encouraged to assign similar ranking policies (with respect to dR) to similar queries (with respect do). The problem of enforcing invariance for individual fairness has been considered in classification (Yurochkin et al., 2020; Yurochkin & Sun, 2021). However, these methods are readily applicable to the LTR setting because of main challenges: (i) defining a fair distance de on queries, i.c., sets of items, and (ii) ensuring the resulting optimization problem is differentiable.
Optimal transport distance de between queries We appeal to the machinery of optimal transport to define an appropriate metric de on queries, i.c., sets of items. First, we need fair metric on items dx that encodes our intuition of which items should be treated similarly. Such metric also appears in the traditional individual fairness definition (Dwork et al., 2012) for classification and regression problems. Learning individually fair metric is important problem of its own that actively studied in the recent literature (Ilvento, 2020; Wang et al., 2019: Yurochkin et al., 2020; Mukherjee al., 2020). In the experiment section, the fair metric items dx is learned from data
3

---

Published as a conference paper at ICLR 2021
using existing methods. The key idea is to view queries, i..., sets of items, distributions X' so that a metric between distributions can be used. In particular, to define de from dx, we utilize an optimal transport distance between queries with dx as the transport cost:
Jxxx dx dx 2'))(((( [T;;)) = E pp(d))
de d') -
subject to
(2.5)
IIX - - v(dy')
where A(X' x X) is the set of probability distributions on X' A' where X' is the feature space of item representations and is the Dirac delta function.
ALGORITHM
In order to apply stochastic optimization Equation (SenSTIR), we appeal duality, particular, we use Theorem 2.3 of Yurochkin & Sun (2021) re- ce-written with the notation of this work:
Theorem (Theorem 2.3 of Yurochkin & Sun (2021)). If ( ②) x(- q¹)) Ado(a. is continuous in (g, v for all X then the invariance regularizer R can be wrillen as
R( inf + / 4)]}, where
(3.1)
(T 9) f sup, s (d 9). ( d')) - Ade(g,
(3.2)
In order compute (TT, q). (')) Ade(q. 9¹). We start by computing the gradient of de(g, (') with respect x' & sp(d" ). Let ((d)). Let (1, g') be the optimal transport plan for the problem defining de(1, d)), that
use gradient ascent on u(g' 7,
dR( | q). T(:
de(a.0') = J ('),x"))dl" x'), (;,
Σ Boar (I, = oldg'y
The probability distribution (q, can be viewed as coupling matrix where I1, e II" (p(()), p(df) )). Using this notation we have
d. -) Eedddrdx(((t) ((d)
(3.3)
where 0zdx denotes the derivative of dx with respect to its second input. If d q), no( (')) = (l/a((((d") ha(yp(d'' 1/1//2 then by (3.3), single iteration of gradient ascent on de with step size y for x' is
2 1(+1) = = + 1 02y (ho(2'0)) -h(()))))))))))))))
Σ mI (=ddddd
(3.4)
In our experiments, we use this choice of dR, which has been widely used, e.g., robustness in image classification (Kannan al., 2018; Yang et al., 2019a) and fairness (Yurochkin & Sun, 2021). However, our theory and set-up do not preclude other metrics. We can now present Algorithm 1, an alternating, stochastic algorithm, to solve (SenSTIR).
Algorithm 1: SenSTIR: Sensitive Set Transport Invariant Ranking
Input: Initial Parameters: 0o λo e, p; Step Sizes: Y,, > 0, Training queries: Q repeat
Sample mini-batch (gr,, rel ) from Q
dh. +- arg max, n l2o ((p(d"):)) - ho, (p((d' ))12 Xedolat, [B] /x Using
(3.4) +/
A + max d, + a 1 Σ. dola. th,))
0,41 + 0.+m El= Oo (0(U(TO, a.))} (a.)-p((80 p(ophe, (g..) -dph,, (gt. (). (ho,, (di.) -ho, (g..)
until convergence
4

---

Published as a conference paper at ICLR 2021
4 THEORETICAL RESULTS
In this section, we study the generalization performance of the invariance regularizer R(ho) := R(mo). which is instance of hierarchical optimal transport problem that does have known uniform convergence results in the literature. Furthermore, the regularizer is not separable function of the training examples so classical proof techniques are not applicable. To state the result, suppose that dx an approximation of the fair metric dx between items that is learned from data. The corresponding learned metric on queries is defined by
inf subject to
Sxxx (2,)'')
delg, -
11(;;²) = 1. -3= Ap(d)) = = IIX,-))
(4.1)
- v(dyy)
and the empirical regularizer is defined by
En (ny (mld)(ho(((dd)) ho (o( ))
R(ha) &
subject to
En [nd(((,))) S 2) Q
(4.2)
where Q is the distribution of training queries and dy is metric on & (holpp(d)) Q).
Define class of loss functions 'D by D (dn, Q x R ho E H), where dn - (y(h()(dd)) h(pp(d))) ))) and H is the hypothesis class of scoring functions.
Let N(D, d, c) be the e-covering of the class D with respect to metric d. The entropy integral of D (w...t. the uniform metric) measures the complexity of the class and is defined by
J(D)
log (D, lloo,
(4.3)
Assumption A1. Bounded diameters: sup ex (x(xxx))) x') S Dx suppwey dyl,, S Dy-
Assumption A2. Estimation error dx bounded: au (dx(2, - dx(x, x')l S nd-
Theorem 4.1. If assumptions Al and A2 hold and J(D) is finite, then with probability at least -
sup R(hh) R(ho)l 48(J(D) + + DxDy) + Dy h
loo
Dyna
+
Vn
2n
c
where n is the number of training queries. A proof the theorem given in the appendix. The key technical challenge is leveraging the transport geometry on the query space to obtain uniform bound on the convergence rate. This theorem implies that for trained ranking model he the error term RRhh)) R(h+)l is small for large n. Therefore, one can certify that the value of the regularizer R(ho) small on yet unseen (test) data by ensuring that the value of f((ho) is small on training data.
COMPUTATIONAL RESULTS
In this section, we demonstrate the efficacy of SenSTIR for learning individually fair LTR models. One key conclusion is that enforcing individual fairness is adequate achieve group faimess but not vice versa. See Section B of the appendix for full details about the experiments.
Fair metric Following Yurochkin et al. (2020), the individually fair metric dx on X' is defined in terms of sensitive subspace A that is learned from data. In particular, dx is the Euclidean distance of the data projected onto the orthogonal complement of A. This metric encodes variation due to sensitive information about individuals in the subspace and ignores it when computing the fair distance. For example, A can be formed by fitting linear classifiers to predict sensitive information,
5

---

Published as a conference paper at ICLR 2021
Baseline: p 0
SenSTIR: p= 0003
SenSTIR: p= 001
3
2-
3
1-
2
0
2
0
2
3
0
1 NDCG .910
3
NDCG .970
NDCG .945
Figure The points represent items shaded by their relevances, and the contours represent the predicted scores. The minority items lie the horizontal = -i-s because their 22 value is corrupted to O. The blue star and black star correspond to minority and majority items that are close in the fair metric with nearly the same relevance. However, they have wildly different predicted scores under the baseline. Using SenSTIR, as increases, they eventually have the same predicted scores.
like gender or age, of individuals and taking the span of the vectors orthogonal to the corresponding decision boundaries. In each experiment, we explain how learned.
Baselines For all methods, we learn linear score functions ha and maximize normalized discounted
cumulative gain (NDCG), i.c., A in Equation 2.2 NDCG. We compare SenSTIR to (1) vanilla training without fairness ("Baseline"), i.e., P = 0, (2) pre-processing by first projecting the data onto the orthogonal complement of the sensitive subspace and then using vanilla training ("Project"), (3)
"Fair-PG PG-Rank' (Singh & Joachims, 2019), recent approach for training fair LTR models, and (4) randomly sampling the linear weights from a standard normal ("Random") to give context to NDCG.
5.1 SYNTHETIC
We use synthetic data considered in prior fair ranking work (Singh & Joachims, 2019). Each query contains 10 majority or minority items in IR2 such that items per query are majority group items in expectation. For each item, and are drawn uniformly from [0, 3). The relevance of an item is 21 + 22 clipped between 0 and 5. majority item's feature vector (21, )" whereas a minority item's feature vector is corrupted and given by 1)7,0)"
Fair Metric The sensitive subspace is spanned by the hyperplane learned by logistic regression to predict whether an item is in the majority group. Recall, the fair metric is the Euclidean distance of the projection of the data onto the orthogonal complement of this subspace. Since this hyperplane is nearly equal to (0, 1)", the biased feature 22 is ignored in the fair metric.
Results Figure illustrates SenSTIR for o E {0, .0003,0000000 .001} with e = .001. Each point is colored by its relevance, and the contours show predicted scores where redder (respectively bluer) regions indicates higher (respectively lower) predicted scores. Minority items are on the horizontal 21-axis because of their corrupted features. When p 0, i..., fairness is not enforced, this score function badly violates individual fairness since there are pairs of items close in the fair metric but with wildly different predicted scores because the biased feature 22 used. For example, the bottom blue star is minority item with nearly the same relevance as the top black star majority item; however, the majority item's predicted score much higher. When p increased. the contours learned by SenSTIR eventually become vertical, thereby ignoring the biased feature z2 and achieving individual fairness. When p = .001, the scores of the blue and black star are nearly equal because they are very close in the fair metric and the fair regularization strength is large enough.
Figure 2 illustrates another individual fairness property of SenSTIR that Fair-PG-Rank does not satisfy: ranking stability with respect to sensitive perturbations of the features. For each test query let o' * q be the closest test query in terms the fair distance de. We can view q' as a hypothetical query in the test set. For each query g. sample 10 rankings corresponding to q and 10 hypothetical rankings corresponding to q' based on the learned ranking policy. The (i. j) entry of a heatmap in Figure is the proportion of times the i-th ranked item for query q is ranked j-th in the hypothetical

---

Published as a conference paper at ICLR 2021
Baseline: p=
Fair-PG-Rank: 25
SenSTIR: p= .003
SenSTIR: p=.001
0.60
3
0.45
4
0.30
7
8
0.15
10
0.00
Figure 2: The (i, entries of these heatmaps represent the proportion times that the i-th ranked item is moved position j under the corresoonding hypothetical ranking. With large enough p. SenSTIR ranks the original queries and hypothetical queries similarly as desired.
ranking. To satisfy individual fairness, the original and hypothetical rankings should be similar, meaning the heatmaps should be close to diagonal. Even though the baseline is relatively stable for highly and lowly ranked items, these items still change positions under the hypothetical rankings more than 50% of the time. Although Fair-PG-Rank satisfies group faimess, it is worse than the baseline in terms of hypothetical stability, i.e., individual fairness. In contrast, as p increases, SenSTIR becomes stable.
5.2 GERMAN CREDIT DATA SET
Following Singh & Joachims (2019), we adapt the German Credit classification data set (Dua & Graff, 2017), which is susceptible to gender and age biases, to a LTR task. This data set contains 1000 individuals with binary labels indicating creditworthiness. Features include demographics like gender and age well as information about savings accounts, housing, and employment. To simulate LTR data, individuals are sampled with replacement to build queries of size 10. Each individual has a binary relevance, and on average 4 individuals are relevant in each query. To apply Fair-PG-Rant age is the binary protected attribute where the two groups are those younger than 25 and those 25 and older, split proposed by Kamiran & Calders (2009). For the fair metric, the sensitive subspace is spanned by the ridge regression coefficients for predicting age based on all other features and the standard basis vector corresponding age.
Comparison metrics See Section B of the appendix for the precise definitions of these metrics. To assess accuracy, following Singh & Joachims (2019), we report the average stochastic test NDCG by sampling 25 rankings for each query from the learned ranking policy. To assess individual fairness, we use ranking stability with respect to demographic perturbations, which is the natural analogue of an evaluation metric for individual fairness in classification (Yurochkin & Sun, 2021; Yurochkin et al., 2020; Garg et al., 2018). In particular, for each query, we create hypothetical query by flipping the (binary) gender of each individual in the query, and deterministically rank by sorting the items by their scores. We report the average Kendall's tau correlation (higher implies better individual fairness) between test query's ranking and its hypothetical ranking. To assess group fairness and fairly compare to Fair-PG-Rank based on their fairness definition, we report the average stochastic disparity of group exposure also with 25 sampled rankings per query. This metric measures the asymmetric differences of the ratio of exposure a group receives to its relevance per query and favors the group with less relevance for given query. Let G1 (respectively Go) be the set of older (respectively younger) people for query For i E {0. 1), let MG. = (1/(G,) Edec, (e)" (d). If Mc., > Mc. let G Go. GD = G, and G = G1. GD Go otherwise. The stochastic disparity group exposure for a set of rankings {ri),
i=l corresponding to query is
max 0. NIGA EdEca Σ (Ps(+()
MiGol Edeao Σ (%
(5.1)
Mc
MG
Results Figure 3 illustrates the fairnsss versus accuracy trade-off on the test set. The error bars represent the standard error over 10 random train/test splits. Both SenSTIR and Fair-PG-Ran enforce faimess through regularization, we vary the regularization strength for SenSTIR with constant). Based on the NDCG of "Random". the regularization strength ranges are reasonable for both methods. The left plot Figure shows the average Kendall's tau correlation (higher is better)
7

---

Published as a conference paper at ICLR 2021
0.850
0.850
0.825
0.825
0.800
0.800
8 0.775
0.775
0.750
0.750
Fair-PG-Rand
0.725
0.725
Baseline
Random
0,700
0.700
Project
0.675
0.675
0.75
0.80
0.85
0.90
0.95
1.00
.002
.004
.006
.008
.01 .012 .014 .016
Kendall's Tau Correlation with Gender Flipped Hypothetical Queries
Group Exposure for Age
Figure Individual (left) and group fairness (right) versus accuracy for the German credit data set
between test queries and their gender-flipeed hypotheticals versus the average stochastic NDCG. The maximum Kendall's tau correlation is 1. which SenSTIR achieves with relatively high NDCG. We emphasize that the sensitive subspace that SenSTIR utilizes define the fair query metric directly relates to age, not gender. In other words, our goal is to mitigate unfairness that arises from age in the training data, not gender. However, age correlated with gender, so this metric shows the individually fair properties of SenSTIR generalize beyond age the test set. We imagine that ML systems can be unfair to people with respect to features that can be difficult to know before deploying these systems, so although flipping gender is simplistic choice, it illustrates that SenSTIR can be meaningfully individually fair with respect to these potentially unknown features that were not given special consideration when choosing the fair metric or in training with SenSTIR. Furthermore, SenSTIR gracefully trades off NDCG for individual fairness unlike Fair-PG-Rank. "Project" is worse in terms of individual fairness than vanilla training without enforcing fairness. Without direct age information, perhaps "Project" must more heavily rely on gender to learn accurate rankings, which illustrates that SenSTIR's generalization properties from age to gender are non-trivial. Disparity of group exposure (where smaller numbers are better) versus NDCG is depicted on the right plot of Figure 3. This group fairness metric exactly what Fair-PG-Rant regularizes with. On average, for the same value of NDCG, SenSTIR typically outperforms Fair-PG-Rank showing that individual fairness can be adequate for group fairness but not vice versa. While "Project" improves mildly upon the baseline, it shows being "age" blind does not result in group fair rankings.
5.3 MICROSOFT LEARNING TO RANK DATA SET
The demographic biases are real in the German Credit data, but the LTR task is simulated. There are no standard LTR data sets with demographic biases, so we consider Microsoft's 's Learning to Rank (MSLR) data set (Qin & Liu, 2013) with an artificial algorithmic faimesss concern dealing with webpage quality following Yadav et al. (2019). The data set consists of query-web page pairs from search engine with nearly 140 features with integral relevance scores. To apply Fair-PG-Rank, following Yadav et al. (2019), the protected binary attribute is whether a web page is high or low quality defined by the 40th percentile of quality scores (feature 133). For the fair metrie, the sensitive subspace is spanned by the ridge regression coefficients for predicting the quality score (feature 133) based on all features and the standard basis vector corresponding to the quality score.
Comparison metrics Again we use average stochastic NDCG to measure accuracy, and the dispartiy of group exposure where the groups are high and low quality web pages. To assess individual fairness, we use the same set-up as in the German Credit experiments except the hypothetical for each test query q is the closest query q' A q with respect to the fair metric over the train and test set.
Results Figure shows the fairesss and accuracy trade-off on the test set. Fair-PG-Rank becomes unstable with large fair regularization as can drop below a random ranking in NDCG. The left plot shows the Kendall's tau correlation between test queries and their hypotheticals. SenSTIR gracefully trades-off NDCG with Kendall's tau correlation unlike Fair-PG-Rank The right plot shows that SenSTIR also smoothly trades-off group fairness for NDCG. In contrast, the regularization strength increases, both NDCG and group exposure worsen for Fair-PG- PG-Rank, which was also observed by Yadav et al. (2019).
8

---

Published as a conference paper at ICLR 2021
0.700
0.700
0.675
0.675
0.650
0.650
d 0.600
0.625
0.625
0.600
0.575
0.575
0.550
0.550
Project
0.40
0.45
0.50 0.55 0.60 0.65
0.70
0.004
0.006
0.008
0.010
0.012
0.014
Kendall's Tau Correlation with Closest Hypothetical Queries
Group Exposure for Quality
Figure Individual (left) and group fairness (right) versus NDCG for the MSLR data set
CONCLUSION
We proposed SenSTIR, algorithm to learn provably individually fair LTR models with optimal transport-basce regularizer. This regularizer encourages the LTR model to produce similar ranking policies, i.c., distributions metric. Our notion of a fair ranking is complementary to prior definitions that require allocating exposure to items fairly with respect merit. In fact, empirically showed that enforcing individual fairness can lead to allocating exposure fairly for groups but allocating exposure fairly for groups does necessarily lead individually fair LTR models. An interesting future work direction is studying the fairness of LTR systems in the context of long-term effects (Mladenov et al., 2020).
rankings, for similar queries where similarity is defined by fair
ACKNOWLEDGEMENT
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 1830247 and 1916271. Any opinions. findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the NSF
REFERENCES
Abolfazl Asudeh, H. V. Jagadish, Julia Stoyanovich, and Gautam Das. Designing fair ranking schemes. Proceedings of the 2019 International Conference on Management of Data, SIG- New York, NY, USA, 2019. Association for Computing Machinery.
MOD '19, pp. ISBN 9781450356435. doi: 00.1145/3299899.330077 URL httpt::////ot http///oo...rg/..1115/////////// 3299869 9. 3300079.
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 2018.
Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. Equity of Attention: Amortizing Individual Fairness in Rankings. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR 18, pp. 405 414, Ann Arbor, MI, USA, June 2018. Association for Computing Machinery. ISBN 978- 105-1--503-565777 doi: 10.1 10.1145/3209978.222 32000999.9...........
Carlos Castillo. Fairness and Transparency in Ranking. ACM SIGIR Forum, 52(2):64-71, January 2019. ISSN 0163-5840, doi: 10. 10.11453308744330855
L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. International Colloquium on Automata, Languages, and Programming, 2018. URL http://
arxiv. org/ abs 1704. 06840.
L. Elisa Celis, Anay Mehrotra, and Nisheeth K. Vishnoi. Interventions for ranking in the presence of implicit bias. In Proceedings of the 2020 Conference Fairness, Accountability. and Trunsparency, F '20, pp. 369-380, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781 9781450369367,
10. 10.1145/3351095.337788 URL https:/ /ooi /o./ 1145/
335109 0955009..0 3372858.
Jeffrey Dastin. Amazon scraps secret Al recruiting tool that showed bias against women. Reuters, October 2018.

---

Published as a conference paper at ICLR 2021
Dheeru Dua and Casey Graff. UCI machine learning repository. https://archiv/e ics.iiieeiii........... uci. edu/m1/ datp//daasesss...mm adult, 2017. URL htttp://archive.iiee www. eeuiieedmmm.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Faireess through awareness. In Proceedings of the 3rd Innovations Theoretical Computer Science Conference, ITCS '12, pp. 214-226, New York. NY, USA. 2012. Association for Computing Machinery. ISBN 9781450311151 doi: 10. 1145/2090223..2000255. URL https: /tt////oi.../// wwwpiiooo///..11.0 2090236. 20 2090255.
Sahaj Garg, Vincent Perot, Nicole Limtiaco, Ankur Taly, Ed H. Chi, and Alex Beutel, Counterfactual Fairness in Text Classification through Robustness. arXiv: /809. 106/0 [cs, stat), September 2018.
Sahin Cem Geyik, Stuart Ambler, and Krishnaram Kenthapadi. Fairness-aware ranking in search & recommendation systems with application to linkedin talent search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2221-2231,
2019.
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Sys- tems 29, pp. 3315-3323. 2016. URL http:/ /atper/papers..o https.ccppappp 6374 1574-equality-oo oww.oooootttttt-iinn innrruiitt-----seeriidd learning. ppdfi
Christina Ilvento. Metric Learning for Individual Fairness. Foundations of Responsible Computing, June 2020.
Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2009 2nd International Conference Computer, Control and Communication, pp. 1-6. IEEE, 2009.
Harini Kamnan, Alexey Kurakin, and lan Goodfellow. Adversarial Logit Pairing. arXiv:1803.06373 [cs, stat], March 2018.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
Caitlin Kuhlman, MaryAnn Van Valkenbbnu and Elke Rundensteiner. Fare: Diagnostics for fair rank- ing using pairwise error metrics. In The World Wide Web Conference, WWW 199, pp. 2936-2942, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 4503667766748 doi: 10.1 00.1145/3308558.31133 333188885558333444..3333 URL https: /ttpt:::://...ooooo http://o....ogg/.///// /1.gg/1..00 1145/ 3308558 .33.33311330 3313443.
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual Fairness. 1rXiv:1703.0663 [cs, stat), March 2018.
Jacho
Lee and Maxim Raginsky. Minimax statistical learning with wasserstein dis- tances. In Advances in Neural Information Processing Systems 31, pp. 2687- 2696. Curran Associates, Inc., 2018 URL http: //tp:::/pppprrsaee waips.cc/paper. pdf.
Martin Mladenov, Elliot Creager, Omer Ben-Porat, Kevin Swersky, Richard Zemel, and Craig Boutilier. Optimizing long-term social welfare in recommender systems:a constrained matching approach. In Proceedings of the Thirty-sevnnth International Conference Machine Learning (ICMI-20), Vienna, Austria, 2020. to appear.
Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun. Two simple ways to learn individual fairness metrics from data. In International Conference on Machine Learning, 2020.
Robin I. Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), 24(2):193-202, 1975.
Tao Qin and Tie- Yan Liu. Introducing LETOR 4.0 datasets. http://axxiv.ozg// /1306. /100 2597.
2597, 2013. URL httttttpp////xii/
10

---

Published as a conference paper at ICLR 2021
Ya' acov Ritov, Yuekai Sun, and Ruofei Zhao. On conditional parity notion of ton-discrimination in machine learning. arXiv:1706.08511 08579 [cs, stat]. June 2017.
Piotr Sapiezynski. Wesley Zeng, Ronald E. Robertson, Alan Mislove, and Christo Wilson. Quantifying the Impact of User Attention Fair Group Representation in Ranked Lists. In Proceedings of the Workshop on Fairness, Accountability, Transparency, Ethics, and Society on the Web (FATES 19), San Francisco, CA, USA, May 2019.
Ashudeep Singh and Thorsten Joachims. Fairness of Exposure in Rankings. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining -DD '18, pp. doi: 10.1 10.1145/3219819.32220
2219-2228, 2018.
Ashudeep Singh and Thorsten Joachims. Policy learning for fairness rank- ing. In Advances in Neural Information Processing Systems 32, pp. 5426-5436. Curran Associates, Inc., 2019. URL htttp:/ppapes wwsssniissc.mm cctpp.c//pappr////////////ppp 8782-pon lea--oolcc--larnng-----e--e
Hanchen Wang, Nina Grgic-Hlaca, Preethi Lahoti, Krishna P. Gummadi, and Adrian Weller. An Empirical Study on Learning Fairness Metrics for COMPAS Data with Human Supervision. NeurIPS HCML Workshop, October 2019.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, Machine learning, 8(3-4):229-256, 1992.
Yongkai Wu, Lu Zhang, and Xintao Wu. On discrimination discovery and removal in ranked data using causal graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '18, pp. 2536-2544, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781 9781450355520, doi: 10.145/3219889932200977 URL www.ttttp///e /woi org /00 1145/1142//2 9819. 3220087.
Himank Yadav, Zhengxiao Du, and Thorsten Joachims. Fair Learning-to-Rant from Implicit Feed- back, arXiv: /91 1. .80054 [cs, stat), November 2019.
Fanny Yang. Zuowen Wang. and Christina Meinz. coariance-induciin regularization using worst-case transformations suffices to boost accuracy and spatial robustness. In Advances in Neural Information Processing Systems 32. pp. 14785-14796. Curran Associates, Inc., 2019a.
Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In Proceedings of the 29th International Conference on Scientific and Statistical Database Management, SSDBM '17, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 4503552228 doi:
10. 04.114/3085554430855222 URL https: /ooi. org/10..//.. 1111111///35550 0ww.8855554080055220 3085526.
Ke Yang, Vasilis Gkatzelis, and Julia Stoyanovich. Balanced ranking with diversity constraints. IJCAI International Join! Conference on Artificial Intelligence, 2019b.
Mikhail Yurochkin and Yuekai Sun. SenSel: Sensitive set invariance for enforcing individual fairness. In International Conference on Learning Representations (ICLR), 2021.
Mikhail Yurochkin, Amanda Bower, and Yuckai Sun. Training individually fair ML models with sensitive subspace robustness. In International Conference on Learning Representations, Addis Ababa, Ethiopia, 2020.
Meike Zehlike and Carlos Castillo. Reducing disparate exposure in ranking: A learning to rank approach. In Proceedings The Web Conference 2020, WWW '20, pp. 2849-2855, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 978 9781450370233. doi: 10.1145/ 3366424.3380044 URL httph::tt///t /ttp:://dooooooooo /ttttts::/o...oo/////... http//1.1111511 111.11336614444444 33313333344444338048888 3380048.
Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza- Yates. Fa ir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 1569-11778, 2017.
11

---

Published as a conference paper at ICLR 2021
A PROOFS OF THEORETICAL RESULTS
Theorem A.1 (Theorem 4.1). If assumptions Al and A2 hold and (D) is finite, then with probability least -
1/2
48(J(D) +5
log 2
Dyna
sup [R( R(h) S WEW
+ Dy
+
Vn.
2n
Proof. For queries q. 9 let
1 a Edpld II(
n J
A(q. (II A(X X) I(x,)
Alay
n
n
Let III aag Eu Euldx (xldx(X,X)) X') and observe that by assumption A2 and the definition of dQ and do we have
d) do(a.0))
inf
Exldx(XXxX)) inf En(dx(X,
πEA(1.0")
NEA(a.0")
inf
En(dx(X,X)) (X) En-(dx [dx (X, X')]
NEA((1.7)
S En- (dx X') En- (xx(XXX))
Enr (Xx, - -x,
S nd-
Similarly,
dola.d') - do(a,d') s (dxx(x(XxxX)) X') - dx(XXXX)) nds
follows that
(dola, do(a. (a(9.99)1= n/-
(A.1)
Next, we will bound the difference (i((h) R(h)). To lighten the notation, write h, h' for h h()(d")), M(b(d") )). From the dual representation of R(h) and R(hh) have
R(hh) R(h)
inf (de + E Bg a))) inf ()e + E Eg 4))
(A.2)
A20
X
inf inf(De (de + E E ( (h, 4)]} x B (h,
(A.3)
A20
I E o ff2- (h, 9)] - E (rx- (h,
(A.4)
E g [rx- (h, 9)] E /ra- (h, + E B (h, rx- (h,
(A.5)
To bound the last term, note that |fx- (h, g) rx- Tx- (h. 9)) -x)d((() p
(h, ("dela
(A.6)
s X sup(lee(a -e(a.
(A.7)
< X'n
(A.8)
Combining (A.8) and (A.5) yields
R(h) - R(h) < E (h, Eg-o(rx-
(h, + A
(A.9)
Using similar argument,
R(h) R(h)) & En-olri. (h, - E (1, + X na-
(A.10)
12

---

Published as a conference paper at ICLR 2021
To find an upper bound on X², observe that r사 (h )) 2 0 for all h E H, 2 as
ra(h, g) = sup (dy 1/) Ado(a, d'Ex'
2 dy(h, 11) -)) = 0.
Thus
N S X Eg (h, R(h) s Dy.
Rearranging the above yields X v Px and the same upper bound is also valid for X by the same argument.
Combining inequalities (A.9.A.10) and the bound on \ 2*, we can write
E p En-of(e) + Dyna
[R(h) R(h) & sup /EF
where = (r)(1),) A E [0, fJ. h E H}. A standard concentration argument proves
48(J(D)
+c-1DxDy + Dy
log 2 8 2n
sup SEF
E (f) - of) <
Vn
with probability at least - t. This completes the proof of the theorem.
The main technical novelty in this proof is the bound on A, terms of the diameter of the output space. This restricts the set of possible c-transformed loss function class, thereby allowing to appeal to standard techniques from empirical process theory to obtain uniform convergence results. Prior work in this area (e.g. Lee Raginsky (2018)) relies on smoothness properties of the loss instead of the geometric properties of the output space, but this precludes non-smooth output metrics.
B EXPERIMENTS
All experiments were ran cluster of CPUS. We do not require a GPU.
B. DATA SETS AND PRE-PROCESSING
Synthetic Synthetic data is generated as described in the main text such that there are 100 queries in the training set and 100 queries in the test set.
German Credit The German Credit data set (Dua & Graff, 2017) consists of 1000 individuals with binary labels indicating if they are credit worthy or not. We use the version of the German Credit data set that Singh & Joachims (2019) used found at https: //s:://wer /www. kaggle. com/ ///uuii miim// ge geran-credd
com/ucin
In particular, this version of the Geramn Credit data set only uses the follow- ing features: age (integer), sex (binary, does not include any marital status information unlike the original data set), job (categorical), housing (categorical), savings account (categor- ical), checking account (integer), credit amount (integer), duration (integer), and purpose (categorical). See Dua & Graff (2017) for an explanation of each feature.
Categorical features are the only features with missing data, category, The following features are standardized by subtracting the mean and dividing by the standard deviation (before this data is turned into LTR data): age, duration, and credit amount. The remaining binary and categorical features are one hot encoded.
treat missing data its
We use 80/20 train/test split of the original 1000 data points, and then sample from the train- ing/testing set with replacement to build the LTR data as discussed in the main text. For our experiments, 10 random train/test splits.
13

---

Published as a conference paper at ICLR 2021
Microsoft Learning to Rank The Microsoft Learning to Rank data set (Qin & Liu, 2013) consists of query-web page pairs each of which has 136 features and integral relevance scores in [0, 4]. We use Fold I's train/validationntest split. Following Yadav et al. (2019), use the data in Fold I and adopt the given train/validationntees split. The data and feature descriptions can be found at https: www.//wmmmmmmmmmmmm............m .ii crosoft. com comm/en-uss resea rch ptrpprooeetc montttmssrr/// We remove the QualityScore feature (feature 132) since we use the QualityScore2 (feature 133) feature to learn the fair metric, and it appears based on the description of these features, they are very similar. We standardize the remaining features (except for the features corresponding to Boolear model, iee. features 96-100, which are binary) by subtracting the mean and dividing by the standard deviation. Following Yadav et al. (2019), we remove any queries with less than 20 web pages. Furthermore, we only consider queries that have at least one web page with a relevance of 4. For each query, we sample 20 web pages without replacement until at least one of the 20 sampled web pages has relevance of 4. After pre pre-processing, there are 33,060 train queries, 1 11,600 validation queries, and 11,200 test queries.
B.2 COMPARISON METRICS
Let be a ranking (i.e. permutation) of a set of n items that are enumerated such that r(i) E [n] is the position of the i-th item in the ranking and (x) [n] is the item that ranked i-th. Let re), be the relevance of item given query q.
Normalized Discounted Cumulative Gain (NDCG) Let S, be the set of all rankings on items. The discounted cumulative gain (DCG) of a ranking r is
a 2rel,(r (00) -1
DCG(r)
log2 (i + 1)
The NDCG of ranking is
DCG(r)
max,'ss DCG(r")
Because we learn a distribution over rankings and the number of rankings is too large, we cannot compute the expected value of the NDCG for given query. Thus, for each query in the test set, we sample N rankings (where N = 10 for synthetic data, N = 25 for German credit data, and N = 32 for Microsoft Learning to Rank data) from the Placket-Luce distribution, compute the NDCG for each of these rankings, and then take average. We refer to this quantity the stochastic NDCG.
Kendall's tau correlation
Let r and r' be two rankings on n items. Then
KT(r,'))
sign(r() - (r))))ig((((((
is the Kendall's tau correlation between two rankings.
(Disparity of) Group exposure This definition was first proposed by Singh & Joachims (2019). Assume each item belongs to one of two groups. Let G, (respectively Go) be the set of items for query q that belongs group (respectively group 0). For E {0, 1), let Mc. द.. Evec, (d). which is referred to as the merit of group for query q. For a ranking r and for i E {0, 1}. let (.... |..| Edeg, (T Because we learn distribution over rankings and the number of rankings is too large, we cannot compute the expected value of v, (G.) over this distribution. Instead, we sample N rankings (where again N 10 for synthetic data, N 25 for German credit data, and N = 32 for Microsoft Learning to Rank data) from the Placket-Luce model. Let R2 be the set of these N sampled rankings for query q. Then the stochastic disparity of group exposure for query q is
ErER, (Go) Mco
1. ErER, or (Gi) Man
max
0,
if Mc. 2 MG. > 0
EreR, (r() Mc.
N Erer, (ro) Mao
max 0,
if < Mc. < Mc
if Mf, = 0 or Mc, = 0.
14

---

Published as a conference paper at ICLR 2021
In the language of Singh & Joachims (2019), use the identity function for merit, and set the position bias at position j to be [1+J] just as they did.
B.3 SENSTIR IMPLEMENTATION DETAILS
We implement SenSTIR in TensorFlow and the Python POT package compute the fair distance between queries and to compute Equation (3.4), which requires solving optimal transport problems. Throughout this section, variable names from our code italicized, and the abbreviation we use to refer to these variables/hyperaaaametess are followed in parenthesis.
Fair regularizer optimization Recall that all of the experiments, the fair metric d, on items is the Euclidean distance of the data projected onto the orthogonal complement of subspace. order to optimize for the fair regularizer in Equation (SenSTIR), first we optimize over this subspace, and refer to this step as the subspace attack. Note, the distance between the original queries and the resulting adversarial queries in the subspace is O. Second, we use the resulting adversarial queries in the subspace an initialization the fill attack, i.e. we find adversarial queries that have non-zen zero fair distance to the original queries. We implement both using the Adam optimizer (Kingma & Ba, 2015).
Learning rates As mentioned above, we use the Adam optimizer to optimize the fair regularizer. For the subspace attack, we set the learning rate to adv_ (tt_sttp(ass) and train for adv eepcc((ac)))) epochs, and for the full attack, we set the learning rate 12 attack(ffs) and train for adv_ adv_epoch epoch full( fe) epochs. We also use the Adam optimizer with learning rate of .001 to learn the parameters of the score function hg.
Fair start Our code allows training the baseline (i.e. when p 0) for percentage- given by (air_start(frs) the total number of epochs before the optimization includes the fair regularizer.
Using baseline for variance reduction Following Singh Joachims (2019), in the gradient estimate of the empirical version of 2 [U[T 4)] in Equation (SenSTIR), subtract off baseline term b(g) for each query q, where b(q) is the average utility (rr g) over the Monte Carlo samples for the query q. This counteracts the high variance in the gradient estimate (Williams, 1992).
Tables and E stands for the total number of epochs used to update the score function ho. B stands for the batch size, 12 stands for the fe regularization strength of the weights, and MC stands for the number of Monte Carlo samples used to estimate the gradient of the empirical version of B [U(m 4)] in Equation (SenSTIR) for each query.
Other hyperparameters
B.4 HYPERPARAMETERS
For the synthetic data, use train/test split. For the German experiments, 10 random train/test splits all of which use the same hyperparameters. For the Microsoft experiments, we pick hyperparameters the validation set (where the range of hyperparameters considered are reported below) based on the trade-off of stochastic NDCG and individual (respectively group) faimesss for SenSTIR (respectively Fair-PG-Rank), and report the comparison metrics the test set.
Fair metric For the synthetic data experiments, we use sklearn's logistic regression solver to classify majority and minority individuals with 1/100 & regularization strength. For German and Microsoft,
sklearn's Ri RidgeCV solver with the default hyperparameters and quality web page score, respectively. For the German experiments, when predicting age, each individual is represented in the training data exactly once, regardless of the number of queries that an individual appears in.
predict age
SenSTIR For every experiment, all weights are initialized by picking numbers in [-00001, .0001] uniformly at random, À in Algorithm 1 is always initialized with 2, and the learn ing rate for Adam for the score function he is always .001. For synthetic data, the fair regularization strength P varied in (000.,,0001). For German, P is varied in
15

---

Published as a conference paper at ICLR 2021
{.001, 001, 0.02, 0.03, 0.04, 0.05, 02
0.16.
0.17, 0.18, 0.19, 0.28, 0.37, 0.46, 0.55, 215.::....4.88.822220.002222331. 6, 7,8,9, 10, 50, 100). For 66, 1.). We report results for all
Microsoft, p is varied in (.00001, 00,.00000..0000,,.000000.. choices of
See Table for the remaining values of hyperparameters where the column names have been defined in the previous section except for which refers to c in the definition of the fair regularizer. For Microsoft, the best performing hyperparameters on the validation regularization parameter for the weights are varied in (_001, .0001, 0}, as is varied in and fe are varied in {20, 40}, and varied in f1..1..00
are reported where the &
de
Table 1: SenSTIR hyperparameter choices
E
B
fs
fe
frs
12
MC
Synthetic
2K
0.001
20
0.001
0.001
20
10
German
20K
10
.01
20
1
0.001
20
.1
25
Microsoft
68K
10
.01
40
.01
0.001
40
.1
0.001
32
Baseline and Project For the baseline (i.e. p O with no fair regularization) and project baseline, we use the same number of epochs, batch sizes, Monte Carlo samples, and &g regularization in Table I for SenSTIR. Furthermore, we use the same weight initialization and learning rate for Adam as in the SenSTIR experiments.
Fair-PG-Rank We the implementation found https: pettts://githiee thub. com asw.dee// Fair-Pae PGRank for the synthetic and German experiments, whereas we use our own implementa- tion for the Microsoft experiments because we could not get their code run on this data. They use Adam for optimization, and the learning rate is .1 for the synthetic data and .001 for Ger- man and Microsoft. Let À refer the Fair-PG-Ran A = 25. For German, is varied in {.1, 1.5,, 5, 2, 2.5, 3, 3.5, 4}. For Microsoft, À is varied in 200,,, .5, 2, 3,3,,,45 5, 6, 7, 8, 9, 10, 50, 100, 500, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, 650, 700, 750, 800, 850, 900, 950, 1000). We report results for all choices of X. See Table which summarizes the remaining hyperparameter choices.
fair regularization strength. For synthetic,
Table 2: Fair-PG-Raan PG-Rank hyperparameter choices
E
B
12
MC
Synthetic
0
10
German
100
1
0
25
Microsoft
68K
10
.01
32
16


Reviews:
[{"review_id": "bhxdTs20MFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper uses an optimal-transport approach to ensure that two similar items that differ only on a sensitive feature (e.g., gender) are ranked similarly. In this way, individual items are treated fairly. For example, if two job candidates differ in gender but are otherwise similar, the job search engine should rank them similarly. The authors employ an optimization problem they call SenSTIR where the objective is maximizing expected utility minus a regularization term, and where the fairness properties are encoded in the regularization term. The regularization term is weighted by rho, a parameter than increases fairness as it increases. The regularization term itself encourages similar queries to lead to similar rankings. The authors appeal to duality to derive a way to run stochastic optimization on their problem. They prove one theorem that I don't fully understand. Then they test their method on three data sets: simulated data used in related work, German credit data used in prior work, and Microsoft learning to rank data. They compare to training without fairness, a projection method, Fair-PG-Rank, and random. They try different values of rho, showing the larger rho indeed leads sensibly to more individually fair rankings. They use the NDCG metric for accuracy and Kendall's tau correlation for fairness. They show that they get individual fairness by design and group fairness \"for free\". In contrast, Fair-PG-Rank design for group fairness does poorly on individual fairness.\n\nThe paper is well written and includes an excellent and extensive survey of related work. The authors approach seems reasonable and their analysis and experiments are convincing. I especially like Figure 2 -- this is a nice visualization of individual fairness and was very helpful.\n\nOne quibble I had is that the authors said that individual fairness is sufficient for group fairness, or at least \"can be sufficient\". Usually \"sufficient\" is a theoretical statement that always holds. Later, it's clear that this is an empirical finding on the particular data sets tried. I'd like the authors to be more careful about using the word \"sufficient\".\n\nOne question I had is how this would generalize to multiple sensitive features? To be practical, that generalization will be valuable.\n\nCan the authors say something about computational complexity? Is the problem 2.4 NP-hard? Is Algorithm 1 an approximation? What is the running time of Algorithm 1 both in theory and in the experiments (seconds). How does the running time of SenSTIR compare with Fair-PG-Rank?\n\nA higher level question is why the authors did not test fair supervised learning algorithms. Yes, as the authors point out, supervised learning is not meant for LTR (and SL doesn't define a fair distance on sets of items and uses different metrics, for example, L2 loss versus NDCG), but a supervised learning method can produce a relevance score. So the experiments could try one of these approaches, and probably should. (I didn't quite understand the point about not defining a distance on sets.)\n\nMinor note: \n\nReferences: Some of the references should be cleaned up and made more uniform. For example, the reference \"Ke Yang, Vasilis Gkatzelis, and Julia Stoyanovich\" repeats the conference title four times.", "extra_scores": {}, "extra_text": {}}, {"review_id": "bXsbyBuf9An", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper tackles the problem of providing rankings that are \"fair\" to individual items being ranked as opposed to groups of items as in previous work on fair ranking.\n\nI have three major issues with the paper:\n\n1- A practical objection to the approach is the use of randomized rankers to get around the important issue that ranking is by its very nature unfair to individuals. To take the example of job applications used in the paper, if 100 people are applying to one job and a ranked list of the candidates is presented to the person making the hiring decision, then well one person will be at the top and one person at the bottom. Now, if there are 100 job openings and the same 100 people apply to all of them, then yes randomizing the results can deal with this issue, but then fairness is not even an issue because everyone gets a job and there won't be any complaints. In other words, fairness is only an issue is there is a lack of resources, which means that randomization doesn't really solve the issue, but just gives one the illusion that it is resolved. I feel like the authors haven't spent too much time thinking about these issues and that they're mostly thinking about the unbounded query scenario. But, even in that setting, there are very few products where the people in charge would be willing to randomize the ranked items because that would result in degradation in user experience (i.e. in this example, the person doing the hiring). There have been some recent attempts to address the planning issue that comes up when dealing with this, so I'd suggest for the authors to have a look at papers like this one: https://arxiv.org/abs/2008.00104\n\n2- A more fundamental issue is that I just can't find a proper metric for individual fairness in the paper. The only proposal is a comparison between the outputs of the ranker before and after altering some features fed into it. This way of evaluating rankers makes no sense to me at all because a really easy way for a ranker to appear fair is by not using the feature being modified (e.g. age or gender) directly, but inferring it from the remaining features. I think the issue is that the authors are confused by the subtle but crucially important distinction between losses and metrics. You're allowed to use whatever information you like when you're designing your loss, but the final evaluation should not rely on the model, but just its output.\n\n3- Finally, on the MSLR dataset, it's important to include LambdaMART as a baseline to report the degradation in NDCG incurred as a result of the fairness constraints. I should point out that there are multiple implementations of LambdaMART out there and it's important to used the best one, which is the one included in the LightGBM package. You can find some results for the MSLR dataset in this paper among others: https://dl.acm.org/doi/pdf/10.1145/3336191.3371844\n\nGiven these issues, I don't think the paper is ready to be published and I encourage the authors to think carefully about their problem definition and experimental setup before resubmitting the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_ckRsDkn29J", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors extended individual fairness approach to the domain of learning to rank domain. This paper proposes a method for training individually fair learning to rank models by making use of optimal transport-based regularizer.\n\nThis work appears to be an extension to Yurochkin et. al. 2020 ICLR SenSR paper in which fair metric was learned from data. While that papers focused on training individually fair ML models by casting the problem as training supervised ML models that are robust to sensitive perturbations, this paper extended the idea to individual fair ranking that are invariant to sensitive perturbations of features of ranked items. \n\n###############\nThis paper is well written. The code and the datasets used for the experimentation have been provided. \nI vote to accept this paper. I like the approach presented in this paper for solving this very important issue. \n\n###############\nThe importance of the problem of dealing with bias in search results cannot be understated. Example of the issue of fairness in search ranking: how to ensure that minority candidates (or candidates of opposite gender) would be fairly ranked together with other job candidates when having similar qualifications. This paper attempts to find a solution to this and similar type-problems.\n\n\n###############\nIn this paper both theoretical and empirical results were presented. The authors showed that using their optimal transport-based regularizer leads to certified individual fair LTR models.\nThe results were demonstrated on several datasets: synthetic and two publicly available datasets. Results showed that authors’ method exhibited ranking stability with respect to sensitive perturbations when compared with a state-of-the-art fair LTR model.\nImportantly, the authors showed empirically that individual fairness implied group fairness by not vice versa. \n\n###############\nRecommendations:\nOn page 4 section 3 authors reference Theorem 2.3 but in the citation there is no Theorem 2.3.  In the citation there is a relevant equation 2.3 and a note that states this equation comes from another paper. So I believe that this should probably needs to be cited differently (by citing Blanchet & Murthy original paper - assuming they were the first to prove this theorem) \nAdditionally, authors keep citing Yurochkin & Sun ArXiv pre-paper even through it has already appeared at ICLR 2020. \n\nQuestion:\nMy only question for the authors is how easy would it be to learn fair metric in a typical application for LTR models? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "T5fyUFKLny", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper address the problem of fair ranking. The authors use a notion of individual fairness, meaning that two similar inputs should receive similar outputs. The presented method uses a transport based regularizer to reach fairness.\nThe authors present a new Algorithm SenSTIR and test it on a synthetic and two real world datasets\n\n\nThe paper is nicely written and readable, however the maths are hard to follow and little intuition is given.\nI didn't find an explanation of how the counterfactuals are computed. This is a difficult task that need many assumptions and hypotheses, just \"flipping\" the gender is hardly enough as gender is correlated to all others attributes.\nThe legend of figure 3 and 4 are not the same \"Kendall's Tau Correlation with Counterfactuals\" and \"Counterfactual Kendall's Tau Correlation\", is it the same metric or something changed ?\n\nIn figure 2, Fair-PG-Rank seems to perform very poorly, worse than baseline. As it is the state of the art method, I think some explanation of why it is the case are needed.\n\nFinally most of the paper is based on work done in Yurochkin &Sun 2020 and Yurochkin et al 2020. I think that the authors should explicit the link between the current paper and those two citations. I also think that the main paper should be self content and that Theorem 2.3 of Yurochkin &Sun 2020 should be written down with its hypotheses.\n\n---- After reading answers ------\n\nI'm still not convinced by the computation of counterfactuals, I still disagree with \"flipping\" the private attribute, because then the naive solution of removing them from the input of the model would appear perfectly fair. This approach seems to forgot about potential proxies, that are not the private attribute, but that a model can learn on and be biases.\nMoreover, if I understand correctly, the same computation of counterfactuals is used for the model and the test set. This is unfair as SenSTIR is the only algorithm to use the same kind of counterfactual data than the one used for the evaluation.\n\nI think this is a crucial point, I prefer to lower my rating to 5.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on individual fair ranking and proposes an approach for that based on optimal transport. The reviewers are in general positive about the paper, however, there are a a couple of concerns that I believe should be addressed before publication.

First, I find the treatment of the term "counterfactual" misleading in the paper.  Counterfactual fairness has been proposed in the literature as a causal notion of individual fairness. However, as far as I can see in the paper, there is not such a causal treatment of counterfactuals in the paper. Thus, I suggest the authors to reconsider their treatment of counterfactuals in the paper, as it may trigger confusion. Second, I also agree with R1 that  it is unfair as SenSTIR is the only algorithm to use the same kind of "counterfactual" data than the one used for the evaluation. 


Decision: Accept (Poster)