Generalizing Fair Top-$k$ Selection: An Integrative Approach

We study the problem of finding a fair (linear) scoring function with multiple protected groups (i.e., minority or disadvantaged groups) while also minimizing the disparity from a reference scoring function, generalizing the prior setup that was restricted to the single-group setting without disparity minimization. Driven by the need for experimental exploration, we find that previous studies overlook a critical issue that may affect the fairness of the outcome. Once it is properly considered, the problem may become computationally intractable even for a two-dimensional dataset and small $k$. However, our analysis also reveals a gap that enables us to recover the efficiency for small $k$ when the number of protected groups is sufficiently small. Furthermore, we introduce a new disparity measure—utility loss—that may yield a more stable scoring function under small weight perturbations. Through careful engineering trade-offs that balance implementation complexity, robustness, and performance, our augmented two-pronged solution demonstrates strong empirical performance on real-world datasets, with experimental observations also informing algorithm design and implementation decisions.