# Fair Active Ranking from Pairwise Preferences

arXiv: https://arxiv.org/abs/2402.03252 · HTML: https://mlsanity.com/paper/2402.03252/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 14 of 14)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [FA*IR: A Fair Top-k Ranking Algorithm](https://mlsanity.com/paper/1706.06368/) (2017)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Fairness in Rankings and Recommendations: An Overview](https://mlsanity.com/paper/2104.05994/) (2021)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Selection Problems in the Presence of Implicit Bias](https://mlsanity.com/paper/1801.03533/) (2018)
- [Interventions for Ranking in the Presence of Implicit Bias](https://mlsanity.com/paper/2001.08767/) (2020)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [Active Ranking with Subset-wise Preferences](https://mlsanity.com/paper/1810.10321/) (2018)
- [Fair Ranking with Noisy Protected Attributes](https://mlsanity.com/paper/2211.17067/) (2022)
- [Data-driven Rank Breaking for Efficient Rank Aggregation](https://mlsanity.com/paper/1601.05495/) (2016)
- [Socially Fair Center-based and Linear Subspace Clustering](https://mlsanity.com/paper/2208.10095/) (2022)

## Abstract (arXiv)

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 (ε, δ)-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 ℓq norm of the error of the groups, where the error of a group is the ℓp norm of the error of all the items within that group, for p, q ≥ 1. This generalizes the objective function of ε-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.