Fair Ranking with Noisy Protected Attributes
Authors: Anay Mehrotra
Nisheeth K Vishnoi
Venue: NeurIPS 2022 Accept (2022)
Keywords: fair ranking
group fairness
stochastic noise in protected attributes

Abstract: The fair-ranking problem, which asks to rank a given set of items to maximize utility subject to group fairness constraints, has received attention in the fairness, information retrieval, and machine learning literature. Recent works, however, observe that errors in socially-salient (including protected) attributes of items can significantly undermine fairness guarantees of existing fair-ranking algorithms and raise the problem of mitigating the effect of such errors. We study the fair-ranking problem under a model where socially-salient attributes of items are randomly and independently perturbed. We present a fair-ranking framework that incorporates group fairness requirements along with probabilistic information about perturbations in socially-salient attributes. We provide provable guarantees on the fairness and utility attainable by our framework and show that it is information-theoretically impossible to significantly beat these guarantees. Our framework works for multiple non-disjoint  attributes and a general class of fairness constraints that includes proportional and equal representation. Empirically, we observe that, compared to baselines, our algorithm outputs rankings with higher fairness, and has a similar or better fairness-utility trade-off compared to baselines.

Fair Ranking with Noisy Protected Attributes
Anay Mehrotra Yale University
Nisheeth K. Vishnoi Yale University
Abstract
The fair-ranking problem, which asks to rank a given set of items to maximize utility subject to group fairness constraints, has received attention in the fairness, information retrieval, and machine learning literature. Recent works, however, observe that errors in socially-salient (including protected) attributes of items can significantly undermine fairness guarantees of existing fair-ranking algorithms and raise the problem of mitigating the effect of such errors. We study the fair- ranking problem under a model where sucially-saliem attributes of items are randomly and independently perturbed. We present fair-ranking framework that incorporates group fairness requirements along with probabilistic information about perturbations in socially-salient attributes. We provide provable guarantees the fairness and utility attainable by our framework and show that it is information- theoretically impossible to significantly beat these guarantees. Our framework works for multiple non-disjoint attributes and a general class of faimnss constraints that includes proportional and equal representation. Empirically, we observe that, compared to baselines, our algorithm outputs rankings with higher fairness, and has a similar or better Eairnsss-ttiltty trade-off compared to baselines.
Introduction
Given a query and a set of m items, ranking problems require one output an ordering of small subset of items in decreasing order of relevance to the query. Such ranking problems have been extensively studied in the information retrieval (46) and the machine learning [45) literature, and algorithms for them are used in applications such as search engines, personalized feed generators, and online recruiting platforms 44] 12, [). Several studies have observed that when the outputs of ranking algorithms consumed by end-users, e.g., image results for couupattio-relatee queries, articles with different political leanings, and job applicants in online recruiting, the outputs can mislead or alter their perceptions about socially-salicn opportunities available to individuals (32. A reason is that relevance (or utilities) input to ranking algo- rithms may be influenced by human societal biases, leading output rankings that skew representa- tions of socially-salient, and often legally-protected, groups such as women and Black people (55).
groups [38], polarize their opinions [24] [50], and affect economic
A growing number of works aim to make the output of ranking algorithms fair with respect to socially- salient attributes 77| 75 (8). As for notions of fairness, in the case when each item belongs to one of two socially-salien groups (Gi or G2), equal representation requires that, for every k, (roughly) 2 items from each of G and G2 appear in the first k positions of the output ranking. Proportional
representation requires that at most k- |Gel items from each G3 appear in the first & positions. Fairness criteria that generalize proportional representation and involve p groups GI...., Gp. where each item may belong to multiple groups, have also been considered: Given values Uke. they require that most URe items from G2 appear in the first k positions of the output ranking [61 18] One set
of works in the fair-ranking literature tries to improve fairnsss in utility-estimation (72 62 73 51).
Such approaches have the benefit that changes to the existing ranking algorithm are necessary but they may be unable to guarantee that the output ranking satisfies the required fairness criteria
27 Another set of works use the given utilities as-it-is and change the ranking algorithm to output
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the ranking with the highest utility subject to satisfying the specified faimess criteria by including them as fairness constraints [6 6
I8 27 30]. While these latter approaches can guarantee fairness, they require coming up with new algorithms to solve the arising constrained ranking problems. Both
approaches, however, rely on knowledge of the socially-salient attributes of the items [56].
Assuming precise access to socially-salient attributes is reasonable in some contexts and has led to successful deployment of fair-ranking frameworks; see [27]. However, in several contexts, socially- salient attributes can be erroneous, missing, or known only probabilistically. For instance, errors can arise due to misreporting, which is common concern with self-reported attributes 4 Attributes can also be missing, as is the case with images in web-search or in settings where it is illegal to collect certain socially-salien attributes (20). Often attributes are predicted using ML-classifiers, but such prediction has inaccuracies [O]. In such cases, one can calibrate the confidence scores of classifiers to derive (aggregate) probabilistic information about the true attributes (35) Moreover, probabilistic information about socially- --saiientt (protected) attributes can be sometimes computed from other attributes. For instance, name and location of an individual, combined with aggregate census data may be used to get conditional distribution of their race [23] 36 20] Even accurate attributes may be randomly and independently flipped to preserve user privacy, and the distribution of flipped attributes is determined by public parameters of, e.g., the randomized response mechanism [7 69]
We consider one such model (due to (5) to capture inaccuracies in socially-saliens attributes. Each item i belongs to the E-th group with a known probability Py.. For each item i, the distribution corresponding to Pizs over groups is assumed to be independent of corresponding distributions of other items. This model can be used in cases where these probabilities are available or can be derived, as in some of the aforementioned examples (see Section Supplementary AT) In other cases, e.g., when errors are strategic or adversarial, other models are needed. This model and its variants have also been used by works on designing fair algorithms in the presence of inaccuracies, for problems including classification
Several models of inaccuracies in data have been proposed 47 26
42 67 66 [1], sub-
set selection [88) and clustering 225 (Supplementary Material B briefly discusses these works).
In this noise model, while cooially-salien attributes are not explicitly specified, one could still use existing fair-ranking algorithms by first sampling groups for items from the given probabilities. Indeed, (2 evaluate existing fair-ranking algorithms on attributes obtained from the probabilities derived from MI. classifiers. They find that "errors (socially-salien attributes] can dramatically undermine fair-ranking algorithms" and can cause "[ "[non- aod-ddddvvantggedd groups] to become disadvantaged after a 'fair' re-ranking." " We confirm this observation on synthetic dataset when the goal is to finding ranking that satisfies equal representation (Section 5. We assigned each item the socially- salient group that is most likely and find that when existing fair-ranking algorithms (for equal representation) are run with this group information, they output rankings that significantly violate the equal representation criteria (Figure I.. Further, we mathematically analyze two natural methods to sample groups from probabilities and give examples where taking such information input, existing fair-ranking algorithms output rankings which provably violate the equal representation criteria (Supplementary Material C). Thus, new ideas are needed to design fair-ranking frameworks that can guarantee given faimess criteria under this noise model.
Our contributions. We present a fair-ranking framework that guarantees given fairness criteria when the socially-salient attributes assumed to follow the probabilistic noise model mentioned above. In particular, it finds a utility maximizing ranking subject to a class of constraints that only rely on given probability distributions (Program 7 These constraints relax the given fairness criteria by a carefully chosen factor: for equal representation, the relaxation is by roughly a 1 + vi multiplicative factor for position k for any k. Moreover, instead of sampling the attribute values and applying constraints on them, these constraints apply the golaxed-faimess criteria to the expected number of items from each group that appear in the first k positions. We show that these constraints ensure that any ranking approximately satisfying the given fairness criteria is feasible for them and any ranking feasible for them approximately satisfies the given fairness criteria (Theorem I... Our fair-ranking framework works for the general class of fairness criteria introduced earlier, which involve multiple overlapping groups GI...., Gp and upper bound URe for the ε-th group and k-th position (Theorem 4.1.. and for their position-wedd weighted versions (Theorem F.I
We show that our fair-ranking framework, besides nearly satisfying the given fairness criteria, has provably high utility (Theorem 4.1p. Complementing Theorem 4.1 we prove near-tightness of the fairness guarantee (Theorem 4.2 for equal representation fairness criteria, this results shows that it
2

---

is information theoretically impossible to output ranking that violates this criteria by less than a multiplicative factor of 1+ Ō( ) at the k-th position for any k. Finally, we give polynomial- algorithm to approximately solve Program (Theorem
Empirically, we evaluate our framework on both synthetic and real-world data against standard metrics like weighted-risk difference (RD) that measure deviation from specific fairness criteria (Section [ We compare its performance to key baselines [18 61 (7 48 on both single and multiple attributes. In all simulations, compared to baselines, framework has a higher maximum fairness (2-10% for RD; Figures to B) and a similar/better maimess-utility trade-off (Figures 2 and 14 I6
2 Related work
Work on automated information retrieval dates back to 1940s
43 21 Since then the IR literature has devoted a significant effort in measuring relevance of items to specific queries across different tasks: including, web search 77). personalization (34), and product rating [22]: also refer the reader to [46] and the references therein. In the last three decades, works in the ML literature have also made significant contributions to relevance-estimation [45]. by proposing methods that: (1) supplement traditional IR approaches, e.g., by automatically tuning their prev-opre hard to tune- uune-parameters
[65 and by improving their efficiency through clustering- based techniques [64] 3], and (2) substitute traditional IR approaches by neural-network based models to predict item relevance 12 68 g).
Fair ranking. Existing works on the fair-ranking problem take diverse approaches: Among works that de-bias utilities, different approaches include, post-procsssing the utilities so that the post-processed utilities satisfy some fairness requirement [7]], introducing "fairness penalty" in the objective function used to train learning-to-ran -t-rin models [62 73 49], and modifying feature representations generated by up-stream algorithms so that the utilities learned from the modified representations satisfy some fairness requirements (72). Works that alter the ranking algorithms can also be further categorized into those which satisfy the constraints for each ranking 18 70 27 30) and those that satisfy the constraints in aggregate over multiple rankings 61 9. Among aforementioned works, [49] uses version of adversarial training make (fair) learning to ta-rank models robust to outliers but, unlike this work, they require socially-salient attributes of items to be accurately known to specify the "fairness penalty." All of the other aforementioned works also need access the socially-salient attributes of items. When protected attributes are inaccurate, these works can fail to satisfy their fairness and/or utility guarantees [29]
Effect of inaccuracies on fair-ngn algorithms. Some recent works have considered assessing fairness of rankings and ranking algorithms with missing inaccurate protected attributes. [39 analyze the setting where all protected attributes are missing, but can be purchased at a fixed cost per item. They give aettistical-technnueeee
to estimate the fairness-value of given ranking a small cost. (29] use ML-classifiers to infer protected attributes from real-world data and study performance of the fair-ranking algorithm by (28 when given inferred attributes as input. While these works underscore the need for fair-ranking algorithms to be robust to inaccuracies in protected attributes, they only assess faimess in the presence of noisy protected attributes.
3 Model of fair ranking with noisy attributes
Ranking problem. In ranking problems, given items, one has to select a subset of n items and output permutation of the selected items. This permutation is said to be a ranking. There is a large body of work on estimating the relevance of items and personalizing these estimates to specific users/queries 44 45). We consider a ranking problem where the relevance of items are known. Abstracting relevance estimation, in this problem, one is given m matrix W, such that placing the i-th item at the j-th position generates utility Way. The utility of a ranking is the sum of utilities generated by each item in its assigned position. The algorithmic task in the ranking problem is to output a ranking with the highest utility. We denote rankings by assignment matrices R E (0, 1} | where R.j = 1 indicates that item i appears in position j. and R,j indicates otherwise. In this notation, the utility of a ranking is (R, W) == >m= Σi=1 R.y W.y- Then this ranking problem is to solve: max (R, W). Where R is the set of all assignment matrices denoting a ranking:
R = x E (0, 1] mxxx Vie [m], Σ
X S 1, Vj E [n]. D. ==
X1y = 1
(1)
3

---

Here, the constraint Ex=1 X3 = 1 ensures position j has exactly one item and the constraint Σj=1 X1 S ensures that item occupies at most one position. While this model captures a variety of applications, in some cases, the entries of W may be skewed by an unknown amount [40] [6] or not known accurately [63] and the utility of the ranking may not be linear in the entries of W These are interesting directions but are not studied in this work.
Fair-ranking problem. There are several versions of the fair-ranking problem. We consider version with p 2 2 socially-saliers groups G1. G2...., GG S [m]] (c.g.. the group of all women or all Black people) which are often protected by law. Each of the m items belongs to salient groups (henceforth referred to as just groups). This fair-ranking problem is to output the ranking with maximum utility subject satisfying certain fairness criteria with respect these groups. The appropriate notion of fairness is context dependent, and to capture different fairess criteria nu- merous fairness constraints have been proposed. We consider class of general fairness constraints.
more of these socially-
Definition 3.1 (Fairness constraints). Given a matrix U E 24
Z a ranking I satisfies the upper bound constraint if Eieg, Ei= Rag S UKe, for all & E [p] and k E [n].
Existing works consider similar constraints and show that they can encapsulate variety of fairness criteria [61] For instance, when groups are disjoint, to capture equal and proportional representation, one can choose U= and UR-= k [Gxl for all l and é respectively. (That said, they do not capture qualitative differences among groups, such as, misrepresentation of demographics in image results [38, [55]. which could arise even when rankings has sufficient individuals from each group.) As a running example, we consider the fair-ranking problem with equal representation with two disjoint groups, i.e.,
k 2
max (R, s.t. vk |
Σ
2j=11
Rij
To ease readability, we omit ceilings-operators henceforth.
Noise model. If the socially-salient attributes of items are known accurately, then can solve the fair-ranking problem. However, as discussed, in many contexts, attributes are inaccurate, missing, or only probabilistically known. Several models have been proposed capture different errors in
attributes. Here, we consider a model (due to (5)) which has also appeared in (25 42 48).
Definition 3.2 (Noise model). Let P E [0, 1 mmp be a known matrix. The groups GI,..., G. S [m] random variables, such that, for each E [m]] and [p). Pr(G, e = Pse. Moreover, for different items # j the events G. 3 and G3 3 j are independent for all f, k E [p]-
Definition 3.2 makes two key assumptions: the matrix P is known and for each item the events Ge i over groups E are independent of the corresponding events for other items. Both of these assumptions hold when attributes are flipped to preserve local differential privacy (Remark I. In other settings, P's estimate can be inaccurate and above events may be correlated. These can adversely affect the performance of our framework. We empirically study this in simulations where is estimated using confidence scores of off-the-shelf classifiers and is mixcalibrated (Figures P and and 3 Supplementary Material A shows how Definition 3.2 captures both disjoint and overlapping groups
Fairness constraint with noisy attributes. Most existing fairness constraints assume that the groups are deterministic. Hence, it is not clear how to impose them when groups are random variables, as in Definition 3.2 One definition is require the constraints to be approximately satisfied with high probability. Consider the instantiation of this definition for equal representation: A ranking R satisfies (p. -equual representation, with probability 1 - 8, at most & (1 + p) items from G2 appear in the first l positions in R places for all & [n] and l [p]- Naturally, one would like to satisfy this definition for small 5, p. However, it turns out to be too stringent and is infeasible for any small 8, p.
Proposition 3.3. No ranking satisfies (p, 8) equull representation for < 1, 8 < 1 and = mxxp
The proof of Proposition 3.3 shows that any ranking R violates the squal-representation constraint at the 2nd position by a multiplicative factor of with probability 1. The issue that the same relaxation parameter p is used for each position & (whereas the information theoretically best- achievable relaxation parameter improves as increases, this, e.g., follows by Theorem 4.] Motivated by this observation, consider the following alternate version of upper bound constraints.

---

Definition 3.4 ((5, 5) -constrain,, For any E R200 and ó E (0, 1], ranking R is said to satisfy (c, -constattt if with probability at least - å over the draw of G1, .I....,G. G.
Rig S (w(1+ 4k E [n] V4 E ipl. EIeG, E
(3)
We would like to output a ranking that satisfies Definition 3.4 for small and small E1, E2,...,
, En-
Problem 3.5 (Ranking problem with noisy attributes). Given matrices P, U, and W, find the ranking maximizing utility (R. W) subject to satisfying (e, -cconstattt for some small and 6.
3.1 Challenges in solving Problem 3.5
In this section we discuss potential approaches for solving Problem 3.3 In other words, solving:
maxneR (R, W), s.t., satisfies (c, 5) connttriin
Even for two disjoint groups, given V, it is NP-hard to decide if the value of Program (4 is least V (Theorem E.12). To bypass this hardness, one can consider approximation algorithms. Program 44) is
an integer program (IP) because the entries of the matrix R are required be integers (Equation (I)).
A standard approach to (approximately) solve IPs is to: (1) consider their continuous relaxation that drops the integrality constraints, (2) compute the optimal solution R. of the relaxed problem, and then (3) "round" R. to satisfy integrality constraints while "retaining" its utility and fairness properties. To take this approach, we first need an efficient algorithm to find R., However, not just Program ( but even its continuous relaxation is non-convex. Hence, it is unclear how to solve it to find R...
Due the independence assumption in Definition 3.2 the number of items from G. appearing in the first k positions of a ranking is concentrated around its expectation (for large k). This implies that if, in expectation, less that Uke items from Ge appear in the top & positions then, with high probability, the number of items from Ge in the top & positions is not much larger than Uke. Using this one can show that ranking satisfying the following constraints
& E E,E,.E,
Vk [n] A [p).
Ris S Uke
(5)
also satisfies (e, c)-costtaii for small & and 5. One idea is to find the ranking maximizing util- ity subject to satisfying Constraint 5 A feature of Constraint (5) is that it is linear in R as E|Eieo, Σ R.,] -> Σラ= Pic and, hence, one may hope to find the ranking with the max- imum utility subject to satisfying Constraint (5). However, the issue that there are examples where any ranking satisfying Constraint (5) has O utility and there are rankings that satisfy (s, (c.))-coostraig and have a large positive utility (Lemma I0). Hence, this approach can output rankings whose utility is significantly smaller than the utility of the solution to Problem 3.5 To overcome this, we relax Constraint (5) by a carefully chosen position-dependent factor, such that, any ranking satisfying the (e, 8) constraiit (for appropriate and 8) is also feasible for our framework.
4 Theoretical results
In this section we present our optimization framework and its fairness and utility guarantees.
Input: Matrices PE [0, 1]"" XP WER"x" "E
Our Fair Pair-Ranking Program
mAxRER (R, W),
(Noise Resilient) (7)
Parameters: Constant
1. failure probability
E (0, 1]. and E [n)), relaxation parameter
s.t. vP (p) Wk [m]
Eiem m)) Pietie S Une (I+ (1- 2/2 ) mm) (8)
7/ = 12 log ((p)) maxtejp)
(6)
3c(k]
The above program modifies the program for fair ranking with accurate groups: It has the same objective but different constraints. Instead of sampling the attribute values and applying constraints on the sampled values, Constraint (8) applies upper bounds on the expected number of items in the first k positions from group & (Section 3.T.. Further, Constraint (8) relaxes upper bounds UR+ by small desition-dependent factor. Like for Constraint (5), one can show that any ranking satisfying
Constraint (8) also satisfies (s, 8 -coostrrai (for small , Ex and 8). But unlike Constraint (
5

---

and somewhat surprisingly. any ranking thatsstissies (s, 6) consstrait (for appropriate En and 6) must also satisfy Constraint (8). (In fact, Y chosen to be the smallest, up to logarithmic factors, value such that this is true.) We use this to prove Theorem 4.1s utility guarantee.
Our first result bounds the fairesss and utility of the optimal solution of Program
Theorem 4.1. Let 7 E IR" be as defined in Equation 6 There is an optimization program (Program (7), parameterized by a constant and failure probability 5, such that for any e. > 1 and 5 E (0, 1] 2 its optimal solution satisfies (ey, 8) conossttaa and has a utility at least as large as the utility of any ranking satisfying ((c ( -V))7, 8) -constraan.
For equal representation, Y/h is Ō (+t)) Thus, Theorem 4.1 guarantees that, with high probability, the optimal solution of Program 7 multiplicatively violates equal representation the k-th position by Further, this solution's utility is higher than the utility of any ranking satisfying a slight relaxation of this fairesss guarantee. Theorem 4.1 can be extended to position- weighted versions of fairness constraints (T...rem[F.I]. where the faimess constraint is Eieg, Σje k/ RUy (for all and E) for specified discount factors V1 2 2... 2 Un such as NDCG [33] If we are also guaranteed Use 2 vik for some constant v > 0 and all k and l, then we can improve y 's dependence on 6 from
at most 1 1+ Ō
position-weighted
log 1/ to Vlog 1/S (Supplementary Material
The proof of Theorem 4.1 appears in Section 6
Lower bound on fairness guarantee. Our next result complements Theorem 4. fairness guarantee. Theorem 4.2. There is a family of matrices U Z such that for any U in the family and any parameters d E [0, 1) and E,,...,E,, En. 2 O, if for any position k E [m]. Ek S 1 and E < maxrelpl V 2nee log 1 then there exists a matrix P E [],,], such that it is information theoreti- i8
cally impossible to output a ranking that satisfies (E, conosttriin This family, in particular, contains the matrices U corresponling to equal representution and proportional representation construints.
Since The is O (lo((P)) maxi Une Theorem 4.2 shows that Theorem 4.1 fairness guarantee is optimal up to log-factors. Supplementary Material D.I proves Theorem
An efficient algorithm. As for solving our optimization program, it is Narhard to check its feasi-
bility (Theorem E.7). However, because Constraint (8) is linear in R. the continuous relaxation of Program (7) is standard linear program and can be solved efficiently. Our algorithm (Algorithm IT] solves the standard linear programming relaxation of Program 7 to find a solution Ra and then uses a dependent-roundee
algorithm by [19 to convert R. to ranking. (See Supplementary Material D.2 for brief discussion of why straightforward rounding approaches are insufficient.)
Theorem 4.3. There is a randomized algorithm (Algorithm 77 that given constants d >> 2, failure probability 0 < S 1, and matrices E [0, 1| and W E [0, 1]mx,, outputs ranking satisfying (O(dr), coonstrrii and with probability at least 1 - 8, and has utility at least (1-1), -- V( dn),,, where V is the utility of any ranking satisfying ((d -Vdy,, coonstrann The algorithm runs in polynomial time in d and the bit complexity of the input.
The tension in setting d is that decreasing d improves the fairness guarantee and the utility guarantee's 's second term, but worsens the first term in the utility guarantee. Under the mild assumption that V=N(n), increasing d improves the utility guarantee because the first term in the utility guarantee dominates the second term. In this case, the utility guarantee improves to (1- - o(1))- V. Finally, while Theorem 4.3 requires utilities to be between 0 and I, it can be extended to any non-negative and bounded utilities by scaling. The proof of Theorem appears in Supplementary Material D.2
Empirical results
In this section we evaluate our framework's 's performance on synthetic and real-world data Baselines and metrics. The correct choice of faimess metric is context-dependent and beyond the scope of this work [60]. To illustrate our results, we arbitrarily fix the fairness metric as weighted
"The complexity of inputs the number bits required to encode the ingut using the standard binury encoding (which. e.g. mups integers to their binary representation, rational numbers as pair of integens, and vectors/marrices as tuple of their entries) M Section 1.3].
Code for our simulations is available attpps: /igh wwn.//o///aaaeee http:///wwwe..taaaaaaattttaaaaaa

---

Figure 1 Synthetic Data: Nonuniform Er- ror Rate. We consider synthetic data where imputed socially-salien attributes have a higher false-discovery rate on the minor- ity group. We vary the fairness constraint (e) and observe the weighted risk-difference (RD) of algorithms. The y-axis plots RD and r-axis plots c. (Note that x-axis de- creases toward the right). We observe that NResilient achieves the most fair RD, while obtaining similar utility for all (FigureB) Error-bars denote the error of the mean.
Weighted risk dikfffffeeence
0.825
work
0,800
CSV [Greedyy]
0.775
MC
GAK [Det-Gresty]
0.750
Uncons
0.725
0.700
0.675
0.650
1.8
166
1.2
1.0
(lexs fair)
(more fair)
risk dikedifference (RD). This is a weeghttd version of the standard risk-difference metric 13 and measures the extent to which ranking violates equal representation. The RD of ranking R is:
1- 7-7 E log k
Σ EiEGuJER Rij - -EEGG,JeI Raj
ma
Where G denotes the ground-truth protected groups and Z is constant so that RD has range [0, 1]. Here, RD = 1 is most fair and RD = 0 is least fair. We compare our framework, NResilient, against state-of-the-art fair-ranking algorithms: CSV ("greedy" in [8]: ). SJ [1], and GAK ("DetGreedy"" in (27)) We also compare against MC, which ranks the items, in the subset output by [48] 's algorithm, to maximize utility. Finally, we compare against the baseline, Uncons, which outputs the utility maximizing ranking without fairness considerations. We present additional discussion of baselines and results, additional plots for RD, and comparisons with weighted selection-lite (instead of RD) and different choices of U (than the ones below) in Supplementary Material
Setup. We consider the DCG model of utilities 33 and relaxation of equal representation con- straints: (1) Given an intrinsic value w; 2 0, for each item
set W = w; (log (j + 1)) Vjj e [n]. (2) Given a parameter & @ [1, p). we set upper bounds Usz == _ k for each k E [mi] and & [p). In simulations,
set m 500, n 25, and vary & from p to 1. To gain some intuition about the relevant values of o, note that satisfying the 80% rule requires Φ S Tp-T i.e., á 1.11 for p and Φ < 1.05 for p = 4. For each é, we draw m items uniformly without replacement and compute an estimate P of the matrix P (from Definition 3.2) using, e.g., off-the-shelff ML classifiers or public APIs (see the paragraphs "Estimating p" in simulation with image data and "Setup" in simulation on name data). We infer socially-saliens groups G1.., Go. via P by assigning each item to its most-likely group. Finally, we run all algorithms using P GI...., Gp as discussed next.
5p
Implementation details. NResilient and MC take probabilistic information about socially- salient attributes as input and are given P. CSV, SJ. and GAK require access to socially-salien groups and are given GI...., Gp. NResilient, SJ. and CSV use fairness constraints from Definition 3.1 and are given: for each i and f, Une p items from G2 that can appear in top-n positions. It is given @ n for each l E [p]. GAK requires the desired proportion 0g for each group G. and, roughly, satisfies the constraint URe ag k for each E [m] and E (p). It is given a₂ = for each E [p]. this corresponds to Φ = (hence, figures only plot the GAK
kt MC requires, for each l [p]. an upper bound the number of
1). As heuristic, set ? o/ max V The in all simulations. We find that this suffices and expect a more refined approach to improve the performance of NResilient.
5.1 Simulation on synthetic data
We show that synthetic data, where error-rates of given socially attributes vary over groups, existing fair-ranking algorithms have worse RD than Uncons.
Data. We generate w and for two groups using code by 48 and fix P P. For all items i, w; is
i..dd. from the uniform distribution over [0. 1]. P is constructed such that attributes inferred from P have a higher false-discovery rate for the minority group compared to the majority (40% vs 10%)
*This 30% difference in false discovery rales is compurable to the 34% difference in the false discovery rates of dark skinned femules and light-skinned men observed by [0] commercial classifier.
7

---

Figure 2: Real-world image data. In this simula- tion. given non-gender labeled images and their utilities, our goal is to generate a high-utility gender-balanced ranking. We estimate P' using an off-the- shelf ML-classifier and vary from p = 2 (less fair) to 1 (more fair). The y-axis plots the utility of algorithms and the x-axis plots RD. We observe that NResilient has the most fair RD and the best fairness-utility trade-off. Error hars show the error of the mean.
0.775
0.950
Utility
This work
0.925
SJ
0.900
CSV [Groody]
MC
0.755
GAK [DaxGroodl]]
0.500
0.55
065 0.70
0.80
(lexs fair) Veighted risk-differenc (more fair)
Results. See Figure for the observed RD averaged over 500 iterations. We observe that NResilient achieves best RD (=8,) while not losing sigmificant utility (2 98% of max.; see Figure 8). MC achieves the next best RD (#=0.79). In contrast, CSV, SJ, and GAK, which do not account for noise in the socially-salient attributes, achieve worse RD (50.68) for Φ I 1.2 than Uncons (5)) This
range of & can be desired in practice: e.g., a platform must set Φ S 1.1 to guarantee the 80% rule satisfied two groups. Thus, we observe that existing fair-ranking algorithms may achieve worse RD than Uncons.
5.2 Simulation on real-world image data
In this simulation, given non- nont-geder labeled images-search results and their utilities, our goal is to generate a high-utility and gender-balanced ranking.
Data. We use the Occupations dataset [15] which contains the top 100 Google Image results for 96 occupation-related queries. For each image, the data has its position in search results, gender (coded as male/female) of the individual depicted in the image, collected via MTurr. We use the (true) gender labels the data to compute RD and to estimate P, but do not provide them to algorithms.
Setup. For each image i, with rank Ti, we define w; = (log (1 r+))= We say occupation is gender-stereotypical if more than 80% of images for this occupation have the same gender label (41/96 occupations). An image is said to be stereotypical if it is in a gender-stereotypical occupation and its gender label is the majority label for its occupation. We define the socially-salient groups as the sets of stereotypical and so-ssterett images in gender-stereotypical occupations.
Estimating P. After pre- rre-processing. we use CNN-based gender-classifier f [59] to predict the (apparent) gender of the person depicted in each image. We calibrate the confidence scores output by f by binning and use these to estimate P (see Supplementary Material G for more details). We perform this calibration once and on all occupations and, then, use it for gender-stereotypiccl occupations. Because of this P is miscalibrated (and hence, inaccurate). For instance, among samples i for which 0.25 < P..maee I 0.5, more than 75% are labeled as 'man' (instead of some percentage between 25% and 50%). This violates the assumption that P accurately known.
Results. See for RD and utilities (NDCG) averaged over 1000 iterations. We observe that NResilient achieves the best RD (==0.81) and has a better RD-utility trade-off than the other baselines. In contrast, CSV, SJ, and GAK, achieve a worse RD (50.77). MC achieves the worst RD (<0.70) and worst RD-utility trade-off. In particular, NResilient's 's RD-utility trade-off strictly dominates all baselines for RD 2 0.66. This value of RD can arise in practice: Figure plots the R.D vs & for this simulation and shows that if 1.1 (as required to, e.g., guarantee satisfaction of the 80% rule), then all baselines have RDD at least 0.66. We further evaluate the robustness of NResilient to varying levels of noise on the Occupations dataset in Supplementary Material G.3.2 and observe NResilient has a better or similar RD than each baseline at all noise levels.
5.3 Simulation on real-world name data
We consider gender and race (encoded as binary) socially-salien attributes. Our goal is to ensure equal representation across the four disjoint groups formed by combinations of these: non- White non-men, White non-men, non-White men, and White men.
Data. We consider the chess ranking data (29] which has of 3,251 chess players. For each player, among other attributes, the data has their full-name, self-identified gender (coded as malc/female).
8

---

Weighted risk risk- di-dffefeeenee
017-
Figure 3: Real-World Name Data: Multi- ple Attributes. In this simulation, the goal is to ensure equal representation across four dis- joint groups formed by combinations of two at- tributes Woon- non-men, White non-men, non- Non-White men, and White men). We estimate P by querying public APIs and libraries with names in the data. The y-axis plots RD and æ- axis plots Φb (Note that the values decrease to- ward the right). We observe that all algorithms have better RD than Uncons and NResilient the best compared to all other baselines. Error bars represent the error of the mean.
066
CSV [Greedy]
0.
GAK (ret-Gr
Uncons
0.4
0.3
2.0
1.5
(less fair)
(more fair)
FIDE rating, and race (Asian, Black, Hispanic, White) collected via MTurk. We use the (true) gender and race labels in the data to evaluate RD, but do not provide them to algorithms.
Setup. We partition the races into White (81.66%) and non-White (18.34%). For each player i, we query Genderize and EthniCol with i's full-name to obtain the "probabilities" py(1) and Prw that player i labeled as women and non-w non-white respectively. We assume that these probabilities are correct and that the gender and race of players are drawn independently. Hence, P.
e.g., we set the probability that is non-white women as P P.. (1). Similarly, we set
Pt Piw+,=(11-2) Pro (i), Pinwam P.w Pw (f)(1 (f)),), and P.,e+m = (1 Proe
pro (f))(1 p))))).
Notably, we do not calibrate P on this data. We verify that, like the previous simulation, P is miscalibrated in this simulation. E.g., only 31% of the samples i for which P Piawtm > 0.75 are labeled as whon-white man' (instead of 75%). Hence, the assumption that P is accurately known is violated in this simulation. We expect calibration to improve NResilient's performance.
Results. See Figure 3 for RD averaged over 500 iterations. We observe that all algorithms (NResilient, CSV, GAK, SJ. and MC) have better RD than Uncons. Among these, NResilient achieves the best RD (>0.67), next CSV, GAK, and SJ obtain RD (=0.61), and MC achieves RD (S 0.53). More specifically, for all & S 1.75, NResilient has a strictly better RD than all baselines (this range of ó subsumes, e.g., the range Φ I 1.05-required guarantee satisfaction of the 80% rule with four groups.) Further, in Figure 10 we observe that all algorithms have a similar fairness-utility trade-off.
6 Proof of Theorem 4.1
In this section we prove Theorem 4.1 Some of the details are deferred to Supplementary Material E.3 due to space constraints. The proof divided into two propositions:
Proposition 6.1. For any 6 E (0, 1], any ranking feasible for Prog. 7 satisfies (e7,, -ooosttriint
Proposition 6.2. For any E (0, {)) and e 1, any ranking satisfying the ((c - vCn,, d) coonstraii is feasible for Program
Since R is feasible by definition, Proposition 6.1 implies that R satisfies the (cy, 8) -oonstrrii Pick any H' that satisfies the ((c- v, 8) conntrriit. Proposition 6.2 implies that H' is feasible for Program (7). Since R an optimal solution of Program (7). 1t*' utility is at least as large as the utility of R².
Proof of Theorem 4.1 Let Rº be the optimal solution of Program
Notation. For each item i and group e, let Zie E {0, 13 be the indicator random variable Z; I[, i). By Definition 3.2, Pr [z,] Pie and Zie and Zie are independent for any # j. Given ranking R E RR group E pl. and position l E [n]] let 7 (R, e, k)) be the number of items from G2 in the top positions of and let (R, e, k) R + R, f, k:)]. From the above, we get:
P e, E 2 # RR e, k)] = [m) Eje(n] Pu PuRua..
We use the following concentration result (proved in Supplementary Material E.2 in the proof. Lemma 6.3. For any position & E [n), group E E [p), parameters & 2 O and L, U E R, and ranking R E R, where R is possibly random variable independent of &. if & (R, k,k) S U or
gender-api.com and www.anggggttua www.ggi..ttttpppppeeeeeoo httpp////wppoeeeeeeeeeeoooooeoeo respecciivvy

---

(=(R, 2 L then the following equations hold respectively Pr PriZ < (1++) o) I.] 2
1 tne and Pr 1 R2 k)
20-0)
Proof of Proposition 6.1 Fix any k and L. Let
Uk (1 0%),, and Ç
(9)
2ve'
1+
Here, U' and satisfy (*(1+ Uke(1 (1 + oyk). Fix any ranking R that is feasible for Program
Since R feasible, it satisfies that
vl [p], e [n]. (=(R, & Uea (1 *%))
(10)
Using U'( = Une(1 (1 + cn., Equation (10), and Lemma 6.3 we get that
20'c2
(1 2Tat
(0
22-0)2.2
[7 R, f, k) 2 (1 + [ & 6
2(1
(11)
Fact 6.4. For all r, y 2 0, if 2 vy. then
1+r Ny y.
Using Fact 6.4 and Equation (6). we can show that for each h
Item
2 [1- U1-0)Uu
2np loog
5
(This
uses d and Uke, n 2 1.) Substituting this in Equation 11 get:
Pr Pr[Z (R, k, 2 U1 +cm)) - 2np"
(12)
Taking the union bound over all positions i and E, we get (as desired) that with probability at least 1 6, for all E [n] and 8 E Z (R, k) S Un.(1 + cyk).
Let á = 2/2. Towards contradiction, suppose that H' satisfies ((c - / Cy,, 5) constraiin but not feasible for Program 7 Then there exists and such that
Proof of Proposition 6.2
P# R R ULe (1 +1++0) (7%)). Fix any & and l satisfying this. Let
b:=1 1
(1+b)%k L' Uke (1 + 0%)) and ç= 1409
(13)
ve
It holds that T/(1 () (pe(1 lxn) and, hence, we get
13
Lem 5.3
L'C2 20-
-(r-))PU 2(1+6)
Cipens (c>0) -Ukekk
Pr [Z (H', K L' c)
S e Dyve
(14)
Since > 2 8 log "2 maxe v Use
8 and U 1, we have Pr [Z (R', Uke
1 1 8.
up
Since R' satisfies ((c - vcyn, 6) constraiit we have a contradiction, hence R' must be feasible.
7 Limitations and conclusion
Recent studies find that errors in socially-salient attributes can adversely affect fairness and utility of existing fair-ranking algorithms (2)]. We consider model of random and independent errors in socially-salient attributes and present framework that can output rankings with high faireess and utility in this model. This framework works for general class of fairness criteria, which involve mul- tiple overlapping groups and upper bounds on the number of items that appear in the first k positions from each group. We also show near-tightness of the framework's ' fairness guarantee. Empirically, on both synthetic and world datasets, we observe that, compared to baselines, our framework can achieve higher fairness- values and a similar or better -utilss--tiiltyy trade-off for standard metrics.
Compared to existing fair-ranking frameworks, our framework does not need accurate socially-saliem attributes, but assumes that errors in attributes are random and independent. When these assumptions do not hold, our framework may not satisfy its guarantees and a careful assessment of this on application-specce
data would be important to avoid any (unintended) negative social impact.
Our work only addresses one aspect of how bias may show up in rankings, and more generally, on the web. For instance, while we consider large class of fairness constraints, it does not capture some important notions such as the qualitative representation of different groups [38 55 It is important to take an holistic approach to mitigate bias and incorporate Finally, our work adds to the line of works that develop fair decision-making algorithms robust to
work as a part of such a broader effort.
inaccuracies in data [42 6 54
25
67 66 48 [4]
Acknowledgements. This research was supported in part by NSF Awards CCF-21 and IIS 2054204 and an AWS MLRA Award.
10

---

References
[1] OpenCV: Open Source Computer Vision Library. https://ggiauub.ooo/oppc//////pp Brdparty/raw/ /dna http:/ddnnnaaaaaaa
140000. caf000.caffeoode. Baapan_samll____eee www.aaccceeeetrrreeeeeeee_eeee http://cc.....t.o........//////a
[2] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Icong. Diversifying Search Results. In Proceedings of the Second ACM International Conference on Web Search and Data Mining, WSDM '09, page 5-14, New York, NY, USA, 2009. Association for Computing Machinery.
[3] Ismail Sengor Altingovde, Engin Demir, Fazli Can, and Özgür Ulusoy. Incremental Cluster- Based Retrieval Using Compressed Cluster-Skipp Skipping Inverted Files. ACM Transactions Information Systems (TOIS), 26(3):1-36, 2008.
[4] McKane Andrus, Elena Spitzer, Jeffrey Brown, and Alice Xiang. What We Can't Measure, We Can't Understand: Challenges to Demographic Data Procurement in the Pursuit of Fairness. In FAceT, pages 249-260. ACM, 2021.
[5] Dana Angluin and Philip D. Laird. Learning From Noisy Examples. Mach. Learn., 2(4):343-
370, 1987.
[6] Pranjal Awasthi, Matthäus Kleindessner, and Jamie Morgenstern. Equalized Odds Postprocess- ing under Imperfect Group Information. In International Conference Artificial Intelligence and Statistics, pages 1770-1780. PMLR, 2020.
[7] Ziv Bos-Yo and Maxim Gurevich. Random Sampling from a Search Engine's Index. Journal of the ACM (JACM), 55(5):1-74, 2008.
[8] Michael Bendersky and Xuanhui Wang. Advances in Ta-Ranking, July 2021. https://at googleblog. com www.o//./////oocc awwp:///aaaesiiinnaaee -t ranking. html
[9] Asia J. Biega, Krishna P. Gummadi, and Gerhard Weikum. Equity of Attention: Amortizing Individual Fairness in Rankings. In SIGIR, pages 405-414. ACM, 2018
[10] Joy Buolamwini and Timnit Gebru, Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification. In FAT, volume 81 of Proceedings of Machine Learning Research, pages 77-91. PMLR, 2018.
[11] Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to Rank Using Gradient Descent. Proceedings of the 22nd international conference on Machine learning, pages 89-96, 2005.
[12] Christopher J.C. Burges. From RankNet to LambdaRank to LambdaMART. An Overview. Learning, 2010.
[13] Toon Calders and Sicco Verwer. Three Naive Bayes Approaches for Discrimination-Free Classification. Data Min. Knowl. Discov, 21 2010.
[14] L. Elisa Celis, Lingxiao Huang, Vijay Keswani, and Nisheeth K. Vishnoi. Fair Classification with Noisy Protected Attributes. In ICML, volume 120 of Proceedings of Machine Learning Research. PMLR, 2021.
[15] L. Elisa Celis and Vijay Keswani. Implicit Diversity in Image Summarization. Proc. ACM Hum. Comput. Interact., 4(CSCW2): 2020.
[16] L. Elisa Celis, Anay Mehrotra, and Nisheeth K. Vishnoi. Interventions for Ranking in the Presence of Implicit Bias. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT* '20, page 369-380, New York, NY. USA, 2020. Association for Computing Machinery.
[17] I. Elisa Celis, Anay Mehrotra, and Nisheeth K. Vishnoi. Fair Classification with Adversarial Perturbations. In A. Beygelzimer, Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.

---

[18] L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with Fairness Constraints. In ICALP, volume 107 of LIPlcs, pages 28:1-28:15. Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, 2018.
[19] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding. In Dana Randall, editor, Proceedings of the Twenty- Second Annual ACM Symposium on Discrete Algorithms, SODA 2011, I, San Francisco, California, USA, Jamuary 23-25, 2011, pages 1080-1097. SIAM, 2011.
[20] Jiahao Chen, Nathan Kallus, Xiaojie Mao, Geoffry Svacha, and Madeleine Udell. Fairness Under Unawareness: Assessing Disparity When Protected Class Is Unobserved. In FAT, pages 339-348, ACM, 2019.
[21] Cyril W Cleverdon. The Significance of the Cranfield Tests on Index Languages. In Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, pages 3-12, 1991.
[22] Kushal Dave, Steve Lawrence, and David M Pennock. Mining the Peanut Gallery: Opin- ion Extraction and Semantic Classification of Product Reviews. In Proceedings of the 12th international conference on World Wide Web, pages 519-528, 2003.
[23] Mare Elliott, Peter Morrison, Allen Fremont, Daniel Mccaffrey, Philip Pantoja, and Nicole Lurie. Using the Census Bureau's s Surname List to Improve Estimates of Race/Ethnicity and Associated Disparities. Health Services and Outcomes Research Methodology, 9:252-2533 06 2009.
[24] Robert Epstein and Ronald Robertson. The Search Engine Manipulation Effect (SEME) And Its Possible Impact on the Outcomes of Elections. Proceedings of the National Academy of Sciences, 12233): 2015.
[25] Seyed A. Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John Dickerson. Probabilistic Fair Clustering. In NewrIPS, 2020.
[26] Benoît Frénay and Michel Verleysen. Classification in the Presence of Label Noise: A Survey. IEEE Trans. Neural Networks Learn. Syst., 25(5):845-869, 2014.
[27] Sahin Cem Geyik, Stuart Ambler, and Krishnaram Kenthapadi. Fairness-Awar Ranking in Search & Recommendation Systems with Application LinkedIn Talent Search. In KDD, pages 2221-2231 ACM, 2019.
[28] Sahin Cem Geyik and Krishnaram Kenthapadi. Building Representative Talent Search at LinkedIn. Linkedln Engineering, October 2018. httt:://bit.1y/2xx500
[29] Avijit Ghosh, Ritam Dutt, and Christo Wilson. When Fair Ranking Meets Uncertain Inference.
In SIGIR, pages 1033-1043, ACM, 2021.
[30] Sruthi Gorantla, Amit Deshpande, and Anand Louis. On the Problem of Underranking in Group-Fair Ranking. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 3777-3787. PMIR, 2021.
[3]] M. Grötschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimiza- tion. Algorithms and Combinatorics. Springer Berlin Heidelherg, 2012.
[32] Anikó Hannák, Claudia Wagner, David Garcia, Alan Mislove, Markus Strohmaier, and Christo Wilson. Bias in Online Freelance Marketplaces: Evidence from TaskRabbit and Fiverr. In CSCW, page 1933- 2017.
[33] Kalervo Järvelin and Jaana Kekäläinen. Cumulated Gain-Based Evaluation of IR Techniques. ACM Trans. Inf Syst. 20(4):422-446 oct 2002.
[34] Glen Jeh and Jennifer Widom. Scaling Personalized Web Search. In Proceedings of the 12th international conference World Wide Web, pages 271-279. ACM, 2003.
12

---

[35] Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Moment Multicalibration for Uncertainty Estimation. Mikhail Belkin and Samory Kpotufe, editors. Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2678-2678. PMLR, 15-19 Aug 2021.
[36] Nathan Kallus, Xiaojie Mao, and Angela Zhou. Assessing Algorithmic Fairness with Unob- served Protected Class Using Data Combination. In FAT*, page 110. ACM, 2020.
[37] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What Can We Learn Privately? SIAM J. Comput., 40()):933-26, 2011.
[38] Matthew Kay, Cynthia Matuszek, and Sean A. Munson. Unequal Representation and Gender Stereotypes in Image Search Results for Occupations. In CHI, pages 3819-3828. ACM, 2015.
[39] Ömer Kirnp, Fernando Diaz, Asia Biega, Michael D. Ekstrand, Ben Carterette, and Emine Yilmaz. Estimation of Fair Ranking Metrics with Incomplete Judgments. In WWW, pages 1065-1075, ACM IW3C2, 2021.
[40] Jon M. Kleinberg and Manish Raghavan. Selection Problems in the Presence of Implicit Bias. In ITCS, pages 33:1-33:17. Schloss BeesstullLLibbnizzZennee fuer Informatik, 2018.
[41] Nikola Konstantinov and Christoph H. Lampert. On the Impossibility of Fairness- Learning from Corrupted Data. In Jessica Schrouff, Awa Dieng. Miriam Rateike, Kweku Kwegyir-Aggrey, and Golnoosh Farnadi, editors, Proceedings of The Algorithmic Fairness through the Lens of Causality and Robustness, volume 171 Proceedings of Machine Learning Research, pages 59 83. PMLR, 13 Dec 2022.
[42] Alexandre Louis Lamy and Ziyuan Zhong. Noise- Tolerant Fair Classification. In NeurIPS, pages 294-305, 2019.
[43] Elizabeth D. Liddy. Automatic Document Retrieval. Encyclopedia of Language and Linguistics. Elsevier, 2005.
[44] Jiahui Liu, Peter Dolan, and Elin Rønby Pedersen. Personalized News Recommendation Based on Click Behavior. In Proceedings of the 15th international conference Intelligent user interfaces, pages 31-40. ACM, 2010.
[45] Tie-Yan Liu. Learning Rank for Information Retrieval. 5(3):225-331) mar 2009.
[46] Christopher Manning, Prabhakar Raghavan, and Hinrich Schütze. Introduction to Information Retrieval. Natural Language Engineering, 16(1):100-103, 2010.
[47] Naresh Manwani and P. S. Sastry. Noise Tolerance Under Risk Minimization. IEEE Truns. Cybern.,
2013.
[48] Anay Mehrotra and L. Elisa Celis. Mitigating Bias in Set Selection with Noisy Protected Attributes. In FAccT, pages 237-248. ACM, 2021.
[49] Omid Memarrast, Ashkan Rezaei, Rizal Fathony, and Brian D. Ziebart. Fairness for robust learning to rank. CoRR, abs/21 12.06288, 2021.
[50] Christopher Mims.
Media Is So Good https://www waj www./ooo/ccccoo. articles/ whciso -atiaaammediiissee so- -oo-good-ateo aor- -0011222000
Why Social
Po-
larizing Us. October
2020.
[51] Marco Morik, Ashudeep Singh, Jessica Hong, and Thorsten Joachims. Controlling Fairness and Bias in Dynamic Learning-to- tank... In SIGIR, pages 429-438. ACM, 2020.
[52] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge university press, 1995.
[53] Nima Mousavi. How Tight Is Chernoff Bound, 2010.
13

---

[54] Hussein Mozannar, Mesrob I. Ohannessian, and Nathan Srebro. Fair Learning with Private Demographic Data. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 1066-7075. PMLR, 2020.
[55] Safiya Umoja Noble. Algorithms of Oppression: How Search Engines Reinforce Racism. NYU Press, 2018.
[56] Gourab K. Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg. Fair Ranking: A Critical Review, Challenges, and Future Directions. In 2022 ACM Conference on Fairness, Accountabiliity and Transparency, FAccT '22, page 1929-1942, New York, NY, USA, 2022. Association for Computing Machinery.
[57] UIrich Pferschy, Joachim Schauer, and Clemens Thielen. Approximating the Product Knapsack Problem. Optimization Letters, 1588)2552--2540, 2021.
[58] Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. Fairness in Rankings and Recom- mendations: An Overview. The VLDB Journal, 2021.
[59] Rasmus Rothe, Radu Timofte, and Luc Van Gool. Deep Expectation of Real and Apparent Age from a Single Image without Facial Landmarks. International Journal of Computer Vision, 1 126(2-4): 14:4:444::555 157, 2018.
[60] Andrew D. Selbst, Danah Boyd, Sorelle A. Friedler, Suresh Venkatasubramanninn and Janet Vertesi. Fairness and Abstraction in Sociotechnical Systems. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT '19, pages 59-68, New York, NY, USA, 2019. ACM.
[61] Ashudeep Singh and Thorsten Joachims. Fairness of Exposure in Rankings. In KDD, pages 2219-2228. ACM, 2018.
[62] Ashudeep Singh and Thorsten Joachims. Policy Learning for Fairness in Ranking. In NeurIPS, pages 5427-5437, 2019.
[63] Ashudeep Singh, David Kempe, and Thorsten Joachims. Fairesss in Ranking under Uncertainty. In A. Beygelzimer, Y. Dauphin, P. Liang. and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[64] Pavan Kumar C Singitham, Mahathi S Mahabhashyam, and Prabhakar Raghavan. Efficiency- quality tradeoffs for vector score aggregation. In Proceedings of the Thirtieth international conference on Very large data bases- Volume 30, pages 624-635 2004.
[65] Michael Taylor, Hugo Zaragoza, Nick Craswell, Stephen Robertson, and Chris Burges. Optimi- sation Methods for Ranking Functions with Multiple Parameters. In Proceedings of the 15th ACM international conference on Information and knowledge management, pages 585-593, 2006.
[66] Jialu Wang, Yang Liu, and Caleb Levy. Fair Classification with Group-Dependent Label Noise. In FAccT, pages 526-536. ACM, 2021.
[67] Serena Wang, Wenshuo Guo, Harikrishma Narasimhan, Andrew Cotter, Maya R. Gupta, and Michael Jordan. Robust Optimization for Fairness with Noisy Protected Groups. In NeurIPS, 2020.
[68] Jason Weston, Samy Bengio, and Nicolas Usunier. Large Scale Image Annotation: Learning to Rank with Joint Word-Image Embeddings. Machine learning, 81(1)211-35, 2010. 2010.
[69] Grace Hui Yang and Sicong Zhang. Differential Privacy for Information Retrieval. In WSDM, pages 777-778. ACM, 2018
[70] Ke Yang. Vasilis Gkatzelis, and Julia Stoyanovich. Balanced Ranking with Diversity Constraints.
In IJCAI, pages 6035-6042. ijcai.org, 2019.
[71] Ke Yang, Joshua R. Loftus, and Julia Stoyanovich. Causal Intersectionality and Fair Ranking. In FORC, volume 192 of I.IPles, pages 7:1-7:20. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
14

---

[72] Ke Yang and Julia Stoyanovich. Measuring Fairness in Ranked Outputs. In SSDBM, pages 22:1-22:55 ACM, 2017.
[73] Meike Zehlike and Carlos Castillo. Reducing disparate exposure ranking: A learning to rank approach. In wwW, pages 2849-2855. ACM / IW3C2, 2020.
[74] Meike Zehlike, Ke Yang. and Julia Stoyanovich. Faimess in Ranking, Part I: Score-Based Ranking. ACM Comput. Surv., apr 2022. Just Accepted.
[75] Meike Zehlike, Ke Yang, and Julia Stoyanovich. Fairness in Ranking, Part II: Learning-to-Rank and Recommender Systems. ACM Comput, Surv., apr 2022. Just Accepted.
15


Reviews:
[{"review_id": "y1bSBA-5wOi", "reviewer": "Reviewer_9Qwf", "summary": "This paper studies fair-ranking where, for each item, its group memberships are only known probabilistically.  The authors introduce an approximation algorithm to solve the fair-ranking problem and prove that it approximately satisfies the considered fairness criteria and (subject to fairness) maximizes utility. In experiments, the proposed approach is the most fair of all baselines and achieves the best tradeoff between utility and fairness.\n", "questions": "- In your simulated experiment, you set $\\hat{P}$ such that false-discovery is much more likely for minority groups. Is this a reasonable setting? How do the results differ if false-discovery rates are more equal?\n- In your experiments, you measure fairness with weighted risk-difference. For what other metrics do you expect your proposed framework to perform similarly well? Are there metrics whether other methods could be more competitive?\n- Theoretically and empirically, how do your results change as $n$ grows or shrinks? For lower values of $n$, would your algorithm be as competitive in terms of fairness?\n- How would your empirical results compare to other algorithms if there were a larger number of groups? The current experiments only use a small number of groups (e.g., religious groups or ethnicities).\n", "limitations": "- The proposed framework makes a number of assumptions (clearly): the probabilities of item-group membership are known, membership probabilities are independent, and item relevances are known. These assumptions may not be realistic in many cases, and as the authors mention, may adversely affect their proposed framework. However, the authors do perform 2 experiments that directly address these cases, and the experiments show that their algorithm is performant.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a clearly written paper with strong theoretical components. The empirical work is relatively good, but it’s hard to know whether the results reflect significant improvements over state of the art. The paper is dense with many details appearing in the supplementary material.\n\n**Originality:** while this work draws on many aspects of other work in fair ranking, the particular setting studied is original.\n- This work is the first to study ranking when socially salient attributes are only known probabilistically. The fairness constraints employed in this paper appear in many other pieces on fair ranking. The algorithm proposed is a rounding algorithm that was introduced in reference [16]. However, the algorithm is applied in a new context and the problem setup is novel.\n- There has been some work on classification with noisy protected attributes, which may deserve a mention (despite this work being focused on ranking).\n- As far as I can tell, the related work is adequately cited.\n\n**Clarity:** overall, this is a very clear paper. \n- While the writing is good, I found the introduction to be too abstract, despite references to specific work. Consider including some specific examples in the introduction to ground the discussion.\n- A few typos:\n    - Line 224: “Constraint (5) _applies_ upper bounds on…”\n    - Line 276: “we evaluate our framework’s performance _on_ synthetic…”\n    - Line 293 & 294: you have G_1, …, G_2, but I think you mean G_p\n    - Line 323: “its” -> “it’s”\n    - Line 399: “this framework works _for_ a…”\n- Line 312: “MC achieves the best RD” this is right after a sentence that says that NResilient achieves the best RD.\n- While the paper is clear, most details are omitted in the main text (there are nearly 30 pages of supplementary material).  I found myself often desiring more detail and examples in various places in the main text, e.g., proof of Proposition 2.3, the last paragraph after Constraint (5), a description of the rounding scheme, and a description of the baselines–to name a few.\n\n**Quality:** from a theoretical standpoint, the paper seems technically rigorous. \n- The paper contains a number of theoretical statements related to the fairness and utility of the proposed approach. The supplementary material includes most of the proofs.\n- Experiments only measure fairness via weighted risk-difference. I wonder if the results would differ if using a different metric.\n- In experiments, it is hard to interpret the significance of the improvement achieved by the proposed algorithm. It would be useful to describe/ground the results in some application, for example: resume ranking.\n- Similarly, it seems as though an advantage of the proposed algorithm is that it can achieve higher utility when more fairness is required. For example, in Figure 2, CSV and NResilient are about equal until weighted risk-difference is greater than 0.66. However, it’s unclear whether these levels of fairness would be required or desirable in some application. \n\n**Significance:** this work is a useful piece in the fair-ranking landscape\n- Theoretically, the work is interesting, although I am unsure of how the theoretical results are likely to be further improved.  I think that this work may inspire future work to study more fair ranking settings in which socially salient attributes are only known probabilistically\n- The problem setup and theoretical proofs are unique, but the algorithm is borrowed from existing work.\n- Empirically, it was interesting to see that when groups are sampled, fair algorithms can be worse than unconstrained maximization in terms of fairness. This observation is likely to be further scrutinized. \n- In experiments, the proposed framework appears to achieve about the same utility-fairness tradeoff as all competitors in 2 or 3 experiments (Fig4 & 6). However, the proposed algorithm is able to produce rankings that are fairer. It’s difficult to know whether this is significant and likely to be used by practitioners.\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": "h0_Z_vV1eyG", "reviewer": "Reviewer_3sFW", "summary": "The paper studies the fair ranking problem under a model where socially-salient (protected) attributes of items are randomly and independently perturbed. The authors provide a fair ranking framework that incorporates group fairness requirements along with probabilistic information about perturbations in socially-salient attributes. This novel framework works for multiple non-disjoint attributes and a general class of fairness constraints that include proportional and equal representation. In the experiments, it has been observed that, this new algorithm outputs rankings with higher fairness compared to baselines, and has a similar or better fairness-utility trade-off compared to them.", "questions": "I have some questions that I mention below:\n\n1) line 4: \"socially-salient (including protected) attributes\" Aren't they the same?\n\n2) line 159: I don't think that [54] uses the similar constraints. The exposure based set of fairness constraints are different form constraints used in this paper. You also have used [54] as a baseline. What fairness constraints you used for this method. Did you implement RD or the demographic parity used in the paper?\n\n3) line 221: how did you find constraint (6)?\n\n4) line 267: The algorithm runs in polynomial time in d and the bit complexity of input --> what does it mean bit complexity? \n\n5) Why not using [1] as a baseline in your experiments? This method seems to perform the same task as your approach.\n\n[1] Serena Wang, Wenshuo Guo, Harikrishna Narasimhan, Andrew Cotter, Maya R. Gupta, and Michael I. Jordan. Robust Optimization for Fairness with Noisy Protected Groups. In NeurIPS, 2020.\n\n\n ", "limitations": "The limitations are discussed briefly in the conclusion:\n\n\"Compared to existing fair-ranking frameworks, our framework does not need accurate socially-salient attributes, but assumes that errors in attributes are random and independent.\" ", "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\nThe paper is well-written and easy to read. The paper proposes a solution for this problem that can be applied to multiple non-disjoint attributes and both proportional and equal representation classes of fairness constraints. Basically, the paper discusses a problem and the corresponding optimization to solve, and then discusses the impossibility of solving such a problem (due to it being NP-hard), then simplifies the problem in order to solve the optimization with guaranteed properties. \nThe paper looks theoretically sound with clearly described assumptions and has provided proofs when needed. In the experiments section, the method has been evaluated on synthetic and real-world data. The authors have compared their approach against 5 different baselines and shown that their approach outperforms others. \n\nWeaknesses/Concerns:\n\nI think the paper is technically sound and well-written, yet it operates under strong (though clearly stated) assumptions, which makes its contributions of interest only to a relatively narrow audience.\n\nI have a few concerns/suggestions to improve the presentation of the paper:\n\n1) line 22: recruiting problems [38, 11, 7] --> add dot to the end of sentence. \n\n2) line 32: equal representation requires that .. --> add citation for equal representation\n\n3) line 34: \"Proportional representation requires ...\" --> add citation\n\n4) line 98: remove extra \"that\"\n\n5) line 224: Constraint (5) apply --> applies\n\n6) line 225: Further, Constraint (5) --> shouldn't be it Constraint (8)??\n\n7) line 276: we evaluate our framework's performance synthetic --> on synthetic\n\n8) line 311: \"We observe that NResilient achieves best RD (≈0.81), while not loosing significant utility (≥ 0.98% of maximum; see Figure 4). MC achieves the best RD (≈0.79).\" --> both methods achieve best RD?!\n\n9) Missing related work: This work studies fair ranking with noisy protected attributes. Related to this work, there is a recent work that studies fair ranking in the presence of label noise [1]. It is an in-processing method which presents a preferable trade-off between fairness and utility.\n\n[1] Memarrast, Omid, Ashkan Rezaei, Rizal Fathony, and Brian Ziebart. \"Fairness for Robust Learning to Rank.\" arXiv preprint arXiv:2112.06288 (2021).\n\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": "camaM5Q4lFb", "reviewer": "Reviewer_TTow", "summary": "Given:\n1. $m$ items,\n2. $G_i$ - Possible overlapping sensitive groups to which items belong,\n3. $W_{ij}$ - The utility of ranking item $i$ at position $j$, and\n4. $U_{ij}$ - The maximum number of items from sensitive group $G_i$ that can appear in the first $j$ positions in the ranking.\n\nThe goal of fair ranking is to find a ranking of top-$n$ items such that the utility with respect to $W_{ij}$s is maximised under the constraint that the ranking obeys the limits imposed by $U_{ij}$s.\n\nThis paper studies the fair ranking problem under a setting where groups $G_i$ are not deterministically known. Instead, the algorithm only observes $P_{ij}$, the probability of item $i$ belonging to group $G_j$.\n\nThe authors begin by defining an $(\\epsilon, \\delta)$-fairness constraint for ranking. For $G_i$s sampled from $P_{ij}$ values, this constraint requires the ranking to satisfy the upper bound constraint defined by $U_{ij}$ values (relaxed by a factor of $1 + \\epsilon$) with high probability.\n\nThey show that directly incorporating this constraint leads to a NP-hard problem. On the other hand, naively replacing the high probability constraint with an expectation constraint leads to feasibility issues.\n\nThe main contribution in the paper is a variant of the expectation constraint. The authors show that a ranking satisfying the $(\\epsilon, \\delta)$-constraint also satisfies the new expectation constraint and vice versa.\n\nBecause the expectation constraint is linear, this allows them to write the problem as an integer program with linear constraints. This is then relaxed to a linear program to get the final algorithm.\n\nBesides providing a fairness guarantee (both for the solution of the integer program and the corresponding linear program), the authors also show that their relaxed expectation constraint is tight in the sense that any further relaxation makes it impossible to find a clustering that satisfies the original $(\\epsilon, \\delta)$-constraint.\n\nExperiments on synthetic and real data highlight the utility and limitations of the proposed work.\n", "questions": "This question has no impact on my assessment. I just want to understand some aspects about the fairness notion used in the paper. Why would one like to have an upper bound on the number of occurrences from a particular sensitive group instead of having a lower bound? I understand that in some cases (like equal representation), having an upper bound indirectly also places a lower bound, but why is upper bound a good idea in general? Are there any unintended negative consequences of such a choice?", "limitations": "The authors have done a fantastic job of discussing potential limitations of their work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** The proposed expectation constraint is novel. The authors have clearly distinguished their contributions from the existing literature.\n\n**Quality:** I have not read the proofs in detail but the outline looks sound to me. The authors have answered a number of interesting questions related to their framework (upper bounds and lower bound, problems with naive solutions) and have supported their claims with detailed experiments.\n\n**Clarity:** Overall, the paper is very clearly written and easy to follow. A few minor issues:\n1. L185-186 - \"The issue is that ... for each position\" - My understanding is that for smaller values of k (position in the ranking), it is harder to satisfy the upper bound constraint and a larger $\\rho$ is needed. Is this correct? Adding a line on the intuition here will be helpful.\n2. Adding a high level idea behind the dependent-rounding algorithm from reference [16] in the paper will improve readability.\n3. The organization of Section 4 can be improved. For example, the description about estimating $\\hat{P}$ in L292 becomes clear only near L326, even though $\\hat{P}$ is referenced several time in between as well.\n\n**Significance:** Because ranking is an important practical problem and the authors consider a fairly general setup, the results are indeed significant in my opinion. The authors also point out avenues for improvement (mis-calibrated P estimation models, non-independent errors etc.) and the ideas presented in this paper will be helpful in exploring these directions.", "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": "EVys39otf9e", "reviewer": "Reviewer_6pGr", "summary": "\nGiven a model of limited knowledge about sensitive demographic attributes where each item has a corresponding distribution of probabilities over groups, and where noise is independent for each item, the work introduces a class of fairness constraints which guarantee (with high probability) both utility and (approximate) fairness. Theorem 3.1, their main theoretical result, upper bounds the fairness violation and lower bounds the utility of the ranking solution found using these constraints. Then, they provide a feasible relaxation of these constraints such that existing methods for optimization can be applied, and demonstrate empirical results on two “real” and one synthetic dataset. These results illustrate the relationships between RD (their chosen fairness metric), phi (a parameter to the optimization problem), and total utility. \n\nThe problem setting makes the key assumption that the true utilities W are known and true (i.e., the measurement of utility does not worsen for different groups), and that total utility of a final ranking can simply be computed additively (i.e. aside from the fairness constraint, there are no other reasons that certain combinations may be disproportionately better or worse than others). Though strong, these are reasonable assumptions for the specific problem which this paper addresses. ", "questions": "By iterations, do you mean you ran the simulation procedure 500/1000 times? This seems high? Are individual iterations highly noisy / what do results look like averaged over fewer iterations? \n\nBy the end of the paper I’m not sure how to interpret phi; I understand that it’s varied between 1 and p, the total number of groups, but what does it represent? Why is it interesting or notable that the method presented in this work can achieve higher RD for a given value of phi? ", "limitations": "Yes - the authors are very clear about the specific scope of their work and the assumptions that their models rely on. As discussed above, I would have appreciated some discussion of these assumptions and choices (e.g. the existence of the utility matrix, choice of fairness constraint and associated values), but understand the need for a focused work. ", "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\nI appreciate the storytelling for why the solution unfolded the way it did, particularly why some initial directions are limited. For example, scaffolding for why existing fair ranking work work fails (70-80), why standard approaches to integer programs fail (199-204), why an initial attempt at a constraint (Constraint 5) fails (211-219), and intuition behind the necessity of pseudo-optimality (243-239). \n\nFigure 2 illustrates pretty good results! \n\nThe appendix is thoughtful. I especially enjoyed the discussion of the model for group membership in Appendix A, and the series of baselines (additional metrics, varying noise, perfect access to group membership). \n\n/// Weaknesses /// \n\nMost of my comments here are related to wanting more results/substantiation relative to what was claimed in the paper, not necessarily fatal flaws. \n\nSensitivity to noise levels: the paper claims their method (NResilient) “has better or similar RD than each baseline at all noise levels” (336-338) — unless I’m drastically misinterpreting figure 10b in the appendix, this seems to be untrue? -> leading me to also wonder at what noise levels do the fairness-utility curves (as shown in the main paper) start looking less nice. \n\nGroup membership: The model for group membership is not clear from the main body of the paper, specifically what it means for the model to handle “multiple” sensitive features, or the case where each individual item can belong to “one or more” groups. The experiments also only illustrate results where group membership is disjoint. This is addressed in the appendix (use marginals to model more complex relationships between different groups), but given that [the uncertainty of] group membership is the core motivation of the paper, it feels important for this model, and how to achieve specific instantiations of the model, to be clearer! I’d further be curious to see empirical results, though I could live without them. \n\nFairness metrics: Though the work as a whole claims to present a framework for a class of metrics/constraints (e.g. 158-160), empirical results are only shown (even in the appendix) for constraints/metrics that implement versions of equal representation, and thm. 3.2 is specific to equal representation (though 3.1 is more general to this class of constraints). Equal representation feels like an \"easier\" metric to achieve than proportional representation (similar to demographic parity being \"easier\" than equalized odds in classification), so I'm just curious as to what performance looks like for other constraints. Furthermore, I do wish there had been at least a nominal discussion, even in the appendix, of choice of constraint and what the consequences of different constraints would be, more than just the handwavy mention of appropriate choice being “context dependent.” \n\n/// Typos /// \n- 191 problem 2.5 format? \n- 224 constraint 5 appl[ies]\n- 249 “solve[d]”\n- 311 “l[o]sing” \n- 399 “works [for?] a general” \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