Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the fairness issue in algorithmic decision-making caused by uncertainty. Since the actual merits are hard to observe, the authors propose a new notion to capture the uncertainty, named approximate fairness in ranking. Based on the notation, they propose different algorithms to achieve approximately fair ranking distributions. In addition to the theoretical analysis, extensive empirical studies are conducted to evaluate their approach.
main_review: This paper is well-written and studies an interesting problem, which is well explained in the introduction. To some extent, it will provide a new perspective for the related research communities to explore the fairness issue under uncertainty. This paper is technically sound for me and the empirical studies are versatile which including data-driven simulation and real implementation.
limitations_and_societal_impact: 1. It would be better to show the running time of the proposed algorithm in the experimental section.
2. Comparisons with other state-of-the-art algorithms are missing, thus readers cannot see whether the proposed algorithms can outperform the related work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of fair ranking under a new notion of fairness. The main point of the paper is that uncertainty is a primary reason for the lack of fairness. In defining this new notion of fairness, authors base their arguments on the axiom that if $A$ has merit greater than or equal to $B$ with probability at least $p$, then a fair policy should treat $A$ at least as well as $B$ with probability at least $p$. Based on this, they say a ranking policy is fair if the probability that it ranks an agent in the first $k$ positions is at least the probability that it actually is among the top $k$ agents. They similarly say an algorithm is $\phi$-fair if the probability that it ranks an agent in the first $k$ positions is at least a $\phi$ fraction of the probability that it actually is among the top $k$ agents. 
Authors then try to design algorithms for fair ranking. They first propose two very simple algorithms which achieve fair and approximately fair ranking without considering its impacts on the utility of the principal. They then show how to compute rankings that optimally trade-off approximate fairness against utility to the principal. Finally, they conduct empirical studies to evaluate the impact of their approach on a paper recommendation system that they built and fielded at a large conference.

main_review: I find this new notion of fairness very interesting. The authors do a good job of explaining why thinking about fairness in this way is useful and how uncertainty plays a significant role in getting unfair policies. The main technical contribution of the paper is designing ranking policies which are quite trivial (So, the paper is not very technically strong). However, using empirical studies, the authors show that these simple algorithms give good results. In conclusion, I believe that the paper meets the bar for a NeurIPS publication mostly due to its novelty (studying this new notion of fairness). 

A minor comment for the authors: There is a typo in the abstract “compute,rankings”.
limitations_and_societal_impact: I don't believe that there is any negative social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers ranking given access to posterior distributions on true scores. They propose a notion of fairness based on these posterior distributions, essentially requiring that probability of inclusion among the top $k$ scale with the probability of being ranked in the top $k$ according to the posterior distributions. These posterior distributions are presumed to be fair, in the sense that an algorithm which is fair (according to this definition) need only be fair with respect to the posterior distributions.
They show that a convex combination of Thompson Sampling and ranking by means is approximately fair but can be suboptimal in terms of utility. They give an optimal algorithm (subject to their fairness constraint) by formulating the problem as a linear program. Finally, they run an experiment on a movie recommendation dataset and implement their algorithm in a real-world paper recommendation setting, comparing their two algorithms and measuring cost of fairness.

main_review: The paper is well-written and clear, presenting simple algorithms that can be easily implemented in practice. The biggest contribution is the notion of fairness, which requires that ordinal probabilities be bounded based on posterior distributions. This is a novel notion of fairness in ranking to my knowledge. The biggest drawback of the paper is that the technical (theory) contribution is somewhat weak.

Some concerns that arise due to the definition of fairness: 
- A notion of fairness based purely on posterior distributions might enhance inequities in the society, simply due to the fact that the initial observations for certain agents might be luckier than for other agents. 
- How are the posterior distributions computed? How might these distributions account for systemic biases? I wonder if the paper is simply by-passing the key issue in evaluation metrics by considering posterior distributions. 
- Randomness -- probabilistic definition of ranking -- why does a probabilistic definition even make sense, when providing a single ranking for agents, for applications such as admissions, hiring, etc?
- A lot of references on rankings seem to be missing -- for e.g., Kleinberg and Raghavan (subset selection under bias), Bower et. al (individually fair rankings), Gupta and Salem (selection under poset model), Celis and Mehrotra (subset selection with noisy protected attributes), Celis Mehrotra Vishnoi (ranking under implicit bias), etc. 

