Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose algorithms for closest fair ranking and fair rank aggregation problems.  Specifically, they consider two notions of fairness - weak : (a, b)-fair up to a prefix k of the ranking and strong : fair for all prefixes.  They provide an exact algorithm for the CFR problem for two metrics - Kendall Tau and Ulam.  Their results hold when the number of groups are a constant in the case of the Ulam metric.
strengths_and_weaknesses: Strengths:
1. Fair ranking is an important problem. 
2. All the details are presented.  The paper is however a bit hard to read in some places.
3. The algorithms are fairly intuitive.

Weaknesses:
1. The algorithms are fairly simple to analyze.
2.  While fair ranking is an important problem, the same might not be the case for rank aggregation - one of the primary goals for aggregation is to overcome biases from any individual ranking.
3. Comparison to related work especially in fair group formation and fair clustering/partitioning is missing.  The latter problems are especially related under the weak notion of fairness when k is set to the size of each parition/cluster/group.
questions: Do the algorithms extend to multi-dimensional spaces when a fairness criterion for each group can be represented as a d-dimensional vector.  The current algorithms are fairly straightforward because of the assumption of no 'overlap' between different groups.
limitations: While the problem of fair ranking is an important problem to consider, fair rank aggregation is not well motivated.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: From a fairness or diversity perspective, this paper examines ranking problems in which candidates belonging to different groups have a fair representation in the final rankings. Using a linear time exact algorithm, the algorithm will find the closest fair ranking for Kendall tau metric under strong fairness (where the final ranking is fair for all values of k) given the parameters for defining fair representation (number of candidates from a particular group in the top-k positions of the ranking).
The authors also provide an exact algorithm for finding the closest fair ranking for the Ulam metric under strong fairness when there are a few number of groups. Additionally, the authors propose a novel meta-algorithm for the general rank aggregation problem under the fairness framework.
In a nutshell, the main contribution is to develop a novel algorithmic toolbox for the fair rank aggregation that solves a variety of rank aggregation objectives satisfying such generic fairness constraints. An essential takeaway of this work is that a set of potentially biased rankings can be aggregated into a fair ranking with only a small loss in the quality of the ranking.
strengths_and_weaknesses: The paper throughly studies the fair rank aggregation problem under different fairness constraints. It provides two meta-algorithms to approximate the fair aggregated ranking. There are a lot of Theorems, Claims, Lemmas and Definitions in the paper which is good in a sense because it adds details but overall makes the paper not easy to follow. I suggest moving some of them to appendix. One of the main sections of the paper (Fair Rank Aggregation) starts in page 7! While the paper looks interesting and novel, it is pure theoretical paper which I'm not sure is a good choice for this venue. The paper introduces a generic approach and argues it is a novel algorithm but it does not test this method on a simulated or real-world data. It would be interesting to see some experiments and comparisons with the methods discussed in [1] or [2] as these papers mentioned in the paper as closest approaches and they provide experiments to show the effectiveness of their method. 

Missing related work: In line 43, Besides mentioned papers, [1] is also a new related work that outputs a fair ranking robust to label noise that maximizes the ranking utility subject to group fairness constraints based on exposure such as demographic parity. It is an in-processing method which presents a preferable trade-off between fairness and utility.

[1] Caitlin Kuhlman and Elke Rundensteiner. Rank aggregation algorithms for fair con- sensus. Proceedings of the VLDB Endowment, 13(12), 2020.

[2] David Wei, Md Moinul Islam, Baruch Schieber, and Senjuti Basu Roy. Rank aggrega- tion with proportional fairness. In SIGMOD, page To appear, 2022.

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

questions: See above. Have you implemented your algorithm to experiment on a real-world data?
limitations: I don't if they have discussed the limitations of their approach.
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: The authors study fair rank aggregation, where candidates may belong to different groups and each group must be represented fairly in the final ranking (in a way that the designer can specify). They provide a linear time algorithm for finding the closest fair ranking under proportional fairness for the Kendall tau distance metric, and a poly-time dynamic programming algorithm for the Ulam metric for a constant number of groups (which is the case in practice). They then study the fair rank aggregation problem, and show that many biased rankings can be aggregated into a fair ranking with only a small loss in quality for a variety of distance metrics.

