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