Venue: NeurIPS 2022 Conference

Reviews:

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: This paper pushes the limit of fairness impossibility theorem where all three group fairness definitions cannot be satisfied simultaneously. Based on an integer-programming approach, the authors propose a framework to yield a certifiably optimal post-processing method for simultaneously satisfying multiple fairness criteria under small violations. In experiments, the framework with minimal model performance reduction achieves fairness improvement across different definitions simultaneously. As an application, the framework advises on model selection and fairness explainability. 
strengths_and_weaknesses: Strength: 
- The motivation of the paper is very interesting. 

Weakness:
- There is no experimental comparison with existing fairness works.
 - While the proposed method belongs to post-processing fairness algorithms, experiments do not include any comparison with post-processing algorithms. 
- Tables and figures are uninformatively presented. 
- In Table 3, few cells are in bold fonts. No interpretation is given. 
- A motivating example is missing, where authors could compare theoretical fairness impossibility result vs. their proposed solution.
questions: - In Figure 1, what does different colours mean?
- Why do authors compare with an in-processing algorithm while the proposed work is a post-processing algorithm?
limitations: There is no negative societal impact of this 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 proposes an optimization-based method to simultaneously reduce the gap in demographic parity, equalized odds, and predictive rate parity. The fairness problem is first formulated as a non-convex optimization task and then solved using mixed integer programming. Experimental results that compares the proposed method against two existing baselines are provided.
strengths_and_weaknesses: Strengths:
1. This paper provides a novel solution to the well-known impossibility theorem in algorithmic fairness. The motif of the paper is novel and very relevant to the fairness community.
2. One major strength of this paper is that this methodology enables the user to select the model from the frontier that offers the best trade-off among all fairness metrics and performance. This feature is very appealing to models that are deployed under multiple applications.
3. This paper is well-organized. All concepts are clearly explained. The authors provide sufficient intuition along with rigorous definitions. 
4. The formulation of the constrained optimization problem fits well with the fairness application. The constraints are well-explained and intuitively make perfect sense.
5. The proposed MILP solution is novel and suitable to this application. MILP is computationally tractable and globally optimal (although the problem formulation accepts tolerance).

Weakness:
The major concern for this approach is on its generalizability. Will the transformation matrix (X) learned on a tune/train set transfer (with great fairness & accuracy performance) to the test set? How is the binning method impact the generalizability? Technically, one can make B -> infinity and learn a X that achieves (almost) perfect performance on both fairness and accuracy perspective. But this performance will not generalize to the unseen test set. 
questions: 
1. What change should be on the target and constrains if protected attributes are non-binary?

2. In table 1, INT significantly under-performs IP for ACS coverage and COMPAS. What's the reason behind this gap for these two datasets?

3. It would be great if the authors could provide additional ablation experiment on the size of bins and see how B impacts the performance.
limitations: Please see the weakness in the previous section for major concern. Minor concerns are:

1. Figure 1 needs to be improved: clearer labels for x,y axis and legend.

2. The experiment set up seems unclear. How was the training/validation/test set split? At which subset the X matrix is learned?
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 how to deal with the trade-off among three common fairness notions: demographic parity, equalized odds, and predictive rate parity. The paper proposes a post-processing approach that aims to modify the decision made by any prediction model. The variable is the probability of flipping the decision from one to another for each group (in the case of continuous decision it is to move instances from one to another). Then, a combinatorial optimization problem is defined which contains the formulations of all fair constraints. The paper develops an efficient approach to solve the problem via mixed integer programming. Finally, experiments show that the proposed method can help the decision maker balance the trade-off between model utility and different fairness constraints.
strengths_and_weaknesses: Strength

The proposed optimization framework is not limited to binary classification. The reformulation makes the optimization problem tractable. The optimization framework is also scalable since its complexity does not depend on the number of features and samples in the data. The experiment results are interesting which show that the proposed method is practically meaningful to practitioners and decision makers.

Weakness

Although the size the optimization problem only depends on the number of groups and the number of bins, in many cases the number of groups may be much larger than two. For example, when we consider intersectional fairness for multiple protected features, and when we consider conditional fairness notions (e.g., conditional demographic parity) which can produce a large number of subgroups by conditioning on certain features, the number of groups will increase significantly. The paper does not analyze the scalability of the proposed method under such situation.

questions: A critical question that may affect my final rating is that, in Eq. (1), when the number of instances in b’ after transformation is computed, why only considering the instances that are transformed into b’? What about the instances that are transformed out of b’?

Other questions:

Mixed integer programming in general is still NP-hard. Why does the paper claim that the proposed MIP reformulation is tractable?

The paper states that the challenge for solving the optimization problem comes from Constraint (3) and (4f) which introduce non-convexities. What if we remove Constraint (3) and (4f)? For Constraint (3), since the most commonly used fairness notions are demographic parity and equalized odds, in some cases it is fine not to consider the third one. For Constraint (4f), it seems to me that its purpose is to further preserve the utility of the solution in addition to the objective function. Thus, it is not a necessary condition in the optimization.

limitations: Yes.
review_title: null

Meta-review: metareview: This paper provides an interesting framework that investigates trade-offs of multiple fairness criteria. The reviewers agree that the proposed techniques are interesting and make meaningful contributions to algorithmic fairness. Please incorporate the reviewers' suggestions in your next revision (e.g., not using "tractable" to describe MIP).

confidence: Less certain
Decision: Accept