- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies fair top-(k) selection under constraints on multiple protected groups, minimizing either the (L_1) distance from a reference scoring vector or utility loss. Its contributions include hardness and tractability results, extensions of (k)-level algorithms to handle ties and multiple groups, and a MILP-based approach for larger (k). Experiments on COMPAS and IIT-JEE demonstrate substantial runtime improvements over baseline algorithms.
Critical strengths
- Explicitly handles ties and multiple protected groups, which can materially affect fairness feasibility.
- Connects complexity analysis, geometric algorithms, and MILP, with substantial reported runtime improvements in some experiments.
Critical weaknesses
- The multidimensional baseline does not handle ties, so it is difficult to tell how the proposed methods would compare against a baseline with the same capabilities in terms of runtime and fairness guarantees.
- The stability evaluation covers only ten scoring vectors, with four perturbations per vector at a single magnitude. This makes it difficult to determine whether the observed advantage holds under other conditions.
Questions for authors
- How would the proposed methods compare with baselines that also handle ties and provide the same fairness guarantees?
- How were the stability perturbations generated, and would the results hold under different perturbation settings?
- What are the main theoretical and algorithmic contributions that go beyond the existing (k)-level-based methods cited in the paper?
3 comments
Q3. What are the main theoretical and algorithmic contributions that go beyond the existing (k)-level-based methods cited in the paper?
For theoretical contributions, we prove the Fair Top-k Selection problem is NP-hard with multiple protected groups once the tie-breaking issue is properly considered, thereby correcting an implication of previous work. Furthermore, we establish a near lower bound for constant values of k under a well-known conjecture in fine-grained complexity. For algorithmic contributions, guided by the hardness analysis, we propose an efficient algorithm for the Fair Top-k Verification problem when both the number of protected groups and k are small. This algorithm is a key component to augment the k-level based algorithm to recover its (theoretical) efficiency for small k, while also constituting an algorithmic contribution in its own right through its important role in experimental exploration. Moreover, we present an augmented MILP-based algorithm for large k.
Finally, as we have argued throughout our submission, we acknowledge that some of these contributions may be of independent interest, still, we emphasize that their primary significance in this work lies in their interconnection, rather than their individual contributions considered in isolation (see Appendix A for further discussion).
Thanks for the response. My concerns are addressed. I will keep my score.
We thank the reviewer for their comments and questions. Please find our answers below.
In Appendix H.1 (line 1457), it has been stated that "the tie-breaking was ignored in the implementation of ATC+ (the multidimensional baseline), as it was not obvious how to do so without introducing significant runtime overhead for ATC+". Making ATC+ correctly handles ties requires additional computational steps, increasing its run time. This means our performances advantages will be even greater when compared with the corrected ATC+ variant. Given that our experiments have already demonstrated speedups of several orders of magnitude, we believe these results sufficiently support our runtime efficiency claim over ATC+ (the multidimensional baseline). Furthermore, given ATC+'s clear runtime inefficiency relative to our method, we use it solely to demonstrate the runtime advantage and do not consider it worthwhile to develop a corrected ATC+ variant.
As stated in Section 6.2 (lines 419–420): "These (stability evaluation) results suggest that optimizing for the utility loss can yield more stable fair weight vectors than optimizing for a distance-based objective, aligning with our theoretical analysis (Section 4.2)". Our claim regarding the stability advantage is primarily supported by our theoretical analysis rather than empirical observations. Specifically, in Section 4.2, we explain that: "A fair weight vector minimizing the w difference (i.e., L1 distance) is inherently unstable, as a small perturbation towards wo would yield top-k subsets violating the fairness constraints." (lines 264–265). In contrast, for a fair weight vector minimizing the utility loss, we state: "This linear program enforces a margin of ξ between the weight vector and the cell boundary, ensuring that a weight vector under small perturbations bounded by ξ induces the same top-k subset (with the minimum utility loss). As a result, the resulting fair weight vector is more stable with respect to perturbations (see Figure 2)" (lines 270–274). The intention of our stability evaluation experiment is only to empirically demonstrate the stability advantage of the utility loss objective over the distance-based objective. The stability advantage, by itself, is established via a theoretical analysis. We will clarify the intended role of this experiment in the revised version.
Of course, as stated in the Reproducibility Statement, the command-line interface (CLI) tool provided in our (anonymous) code repository "supports experimental configurations beyond those reported in the paper" (Lines 498–499). Here, we report additional experimental results that for 25 weight vectors, with 8 perturbations per vector at a perturbation L1 distance of 2×10−4, 24 of 25 fair weight vectors found under the utility loss objective (with stabilization) passed the stability test. In contrast, all fair weight vectors found under the w difference objective failed. However, we believe our original experimental results (10 vs. 0) are good enough to empirically demonstrate the stability advantage, as the claim is primarily supported by our theoretical analysis rather than empirical observations.
We have briefly mentioned how were the stability perturbations generated in Section 6.2 (lines 414–416): "For each fair weight vector, four randomly perturbed weight vectors were generated with an L1 distance of 10−4 from it". That is, each perturbed weight vector is obtained by randomly perturbing the weights of the original fair weight vector, but subject to two constraints: all weights in the perturbed weight vector are non-negative and sum to 1 (i.e., its L1 norm is 1), and its L1 distance from the original fair weight vector (i.e. the sum of the absolute differences between corresponding components of the weight vectors) is exactly 10−4. We will clarify this in the revised version. While one can certainly test other different perturbation settings (see our reply to W2 for additional results), the stability advantage is primarily established through our theoretical analysis rather than empirical observations. Therefore, we believe that the current experimental results are good enough for our purposes.