Pairwise Sample Complexity for Fair Active Ranking with Cascaded Norm Objectives

Ranking systems based on pairwise comparisons are fundamental in decision-making applications, yet fairness concerns remain largely unaddressed, particularly in active ranking frameworks. We propose a novel fairness-aware active ranking approach that adaptively queries pairwise preferences to construct rankings that are both probably approximately correct (PAC) and fair. We propose a flexible cascaded norm-based objective that balances error distribution within and across socially salient groups, providing a unified framework to mitigate systemic disparities. Adopting our objective function allows us to explore fundamental fairness concepts like equal or proportionate errors within a unified framework. We develop both group-blind and group-aware algorithms and derive their sample complexity bounds. Empirical evaluations on real-world datasets, including COMPAS and German Credit, demonstrate the efficiency of our approach, reducing sample complexity while achieving fairer rankings. Our findings offer theoretical insights and practical methods to enhance fairness in active ranking systems, improving their reliability in hiring, recommendations, and other applications.