Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

The 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. 
The 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. 

Weaknesses/Concerns:

I 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.

I have a few concerns/suggestions to improve the presentation of the paper:

1) line 22: recruiting problems [38, 11, 7] --> add dot to the end of sentence. 

2) line 32: equal representation requires that .. --> add citation for equal representation

3) line 34: "Proportional representation requires ..." --> add citation

4) line 98: remove extra "that"

5) line 224: Constraint (5) apply --> applies

6) line 225: Further, Constraint (5) --> shouldn't be it Constraint (8)??

7) line 276: we evaluate our framework's performance synthetic --> on synthetic

8) 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?!

9) 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.

[1] Memarrast, Omid, Ashkan Rezaei, Rizal Fathony, and Brian Ziebart. "Fairness for Robust Learning to Rank." arXiv preprint arXiv:2112.06288 (2021).


questions: I have some questions that I mention below:

1) line 4: "socially-salient (including protected) attributes" Aren't they the same?

2) 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?

3) line 221: how did you find constraint (6)?

4) line 267: The algorithm runs in polynomial time in d and the bit complexity of input --> what does it mean bit complexity? 

5) Why not using [1] as a baseline in your experiments? This method seems to perform the same task as your approach.

[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.


 
limitations: The limitations are discussed briefly in the conclusion:

"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."
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
Given 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. 

The 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. 
strengths_and_weaknesses: /// Strengths /// 

I 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). 

Figure 2 illustrates pretty good results! 

The 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). 

/// Weaknesses /// 

Most of my comments here are related to wanting more results/substantiation relative to what was claimed in the paper, not necessarily fatal flaws. 

Sensitivity 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. 

Group 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. 

Fairness 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.” 

/// Typos /// 
- 191 problem 2.5 format? 
- 224 constraint 5 appl[ies]
- 249 “solve[d]”
- 311 “l[o]sing” 
- 399 “works [for?] a general” 

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? 

By 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

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.

**Originality:** while this work draws on many aspects of other work in fair ranking, the particular setting studied is original.
- 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.
- There has been some work on classification with noisy protected attributes, which may deserve a mention (despite this work being focused on ranking).
- As far as I can tell, the related work is adequately cited.

**Clarity:** overall, this is a very clear paper. 
- 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.
- A few typos:
    - Line 224: “Constraint (5) _applies_ upper bounds on…”
    - Line 276: “we evaluate our framework’s performance _on_ synthetic…”
    - Line 293 & 294: you have G_1, …, G_2, but I think you mean G_p
    - Line 323: “its” -> “it’s”
    - Line 399: “this framework works _for_ a…”
- Line 312: “MC achieves the best RD” this is right after a sentence that says that NResilient achieves the best RD.
- 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.

**Quality:** from a theoretical standpoint, the paper seems technically rigorous. 
- 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.
- Experiments only measure fairness via weighted risk-difference. I wonder if the results would differ if using a different metric.
- 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.
- 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. 

**Significance:** this work is a useful piece in the fair-ranking landscape
- 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
- The problem setup and theoretical proofs are unique, but the algorithm is borrowed from existing work.
- 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. 
- 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.

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?
- 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?
- 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?
- 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).

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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Given:
1. $m$ items,
2. $G_i$ - Possible overlapping sensitive groups to which items belong,
3. $W_{ij}$ - The utility of ranking item $i$ at position $j$, and
4. $U_{ij}$ - The maximum number of items from sensitive group $G_i$ that can appear in the first $j$ positions in the ranking.

The 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.

This 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$.

The 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.

They 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.

The 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.

Because 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.

Besides 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.

Experiments on synthetic and real data highlight the utility and limitations of the proposed work.

strengths_and_weaknesses: **Originality:** The proposed expectation constraint is novel. The authors have clearly distinguished their contributions from the existing literature.

**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.

**Clarity:** Overall, the paper is very clearly written and easy to follow. A few minor issues:
1. 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.
2. Adding a high level idea behind the dependent-rounding algorithm from reference [16] in the paper will improve readability.
3. 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.

**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.
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.
review_title: null

Meta-review: metareview: This paper looks at the fair ranking problem, a known variant of ranking where group fairness constraints (typically hard, sometimes soft) are imposed on the traditional ranking objective, but where membership of each item to be ranked in a group (aka the sensitive attribute's value associated with that item) is unknown.  The paper provides strong theoretical results and, especially post-rebuttal, strong experimental backing of the setting at hand.  Some assumptions are relatively strong, as surfaced by reviewers (e.g., 3sFW), but by and large reviewers believed the work to be well motivated and complete, and I agree with that.
confidence: Certain
Decision: Accept