strengths_and_weaknesses: Strengths: 
+ The definition of proportional fairness is general and flexible, and nicely generalizes previous results.
+ The fair rank aggregation problem is also an interesting line of inquiry, where the goal is to find a fair ranking that minimizes the generalized mean distance to the input profile.

Strength/weakness: 
+ The meta-algorithms for fair rank aggregation are also simple (which could be a weakness, but as a first foray into the field seems like a plus), where the ideas are either to (1) find fair approximations of each input ranking and then choose the most central one, or (2) find a fair approximation of the (unfair) ranking that minimizes the generalized mean objective. However, there is perhaps more room for more sophisticated algorithms that don't involve the CFR subproblem.

Weaknesses:
- The algorithms described in the paper are all relatively simple (even if the analysis is nontrivial). This is only a minor critique, however: as an early paper in this area, that is to be expected.
questions: 1. Have you considered fair rank aggregation algorithms that do not use closest fair ranking as a subroutine?

limitations: Yes
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: This paper focused on the rank aggregation problem under a very general notion of proportional fairness. Authors propose a linear time exact algorithm to find the closest fair ranking (CFR) by a greedy strategy for Kendall tau and Ulam metrics and propose a novel algorithmic toolbox to solve a wide variety of rank aggregation objectives satisfying such generic fairness constraints. They provide rigorous mathematical derivation to prove that the there exists a linear time ranking algorithm.
strengths_and_weaknesses: Strengths:
* This paper gives a novel meta-algorithm for the general rank aggregation problem under the fairness framework, which works for any generalized mean objective and any fairness criteria.
* This paper proves that the there exists a linear time ranking algorithm through rigorous mathematical derivation.
Weaknesses:
* The structure of this paper is incomplete, which makes the paper poor readable. This paper misses Sections of Related Works and Conclusion. Authors can refer to previous paper published in NeurIPS for revision. 
* In this paper, authors only use one paragraph in Section 1.1 to introduce the comparison with only one concurrent work. It is difficult to convince me that the algorithm proposed in this paper is superior to the state-of-the-art algorithms.
* Some formulations are not correct. For example, in Section 1, the generalized mean objective in Section 1.1 $\sum_{i=1}^n (\rho(\pi_i, \sigma)^q)^{1/q}$ should be $(\sum_{i=1}^n \rho(\pi_i, \sigma)^q)^{1/q}$ in line 105.
* I think the contribution of the proposed algorithm is that authors design a novel objection function of greedy strategy for fair ranking and prove the algorithm is a linear time ranking algorithm. However, the greedy strategy for ranking is lack of innovation

questions: * This paper discusses the different cases by leveraging different distance function, Kendall tau and Ulam. But there is no comparison between these two different distance functions. Which one is more suitable for the fair rank aggregation task?

*This paper provides some mathematical derivation to compute the time complexity of the proposed algorithms. How about the performance of ranking by the proposed algorithms? Can you deliver some experiments to show the performance of your ranking, such as precision?  

limitations: *This paper focuses on the mathematical derivation for the fair rank aggregation and illustrates that the proposed algorithms are better than concurrent work [WISR22] in line 132. Maybe authors can add more comparisons and give more detailed explanation for proving the superiority of the proposed algorithms.

*This paper studies group fairness, as well as proportional fairness. The assumption of this problem seems to be that each candidate only belongs to one group. I wonder if the algorithms in this paper still works if each candidate can belong to multiple groups at the same time.
review_title: null

Meta-review: metareview: Reviewers liked the novelty in the fair range aggregation problem and enjoyed the simplicity of the proposed algorithms. The theoretical results are solid though the proof techniques are believed to be standard. There is a large room to improve the quality of presentation. Reviewers' opinions stayed the same after rebuttal and no additional points were raised during the discussion and no reviewer had a strong opinion on acceptance or rejection. So the paper  is on the slightly positive side of the fence.
confidence: Less certain
Decision: Accept