Minor comment: The discussion of error decay in lines 244-249 should be written formally as a proposition.

limitations_and_societal_impact: As noted in the paper, bias mitigation—if it were to happen—would take place in choosing the posterior distributions, not in choosing the ranking. Some discussion on how one might mitigate a bias by choosing an appropriate posterior distribution would be helpful.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new definition of fairness in rankings. An LP-based algorithm is given for finding best (max utility) ranking for a given fairness level. Two empirical evaluations of the proposed frameworks are given 1) based on ranking movies from a public dataset and 2) an experiment was run during a large virtual conference in which participants were given paper recommendations according to a ranking.


main_review: The main assumption (or belief) behind this paper is that there is inherent uncertainty in the ranked items' merits which are observed by the ranker. This uncertainty is modelled by a probability distribution over merits that is given as input to the ranker. Also the solution is then not a single permutation over items but rather a whole distribution over them. A (candidate solution) distribution over rankings is said to be \phi-fair if for every item x and every position k in the ranking, the probability of x being ranked in top-k is at least \phi times the probability of x being top-k according to the given distribution of merits.

What is important to point out is that for the standard setting of a ranking problem, where *a single ranking must be produced* based on some kind of data, this framework does not seem applicable -- the main point of having a probabilistic solution is that one samples from it repeatedly, multiple times, and not just once. It is mentioned in the paragraph 180-185 that because of this issue the applicability of this approach is limited. In the reviewer's opinion this is a rather strong limitation, and the paper makes the impression as if the "framework" was very general -- it would be certainly beneficial to state upfront what is the setting the framework is expected to be applied to, because it is certainly not the most common one.

The mathematical formulation of the fairness notion proposed by the authors is quite nice and ellegant. This ellegance also translates to a very natural LP formulation of the problem that the authors give as a solution method. However, several natural questions come to mind:
1) The knowledge of Prob[M^{(v)}_{x, k}] is a very strong assumption, it is not at all convincing that this can be obtained -- and even if it can by MC, then the error can significantly impact the optimal solution.
2) There is no discussion of other, perhaps combinatorial approaches to solve this problem. Is it obviosly hard? Is LP somehow necessary?
3) Even if LP is necessary, and no greedy approach works, then giving a practical algorithm for ranking that involves solving an LP does not sound right. It would be great if the authors discussed some possible practical, efficient algorithmic approaches (or at least heuristics) for solving this linear program that could allow avoiding a general LP-solver.


When it comes to the experiments, first of all the reviewer is impressed by the Real World Experiment on paper recommendation (during a virtual conference). This is a great piece of work which deserves appreciation as it certainly required a lot of effort to implement. That being said, even though this single part of the paper makes a great, positive impression, the reviewer's overall feedback on the experiments, or rather the whole proposed "framework" is not quite positive. The main objection is that the premise of uncertainty and probabilistic modelling of the problem feels rather artificial and does not seem to arise naturally in real-world examples. This is unfortunately confirmed by the design forced in both experiments: in each of them, some kind of artificial randomness must be injected just so that the assumption of "uncertainty" is met. If this assumption was correct and natural, why would there ever be need to inject artificial randomness into the data?


To conclude, the paper is well written and the considered idea for a framework for ranking seems reasonable from the mathematical perspective. Also the obtained algorithm is natural, and the performed experiments are strong parts of the paper. However, the reviewer is of the opinion that the main assumption made in this paper -- that uncertainty is inherent in ranking problems -- in the way it is modelled in this framework, is doubtful, and somehow even the experiments reinforce this doubt (injecting artificial randomness) instead of proving the opposite.


Minor comments:

1. typo in abstract, line 17 'compute,rankings'
2. there are multiple papers that are referenced via arxiv, but have been published in conferences in the meantime
limitations_and_societal_impact: -
review_title: null

Meta-review: After discussion, the reviewers were all in favor of accepting the paper. The discussion of related work should be expanded (in particular, KRW seems to ask for a very similar notion of fairness in rankings, although as you point out, the actual setting considered is distinct). Thanks for the strong submission!
Decision: Accept (Poster)