Fair Active Ranking from Pairwise Preferences

• DOI: 10.48550/arxiv.2402.03252
• Publication Date: 2024-02-05
• Authors: Sruthi Gorantla; Sara Ahmadian

We investigate the problem of probably approximately correct and fair (PACF) ranking items by adaptively evoking pairwise comparisons. Given a set $n$ that belong to disjoint groups, our goal is find an $(\epsilon, \delta)$-PACF-Ranking according objective function we propose. assume access oracle, wherein, for each query, learner can choose pair receive stochastic winner feedback from oracle. Our proposed asks minimize $\ell_q$ norm error where group $\ell_p$ all within group, $p, q \geq 1$. This generalizes $\epsilon$-Best-Ranking, Saha & Gopalan (2019). By adopting function, gain flexibility explore fundamental fairness concepts like equal or proportionate errors unified framework. Adjusting parameters $p$ $q$ allows tailoring specific preferences. present both group-blind group-aware algorithms analyze their sample complexity. provide matching lower bounds up certain logarithmic factors algorithms. For restricted class algorithms, show get reasonable bounds. conduct comprehensive experiments on real-world synthetic datasets complement theoretical findings.