Generizing Fair Top-k Selection: Stability, Intersectional Fairness, and Geometric Efficiency

TL;DR

In algorithmic decision-making (hiring, admissions), selecting the "top-k" candidates often inadvertently discriminates against minority groups. This paper provides a rigorous mathematical and engineering framework to find a fair scoring function that satisfies multiple group constraints (e.g., gender AND race) while staying as close as possible to an original, high-utility "unfair" scoring principle. By combining geometric dual-space traversal with MILP, the author achieves massive speed gains and introduces "Utility Loss" as a superior metric for ranking stability.

Background & Motivation: Beyond Single-Group Fairness

Most existing fair ranking systems focus on a single protected attribute (e.g., just gender). However, real-world fairness is intersectional. A black female candidate belongs to two protected groups, and a system fair to women or black people generally might still fail to represent black women specifically.

The core challenge is this: if we have an "ideal" but unfair scoring function (e.g., $f=0.5\cdot extGPA+0.5\cdot extSAT$), how do we find a nearby fair function (e.g., $f^{\prime }=0.54\cdot extGPA+0.46\cdot extSAT$) efficiently? Prior work either didn't scale or ignored the "tie-breaking" problem—where two candidates have the same score, but picking one over the other changes the fairness outcome.

The "Small k" Opportunity and the Hardness Barrier

The author proves a sobering reality: if the number of protected groups ($n_p$) grows, the problem becomes NP-hard even in 2D. Furthermore, if $k$ (the number of people selected) is large, the problem hit a (conditional) lower bound of $\Omega (n^{k-\delta })$.

However, the author discovers a "gap in the hardness barrier." When $k$ and $n_p$ are relatively small (logarithmic or constant), we can use a k-level-based geometric approach to solve the problem in near-linear time.

Methodology: The Two-Pronged Solution

The author proposes a structure that adapts based on the workload:

1. Geometric k-level Algorithm (For small k):
   • Maps candidates into a "Dual Space" where scoring functions are points and candidates are hyperplanes.
   • Traverses the cells of the $(k-1)$-level to find weight vectors that satisfy all fairness bounds.
   • Tie-Breaking: Uses a backtracking subroutine that treats candidates with the same group profile as "exchangeable," drastically reducing the search space.

2. MILP-based Algorithm (For large k):
   • When $k$ is too large for geometric traversal, the problem is formulated as a Mixed-Integer Linear Program.
   • Uses binary indicators to decide if a candidate is in the top-k, constrained by the required proportions for each group.

Stability and Utility Loss

A key contribution is the shift from Weight Difference (L1 distance between weight vectors) to Utility Loss.

• Weight Difference often places the solution on a "fairness boundary," making it unstable; a tiny nudge in weights could make the ranking unfair again.
• Utility Loss measures how much total "quality" we lose. Maximizing utility within a fair cell allows the algorithm to pick a "stable" weight vector right in the middle of a fair region.

Experiments & Results

The author tested the approach on the COMPAS (criminal recidivism) and IIT-JEE (entrance exam) datasets.

• Speedups: The k-level algorithm was up to 50x faster than traditional sweep-line baselines because it explicitly handles multiple constraints without re-scanning the whole dataset for every change.
• Efficiency in High Dimensions: Even in 6-D (COMPAS), the MILP approach found optimal fair solutions in seconds, whereas prior "fair-aware" methods often failed to converge or ignored tie-breaking.

Critical Insight & Conclusion

The "takeaway" for engineers is the Importance of the Tie-Breaking Profile. By encoding candidates into $2^{n_p}$ membership profiles, the author turned an exponential search problem into a manageable backtracking task.

Conclusion: This work bridges the gap between theoretical geometry and fair ML practice. It proves that while "General Fair Top-K" is hard in the limit, for most real-world scenarios where we pick a few hundred candidates ($k$) based on a few protected groups ($n_p$), we can find optimal, high-utility, and stable fair rewards with near-linear efficiency.

Future Work

The author suggests that the current model assumes static attribute values; extending this to dynamic environments where candidate scores change over time remains a promising open challenge.